论文标题：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

　　经典的消息传递机制回顾：

　　　　mlv=MESl({(hl−1u,euv)∣u∈N1v,G}),hlv=UPDl(mlv,hl−1v)(1)mvl=MESl⁡({(hul−1,euv)∣u∈Nv,G1}),hvl=UPDl⁡(mvl,hvl−1)(1)

　　其中，mLvmvL 是发送到第 ll 层的节点 vv 的消息，MESlMESl 和 UPDlUPDl 分别是第 ll 层的消息和更新函数。在 LL 层消息传递后，使用 hLvhvL 作为节点 vv 的最终节点表示。这种表示可用于执行节点分类和节点回归等节点级任务。要获得图表示，需要使用一个读出函数：

　　　　hG=READOUT({hLv∣v∈V})(2)hG=READOUT⁡({hvL∣v∈V})(2)

　　其中，读数是计算最终图表示的读出函数。然后可以使用 hGhG 来进行图分类和图回归等图级任务。

2.2 K-hop message passing framework

　　首先，我们区分了两个不同的 K−hopK−hop 邻居核，它们在以前的研究中被互换和滥用。

shortest path distance (spd) kernel

　　即图 GG 中节点 vv 的第 kk 个跳邻居是与 vv 的最短路径距离为 kk 的节点集。

　　Definition 1. For a node  vv  in graph  GG , the  K−hopK−hop neighbors  NK,spdv,GNv,GK,spd  of  vv  based on shortest path distance kernel is the set of nodes that have the shortest path distance from node vv less than or equal to  KK . We further denote  Qk,spdv,GQv,Gk,spd  as the set of nodes in  GG  that are exactly the  k−thk−th hop neighbors (with shortest path distance of exactly  kk  ) and  N0,spdv,G=Q0,spdv,G={v}Nv,G0,spd=Qv,G0,spd={v}  is the node itself.

　　Definition 2. For a node  vv  in graph  GG , the K−hopK−hop neighbors  NK,gdv,GNv,GK,gd  of  vv  based on graph diffusion kernel is the set of nodes that can diffuse information to node  vv  within the number of random walk diffusion steps  KK  with the diffusion kernel  AA . We further denote  Qk,gdv,GQv,Gk,gd  as the set of nodes in  GG  that are exactly the  k−thk−th hop neighbors (nodes that can diffuse information to node  vv  with  kk  diffusion steps) and  N0,gdv,G=Q0,gdv,G={v}Nv,G0,gd=Qv,G0,gd={v}  is the node itself.

　　从上述定义不难得到：

• • 节点 vv 的 K−hopK−hop 邻居的在两个不同的内核将是相同的，即 NK,spdv,G=NK,gdv,GNv,GK,spd=Nv,GK,gd；
  • 当 K=1K=1 时，N1,spdv,G=Q1,spdv,G=N1,gdv,G=Q1,gdv,GNv,G1,spd=Qv,G1,spd=Nv,G1,gd=Qv,G1,gd；
  • 对于某些 kkQk,spdv,GQv,Gk,spd 并不总是等于 Qk,gdv,GQv,Gk,gd ；
  • 注意，基于图扩散核，一个节点可以是 vv 的第 kk 个跳邻居；

　　上述两种图核的直观例子：[附上 GraphSAGE ]

　　首先，如果我们执行 11跳消息传递，它将编码一个高 22 的有根的子树，如图右上方所示。请注意，每个节点都是使用相同的参数集来学习的，这可以通过用相同的颜色（图中为白色）来表示。

　　现在，我们考虑使用最短路径距离内核来执行 22 跳消息传递。节点 v1v1 的有根子树如图中间所示。我们可以看到，在每个高度，第 11 跳邻居和 22 跳邻居都包括在内。此外，在不同的跳中使用不同的参数集，这是通过用不同的颜色填充不同跳中的节点（蓝色表示第 11 跳，黄色表示第 22 跳）来表示的。

　　最后，在图的底部，我们展示了具有图扩散核的 22 跳消息传递图神经网络。很容易看出，有根的子树不同于使用最短路径距离核的子树不同，因为节点可以同时出现在邻居的第 11 跳和第 22 跳中。

　　接下来，我们正式定义 k−hopk−hop 消息传递框架如下：

　　　　ml,kv=MESlk({(hl−1u,euv)∣u∈Qk,tv,G)})hl,kv=UPDlk(ml,kv,hl−1v)hlv=COMBINEl({hl,kv∣k=1,2,…,K})(3)mvl,k=MESkl⁡({(hul−1,euv)∣u∈Qv,Gk,t)})hvl,k=UPDkl⁡(mvl,k,hvl−1)hvl=COMBINEl⁡({hvl,k∣k=1,2,…,K})(3)

