论文导读 | 使用图神经网络的链接预测方法

近年来，图神经网络作为图表征学习的一类代表性方法发展迅速，并被广泛应用于社交网络、知识图谱、生物网络、分子结构等图数据中。在图机器学习中，一类重要的问题是链接预测问题。本文以图的同构性为切入点，介绍近年来使用图神经网络进行链接预测的方法。

背景介绍

图同构

我们首先介绍图的同构问题。给定两个图 ，如果存在一个映射 ，使得：

那么 就是同构的，记作 ，且称 是图 和 的一个同构。将图的同构这一概念扩展，我们可以描述：

1. 节点同构：令 。如果存在从 到 的一个同构 ，且 ，那么节点 和 是同构的。记作 。

2. 节点组同构：令 分别为 个节点组成的有序节点组。如果存在从 到 的一个同构 ，且 ，那么节点组 和 是同构的。记作 。

消息传递神经网络

图神经网络的一个标准范式就是消息传递神经网络 (MPNN)。它的基本思想是：针对图中的每个节点 ，赋予一个变量表示 。而后，重复下面的迭代过程：在第 次迭代过程中，更新节点的变量表示

其中， 是含有可训练参数的函数， 是满足置换不变性的函数（如 ）， 指节点 的邻居节点。

图卷积网络（GCN）就是一个典型的消息传递神经网络。它的每一步更新可以表示为：

其中， 表示节点的度数， 为可训练的参数。

消息传递的表达能力上限

为了研究和提高图神经网络的性能，我们需要研究它的表达能力，来更好的理解哪些图的结构可以被它识别，而哪些结构则无法被区分。基于消息传递的方法的表达能力的上限可以很好地利用一个经典的图同构算法，即 Weisfeiler-Lehman(WL) 算法，来进行描述。该算法的流程如下：

2. 重复下面步骤直至收敛:
4. 返回

该算法中，我们首先对所有节点都赋予一个“颜色” （如果节点有输入的特征 ，那么根据不同的特征赋予不同的颜色）。而后，我们根据每个节点的邻居节点的颜色，去更新该节点在下一次迭代时的颜色。这里的哈希函数 必须是单射的，即它将不同的输入映射到不同的输出。

我们以下面的这两个图为例（例子来源于 https://www.davidbieber.com/post/2019-05-10-weisfeiler-lehman-isomorphism-test/）。

图1和图2的颜色表示在 WL 测试结束后的颜色分配，而初始时我们把所有节点都分配成一样的颜色，即 ：

第一轮迭代中，我们首先将所有节点的邻居节点聚合起来，如下图所示。每个节点的标签此时有两个部分，分别是：它原来的标签，和它邻居节点的标签组成的多重集合。

下一步，我们需要“压缩”每个节点的标签来得到统一的表示：

将此步骤不断重复，直到最后我们可以得到如下的颜色分配：

在此状态后，无论我们如何重复WL算法的迭代过程，图中所有不同颜色节点构成的划分不会再改变，因此到达了收敛阶段，算法完成。

WL 测试虽然能够判定大多数情况下的图同构问题，但仍有相当多一部分例外，两个图并非同构，但 WL 测试却分配给它们相同的颜色。这些例外对于链接预测的问题来说十分重要。下图中的 两个图明显具有不同的结构，但 WL 测试无法将它们区分。

为了扩展 WL 测试的区分能力，学者们提出了更高维度的 WL 测试。这里，我们介绍 k-Folklore WL (k-FWL)算法。该算法对每个k节点组 赋予一个颜色；除此之外，它的基本过程与 WL 算法一致。

2. 重复下面步骤直至收敛:
4. 返回

其中，一个节点组 的邻居 定义如下：每个 有 个邻居（ 为图中节点的个数），且第 个邻居是由k个节点组构成的序列：

可以证明，对任意的 , -FWL 的区分能力严格大于 -FWL，且严格大于 WL。

介绍完上面的研究背景后，我们接下来介绍使用图神经网络进行链接预测的方法，并逐一分析它们的表达能力、时间复杂度等。

图自编码器

如何使用图神经网络进行链接预测？既然 GNN 为图中的每个节点学习一个向量表示，而一个链接 由两个节点 组成，那么最直接的办法就是聚合 的节点表示来得到链接 的表示：

其中， 分别是 对应的向量表示， 是一个函数。一个例子是 VGAE[2]，它的形式为：

