摘要：

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

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

Abstract:

Link prediction is an important task in graph machine learning that aims to recover missing edges in graphs or predict potential future connections between nodes. Link prediction has various applications across graphs of different types, such as friend recommendations in social networks, recommendation systems on user-item bipartite graphs, and knowledge graph completion. With the advancement of Graph Neural Networks (GNNs), GNN-based methods have become increasingly important in link predictions. These methods can be broadly categorized into node-based and subgraph-based approaches. Compared to node-based methods, subgraph-based approaches better capture the topological structure between nodes and avoid node isomorphism. Current subgraph-based methods utilize enclosing subgraphs that include the target nodes and their first- or second-order neighbors. However, these enclosing subgraphs can be overly large and susceptible to the influence of central nodes. To address this issue, this paper proposes a link prediction method using simple path graphs. Under certain order constraints, simple path graphs have been proven to be subgraphs of enclosing subgraphs, effectively reducing subgraph size. Furthermore, even when relaxing these order constraints, simple path graphs remain smaller than enclosing subgraphs. Experimental results show that the method based on simple path graphs outperforms other methods on datasets, both with and without node features, and has a better link prediction performance.

Key words: Graph Neural Network (GNN), link prediction, simple path graph, enclosing subgraph, sparse graph