　　其中，t={spd,gd}t={spd,gd} 表示 kk 跳邻居的内核。在这里，对于每个跳，我们可以应用唯一的 MES 和 UPD 函数。注意，对于 k>1k>1，可能不存在边特征 euveuv，因为边并不直接连接。但我们把它留在这里，因为我们可以使用另一种类型的特性来替换它。与 Eq.1Eq.1 中描述的 11 跳消息传递框架相比，引入了组合函数来组合节点 vv 在不同跳下的表示。很容易看出，LL 层 1−WL1−WL gnn实际上是 LL 层 KK 跳消息传递 GNN，如果我们只执行 11 跳消息传递，我们有 hlv=hl,1vhvl=hvl,1。

G Implementation detail of KP-GNN

Combine function

　　1 跳消息传递 GNNs 没有 COMBINElCOMBINEl 功能。这里我们介绍了两种不同的 COMBINElCOMBINEl 函数。
　　第一个是基于注意的组合机制，它自动学习每个跳中每个节点表示的重要性。
　　第二种方法使用了众所周知的 geometric distribution[13]。第 ii 跳的的权重是基于 θi=α(1−α)iθi=α(1−α)i 计算的，其中 α∈(0,1]α∈(0,1]。最终的表示是通过所有跳的表示的加权和计算的。

Peripheral subgraph information

　　在当前的实现中，KP-GNN只考虑外围子图中的组件数和每个组件中的边数。然而，每个节点可能有一个不同的外围子图。为了使模型能够工作，我们为实现中每个组件中的最大组件数和最大边数设置了阈值。

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

　　我们分别使用 GCN、GIN 和 GraphSAGE 中定义的消息和更新函数，实现了 KP-GCN、KP-GIN 和 KPGraphSAGE。

　　.在每个跳中，使用独立的参数集，每个跳的计算严格遵循相应的模型。但是，增加 KK 的数量也会增加参数的总数，这是不能扩展到 KK。为了避免这个问题，我们采用以下方式设计了 K−hopK−hop 消息传递。假设模型的总隐藏大小为H，则每个跳的隐藏大小为 H/KH/K。这样，即使 KK 很大，模型的规模仍然在相同的尺度上。

KP-GIN+

　　在一个普通的 kk 跳消息传递框架中，将为每个节点聚合所有的 kk 跳邻居。这意味着，在 LL 层之后，GNN 的接受域为LKLK。这可能会导致训练的不稳定，因为不相关的信息可能会被聚合。为了缓解这个问题，我们采用了来自 GINE+GINE+[15]的想法。具体来说，我们实现了 KP−GIN+KP−GIN+，它应用了与 GINE+GINE+ 完全相同的架构，除了在这里我们添加了外围子图信息。在第 11 层，GINE+GINE+ 只从 l−hopl−hop 内的邻居收集信息，这使得 LL 层 GINE+GINE+ 仍然有一个 LL 的接受域。注意，在 KP−GIN+KP−GIN+ 中，我们为每个跳使用一个共享参数集。

Path encoding

　　为了进一步利用每个跳上的图结构信息，我们引入了KP-GNN的路径编码。具体来说，我们不仅计算两个节点在跳 kk 处是否是邻居，而且还计算两个节点之间长度为 kk 的路径数。这些信息很容易计算出来，因为邻接的图 GG 的 AkAk 是一个长度为 kk 的路径计数器。然后将信息添加到AGGl中，正常的 kk 函数作为附加特征。

Other implementation

　　对于所有的 GNN，我们应用 Jumping Knowledge 方法[51]来得到最终的节点表示。可能的方法包括和、平均、连接、最后一个和注意。在每一层之后都使用批处理归一化。

2.3 Expressive power of K-hop message passing framework

　　我们证明，当 K>1K>1 时，传递的 KK 跳消息严格比 1−WLtest1−WLtest 更强大。在整个分析过程中，我们使用正则图作为例子来说明我们的定理，因为它们不能通过 1-hop 消息传递或 1−WL1−WL 测试来区分。请注意，我们的分析并不局限于正则图，但它能够描述任何图。

　　Definition 3. A proper K−hopK−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，很容易找到一个合适的传递 kk 跳消息的 GNN。在后面的部分中，默认情况下，所有提到的传递 GNN 的 kk 跳消息都是正确的。接下来，我们定义节点配置。　　

　　Definition 4. The node configuration of node  vv  in graph  GG  within  kk  hops under  tt  kernel is a list  Ak,tv,G=(a1,tv,G,a2,tv,G,…,ak,tv,G)Av,Gk,t=(av,G1,t,av,G2,t,…,av,Gk,t) , where  ai,tv,G=∣∣Qi,tv,G∣∣av,Gi,t=|Qv,Gi,t|  is the number of  ii-th hop neighbors of node  vv .

