点击上方 蓝字关注我们
本文来自转自MIND Laboratory微信公众号
Distance-Enhanced Graph Neural Network for Link Prediction
ICML 2021
本文介绍
许多生物与医学上的问题都可以用图上的问题来表示，而链接预测是图学习中的一个重要课题，即预测图上边的性质（如边的存在性，边的类型等等）。一般来说，假如在图上节点u与v之间的距离很长，那么这两个节点的联系可能并不紧密，即它们之间存在边的概率就会很小；反之，若两个节点之间的距离很短，则它们之间很可能存在联系。然而现有的基于GNN的链接预测方法并没有考虑到顶点之间的距离信息，故本文提出了一种结合距离信息的基于GNN的链接预测方法：DLGNN。由于在大型图上计算顶点对的距离的计算成本很高，本文提出了一种基于锚节点的距离计算方法，即首先从节点中随机选择KA个锚节点，然后计算锚节点与其他节点之间的最短路径。
本文方法
本文方法的整体框架如图1所示，给定图G(V,Etrain)，首先利用GNN模型（如GCN,GAT等）来提取各个顶点的特征，具体表示为：
而各个边的特征可由下式获得：
其中，K为超参，其表示K层MLP，得到节点表征
。
而距离信息由一个d1维的dist向量表示，其中每个元素表示一个特定的距离信息。将hu,v与dist拼接之后，得到一个带有距离信息的节点表征向量。最终通过一个二元的分类器φf，来预测节点u、v之间存在边的概率。
其次，本文提出了一种有效的距离测量方法，即基于锚节点的距离。首先，随机选取KA个锚节点；对于每个锚节点ai，利用广度优先搜索算法来计算ai到图中所有非锚节点的最短路径。节点u、v之间的锚距离表示为：
而计算锚距离的时间复杂度为O(KA(V+E))，远远小于计算图上所有节点对最短路径的时间复杂度。
由于在训练中，A\Etrain中的所有边都可看作是负样本，而一般在链接预测任务中，|Etrain|<<|A|，故计算所有负边距离的开销十分巨大，故本文利用了一个负边样本采样器来模拟它们的距离。给定一条负边(u,v)，其距离可由
中均匀采样得到，distu,v可表示为各种距离算法，此训练过程如算法1所示。
实验
本文使用的数据集为OGB基准数据集中的DDI以及PPA，其中，DDI数据集用于药物相互作用的预测，PPA数据集则用于预测蛋白质之间的关联属性，两个数据集的具体分布如表1所示。
本文方法在DDI及PPA数据集上的实验结果如表3表4所示。
本文总结
本文提出了一种结合距离信息的基于GNN的链接预测方法：DLGNN。为了减少距离计算的成本，本文提出了一种基于锚节点的距离计算方法，其显著减少了距离计算的时间复杂度。在基准数据集上的大量实验证明了本文方法的有效性。
原文地址：Distance-Enhanced Graph Neural Network for Link Prediction (icml-compbio.github.io)
大家好我们是深度学习与图网络公众号
关注图神经网络，图神经网络的应用，
最新的图学习研究进展
欢迎关注我们
