論文資訊

論文標題：How Powerful are K-hop Message Passing Graph Neural Networks
論文作者：Jiarui Feng, Yixin Chen, Fuhai Li, Anindya Sarkar, Muhan Zhang
論文來源：2022,arXiv
論文地址：download
論文程式碼：download

1 Introduction

　　本文工作：

- 1)正式區分了 K-hop 鄰居的兩個不同的核心，它們在以前的工作中經常被濫用。一種是基於圖擴散（graph diffusion），另一種是基於最短路徑距離（shortest path distance）。我們表明，不同的 K-hop 鄰居核心會導致不同的 K-hop 訊息傳遞的表達能力；
- 2)從理論上描述了 K-hop 訊息傳遞 GNN 的表達能力，並將所提出的定理推廣到大多數現有的 K-hop 模型中；
- 3)證明了 K-hop 訊息傳遞在嚴格意義上比 1-hop 訊息傳遞更強大；
- 4)演示了無論使用哪個核心，使用 K-hop 訊息傳遞來區分一些簡單的正則圖都會帶來一定的限制，這促使我們進一步改進 K-hop 訊息的傳遞；
- 5)介紹了一種新的GNN框架的k跳訊息傳遞KP-GNN，它顯著提高了標準k跳訊息傳遞GNN的表達能力；

2 K-hop message passing and its representation power

2.1 1-hop message passing framework

　　經典的訊息傳遞機制回顧：

　　　　$m_{v}^{l}=\operatorname{MES}^{l}\left(\left\{\left(h_{u}^{l-1}, e_{u v}\right) \mid u \in \mathcal{N}_{v, G}^{1}\right\}\right), h_{v}^{l}=\operatorname{UPD}^{l}\left(m_{v}^{l}, h_{v}^{l-1}\right)\quad\quad\quad(1)$

　　其中，$m_{v}^{L}$ 是傳送到第 $l$ 層的節點 $v$ 的訊息，$MESl$ 和 $UPDl$ 分別是第 $l$ 層的訊息和更新函數。在 $L$ 層訊息傳遞後，使用 $h_{v}^{L}$ 作為節點 $v$ 的最終節點表示。這種表示可用於執行節點分類和節點回歸等節點級任務。要獲得圖表示，需要使用一個讀出函數：

　　　　$h_{G}=\operatorname{READOUT}\left(\left\{h_{v}^{L} \mid v \in V\right\}\right)\quad\quad\quad(2)$

　　其中，讀數是計算最終圖表示的讀出函數。然後可以使用 $h_{G}$ 來進行圖分類和圖迴歸等圖級任務。

2.2 K-hop message passing framework

　　$1-hop$ 訊息傳遞框架可以直接推廣到 $K-hop$ 訊息傳遞，因為它共用相同的訊息和更新機制。

　　首先，我們區分了兩個不同的 $K-hop$ 鄰居核，它們在以前的研究中被互換和濫用。

shortest path distance (spd) kernel

　　即圖 $G$ 中節點 $v$ 的第 $k$ 個跳鄰居是與 $v$ 的最短路徑距離為 $k$ 的節點集。

　　Definition 1. For a node $v$ in graph $G$ , the $K-hop$ neighbors $\mathcal{N}_{v, G}^{K, s p d}$ of $v$ based on shortest path distance kernel is the set of nodes that have the shortest path distance from node $v$ less than or equal to $K$ . We further denote $Q_{v, G}^{k, s p d}$ as the set of nodes in $G$ that are exactly the $k-th$ hop neighbors (with shortest path distance of exactly $k$ ) and $\mathcal{N}_{v, G}^{0, s p d}=Q_{v, G}^{0, s p d}=\{v\}$ is the node itself.

graph diffusion (gd) kernel

　　Definition 2. For a node $v$ in graph $G$ , the $K-hop$ neighbors $\mathcal{N}_{v, G}^{K, g d}$ of $v$ based on graph diffusion kernel is the set of nodes that can diffuse information to node $v$ within the number of random walk diffusion steps $K$ with the diffusion kernel $A$ . We further denote $Q_{v, G}^{k, g d}$ as the set of nodes in $G$ that are exactly the $k-th$ hop neighbors (nodes that can diffuse information to node $v$ with $k$ diffusion steps) and $\mathcal{N}_{v, G}^{0, g d}=Q_{v, G}^{0, g d}=\{v\}$ is the node itself.