　　当我们说两个节点构型 Ak,tv1,G(1)Av1,G(1)k,t 和 Ak,tv2,G(2)Av2,G(2)k,t 相等时，我们的意思是这两个列表在组件上是相等的。现在我们可以提出第一个命题：

　　Proposition 1. For two graphs G(1)=(V(1),E(1))G(1)=(V(1),E(1)) and G(2)=(V(2),E(2))G(2)=(V(2),E(2)) , we pick two nodes v1v1 and v2v2 from two graphs respectively. Given a proper 11-layer KK-hop message passing GNN, it can distinguish v1v1 and v2v2 if AK,tv1,G(1)≠AK,v2,G(2)Av1,G(1)K,t≠Av2,G(2)K, .

 Proposition 1 证明

　　

　　上述证明主要利用：

• • 对于每一跳的参数不同；
  • ∣∣Qk,tv,G∣∣|Qv,Gk,t| 在特定的 kk 不同，且结合 GNN 单射性质；

　　首先说明 Corollary 1 为什么正确？

　　当 K=1K=1 时，v1v1 和 v2v2 的节点构型为 dv1,G(1)dv1,G(1) 和 dv2,G(2)dv2,G(2)，其中 dv,Gdv,G 为 vv 的节点度。在 LL 个层之后，GNN 可以得到 LL 个跳数内每个节点的节点配置。根据这句话，可以很容易地看出为什么这些 GNN 不能区分任何 大小为 nn 的 r-regular graphr-regular graph，因为正则图中的每个节点都具有相同的度。从另一个角度来看，1 跳消息传递GNN的表达能力是有限的，因为它只有GNN接受域内图中每个节点的度信息。

　　

　　当 K>1K>1 时，KK 跳消息传递至少与 11 跳消息传递同等强大，因为K跳消息传递包含了11 跳消息传递所具有的所有信息。为了了解为什么它更强大，我们使用了两个例子来说明它。第一个示例显示在图1的左侧部分。假设我们使用图扩散核，我们想学习节点的表示 v1v1 和节点 v2v2 两个图，我们知道 11 跳消息传递框架产生相同的表示两个节点都是大小为 66 的 33 正则图。但是，很容易看出 v1v1 和 v2v2 有不同的局部结构，应该有不同的表示。相反，如果我们使用与图扩散核一起进行的两跳消息传递，我们可以通过检查节点的第二跳邻居来很容易地区分这两个节点，因为节点 v1v1 有四个第二跳邻居，而节点 v2v2 只有两个第二跳邻居。第二个示例如图1的右侧所示。本例中的两个图仍然是规则图，11 跳消息传递仍然无法区分节点 v1v1 和节点 v2v2。相比之下，假设我们使用最短路径距离核，节点 v1v1 和 v2v2 有不同数量的第 22 跳邻居，因此通过执行 22 跳消息传递将有不同的表示。这两个例子令人信服地证明了用 K>1K>1 传递的 KK 跳消息比 K=1K=1 具有更好的表达能力。

　　接下来，我们简要总结了一些现有的传递 kk 跳消息的 GNN，它们的表达能力可以用 Proposition1 来描述。

　　Corollary 2. When  K>1K>1  and  t=spdt=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−hopK−hop 消息传递框架比之前的一些基于图扩散的 GNNsGNNs，如 MixHop[11]，GPR-GNN[14]，magna[13]更强大。我们将详细的讨论留在附录C中

　　请继续查看所提供的示例。在 example 1中，我们知道节点 v1v1 和  v2v2 与图扩散核有不同数量的第二跳邻居。但是，如果我们使用最短路径距离核，则这两个节点在第 2 跳中有相同数量的邻居，这意味着我们不能使用具有最短路径距离核的 2 跳消息传递来区分两个节点。类似地，在 example 2 中，两个节点在具有图扩散核的第 1 跳和第 2 跳中具有相同数量的邻居。这些结果突出表明，内核的选择会影响 kk 跳消息传递的表达能力。此外，它们都不能通过 2 跳消息传递来区分这两个示例。鉴于所有这些观察结果，我们可能会想知道是否有一种方法可以进一步提高 kk 跳消息传递的表达能力？

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(Qk,tv,G)E(Qv,Gk,t)  are defined as the set of edges that connect nodes within set  Qk,tv,GQv,Gk,t . We further denote  ∣∣E(Qk,tv,G)∣∣|E(Qv,Gk,t)|  as the number of peripheral edges. The peripheral subgraph  Gk,tv,G=(Qk,tv,G,E(Qk,tv,G))Gv,Gk,t=(Qv,Gk,t,E(Qv,Gk,t))  is defined as the subgraph induced by  Qk,tv,GQv,Gk,t  from the whole graph  GG . 

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

　　KP-GNN 消息传递函数如下：

