Link Prediction: Beyond Triadic Closure
The task of link prediction is as follows: given a current graph, predict which edges are likely to form in that graph in the future. This task has many real-world parallels, including the task of recommending friends on social media sites such as Facebook, as we have discussed in class. We have gone into the principle of triadic closure as a possible heuristic for this problem, and it is indeed a very simple one; however, the history of research into developing algorithms for the link prediction problem is quite extensive and interesting.
Since the pre-machine learning era, there have been many heuristics developed for predicting a score associated with how likely two nodes are to have a link between them. In their 2004 paper, Liben-Nowell and Kleinberg outline some commonly used heuristics to compute this: ranging from as simple as common neighbors of (counting the number of neighbors two nodes share in common) and Adamic-Adar (a weighted sum of common neighbors such that a common neighbor with fewer total neighbors will have a higher weight), to more complex random walk-based heuristics such as PageRank. As it stood, however, most of the more complicated heuristics are difficult to compute on graphs of more than a few thousand nodes, and even the simple heuristics were quite effective.
Then, the machine learning era came along, and researchers tried to apply machine learning models to this task. A common general architecture choice for it was the graph neural network architecture, a “message passing” network where each node sends a signal to each of its neighbors in each layer of the network. A relatively recent application of this architecture is SEAL (Zhang and Chen, 2018). At a high level, instead of considering each pair of nodes (x,y) on its own, it considers the subgraph consisting of the first- or second-order neighbors of both x and y and uses a graph neural network to perform graph classification on that subgraph. It does indeed outperform the simpler heuristics on many benchmarks, as shown by the OGB leaderboard (https://ogb.stanford.edu/docs/leader_linkprop/), showing that machine learning methods can indeed improve accuracies.
However, although machine learning achieves higher results on this task than just the pure simple heuristics, that in no way renders non-ML-based approaches to this task obsolete. As a matter of fact, the simple heuristics can be used in combination with simply modifying the input graph structure. In their paper “Edge Proposal Sets for Link Prediction,” (2021) Singh et. al. showed that by taking the results of a link prediction model, using that to modify the structure of the input graph, and applying another link prediction model to this new graph, it can be possible to improve the results of the original link prediction model. Singh et. al. used ML-based and non-ML-based link predictors in their setup, and it turns out that for certain datasets, the non-ML-based link predictors outperformed the ML-based ones. This goes to show that despite the many advances made in ML-based link prediction, the task is still far from being solved perfectly, and that research about this task and in the field of graph ML in general will still continue to be done—there’s always something new to discover.
Bibliography:
David Liben-Nowell and Jon Kleinberg. The link prediction problem for social networks. In Journal of the American Society for Information Science and Technology. https://www.cs.cornell.edu/home/kleinber/link-pred.pdf, 2003.
Muhan Zhang and Yixin Chen. Link prediction based on graph neural networks. In 32nd Conference on Neural Information Processing Systems. https://papers.nips.cc/paper/2018/file/53f0d7c537d99b3824f0f99d62ea2428-Paper.pdf, 2018.
Abhay Singh, Qian Huang, Sijia Linda Huang, Omkar Bhalerao, Horace He, Ser-Nam Lim, and Austin R. Benson. Edge proposal sets for link prediction. https://arxiv.org/pdf/2106.15810.pdf, 2021.