如上所述，图自编码器的想法和实现都十分简单，但它是否能够完全解决链接预测的问题？答案是否定的。以下图为例，假设我们需要分别预测链接 以及 是否存在。容易发现，在下图中，节点 是互相对称的；节点 是互相对称的。因此，在使用 GNN 得到的节点表示中， 的节点表示一定与 相同； 的节点表示则一定与 相同。从而，通过自编码器得到的链接 以及 的预测结果也一定相同。这显然是不正确的，因为在该图中节点 与节点 之间的相对位置完全不同。从而，我们知道，图自编码器无法记录两个节点间的相对位置信息，因而并不十分适用于链接预测任务。

Labeling trick

那么，如何才能区分这样不同的链接？首先，我们回顾一下，MPNN 为每个节点学习一个向量表示，从而擅长于区分图同构和节点同构。那么，我们是否可以将链接预测这一任务中的链接同构问题转化为图同构或者节点同构问题？Labeling trick给出了将链接同构转化为图同构的方法。

如上图，在原图 中预测目标链接时，我们对所有节点增加额外的标签，将 标记得与其他节点不同，从而得到左图 。同样的，在预测目标链接时，我们将 标记得与其他节点不同，得到右图 。这样，我们将 与 的同构问题转化为了两个图的同构问题。事实上，我们有如下结论：

从而，链接同构的问题被严格转换成了 和 的同构问题。使用 MPNN 学习诱导出的图 的表示，我们可以增强它的表示能力。例如下图：

上图分别为 Rook's 4x4 和 Shrikhande 图。假设目标链接为蓝色节点对。2-FWL测试无法区分两个链接，而使用上述的 labeing trick 后，1-WL 测试即可区分两个链接。

缺点

当然，labeling trick 也有一些缺点。最大的缺点在于，它的时间复杂度相当高：每计算一个目标链接，它就需要重新标注一遍图，再在诱导出的图上重新运行一遍 GNN 模型。因此，所有基于 labeling trick 的方法都需要首先抽取出目标链接附近节点构成的子图，再在子图上进行训练和预测。总的来说，labeling trick 方法进行链接预测的一般工作流程为：

1. 在目标链接 的附近抽取子图 ；
2. 在 上进行 labeling trick；
3. 在 上运行 GNN；
4. 得到最终的链接表示。

算法复杂度

给定一个图 ，假设使用的 GNN 模型是 GCN，不使用子图抽取，则预测 个目标链接需要：

• 时间：， 为 GCN 层数， 分别是边和节点的个数；
• 空间：。

Labeling trick 的实现

此处，我们介绍 SEAL[3]。它实现的 labeling trick 方法为 Double Radius Node Labeling(DRNL)：给定图 和目标链接 ：

1. 抽取 周围的 跳子图 ，其中 的节点 满足：

其中 表示 之间的最短距离。

1. 节点标注：
• 赋予 标签 ；
• 距离 的距离为 的节点标签为 ；
• 距离 的距离为 的节点标签为 ；
• ，其中 。

在 SEAL 的实验中，。

Labeling trick 的扩展

综上所述，labeling trick 的四步：

1. 在目标链接 的附近抽取子图 ；
2. 在 上进行 labeling trick；
3. 在 上运行 GNN；
4. 得到最终的链接表示。

其中，时间主要消耗在针对每个目标链接对应的不同的子图上运行 GNN。那么，可否改变步骤 2、3 的顺序，从而相当于我们在原图上只运行一遍 GNN，而在预测不同的链接时，才对节点进行额外的标注？这正是 ELPH[5]、 GDGNN[6] 的想法。ELPH 的基本过程如下：

1. 根据原图 ，构建一个增强的图 （ 与目标链接无关）；
2. 在 上运行一次 GNN，得到节点表示；
3. 在预测目标链接 时，有

预测链接 用到两部分信息，分别是基于节点表示的预测 以及后面的针对链接 的标注（具体标注的方法此处不再赘述，但它与 GNN 的运行无关）。从而，尽管我们仍然需要针对每个目标链接 进行不同的标注 ，但只需要在原图上运行一遍 GNN，效率得到了极大的提升。

Partial labeling trick

上面讲述的 labeing trick 将链接同构问题转化为了图同构问题，那么我们是否可以通过类似的方法将它转化为节点同构问题？答案也是可以的，以下图为例。

要预测原图 中以节点 为端点的链接 ，我们只需要标注节点 ，使其与其它节点不同，得到诱导出的图 如上所示。我们有：

从而，我们将链接同构问题转化为了节点同构问题。这个方法的优点在于，平均来说相比于 labeing trick，我们只需要运行 次 GNN 即可。从而，一般情况下这种方法可以在整个图上进行学习，而无需抽取目标链接周围的子图。

