Link Prediction without Graph Neural Networks
Zexi Huang Mert Kosan Arlei Silva Ambuj Singh
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.