Link Prediction — Missing and Future Edge Inference in Networks
Link Prediction (Missing and Future Edge Inference) · Also known as: Bağlantı Tahmini (Link Prediction), missing link prediction, future link prediction, edge prediction
Link prediction is a network-analysis task that estimates which edges are missing from an observed graph or which edges are likely to form in the future. Formalised by Liben-Nowell and Kleinberg (2003, 2007), it covers a spectrum of approaches — from simple structural similarity indices such as Common Neighbors, Jaccard coefficient, and Adamic-Adar, to matrix factorisation, and graph neural network (GNN) methods — and is evaluated with AUC and Average Precision to account for the heavily imbalanced ratio of real to non-existing edges.
Read the full method
Sign in with a free account to read this section.
Method map
The neighbourhood of related methods — select a node to explore.
When to use it
Link prediction fits any problem in which the network is incomplete or evolving and the goal is to recover or anticipate edges. Suitable scenarios include recommending new connections in social networks, predicting future citations or collaborations, inferring protein-protein interactions, and completing knowledge graphs. The method requires at least 50 nodes and a sufficient density of observed edges so that structural patterns are learnable. When fewer than 20 nodes are available, centraliy analysis is a safer choice. The observed portion of the graph must be representative; if the sampling mechanism is heavily biased the inferred edges may reflect sampling artefacts rather than true structure.
Strengths & limitations
- Spans a wide range of complexity — simple Jaccard or Adamic-Adar indices require no training and work directly on the graph topology, while GNN-based methods learn complex structural patterns.
- Model-free similarity indices are fast, interpretable, and robust on sparse graphs with limited training signal.
- GNN approaches generalise well across domains (social, biological, knowledge-graph) and capture higher-order topology.
- The AUC/AP evaluation framework is robust to severe class imbalance between real and non-existing edges.
- Performance depends critically on the negative-sampling strategy; different strategies can yield different conclusions from the same model.
- GNN-based methods require a sufficiently large labelled edge set and significant computational resources.
- Structural indices assume that similarity in observed topology implies future connectivity, which may not hold in networks with heterophilic structure.
- Temporal train–test splitting is essential but requires reliable timestamps; without them, information leakage inflates apparent performance.
Frequently asked
Which approach should I choose — a similarity index or a GNN?
Similarity indices (Common Neighbors, Jaccard, Adamic-Adar) are a good starting point: they require no training, are interpretable, and perform surprisingly well on sparse graphs. GNN-based methods like Seal outperform indices on networks with complex higher-order structure but require a sufficient number of labelled edges and more computational resources. When data are limited or interpretability matters, start with indices.
How do I split the graph for evaluation without leaking information?
If your edges carry timestamps, use a temporal split: train on edges observed before a cutoff time and test on edges formed after it. Without timestamps, hold out a random fraction of edges as positives and sample an equal or fixed number of non-edges as negatives, ensuring no held-out edge appears in the training adjacency matrix.
Why is AUC preferred over accuracy?
In any real network the number of absent edges vastly exceeds the number of present ones — often by several orders of magnitude. A trivial model that predicts 'no edge' for every pair achieves near-perfect accuracy while predicting nothing useful. AUC-ROC and Average Precision are rank-based metrics that are insensitive to this imbalance and directly measure the quality of the ranking.
Can link prediction be applied to directed or weighted graphs?
Yes. For directed graphs, scores can be computed separately in each direction, and some GNN frameworks natively handle directed adjacency. For weighted graphs, similarity indices can incorporate edge weights in the neighbourhood computation, and GNN methods can use edge features. However, most benchmark studies are on unweighted undirected graphs, so extra care is needed when adapting methods.
Sources
- Liben-Nowell, D. & Kleinberg, J. (2007). The Link-Prediction Problem for Social Networks. Journal of the American Society for Information Science and Technology, 58(7), 1019-1031. DOI: 10.1002/asi.20591 ↗
- Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31. link ↗
How to cite this page
ScholarGate. (2026, June 1). Link Prediction (Missing and Future Edge Inference). ScholarGate. https://scholargate.app/en/network-analysis/link-prediction
Which method?
Set this method beside its closest kin and read them side by side — the library lays the books on the table; the choice is yours.
- Centrality AnalysisNetwork analysis↔ compare
- Community DetectionNetwork analysis↔ compare
- Graph Neural Network (Network Analysis)Network analysis↔ compare
- Network EmbeddingNetwork analysis↔ compare
- Stochastic Block ModelNetwork analysis↔ compare