论文阅读 Link Prediction Based on Graph Neural Networks

论文阅读 Link Prediction Based on Graph Neural Networks

论文阅读 Link Prediction Based on Graph Neural Networks

摘要

链路预测是图的关键问题。边预测启发式算法使用一些评分函数，如公共邻域和katz指数，来测量边的可能性。由于它们的简单性、可解释性和可伸缩性，它们获得了广泛的实际应用。然而，每种启发式算法都有一个很强的假设，即当两个节点可能有边，这就限制了它们在这些假设失败的图上的有效性。在这方面，一个更合理的方法应该是从一个给定的图中学习一个合适的启发式方法，而不是使用预定义的启发式方法。通过提取每个目标边周围的局部子图，我们的目的是学习一个函数从子图模式映射到边的存在性，从而自动学习适合于当前网络的“启发式”。在本文中，我们研究了这种启发式学习模式的边预测。首先，我们发展了一个新的gamma-衰退的启发式理论。该理论在一个框架内统一了广泛的启发式算法，并证明了所有这些启发式可以很好地近似于局部子图。结果表明，局部子图保留了与链路存在相关的丰富信息。其次，基于衰减理论，提出了一种利用图神经网络（GNN）从局部子图学习启发式的新方法。它的实验结果显示了前所未有的性能，在各种各样的问题上都工作得很好。

介绍

边预测可使用简单的启发式算法：计算节点之间的相似度作为边的似然。启发式算法可根据hop（h-order）的大小来归类。启发式是一种预定义的方法，并且强依赖于假设。

• Weisfeiler-Lehman Neural Machine (WLNM)：预测节点对（a，b）是否可能有边时，将a、b的h-hop得到的子图（common neighbors、jaccard参数）作为网络的输入，预测是否有边。
• high-order的图结构信息如PageRank and Katz需要high-hop来获得。作者论文不需要high-hop来获得high-order的图结构信息。大多数high-order启发式可以使用gamma-decaying theory统一，并且small h可获得高阶启发式，并且误差随h指数级降低。
• 根据上述理论，作者提出SEAL，通过局部封闭子图学习图结构信息。相比WLNM：使用GNN替代全连接、同样学习节点特征。

准备工作

符号表示、节点显示隐式嵌入、GNN、有监督启发式学习

统一边预测启发式算法的理论

WLNM将子图作为网络输入预测边。但是高阶的启发式需要较大的子图，计算复杂。
作者将启发式归纳出一种框架：

其中，
论证可得：
大部分高阶启发式符合相似的gamma-decaying 启发框架，因此可以在h-hop子图上计算，可有效地以小指数级误差近似。
根据启发式框架定义，较远的部分结构影响权重较小，因此局部封闭子图已经包含足够的图结构信息来进行边预测。
总结：使用封闭局部子图，可以学到一阶二阶启发式信息，并以较小误差学到高阶信息

SEAL

SEAL（learning from Subgraphs, Embeddings and Attributes for
Link prediction）并不限制学习到的图结构特征符合某一种特别的形式（如gamma-decaying heuristics），而是之直接学习一般图结构特征
步骤为：
（1）提取子图
（2）构造点信息矩阵
（3）GNN学习
第二步中点信息矩阵包含三部分：点结构标签、点嵌入、点属性

• 点结构标签：表示点在子图中的作用。这么做因为要预测的边的两个节点是center，而子图中相对center的位置不同的点的重要性也不同。
  不过不mark出点的结构性标签，GNN就不知道是要预测哪两个点之间的边
  边结构标注的方法符合两个原则：
  （1）center 的label为1
  （2）对于其他点，任意两点i、j如果d(x,i)=d(x,j) d(y,i)=d(y,j) 那么i、j的label相同。d为两点之间的路径长度。
  根据以上两个原则提出Double-Radius Node Labeling (DRNL)方法
  DRNL正好是个hash函数（f为标签值）：
  
  其中
  
  若d为无穷，f=0
• 加入显示、隐式特征
  将点嵌入、点属性拼接