Link Prediction (LP) is an important problem in graph ML with many industrial applications. For example, recommender systems can be formulated as LP; link prediction is also a key process in drug discovery and knowledge graph construction.
There are three main classes of LP methods: (i) heuristics (See Appendix REF ) that estimate the distance between two nodes (e.g. personalized page rank (PPR) [1]} or graph distance [2]}) or the similarity of their neighborhoods (e.g Common Neighbors (CN), Adamic-Adar (AA) [3]}, or Resource Allocation (RA) [2]}); (ii) unsupervised node embeddings or factorization methods, which encompass the majority of production recommendation systems [5]}, [6]}; and, recently, (iii) Graph Neural Networks, in particular of the Message-Passing type (MPNNs) [7]}, [8]}, [9]}.GNNs are a broader category than MPNNs. Since the majority of GNNs used in practice are of the message passing type, we will use the terms synonymously.
GNNs excel in graph- and node-level tasks, but often fail to outperform node embeddings or heuristics on common LP benchmarks such as the Open Graph Benchmark (OGB) [10]}.
