Enhancing Link Prediction Based on Simple Path Graphs
摘要
Link prediction is one of the prominent tasks in the field of graph machine learning, aiming to fill in missing edges in graph data or predict potential connections between nodes in the graph. Early link prediction methods primarily utilized traditional machine learning models, leveraging heuristic rules, embedded representations of nodes, and node features for prediction. However, graph neural networks possess powerful learning capabilities, effectively capturing the topological structure and node features of graphs, thus exhibiting increasingly superior performance in link prediction tasks. Methods for link prediction tasks based on graph neural networks primarily fall into two categories: node-based methods and subgraph-based methods. Among them, subgraph-based methods excel in link prediction tasks due to their ability to capture the graph topological structure between nodes and effectively address the issue of node isomorphism. Currently, subgraph-based methods typically employ enclosing subgraphs formed by the first or second-order neighboring nodes around the target nodes. Despite the effectiveness of enclosing subgraph-based methods in link prediction tasks, they face challenges such as the scalability issue arising from the large size of enclosing subgraphs and susceptibility to influence from hub nodes in the graph. To address this challenge, this study proposes a novel subgraph pattern, namely, utilizing target nodes to construct the simple path graph and conducting link prediction on these simple path graphs. We demonstrate in this study that, under certain order constraints, simple path graph is a subgraph of enclosing subgraph, thus alleviating the issue of excessive subgraph size encountered by subgraph-based methods. Furthermore, through experimental validation, we show that even with relaxed order constraints, the size of the simple path graph remains smaller than that of the enclosing subgraph. Experimental results demonstrate that the proposed link prediction method based on the simple path graph outperforms other methods, both on datasets with node features and datasets without node features.