论文标题：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)正式区分了 k-hop 邻居的两个不同的内核，它们在以前的工作中经常被滥用。一种是基于图扩散（graph diffusion），另一种是基于最短路径距离（shortest path distance）。我们表明，不同的 k-hop 邻居内核会导致不同的 k-hop 消息传递的表达能力；
2)从理论上描述了 k-hop 消息传递 的表达能力，并将所提出的定理推广到大多数现有的 k-hop 模型中；
3)证明了 k-hop 消息传递在严格意义上比 1-hop 消息传递更强大；
4)演示了无论使用哪个内核，使用 k-hop 消息传递来区分一些简单的正则图都会带来一定的限制，这促使我们进一步改进 k-hop 消息的传递；
5)介绍了一种新的gnn框架的k跳消息传递kp-gnn，它显著提高了标准k跳消息传递gnn的表达能力；
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 function1 跳消息传递 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.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不能区分所有的距离正则图。\
4.1 datasets
4.2 empirical verification of the expressive power
4.3 evaluation on tu datasets
4.4 evaluation on molecular prediction tasks
本文从理论上描述了k跳消息传递gnn的能力，并提出了kp-gnn通过利用每跳的外围子图信息来提高表达能力。从理论上证明了kp-gnn几乎可以区分所有的正则图，包括一些距离正则图。根据经验，kp-gnn在所有模拟和真实数据集上都取得了有竞争力的结果。
2022-06-20 创建文章
论文解读目录
![[论文解读] 阿里dien整体代码结构](/file/thumb/3.jpg/280-180.jpg)