利用序列潜在变量扩散模型提升图链接预测的准确性

《Pattern Recognition》：Enhancing graph link prediction with sequential latent variable diffusion models

　　•揭示了传统方法在链接预测中的局限性。
•引入了多个独立的潜在变量以提高表达能力。
•开发了一种基于马尔可夫链的链接预测方法。
•将扩散模型原理应用于链接预测。
•在数据集上展示了改进的预测准确性，并提供了详细的可视化结果。

**引言**
在图分析领域[1]中，链接预测是一项关键的模式识别任务，旨在根据现有的图拓扑结构预测节点之间的潜在未来连接，或者预测图内连接将如何随时间演变。链接预测技术被广泛应用于各个领域，包括推荐系统、药物发现、异常检测、交通预测和构建知识图谱[2]。这些应用从根本上依赖于链接预测来实现它们的目标[3]，[4]。然而，链接预测面临挑战，主要是由于分离用于训练的边的复杂性以及专注于节点对的预测算法的复杂性。

**现代方法**
现代方法利用图神经网络（GNNs）从局部邻域中提取关键特征来进行链接预测，采用复杂的模型，如图自动编码器（GAE）、变分图自动编码器（VGAE）[5]及其衍生模型，如GMM-VGAE[6]、DGVAE[7]、FASTGAE[8]和VGNAE[9]等。这些模型利用深度生成方法和潜在变量，表现出卓越的性能，因为GNNs具有表达能力，并且能够通过潜在空间重建数据，展现出最先进的性能。尽管基于潜在变量的模型已成为链接预测的重要范式，但在这项工作中，我们通过分析研究揭示了它们的局限性。具体来说，它们对单一潜在变量的依赖往往无法捕捉图中节点之间复杂相互作用和潜在链接结构的全部范围。此外，我们数学上证明了整合多个潜在变量可以显著提高模型的表达能力。因此，在这项工作中，我们提出了一种新方法，通过结合多个潜在变量来增强模型的表达能力，这些潜在变量通过一系列潜在变量进行多步潜在细化，其中时间步索引的潜在嵌入是由编码器根据输入图直接生成的（而不是通过在时间步之间学习的潜在转换生成的）。这种方法构建了一个参数化的正向过程和一个反向重建模型，以最大化重建邻接矩阵的可能性，从而实现图中潜在链接的更准确预测。如图1所示，这种方法与受扩散启发的模型原理一致[10]。为了验证我们方法的有效性，我们在具有同质性和异质性的数据集上进行了广泛的测试，并通过详细的可视化研究进行了支持。我们的实验结果在这些多样化的数据集中显示了显著的性能提升，突出了我们的模型在准确预测潜在链接和有效管理复杂图结构中的节点特征方面的能力。

**总结**
我们的主要贡献如下：
1. 我们从数学上证明了在多个潜在变量框架下使用的优势，并通过各种应用场景的实际结果进行了支持。
2. 我们提出了一种新的框架，采用时间步索引的潜在嵌入来增强链接预测模型的能力。
3. 我们的方法结合了受扩散启发的迭代重建技术来恢复邻接矩阵，利用最新的生成建模发展探索图分析中链接预测的新可能性。
4. 我们在具有不同同质性和异质性水平的数据集上的广泛测试，结合深入的可视化研究，证明了改进的链接预测性能，突出了我们的模型在管理复杂图结构中的节点特征方面的有效性。

**链接预测**
链接预测旨在学习估计部分观察到的图中一对节点之间存在边的可能性。传统的启发式方法，如Common Neighbors[11]和Adamic–Adar[12]，以及浅层嵌入技术（包括矩阵分解（MF）[13]、DeepWalk[14]和node2vec[15]），在同质图中表现出了竞争力。然而，这些方法依赖于单一的全局相似性度量，无法有效地结合节点特征。

**图和链接预测的表述**
图定义为G=(V,E)，其中V包含顶点，E表示连接这些顶点的边。顶点之间的连通性由邻接矩阵A∈Rn×n详细描述，其中Aij=1表示顶点i和顶点j之间存在边，否则Aij=0；这里的n是图中的顶点数量。顶点属性在矩阵X∈Rn×d中聚合，每一行提供了一个顶点的d维属性。此外，zi表示任何顶点的潜在向量。

**提出的方法**
基于引理1的见解，我们提出了一种新方法，利用一组潜在变量在数据的低维流形中实现更紧凑和信息丰富的表示。我们的方法旨在通过预测节点之间的潜在未来连接来增强链接预测，利用现有的网络拓扑结构。具体来说，我们致力于设计一个神经网络，以最大化准确重建邻接矩阵A0的可能性，使得A0=A。

**实验**
本节评估了我们的方法在各种数据集上的性能。我们的源代码可在以下链接获取：https://github.com/zxj8806/LPDiffusion。此外，我们在附录中提供了实现细节，如随机种子、超参数调整范围、扩展的消融结果和训练稳定性分析。

**结论和未来工作**
在这项工作中，我们对当前用于链接预测的深度生成模型进行了全面评估，这些模型主要依赖于单一的潜在变量集。通过数学分析，我们揭示了这些模型固有的局限性。基于这些见解，我们引入了一种受扩散启发的链接预测方法，该方法使用一系列潜在变量组织在一个多步反向重建链中。我们的方法已在多个数据集上得到了验证。

**CRediT作者贡献声明**
张文川：撰写——原始草稿、可视化、软件、方法论、形式分析、概念化。
苏伟峰：撰写——审阅与编辑、验证、方法论。
范文涛：撰写——审阅与编辑、监督、项目管理、资金获取、概念化。
尼扎尔·布古拉：撰写——审阅与编辑、监督。

**伦理声明**
我们仅使用GPT进行少量的语言编辑和润色；所有技术内容均由作者编写和验证。

**未引用的参考文献**
[52]

**利益冲突声明**
作者声明他们没有已知的竞争财务利益或个人关系，这些关系可能会影响本文所述的工作。

**致谢**
本工作的完成得到了国家自然科学基金（62276106）、广东省基础与应用基础研究基金（2024A1515011767）和广东省重点实验室IRADS（2022B1212010006）的支持。
张文川在中国广州的济南大学获得了电气工程与自动化专业的学士学位，并在贵州贵阳的贵州师范大学大数据与计算机科学学院获得了工程硕士学位。他目前在中国珠海的北京师范大学-香港浸会大学（BNBU）和香港九龙的香港浸会大学联合攻读博士学位。

**研究领域**
张文川 | 苏伟峰 | 范文涛 | 尼扎尔·布古拉