Link Prediction with Simple Path-Aware Graph Neural Networks

Graph Neural Networks (GNNs) are expert in node classification and graph classification, but are relatively weak on link prediction due to their limited expressiveness. Recently, two popular GNN variants, namely higher-order GNNs and labeling trick are proposed to address the limitations of GNNs. Compared with plain GNNs, these variants provably capture inter-node patterns such as common neighbors which facilitates link prediction. However, we notice that these methods actually suffer from two critical problems. First, their algorithm complexities are impractical for large graphs. Second, we prove that although these methods can identify paths between target nodes, they cannot identify simple paths, which are very fundamental in the field of graph theory. To overcome these deficiencies, we systematically study the common advantages of previous link prediction GNNs and propose a novel GNN framework that summarizes these advantages while remaining simple and efficient. Various experiments show the effectiveness of our method.