Chapter10: Graph Neural Networks: Link Prediction

Muhan Zhang, Peking University,


Link prediction is an important application of graph neural networks. By predicting missing or future links between pairs of nodes, link prediction is widely used in social networks, citation networks, biological networks, recommender systems, and security, etc. Traditional link prediction methods rely on heuristic node similarity scores, latent embeddings of nodes, or explicit node features. Graph neural network (GNN), as a powerful tool for jointly learning from graph structure and node/edge features, has gradually shown its advantages over traditional methods for link prediction. In this chapter, we discuss GNNs for link prediction. We first introduce the link prediction problem and review traditional link prediction methods. Then, we introduce two popular GNN-based link prediction paradigms, node-based and subgraph-based approaches, and discuss their differences in link representation power. Finally, we review recent theoretical advancements on GNN-based link prediction and provide several future directions.


  • Introduction
  • Traditional Link Prediction Methods
    • Heuristic Methods
    • Latent-Feature Methods
    • Content-Based Methods
  • GNN Methods for Link Prediction
    • Node-Based Methods
    • Subgraph-Based Methods
    • Comparing Node-Based Methods and Subgraph-Based Methods
  • Theory for Link Prediction
    • gamma-Decaying Heuristic Theory
    • Labeling Trick
  • Future Directions
    • Accelerating Subgraph-Based Methods
    • Designing More Powerful Labeling Tricks
    • Understanding When to Use One-Hot Features


author = "Zhang, Muhan",
editor = "Wu, Lingfei and Cui, Peng and Pei, Jian and Zhao, Liang",
title = "Graph Neural Networks: Link Prediction",
booktitle = "Graph Neural Networks: Foundations, Frontiers, and Applications",
year = "2022",
publisher = "Springer Singapore",
address = "Singapore",
pages = "195--223",

M. Zhang, “Graph neural networks: Link prediction,” in Graph Neural Networks: Foundations, Frontiers, and Applications, L. Wu, P. Cui, J. Pei, and L. Zhao, Eds. Springer Singapore, 2022, pp. 195–223.