通过基于聚类的扩散和动态信息的图神经网络进行链接预测

《Physica A: Statistical Mechanics and its Applications》：Link prediction via graph neural network with clustering-based diffusion and dynamic information

　　

• •
  我们提出了一种基于图神经网络（GNN）的新型链接预测方法。
• •
  引入高阶聚类系数以增强网络拓扑结构。
• •
  基于改进的拓扑结构，使用PMFI获取扩散信息。
• •
  将扩散信息和动态信息纳入GNN学习中。
• •
  所提出的方法具有更优越的链接预测性能。

引言

复杂网络在自然和社会系统中无处不在，其中的核心问题之一是链接预测，即推断缺失的链接或预测网络未来可能的连接方式，这一方法在社交推荐和药物-靶点相互作用发现等领域有广泛的应用[1]。

早期的方法主要是启发式方法[2]，这些方法使用相似性指标，例如常见邻居（CN）[3]和资源分配（RA）指标[4]。为了捕捉更丰富的结构模式，后续的研究加入了更多的拓扑信息。例如，聚类系数被用来描述更复杂的结构相似性[5]。启发式方法简单且节省时间。然而，大多数启发式方法依赖于网络的结构特征，因此泛化能力有限。

为了提高泛化能力，人们提出了网络嵌入方法[6]。早期的研究是DeepWalk[7]，它利用随机游走生成节点序列，并使用Skip-Gram模型学习低维节点表示。还提出了改进的网络嵌入方法。例如，Node2vec[8]结合了广度优先和深度优先搜索策略通过有偏随机游走来学习节点嵌入。LINE方法[9]考虑了一阶和二阶邻居来学习节点嵌入。这些网络嵌入方法主要基于浅层表示学习，这限制了它们捕捉复杂结构模式的能力。

图神经网络（GNN）已成为深度表示学习的有效工具，为链接预测提供了强大的方法。一个代表性的模型是图卷积网络（GCN）[10]，它使用局部图卷积操作来捕捉网络的结构特征。大多数GNN框架遵循消息传递机制，其中节点表示通过邻居聚合进行迭代更新。例如，GraphSAGE[11]采用邻居采样策略生成节点嵌入。图注意力网络（GAT）[12]使用注意力机制来聚合邻居信息。

GNN的消息传递机制主要依赖于局部邻域信息，而GCN、GAT和GraphSAGE等框架通常基于静态网络拓扑。这些特性可能使得捕捉更复杂的结构信息变得困难。为了丰富GNN可用的信息，许多研究加入了补充的节点特征，这些特征通常可以分为静态特征和动态特征。例如，Gupta等人[13]使用Node2vec获得编码网络结构信息（超出局部邻域）的低维节点嵌入。TDGCN模型[14]结合了动态节点特征和静态节点特征，实现了更优越的预测性能。

然而，这些方法通常依赖于邻接矩阵来描述网络结构，而忽略了节点邻居之间的连接。聚类系数是衡量网络拓扑的重要指标，它表示节点的邻居之间的连接程度[15]。因此，将聚类信息纳入邻接矩阵可以提供更丰富的网络结构描述。此外，许多现实世界的网络是稀疏的，包含大量低度节点[16]。这些节点可能不会形成任何三角形，导致聚类系数为零。扩展的二阶邻居可以提供二阶聚类系数，为这些低度节点提供补充的结构信息。

这样的拓扑信息仍然是局部的，无法完全捕捉网络上的全局依赖关系或信息流。参数化矩阵森林指数（PMFI）[17]通过建模不同长度的网络路径上的信息传播来补充局部拓扑信息，从而捕捉超出局部邻居的更广泛的结构依赖关系。

除了静态结构特征外，动态信息还可以进一步洞察节点的演化状态。特别是，流行病模型可以有效地模拟节点的动态演化，从而描述它们的动态行为。

受到这些特性的启发，本文将聚类特征、信息扩散和动态信息纳入GNN框架（CDDGNN），并提出了一种新的CDDGNN方法。我们的主要贡献如下。

1. 通过引入网络的高阶聚类特征来增强网络拓扑。邻接矩阵基本上描述了节点之间的成对连通性，但无法捕捉网络的其他复杂内在特征。在我们的研究中，我们考虑了聚类系数，它有效地反映了节点形成群体的倾向。特别是，引入了高阶聚类属性，从而大大丰富了稀疏网络中低度节点的结构信息。

2. 基于改进的网络拓扑，使用参数化矩阵森林指数（PMFI）来模拟图扩散。基于聚类的扩散使得信息能够在图中传播，从而将全局结构信息纳入基于GNN的节点表示学习中。

3. 将扩散信息与从SIS模型中得到的动态传播特征结合，形成丰富的节点表示，共同捕捉结构和动态特征，用于GNN学习。因此，所提出的方法有助于减轻GNN框架中信息聚合的局限性。

基于10个真实世界数据集的实验结果表明，所提出的CDDGNN方法在链接预测方面优于13个基线方法。

章节片段

相关工作

链接预测方法大致可以分为三类：基于拓扑相似性的启发式方法、浅层网络表示学习和深层网络表示学习。

提出的方法

所提出的CDDGNN方法通过四个步骤将基于聚类的扩散和动态信息纳入GNN。首先，引入高阶聚类特征来增强拓扑结构，然后使用PMFI获得图扩散信息。其次，使用SIS模型获得动态信息。第三，将扩散和动态信息输入GCN以学习节点表示。最后，使用神经张量网络（NTN）进行解码以进行链接预测。

数据集

为了全面评估方法的性能，我们选择了10个不同领域的真实世界数据集进行测试，包括生物网络（秀丽隐杆线虫[35]、酵母[36]）、社交网络（Soc-wiki-vote [37]、Polblogs [37]、海豚[38]）、交通网络（USAir [37]）、引用网络（Cora [37]）、电子邮件通信网络（Email [37]）、电网（Power [37]）和书籍网络（Polbooks [37]）。这十个数据集的统计特性在表1中呈现。

结论

在本文中，我们提出了一种改进的CDDGNN链接预测方法，该方法将基于聚类的图扩散和动态特征纳入图神经网络。通过引入高阶聚类特征构建了增强的拓扑结构，捕获了网络的内在结构，并为低度节点提供了额外的信息。然后使用PMFI方法根据增强后的拓扑结构获取扩散信息，实现信息传播。

CRediT作者贡献声明

Cheng-Long Xu：撰写——初稿，方法论，数据整理，概念化。Tian Qiu：撰写——审阅与编辑，撰写——初稿，监督，方法论，概念化。Guang Chen：撰写——审阅与编辑，方法论。

利益冲突声明

作者声明他们没有已知的可能会影响本文工作的竞争性财务利益或个人关系。

致谢

本工作部分得到了
中国国家自然科学基金（资助编号：11865009）的支持。

Cheng-Long Xu|Tian Qiu|Guang Chen