　　從上述定義不難得到：

- 節點 $v$ 的 $K-hop$ 鄰居的在兩個不同的核心將是相同的，即 $\mathcal{N}_{v, G}^{K, s p d}=\mathcal{N}_{v, G}^{K, g d}$；
- 當 $K=1$ 時，$\mathcal{N}_{v, G}^{1, s p d}=Q_{v, G}^{1, s p d}=\mathcal{N}_{v, G}^{1, g d}=Q_{v, G}^{1, g d}$；
- 對於某些 $k$ $Q_{v, G}^{k, s p d}$ 並不總是等於 $Q_{v, G}^{k, g d}$ ；
- 注意，基於圖擴散核，一個節點可以是 $v$ 的第 $k$ 個跳鄰居；

　　上述兩種圖核的直觀例子：[附上 GraphSAGE ]

　　首先，如果我們執行 $1$跳訊息傳遞，它將編碼一個高 $2$ 的有根的子樹，如圖右上方所示。請注意，每個節點都是使用相同的引數集來學習的，這可以通過用相同的顏色（圖中為白色）來表示。

　　現在，我們考慮使用最短路徑距離核心來執行 $2$ 跳訊息傳遞。節點 $v_1$ 的有根子樹如圖中間所示。我們可以看到，在每個高度，第 $1$ 跳鄰居和 $2$ 跳鄰居都包括在內。此外，在不同的跳中使用不同的引數集，這是通過用不同的顏色填充不同跳中的節點（藍色表示第 $1$ 跳，黃色表示第 $2$ 跳）來表示的。

　　最後，在圖的底部，我們展示了具有圖擴散核的 $2$ 跳訊息傳遞圖神經網路。很容易看出，有根的子樹不同於使用最短路徑距離核的子樹不同，因為節點可以同時出現在鄰居的第 $1$ 跳和第 $2$ 跳中。

　　接下來，我們正式定義 $k-hop$ 訊息傳遞框架如下：

　　　　$\begin{array}{l}\left.m_{v}^{l, k}=\operatorname{MES}_{k}^{l}\left(\left\{\left(h_{u}^{l-1}, e_{u v}\right) \mid u \in Q_{v, G}^{k, t}\right)\right\}\right)\\ h_{v}^{l, k}=\operatorname{UPD}_{k}^{l}\left(m_{v}^{l, k}, h_{v}^{l-1}\right)\\h_{v}^{l}=\operatorname{COMBINE}^{l}\left(\left\{h_{v}^{l, k} \mid k=1,2, \ldots, K\right\}\right)\end{array}\quad\quad\quad(3)$

　　其中，$t=\{s p d, g d\}$ 表示 $k$ 跳鄰居的核心。在這裡，對於每個跳，我們可以應用唯一的 MES 和 UPD 函數。注意，對於 $k>1$，可能不存在邊特徵 $e_{u v}$，因為邊並不直接連線。但我們把它留在這裡，因為我們可以使用另一種型別的特性來替換它。與 $Eq.1$ 中描述的 $1$ 跳訊息傳遞框架相比，引入了組合函數來組合節點 $v$ 在不同跳下的表示。很容易看出，$L$ 層 $1-WL$ gnn實際上是 $L$ 層 $K$ 跳訊息傳遞 GNN，如果我們只執行 $1$ 跳訊息傳遞，我們有 $h_{v}^{l}=h_{v}^{l, 1}$。

G Implementation detail of KP-GNN

Combine function

　　1 跳訊息傳遞 GNNs 沒有 $C O M B I N E^{l}$ 功能。這裡我們介紹了兩種不同的 $COMBINE^{l}$ 函數。
　　第一個是基於注意的組合機制，它自動學習每個跳中每個節點表示的重要性。
　　第二種方法使用了眾所周知的 geometric distribution[13]。第 $i$ 跳的的權重是基於 $\theta_{i}=\alpha(1-\alpha)^{i}$ 計算的，其中 $\alpha \in(0,1]$。最終的表示是通過所有跳的表示的加權和計算的。

Peripheral subgraph information

　　在當前的實現中，KP-GNN只考慮外圍子圖中的元件數和每個元件中的邊數。然而，每個節點可能有一個不同的外圍子圖。為了使模型能夠工作，我們為實現中每個元件中的最大元件數和最大邊數設定了閾值。

