Link Prediction Based on Simple Path Graphs

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.