今天为大家介绍Felix L. Opolka和Pietro Li`o在ELLIS上的一篇文章，这篇文章是关于图的链接预测的。作者介绍了一种新的在图节点上运行的图卷积高斯过程模型，先是通过图形卷积变换将欧几里得域上的高斯过程转换成图形卷积高斯过程，再进一步调整节点上的生成模型来适应节点对上的高斯过程，以此来进行链接预测。
1
介绍
近期在链接预测领域的工作专注于具有两个关键属性的方法。第一，这些方法可以根据图结构本身和图节点上的信号(通常称为节点特征)来预测缺失的链接。其次，这些方法不仅从每个节点的孤立特征计算节点嵌入，还考虑了每个节点的局部邻域特征，从而为预测缺失链接提供了更多的上下文信息。这些方法的核心通常是具有参数化图卷积操作的神经网络，虽然这些神经网络模型达到了最先进的性能，但由于使用最大似然估计优化了大量参数，它们需要大量的标记数据。为了克服以上不足，作者提出用高斯过程模型来处理链路预测任务。所提出的模型在识别图结构和节点特征的同时，利用图卷积在预测链接时纳入邻域信息。通过在贝叶斯推理设置中边缘化参数和使用变分下界优化超参数来对抗过拟合，因此无需为early stop设置验证集。此外，高斯过程为下游任务提供了获取估值的方法。
2
背景
1.1高斯过程
1.2图卷积
图卷积通过将本地模式嵌入节点表示中，抓住本地特征的归纳。图卷积的出现得益于卷积神经网络的启发，并将卷积运算从规则网格的域推广到一般图的域。
3
相关工作
3.1 图结构数据的高斯处理
先前图结构数据的高斯过程模型已经在关系学习这个术语下进行了研究。这些方法已应用于图中节点的半监督分类，例如：关系高斯处理、混合图高斯过程、标签传播算法等。受图形神经网络的启发，最近的研究开发了高斯过程模型，明确地考虑节点及其邻近节点的特征。2018年NG提出的图高斯过程通过平均1跳邻域的节点特征来计算节点表示，然后执行半监督节点分类。与作者提出的图卷积高斯过程不同，它只考虑1跳节点的邻域，从而限制了模型对节点邻域信息的访问。2017年van der Wilk提出的图形卷积高斯过程使用图卷积产生图中小块的表示，并通过累积的高斯过程模型总结这些小块。与目前所描述的模型不同，它用于图像或网格分类等图级预测。目前唯一的另一个用于链路预测的高斯处理模型是由Yu，K.和Chu,W. 2008年提出的， 但它不包含来自邻居节点的信息，这限制了它的预测性能。
3.2链接预测模型
2018年Zhang, M.和Chen, Y.系统探索了由启发式模型表示的一种常见的链接预测方法，这些方法计算节点相似性的启发式算法，并将其作为链接的可能性输出。流行的启发式方法包括共同邻居、Jaccard、偏好链接、Adamic-Adar等。其他方法则侧重于基于从图结构中导出的潜在节点特征来预测链接。例如，通过光谱聚类计算出的节点特征可以用于链路预测。其他的潜在特征方法是矩阵分解和链路预测的随机块模型(SBM)
另一类链路预测方法利用神经网络。2017年提出的MLNM利用邻接矩阵训练全连接神经网络。2018年的SEAL在非概率设置中使用图形神经网络。网络运行在节点特性和手工制作的节点标签上，表明一个节点在它的邻居的作用。与作者模型最相似的是，Kipf, T. N.和 Welling, M. 2016年提出的的图变分自动编码器结合了概率建模和图卷积，因此也考虑了邻域信息。由于依赖节点表示之间的内积，链接上分布的形式受到了更大的限制。相反，作者通过选择变分分布作为一个高斯过程来评估诱导点，而诱导点本身是自由参数，从而实现了很高的灵活性。
4
模型
4.1 图卷积高斯过程
作者从一个常规的高斯过程开始，它只作用于对图结构无关的节点特征。每个节点特征被视为欧几里得域 上的一个观测。这个高斯过程被转换使用简化的图形卷积，以产生一个图形卷积对图的节点 进行高斯处理g. 最后，定义的一系列图卷积高斯过程按下面公式在边缘上生成一个卷积高斯过程r的图。上面过程中的函数值分别通过节点的大小和链接的厚度来表示。
4.2使用稀疏变分高斯过程的链接预测
作者要将节点上的这种高斯过程转换为节点对上的高斯过程以预测它们之间的潜在边缘。预测节点对之间的潜在链接可以归结为一个二元分类问题，它规定了伯努利可能性。这将导致一个难以处理的后验分布，作者将用一个变分分布来近似它。作者还将使用一组m诱导点来降低推理的计算复杂度。
5
实验
5.1数据集
数据集如下图所示：
5.2实验装置
5.3结果
作者将自己提出的图卷积高斯过程与2008年提出的带核函数的非卷积高斯过程、2016年提出的变分图自动编码器对比试验，以两种标准进行比较：ROC曲线下面积(AUC)和平均准确率(AP)。AUC的标准下结果如下图所示：
AP标准下结果如下图所示：
在比较作者提出的的GCLGP与非卷积LGP相比，我们发现前者在大多数数据集上优于后者，某些数据集的AUC高达10.0。我们发现，在AUC方面，8个数据集中有6个数据集的性能有所改善，在AP方面，同样8个数据集中有6个数据集的性能有所改善。在其他情况下，比如NS数据集，LGP在AUC方面的表现仅略好于标准偏差。结果表明，GCLGP能够使用本地社区信息，这确实对我们正在评估的大部分数据集有益。在AUC方面，8个数据集中的6个数据集GCLGP都要优于VGAE，且通常有一个大的差额(在Router数据集上超过15.0)。在AP方面，GCLGP与VGAE大致相当，在8个数据集中的4个上优于它。结果突出了这种高度灵活的概率建模方法的优点。
6
结论
作者描述了一个包含节点特征和局部邻域信息的链路预测的高斯过程模型。作者介绍了在基于在不同大小的节点邻居之间可进行插值的核的节点之上的一个图卷积高斯过程。作者展示了该模型如何应用于链路预测的任务，并介绍了一种针对成对节点的高斯过程的变分诱导点方法，该方法将诱导点放置在随机生成的连接诱导图的节点上。最后，作者实验证明其所提出的模型在一系列图数据集上表现出了强大的性能，在许多情况下优于非卷积高斯过程和基于图神经网络的变分自编码器。