KP-GCN, KP-GIN, and KP-GraphSAGE

　　我們分別使用 GCN、GIN 和 GraphSAGE 中定義的訊息和更新函數，實現了 KP-GCN、KP-GIN 和 KPGraphSAGE。

　　.在每個跳中，使用獨立的引數集，每個跳的計算嚴格遵循相應的模型。但是，增加 $K$ 的數量也會增加引數的總數，這是不能擴充套件到 $K$。為了避免這個問題，我們採用以下方式設計了 $K-hop$ 訊息傳遞。假設模型的總隱藏大小為H，則每個跳的隱藏大小為 $H/K$。這樣，即使 $K$ 很大，模型的規模仍然在相同的尺度上。

KP-GIN+

　　在一個普通的 $k$ 跳訊息傳遞框架中，將為每個節點聚合所有的 $k$ 跳鄰居。這意味著，在 $L$ 層之後，GNN 的接受域為$LK$。這可能會導致訓練的不穩定，因為不相關的資訊可能會被聚合。為了緩解這個問題，我們採用了來自 $GINE+$[15]的想法。具體來說，我們實現了 $KP-GIN+$，它應用了與 $GINE+$ 完全相同的架構，除了在這裡我們新增了外圍子圖資訊。在第 $1$ 層，$GINE+$ 只從 $l-hop$ 內的鄰居收集資訊，這使得 $L$ 層 $GINE+$ 仍然有一個 $L$ 的接受域。注意，在 $KP-GIN+$ 中，我們為每個跳使用一個共用引數集。

Path encoding

　　為了進一步利用每個跳上的圖結構資訊，我們引入了KP-GNN的路徑編碼。具體來說，我們不僅計算兩個節點在跳 $k$ 處是否是鄰居，而且還計算兩個節點之間長度為 $k$ 的路徑數。這些資訊很容易計算出來，因為鄰接的圖 $G$ 的 $A^{k}$ 是一個長度為 $k$ 的路徑計數器。然後將資訊新增到AGGl中，正常的 $k$ 函數作為附加特徵。

Other implementation

　　對於所有的 GNN，我們應用 Jumping Knowledge 方法[51]來得到最終的節點表示。可能的方法包括和、平均、連線、最後一個和注意。在每一層之後都使用批次處理歸一化。

2.3 Expressive power of K-hop message passing framework

　　我們證明，當 $K>1$ 時，傳遞的 $K$ 跳訊息嚴格比 $ 1-WL test$ 更強大。在整個分析過程中，我們使用正則圖作為例子來說明我們的定理，因為它們不能通過 1-hop 訊息傳遞或 $1-WL$ 測試來區分。請注意，我們的分析並不侷限於正則圖，但它能夠描述任何圖。

　　Definition 3. A proper $K-hop$ message passing GNN is a class of GNN models where the message, update and combine functions are all injective given the input from a countable space.

　　由於神經網路的 universal approximation theorem [17]和集合操作[18]的 Deep Set，很容易找到一個合適的傳遞 $k$ 跳訊息的 GNN。在後面的部分中，預設情況下，所有提到的傳遞 GNN 的 $k$ 跳訊息都是正確的。接下來，我們定義節點設定。　　

　　Definition 4. The node configuration of node $v$ in graph $G$ within $k$ hops under $t$ kernel is a list $A_{v, G}^{k, t}=\left(a_{v, G}^{1, t}, a_{v, G}^{2, t}, \ldots, a_{v, G}^{k, t}\right)$ , where $a_{v, G}^{i, t}=\left|Q_{v, G}^{i, t}\right|$ is the number of $i$-th hop neighbors of node $v$ .

　　當我們說兩個節點構型 $A_{v_{1}, G^{(1)}}^{k, t}$ 和 $A_{v_{2}, G^{(2)}}^{k, t}$ 相等時，我們的意思是這兩個列表在元件上是相等的。現在我們可以提出第一個命題：

　　Proposition 1. For two graphs $G^{(1)}=\left(V^{(1)}, E^{(1)}\right)$ and $G^{(2)}=\left(V^{(2)}, E^{(2)}\right)$ , we pick two nodes $v_{1}$ and $v_{2}$ from two graphs respectively. Given a proper $1$-layer $K$-hop message passing GNN, it can distinguish $v_{1}$ and $v_{2}$ if $A_{v_{1}, G^{(1)}}^{K, t} \neq A_{v_{2}, G^{(2)}}^{K,}$ .