　　　　h^l,kv=MESlk({{(hl−1u,euv)∣u∈Qk,tv,G},Gk,tv,G)(4)h^vl,k=MESkl⁡({{(hul−1,euv)∣u∈Qv,Gk,t},Gv,Gk,t)(4)

　　在第 kk 跳的消息步骤中，我们不仅聚合了邻居的信息，而且还聚合了第 kk 跳的外围子图。KP-GNN的实现可以非常灵活，因为任何图编码函数都可以使用。为了最大化模型可以在保持简单的同时编码的信息，我们实现了消息函数为：

　　　　MESlk=MESl, normal k({(hl−1u,euv)∣u∈Qk,tv,G})+∑c∈C1|C|∑(i,j)∈E(Qk,tv,G)ceij(5)MESkl=MESkl, normal ⁡({(hul−1,euv)∣u∈Qv,Gk,t})+∑c∈C1|C|∑(i,j)∈E(Qv,Gk,t)ceij(5)

• • MESl, normal kMESkl, normal  表示原始GNN模型中的消息函数；
  • CC 是 Gk,tv,GGv,Gk,t 中连接组件的集合；
  • E(Qk,tv,G)cE(Qv,Gk,t)c 是 Gk,tv,GGv,Gk,t中第 cc 个连接分量的边集；

　　这种实现有助于KP-GNN不仅编码 E(Qk,tv,G)E(Qv,Gk,t)，还可以编码 Gk,tv,GGv,Gk,t（组件数量）的部分信息。有了这个实现，任何GNN模型都可以被合并到KP-GNN框架中并得到增强，通过用每个跳 kk 的相应函数替换 MESl, normal kMESkl, normal 、正常 kk 和 UPDlkUPDkl。我们在附录G中留下了详细的实现。

3.3 The expressive power of KP-GNN

　　在本节中，我们从理论上描述了KP-GNN的表达能力，并将其与原始的K-hop消息传递框架进行了比较。关键的观点是，根据 Eq.4Eq.4，与正常的 kk 跳消息传递相比，第 kk 跳的消息函数另外编码了 Gk,tv,GGv,Gk,t。然后，我们提出以下定理。

　　Theorem 1. For two graphs  G(1)=(V(1),E(1))G(1)=(V(1),E(1))  and  G(2)=(V(2),E(2))G(2)=(V(2),E(2)) , we pick two nodes  v1v1  and  v2v2  from two graphs respectively. Suppose there is a proper K−hopK−hop11-layer KP-GNN with message functions as powerful as  ww-WL test on distinguishing graph structures. Then it can distinguish  v1v1  and v2v2  if Gk,tv1,G(1)Gv1,G(1)k,t  and  Gk,tv2,G(2)Gv2,G(2)k,t  are non-isomorphic and  ww-WL test distinguishable for some  k≤Kk≤K .

　　Theorem 2. Consider all pair of  nn-sized  rr-regular graphs, where  3≤r<2logn−−−−−√3≤r<2log⁡n . For any small constant  ϵ>0ϵ>0 , there exists a KP-GNN using shortest path distance as kernel and only peripheral edge information with at most  K=⌈(12+ϵlognlog(r−1−ϵ))⌉K=⌈(12+ϵlognlog⁡(r−1−ϵ))⌉ , which distinguishes almost all  (1−o(1))(1−o(1))  such pair of graphs with only 11-layer message passing.

　　上述定理证明了仅利用 peripheral edge 信息的 KP-GNN 的简单实现可以区分几乎所有具有一定 KK 层和 11 层的正则图。

　　此外，根据 Distance Encoding [19] 中的定理3.7，具有最短路径距离核的 kk 跳消息不能区分任何具有相同交集数组的任何距离正则图。这里我们证明了 KP−GNNKP−GNN 在区分距离正则图方面比距离编码更强大。

　　Theorem 3. For two non-isomorphic distance regular graphs  G(1)=(V(1),E(1))G(1)=(V(1),E(1))  and  G(2)=(V(2),E(2))G(2)=(V(2),E(2))  with the same intersection array  (b0,b1,…,bd−1;c1,c2,…,cd)(b0,b1,…,bd−1;c1,c2,…,cd) , we pick two nodes  v1v1  and  v2v2  from two graphs respectively. Given a proper 11-layer  KK-hop  KP-GNN with message functions defined in Equation (5), it can distinguish  v1v1  and  v2v2  if  b0−bj−cj=2b0−bj−cj=2  for some  j≤Kj≤K  and  Gj,tv1,G(1)Gv1,G(1)j,t  and  Gj,tv2,G(2)Gv2,G(2)j,t  are non-isomorphic.

4.1 Datasets

4.2 Empirical verification of the expressive power

4.3 Evaluation on TU datasets

4.4 Evaluation on molecular prediction tasks

5 Conclusion

2022-06-20 创建文章

论文解读目录

__EOF__