计算机工程2026，Vol.52Issue(1)：95-104,10.DOI:10.19678/j.issn.1000-3428.0070041
基于简单路径图的链接预测
Link Prediction Based on Simple Path Graphs
摘要
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分类
信息技术与安全科学引用本文复制引用
李志仁,郑卫国..基于简单路径图的链接预测[J].计算机工程,2026,52(1):95-104,10.基金项目
国家自然科学基金联合基金重点支持项目(U23A20496). （U23A20496）