算法复杂度

给定一个图 ，假设我们要：

• 预测一个链接：
• 时间：， 为 GCN 层数， 分别是边和节点的个数；
• 空间：。
• 预测所有头节点（尾节点）相同的链接：
• 时间、空间与上面相同。

从而，平均意义上 partial labeling trick 计算每一个目标链接需要时间 ，与 GCN 计算一个目标节点需要的平均时间相同。

实现

此处我们简要介绍 NBFNet[7]。NBFNet 通过参数化 Bellman-Ford 算法得到了 partial labeling trick。考虑图中单源最短路径的表示：

参数化上面的式子，可以得到：

在预测任意首节点为 的链接时，NBFNet 首先重新标注图：

剩余的部分等同于在该图上运行一个 GNN。

总结 Labeling trick

• GNN 擅长学习节点、图的结构；
• 将链接预测问题转化为节点分类、图分类问题；

Higher-order 表示

既然 GNN 能够学习节点表示，那么我们直接扩展 GNN 的结构，使其能够直接学习链接表示。一般来说，我们需要：

• 对所有的节点对 赋予一个对应的向量表示 。
• 在 上进行消息传递。

我们直到，消息传递需要在每个节点的邻居处聚合信息。如何定义 的邻居节点 ？目前来说，方法主要有两种，分别对应于 2-WL 和 2-FWL 图同构测试。

• 2-WL:
• 2-FWL:

定义了邻居后，我们就可以同样运行消息传递，来计算节点对的向量表示。这种方法的缺点在于，由于共有 个节点对存在，算法的时间、空间复杂度都相当高。

实现

此处我们介绍 EdgeTransformer[8]。它实现了 2-FWL 的消息传递模式。假设 是图的全连接张量表示，其中 对应于边 的表示， 对应于节点 的表示。在每一层，有

其中， 为一个全连接层，独立地应用于每个 ， 表示 layer normalization， 是论文中提出的注意力计算方法，实际上是 2-FWL 的计算模式，它对每个 ，输出一个向量 ：

Partial higher-order 表示

由上面的讨论可知，higher-order 表示主要的空间复杂度来源于它的邻居定义并没有考虑到图的稀疏性。为了将稀疏性也考虑在内，我们可以稍微修改一下邻居的定义方法[9][10]：

Morris et al.[11] 证明了使用 MPNN， Partial 2-WL 方法表达能力严格大于 2-WL；然而，Partial 2-FWL 的表达能力却小于 2-FWL。

实现

我们简要介绍一下 [10] 中的实现方法。同样假设 是图的张量表示。那么

从而，计算过程需要 时间和 空间。[10] 提出了该算法的局部版本 (local version)，对应于 partial higher-order 表示。计算过程中，只考虑 ；计算过程中，也只考虑张量 的非 0 部分。

总结

综合上面的讨论，给定两个图 和 ，那么下面的陈述是等价的：

• 使用 partial labeing trick 得到 ，且
• 使用 labeling trick 得到 ，且

推广上述结论，给定图 ，假设我们要学习 节点组的表示：

那么对任意的 ，下面的陈述是等价的：

• 使用 (partial) labeling trick 部分标注节点 和 ，分别得到图 ，且

实验

同质图

异质图

参考文献

[1] Labeling Trick: A Theory of Using Graph Neural Networks for Multi-Node Representation Learning. Zhang et al, NeurIPS 2021.

[2] Variational Graph Auto-Encoders. Kipf et al. NeurIPS 2016 Workshop.

[3] Link prediction based on graph neural networks. Zhang et al. NeurIPS 2018.

[4] Inductive relation prediction by subgraph reasoning. Teru et al. ICML 2020.

[5] Graph Neural Networks For Link Prediction With Subgraph Sketching. Chamberlain et al. ICLR 2023.

[6] Geodesic Graph Neural Network for Efficient Graph Representation Learning. Kong et al. NeurIPS 2022.

[7] Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction. Zhu et al. NeurIPS 2021.

[8] Systematic Generalization with Edge Transformers. Bergen et al. NeurIPS 2021.

[9] Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networks. Morris et al. AAAI 2018.

[10] Two-Dimensional Weisfeiler-Lehman Graph Neural Networks for Link Prediction. Hu et al. ArXiv.

[11] Weisfeiler and Leman go sparse: Towards scalable higher-order graph embeddings. Morris et al. NeurIPS 2020.