Proposition 1 證明

　　

　　上述證明主要利用：

對於每一跳的引數不同；

$\left|Q_{v, G}^{k, t}\right|$ 在特定的 $k$ 不同，且結合 GNN 單射性質；

　　Corollary 1. A proper $K-hop$ message passing GNN is strictly more powerful than $1$-hop message passing GNNs when $K>1$ .

　　首先說明 Corollary 1 為什麼正確？

　　為了瞭解為什麼這是正確的，我們首先使用命題1描述傳遞 $1$ 跳訊息 GNN 的表達能力。

　　當 $K=1$ 時，$v_1$ 和 $v_2$ 的節點構型為 $d_{v_{1}, G^{(1)}}$ 和 $d_{v_{2}, G^{(2)}}$，其中 $d_{v, G}$ 為 $v$ 的節點度。在 $L$ 個層之後，GNN 可以得到 $L$ 個跳數內每個節點的節點設定。根據這句話，可以很容易地看出為什麼這些 GNN 不能區分任何大小為 $n$ 的 $\text{r-regular graph}$，因為正則圖中的每個節點都具有相同的度。從另一個角度來看，1 跳訊息傳遞GNN的表達能力是有限的，因為它只有GNN接受域內圖中每個節點的度資訊。

知識點：正則圖

正則圖是指各頂點的度均相同的無向簡單圖。
在圖論中，正則圖中每個頂點具有相同數量的鄰點；即每個頂點具有相同的度或價態。正則的有向圖也必須滿足更多的條件，即每個頂點的內外自由度都要彼此相等。具有 $k$ 個自由度的頂點的正則圖被稱為 $k$ 度的 $k$-正則圖。此外，奇數程度的正則圖形將包含偶數個頂點。

　　例子：

　　

　　接下來，當 $K>1$ 時，$K$ 跳訊息傳遞至少與 $1$ 跳訊息傳遞同等強大，因為 $K$ 跳訊息傳遞包含了 $1$ 跳訊息傳遞所具有的所有資訊。為了瞭解為什麼它更強大，我們使用了兩個例子來說明它。第一個範例顯示在 Figure 1 的左側部分。

　　當 $K>1$ 時，$K$ 跳訊息傳遞至少與 $1$ 跳訊息傳遞同等強大，因為K跳訊息傳遞包含了$1$ 跳訊息傳遞所具有的所有資訊。為了瞭解為什麼它更強大，我們使用了兩個例子來說明它。第一個範例顯示在圖1的左側部分。假設我們使用圖擴散核，我們想學習節點的表示 $v_1$ 和節點 $v_2$ 兩個圖，我們知道 $1$ 跳訊息傳遞框架產生相同的表示兩個節點都是大小為 $6$ 的 $3$ 正則圖。但是，很容易看出 $v_1$ 和 $v_2$ 有不同的區域性結構，應該有不同的表示。相反，如果我們使用與圖擴散核一起進行的兩跳訊息傳遞，我們可以通過檢查節點的第二跳鄰居來很容易地區分這兩個節點，因為節點 $v_1$ 有四個第二跳鄰居，而節點 $v_2$ 只有兩個第二跳鄰居。第二個範例如圖1的右側所示。本例中的兩個圖仍然是規則圖，$1$ 跳訊息傳遞仍然無法區分節點 $v_1$ 和節點 $v_2$。相比之下，假設我們使用最短路徑距離核，節點 $v_1$ 和 $v_2$ 有不同數量的第 $2$ 跳鄰居，因此通過執行 $2$ 跳訊息傳遞將有不同的表示。這兩個例子令人信服地證明了用 $K>1$ 傳遞的 $K$ 跳訊息比 $K=1$ 具有更好的表達能力。

　　接下來，我們簡要總結了一些現有的傳遞 $k$ 跳訊息的 GNN，它們的表達能力可以用 Proposition1 來描述。

　　Corollary 2. When $K>1$ and $t=spd$ , Proposition 1 characterizes the expressive power of GINE [15]]. It also characterize DEA-GNN [19] and Graphormer [20] with shortest path distance as the distance feature or the spatial encoding respectively.

　　此外，我們提出的 $K-hop$ 訊息傳遞框架比之前的一些基於圖擴散的 $GNNs$，如 MixHop[11]，GPR-GNN[14]，magna[13]更強大。我們將詳細的討論留在附錄C中

