Link Prediction without Graph Neural Networks
This work challenges the dominant GNN paradigm for link prediction, offering a simpler and more efficient alternative that could benefit applications relying on graph analysis.
The paper tackled the problem of link prediction by questioning the necessity of Graph Neural Networks (GNNs) and proposed Gelato, a topology-centric framework that addresses class imbalance, resulting in 145% higher accuracy, 11x faster training, 6,000x faster inference, and fewer parameters compared to state-of-the-art GNNs.
Link prediction, which consists of predicting edges based on graph features, is a fundamental task in many graph applications. As for several related problems, Graph Neural Networks (GNNs), which are based on an attribute-centric message-passing paradigm, have become the predominant framework for link prediction. GNNs have consistently outperformed traditional topology-based heuristics, but what contributes to their performance? Are there simpler approaches that achieve comparable or better results? To answer these questions, we first identify important limitations in how GNN-based link prediction methods handle the intrinsic class imbalance of the problem -- due to the graph sparsity -- in their training and evaluation. Moreover, we propose Gelato, a novel topology-centric framework that applies a topological heuristic to a graph enhanced by attribute information via graph learning. Our model is trained end-to-end with an N-pair loss on an unbiased training set to address class imbalance. Experiments show that Gelato is 145% more accurate, trains 11 times faster, infers 6,000 times faster, and has less than half of the trainable parameters compared to state-of-the-art GNNs for link prediction.