A Simple and Expressive Graph Neural Network Based Method for Structural Link Representation

Graph Neural Networks (GNNs) have achieved state-of-the-art results in tasks like node classification, link prediction, and graph classification. While much research has focused on their ability to distinguish graphs, fewer studies have addressed their capacity to differentiate links, a complex and less explored area. This paper introduces SLRGNN, a novel, theoretically grounded GNN-based method for link prediction. SLRGNN ensures that link representations are distinct if and only if the links have different structural roles within the graph. Our approach transforms the link prediction problem into a node classification problem on the corresponding line graph, enhancing expressiveness without sacrificing efficiency. Unlike existing methods, SLRGNN computes link probabilities in a single inference step, avoiding the need for individual subgraph constructions. We provide a formal proof of our method’s expressiveness and validate its superior performance through experiments on real-world datasets. The code is publicly available1