2.4 Limitation of K-hop message passing framework

　　隨然 $\text{K-hop}$ 訊息傳遞機制比 $\text{1-hop}$ 訊息傳遞機制好，但是任然存在一些問題。具體地說，我們證明了核心的選擇會影響 $k$ 跳訊息傳遞的能力。此外，即使傳遞 k-hop 訊息，我們也不能區分一些簡單的非同構結構。

　　請繼續檢視所提供的範例。在 example 1中，我們知道節點 $v_1$ 和 $v_2$ 與圖擴散核有不同數量的第二跳鄰居。但是，如果我們使用最短路徑距離核，則這兩個節點在第 2 跳中有相同數量的鄰居，這意味著我們不能使用具有最短路徑距離核的 2 跳訊息傳遞來區分兩個節點。類似地，在 example 2 中，兩個節點在具有圖擴散核的第 1 跳和第 2 跳中具有相同數量的鄰居。這些結果突出表明，核心的選擇會影響 $k$ 跳訊息傳遞的表達能力。此外，它們都不能通過 2 跳訊息傳遞來區分這兩個範例。鑑於所有這些觀察結果，我們可能會想知道是否有一種方法可以進一步提高 $k$ 跳訊息傳遞的表達能力？

3 KP-GNN: improving the power of K-hop message passing by peripheral subgraph

3.1 Peripheral edge and peripheral subgraph

　　Definition 5. The peripheral edges $E\left(Q_{v, G}^{k, t}\right)$ are defined as the set of edges that connect nodes within set $Q_{v, G}^{k, t}$ . We further denote $\left|E\left(Q_{v, G}^{k, t}\right)\right|$ as the number of peripheral edges. The peripheral subgraph $G_{v, G}^{k, t}=\left(Q_{v, G}^{k, t}, E\left(Q_{v, G}^{k, t}\right)\right)$ is defined as the subgraph induced by $Q_{v, G}^{k, t}$ from the whole graph $G$ .

　　在 example 1 中，我們注意到在第 $1$ 跳時，在左圖中的節點 $3$ 和節點 $4$ 之間有一條邊。更具體地說，是 $E\left(Q_{v_{1}, G^{(1)}}^{1, t}\right)=\{(3,4)\}$。相比之下，我們在右圖中有 $E\left(Q_{v_{2}, G^{(2)}}^{1, t}\right)=\{\}$，這意味著在 $v_2$ 的第一跳鄰居之間沒有邊。因此，通過將這些資訊新增到訊息傳遞中，我們可以成功地區分這兩個節點。類似地，在example 2 中，在節點 $v_2$ 的第 $1$ 跳鄰居之間有一條邊，但對於節點 $v_1$ 則不存在這樣的邊。通過利用 peripheral edge 資訊，我們也可以區分這兩個節點。以上例子證明了 peripheral edge 和 peripheral subgraph 資訊的有效性。

3.2 K-hop peripheral-subgraph-enhanced graph neural network

　　本節提出 KP-GNN ,它將 $k$ 跳訊息傳遞與 peripheral subgraph 資訊相結合，用於更強大的GNN設計。　　

　　KP-GNN 訊息傳遞函數如下：

