基于简单路径图的链接预测

来源：计算机工程杂志2026年第1期北京时间：

作者：李志仁, 郑卫国

单位：复旦大学大数据学院, 上海 200433

摘要：链接预测是图机器学习中的重要任务, 旨在填补图中缺失的边或预测未来节点间可能的连接。链接预测在不同的图数据类型下有不同的应用场景, 例如社交网络下的好友推荐、用户-商品二部图上的推荐系统以及知识图谱的补全等。随着图神经网络(GNN)的研究与发展, 基于GNN的方法在链接预测中扮演着越来越重要的角色, 基于GNN的链接预测方法主要分为基于节点和基于子图两类, 相较于基于节点的方法, 基于子图的方法能够更好地捕捉节点间的拓扑结构信息, 避免节点同构问题。目前基于子图的方法通常使用包含目标节点及其1阶或2阶邻居的闭包图, 然而闭包图规模过大且易受中枢节点的影响。为解决这一问题, 提出在简单路径图上进行链接预测的方法, 并通过理论证明了在一定阶数的限制下简单路径图作为闭包图的子图能有效减小子图规模。此外, 在放宽阶数的限制下, 即使简单路径图不再是闭包图的子图, 通过实验验证了其规模依然小于闭包图。对比实验结果表明, 基于简单路径图的方法在无节点特征和有节点特征的数据集上总体优于其他方法, 链接预测性能更好。

关键词：图神经网络,链接预测,简单路径图,闭包图,稀疏图

基金资助：国家自然科学基金联合基金重点支持项目(U23A20496)