Link Prediction — Missing and Future Edge Inference in Networks
- Year
- 2003
- Type
- Network inference task
What does it do?
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.
The intuition behind the method
In any real-world network, the recorded edges represent only a fraction of the true connections: friendship platforms miss undisclosed ties, citation databases omit unindexed papers, and protein-interaction assays leave many pairs untested. Link prediction asks: given the connections we can see, which unobserved pairs are most likely to be connected? The core intuition is that two nodes sharing many common neighbours, or sitting close to each other in a learned embedding space, are more likely to be linked than two structurally distant nodes. Similarity-based indices make this explicit with a single formula; GNN-based approaches learn which structural patterns best predict connectivity from labelled examples.
History
The task was formally defined by Liben-Nowell and Kleinberg in a 2003 SODA paper and its extended 2007 JASIST version, where they benchmarked simple structural similarity indices on co-authorship networks and showed that topology alone carries strong predictive signal. Subsequent work extended the task to matrix-factorisation and probabilistic generative models. The field was substantially advanced by Zhang and Chen (2018), who proposed the Seal framework — extracting local enclosing subgraphs and classifying them with a GNN — demonstrating that learned structural features consistently outperform handcrafted similarity indices across diverse benchmark networks.
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.
Limitations and considerations
- 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.
Source conditions do not replace independent scientific review or validation by an analysis engine.
Strengths
- 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.
Applications
- Friend or connection recommendation in social networks (Facebook People You May Know, LinkedIn).
- Predicting future research collaborations or citation relationships in academic networks.
- Inferring missing protein-protein interactions in biological networks from partial experimental data.
- Completing knowledge graphs by predicting relations between entities.
- Drug-target interaction prediction in pharmacological networks.
How it works
How it works
The network is assembled from observed edges and partitioned into training and test sets using a temporal or random split. Temporal splitting is preferred whenever timestamps are available because it prevents information leakage: future edges must not inform the model about past ones. The training graph is the only graph the scoring method may observe.
Because the vast majority of node pairs are unconnected, evaluating every absent pair is impractical. A negative-sampling strategy selects a set of non-existing edges to serve as negative examples. The size and sampling strategy (random, hard-negative, degree-balanced) affect measured performance substantially and must be reported alongside results.
Each candidate pair receives a likelihood score. Structural indices compute the score from the observed graph topology — Common Neighbors counts shared neighbours, Jaccard normalises that count by the union, and Adamic-Adar weights shared neighbours by the inverse log of their degree. Matrix-factorisation methods decompose the adjacency matrix into latent factors whose dot product approximates edge probability. GNN-based methods, most prominently the Seal framework of Zhang and Chen (2018), extract local subgraphs around each candidate pair and train a graph classifier to distinguish real from spurious edges, capturing higher-order structural patterns that simple indices miss.
Predictions are ranked by score and compared against held-out positive and negative edges. AUC-ROC measures the probability that a random positive pair is ranked above a random negative pair. Average Precision (AP) summarises precision across the full ranking and is more informative when positive examples are rare. Both metrics must be reported; accuracy alone is misleading under severe class imbalance.
Common pitfalls
- Leaking future edges into the training graph — always use temporal or strictly random splits and verify no test edge appears in the training adjacency matrix.
- Reporting only accuracy; because non-edges vastly outnumber true edges, accuracy is almost meaningless — always report AUC and AP.
- Ignoring the negative-sampling strategy when comparing methods; changing sampling can reverse rankings between models.
- Applying link prediction to graphs with fewer than 20 nodes — with so few nodes the structural patterns are too sparse to yield reliable predictions; prefer centrality analysis instead.
- Treating a biased observed graph as a representative sample — if observed edges are systematically missing certain node types, predictions will inherit that bias.
Frequently asked questions
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.
Related 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.
Open DOI referenceCopied.Zhang, M. & Chen, Y. (2018). Link Prediction Based on Graph Neural Networks. Advances in Neural Information Processing Systems (NeurIPS), 31.
Open publication referenceCopied.