　　　　$\hat{h}_{v}^{l, k}=\operatorname{MES}_{k}^{l}\left(\left\{\left\{\left(h_{u}^{l-1}, e_{u v}\right) \mid u \in Q_{v, G}^{k, t}\right\}, G_{v, G}^{k, t}\right)\right.\quad\quad\quad(4)$

　　在第 $k$ 跳的訊息步驟中，我們不僅聚合了鄰居的資訊，而且還聚合了第 $k$ 跳的外圍子圖。KP-GNN的實現可以非常靈活，因為任何圖編碼函數都可以使用。為了最大化模型可以在保持簡單的同時編碼的資訊，我們實現了訊息函數為：

　　　　${\large \operatorname{MES}_{k}^{l}=\operatorname{MES}_{k}^{l, \text { normal }}\left(\left\{\left(h_{u}^{l-1}, e_{u v}\right) \mid u \in Q_{v, G}^{k, t}\right\}\right)+\sum \limits_{c \in C} \frac{1}{|C|} \sum \limits_{(i, j) \in E\left(Q_{v, G}^{k, t}\right)_{c}} e_{i j}} \quad\quad\quad(5)$

　　其中

- $\operatorname{MES}_{k}^{l, \text { normal }}$ 表示原始GNN模型中的訊息函數；
- $C$ 是 $G_{v, G}^{k, t}$ 中連線元件的集合；
- $E\left(Q_{v, G}^{k, t}\right)_{c}$ 是 $G_{v, G}^{k, t}$中第 $c$ 個連線分量的邊集；

　　這種實現有助於KP-GNN不僅編碼 $E\left(Q_{v, G}^{k, t}\right)$，還可以編碼 $G_{v, G}^{k, t}$（元件數量）的部分資訊。有了這個實現，任何GNN模型都可以被合併到KP-GNN框架中並得到增強，通過用每個跳 $k$ 的相應函數替換 $\mathrm{MES}_{k}^{l, \text { normal }}$、正常 $k$ 和 $\mathrm{UPD}_{k}^{l}$。我們在附錄G中留下了詳細的實現。

3.3 The expressive power of KP-GNN

　　在本節中，我們從理論上描述了KP-GNN的表達能力，並將其與原始的K-hop訊息傳遞框架進行了比較。關鍵的觀點是，根據 $\text{Eq.4}$，與正常的 $k$ 跳訊息傳遞相比，第 $k$ 跳的訊息函數另外編碼了 $G_{v, G}^{k, t}$。然後，我們提出以下定理。

　　Theorem 1. For two graphs $G^{(1)}=\left(V^{(1)}, E^{(1)}\right)$ and $G^{(2)}=\left(V^{(2)}, E^{(2)}\right)$ , we pick two nodes $v_{1}$ and $v_{2}$ from two graphs respectively. Suppose there is a proper $K-hop$ $1$-layer KP-GNN with message functions as powerful as $w$-WL test on distinguishing graph structures. Then it can distinguish $v_{1}$ and $v_{2}$ if $G_{v_{1}, G^{(1)}}^{k, t}$ and $G_{v_{2}, G^{(2)}}^{k, t}$ are non-isomorphic and $w$-WL test distinguishable for some $k \leq K$ .

　　Theorem 2. Consider all pair of $n$-sized $r$-regular graphs, where $3 \leq r<\sqrt{2 \log n}$ . For any small constant $\epsilon>0$ , there exists a KP-GNN using shortest path distance as kernel and only peripheral edge information with at most $K=\left\lceil\left(\frac{1}{2}+\epsilon \frac{\operatorname{logn}}{\log (r-1-\epsilon)}\right)\right\rceil$ , which distinguishes almost all $(1-o(1))$ such pair of graphs with only $1$-layer message passing.

　　上述定理證明了僅利用 peripheral edge 資訊的 KP-GNN 的簡單實現可以區分幾乎所有具有一定 $K$ 層和 $1$ 層的正則圖。

　　此外，根據 Distance Encoding [19] 中的定理3.7，具有最短路徑距離核的 $k$ 跳訊息不能區分任何具有相同交集陣列的任何距離正則圖。這裡我們證明了 $KP-GNN$ 在區分距離正則圖方面比距離編碼更強大。

　　Theorem 3. For two non-isomorphic distance regular graphs $G^{(1)}=\left(V^{(1)}, E^{(1)}\right)$ and $G^{(2)}= \left(V^{(2)}, E^{(2)}\right)$ with the same intersection array $\left(b_{0}, b_{1}, \ldots, b_{d-1} ; c_{1}, c_{2}, \ldots, c_{d}\right)$ , we pick two nodes $v_{1}$ and $v_{2}$ from two graphs respectively. Given a proper $1$-layer $K$-hop KP-GNN with message functions defined in Equation (5), it can distinguish $v_{1}$ and $v_{2}$ if $b_{0}-b_{j}-c_{j}=2$ for some $j \leq K$ and $G_{v_{1}, G^{(1)}}^{j, t}$ and $G_{v_{2}, G^{(2)}}^{j, t}$ are non-isomorphic.

　　我們在附錄 F 中包含了證明。Theorem 3 表明，具有簡單實現的 KP-GNN 可以區分一些距離正則圖，這進一步證明了 KP-GNN 比正常距離增強的 GNN 具有更高的表達能力。然而，在目前的實現中，KP-GNN不能區分所有的距離正則圖。\