Introduction

 链接预测的任务是给定图G中一对目标节点对 (vi, vj)，根据图G来预测节点对 (vi, vj)之间是否存在一条边，其典型的应用包括知识图谱补全、推荐系统等。

现有方法局限性

1. 缺乏长程结构性信息：传统GNN模型的计算范围受限于邻居节点，无法捕获远距离的结构信息。
2. 节点中心模型与链接中心任务之间的冲突：传统GNN模型只关注单个节点的表示，而忽略了节点对之间的关系。

用于链接预测的结构信息增强型图表示框架（SIEG）

• 通过移除邻居节点特征并更聚焦于邻域图结构的拟合来增强结构信息
• 引入二元结构Transformer（BST）来编码目标节点之间的结构关系。
• 该方法在多个流行基准测试中取得了显著成果，在数据集ogbl-ppa、ogbl-citation2和Pubmed排名第一。

Methodology

该框架包括四个主要部分：子图采样、结构信息增强的GNN、二元结构编码器以及链接解码器。

子图采样

 给定一对目标节点对 (vi, vj)，采样一个k跳闭包子图。该子图由围绕每个目标节点的两个k跳子图的并组成，并且在两个子图之间的边也被纳入其中。闭包子图提供了比普通子图更好的连通性和更有信息量的输入以进行链接预测。

邻居结构编码

 输入到 GNN 的信息不包含任何节点特征，转为采用 双半径节点编码（DRNL） 的结构特征。

节点对结构编码

 输入：两个目标节点的特征和目标节点对的二元结构特征。

 将启发式结构（最短路径距离（SPD）、最短路径数（SPN）、共同邻居（CN）、Jaccard指数、Adamic-Adar指数（AA）等）与节点特征融合起来，表征了查询节点对的结构相关性。

 aij为注意力系数，bij即sij。

本文提出的二元结构Transformer（BST）与常规Transformer相比：

1. 避免了节点远离目标所带来的潜在噪声和覆盖风险。
2. 收集了更多的与任务相关的结构信息。
3. 大大降低了计算复杂度。

链接解码

Experiments

数据集

三个Open Graph Benchmark数据集：ogbl-ppa, ogbl-citation2,ogbl-vessel

三个经典的属性图数据集：Pubmed， Cora, Citeseer

评价指标

AUC

结果

消融实验

Case Study

 使用一个简单的例子来说明SIEG如何利用成对的结构特征来进行链接预测。在Cora测试集上，SIEG对具有目标节点id（1111,1273）的正样本对获得了较高的8.22分，并预测了它们之间的引用关系。对样本对两两结构特征进行检查发现，CN得分为4分，AA得分为2.21分，表明二者存在4个未被广泛引用的常见引文，

Conclusion

• 本文对图神经网络（GNNs）在链接预测方面的两个固有缺陷进行了理论分析，这些缺陷涉及到信息感知和传输。
• 为了解决这些问题，我们提出了一个结构信息增强的链接预测框架。该框架包括去除邻居节点特征的同时，通过GNN更加聚焦地拟合邻域结构，并引入二元结构Transformer来编码目标节点之间的结构关系，以弥补GNN的缺陷。
• 所提出的方法在六个流行的基准测试上取得了显著成果，包括在ogbl-ppa、ogbl-citation2和Pubmed上排名第一。

• 未来展望
• 可以进一步研究如何更好地融合不同类型的邻居节点特征，以及如何在不损失性能的情况下减少参数数量。
• 可以探索将SIEG框架扩展到更广泛的多节点表示学习任务中，例如社交网络分析、推荐系统等领域。
• 可以进一步探究如何利用结构化信息提高链接预测的效率和准确性，例如结合知识图谱或领域特定的知识库。