Definition
Link prediction is the task of scoring a node pair by how likely an edge between them is missing from, or will appear in, an observed graph. Liben-Nowell and Kleinberg posed it for social networks in "The Link Prediction Problem for Social Networks" (CIKM 2003) and compared neighbourhood and path heuristics. Recommendation (user–item edges), knowledge-graph completion and drug–drug interaction prediction are all instances.
The input is a graph with optional node features . The output is a score for any pair, so the task sits at the edge level: one prediction per pair, not per node or per graph. There are candidate pairs and real graphs are sparse, so almost every pair is a non-edge. Training and evaluation therefore always compare a few positives with a sample of negatives.
Before GNNs, two families dominated. Heuristics compute a score from the graph alone. Shallow embeddings (DeepWalk, node2vec, matrix factorisation; see Graph representation learning) learn a vector per node and score pairs by a dot product. A GNN encoder replaces the free vectors with message passing over features and neighbourhoods.
Heuristic scores
- neighbours of ; degree of
- Adamic–Adar (Adamic and Adar, 2003): a shared neighbour counts more when it has few other neighbours. Resource allocation uses instead
- Katz (1953) decay; the series converges for , giving
Common neighbours and Adamic–Adar are first- and second-order local scores: they use two-hop paths only. Katz counts paths of every length with geometric decay. On graphs with strong triadic closure (social, citation, co-authorship) these heuristics are hard to beat, and every new method should be compared with them.
The GNN pipeline
An encoder (Graph Convolutional Network (GCN), GraphSAGE, Graph Attention Network (GAT)) turns the observed graph into node embeddings . A decoder scores pairs, either with a dot product or with an MLP on . The model is trained with Binary cross-entropy on positive edges and sampled negative pairs. Kipf and Welling's Graph autoencoders are exactly this recipe with a dot-product decoder.
- supervision edges: positives the loss sees, held out of the message-passing graph when possible
- negatives, usually drawn uniformly from non-edges, resampled every epoch, often one per positive
- encoder output for node u, computed on message-passing edges only
Splits and negatives
A transductive random split removes a fraction of edges (Kipf and Welling used 85/5/10% for train/validation/test) and keeps all nodes. The removed edges must disappear from the message-passing graph, or the encoder sees the answer. Training edges have the same problem: if a positive is also a message-passing edge, the model can learn to detect the edge itself. PyG's RandomLinkSplit can split training edges into disjoint message-passing and supervision sets with disjoint_train_ratio. Temporal graphs should be split by time, and inductive settings hold out whole nodes.
The negatives decide how hard the test is. Uniform random pairs are almost always far apart, so any score that knows "nearby" wins. Li et al. (NeurIPS 2023) showed that with harder, per-positive negatives drawn from heuristic top candidates, the ranking of published methods changes, and many reported gains shrink.
Metrics
- probability that a random positive outscores a random negative; independent of the number of negatives
- position of positive i among itself and its own negatives (or, in OGB's Hits@K, against a shared negative set)
- share of positives in the top ; meaningless if each positive has fewer than negatives
AUC and average precision with one negative per positive were standard on Cora, Citeseer and PubMed. They saturate quickly. The Open Graph Benchmark (Hu et al., NeurIPS 2020) moved to ranking metrics that resemble retrieval: a positive must beat many negatives, not one.
Benchmarks and reported numbers
- Cora (PyG)
- 2,708 nodes, 5,278 undirected edges, 1,433 bag-of-words features; random 85/5/10 edge split
- GAE / VGAE on Cora
- test AUC 91.0 / 91.4 and AP 92.0 / 92.6 (Kipf and Welling, 2016); spectral clustering 84.6 AUC, DeepWalk 83.1
- ogbl-collab
- author collaboration graph, split by year; metric Hits@50
- ogbl-ddi
- drug–drug interaction graph, no node features; metric Hits@20
- ogbl-ppa / ogbl-citation2
- protein association (Hits@100) and citation graph (MRR against sampled negatives per positive)
- SEAL
- Zhang and Chen (NeurIPS 2018): classify the enclosing subgraph around (u, v) with node labels by distance to u and v
Worked example
| Pair | Label | Common nbrs | CN | Jaccard | Adamic–Adar |
|---|---|---|---|---|---|
| B–C | 1 | A, D | 2 | 0.667 | 2.885 |
| D–E | 1 | C | 1 | 0.333 | 0.910 |
| A–D | 0 | B, C | 2 | 1.000 | 2.353 |
| A–E | 0 | C | 1 | 0.333 | 0.910 |
| B–E | 0 | none | 0 | 0 | 0 |
| A–F | 0 | none | 0 | 0 | 0 |
| AUC | 0.750 | 0.688 | 0.813 |
Jaccard normalises by , so the negative A–D, whose two neighbourhoods coincide, gets the top score 1.0 and AUC drops. Adamic–Adar separates B–C from A–D because B–C's shared neighbours A and D both have degree 2, while A–D shares C, which has degree 3.
1import torch, torch.nn.functional as F2import torch_geometric.transforms as T3from torch_geometric.datasets import Planetoid4from torch_geometric.nn import GCNConv5from torch_geometric.utils import negative_sampling6from sklearn.metrics import roc_auc_score78data = Planetoid("data", "Cora")[0]9split = T.RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True,10 add_negative_train_samples=False)11train, val, test = split(data) # test.edge_index = train + val edges only1213class Encoder(torch.nn.Module):14 def __init__(self, d_in, d_hid=128, d_out=64):15 super().__init__()16 self.c1, self.c2 = GCNConv(d_in, d_hid), GCNConv(d_hid, d_out)17 def forward(self, x, edge_index):18 return self.c2(self.c1(x, edge_index).relu(), edge_index)1920enc = Encoder(data.num_features)21opt = torch.optim.Adam(enc.parameters(), lr=0.01)22score = lambda z, ei: (z[ei[0]] * z[ei[1]]).sum(-1)2324for epoch in range(200):25 enc.train(); opt.zero_grad()26 z = enc(train.x, train.edge_index)27 pos = train.edge_label_index28 neg = negative_sampling(train.edge_index, num_nodes=data.num_nodes,29 num_neg_samples=pos.size(1)) # fresh each epoch30 logits = torch.cat([score(z, pos), score(z, neg)])31 labels = torch.cat([torch.ones(pos.size(1)), torch.zeros(neg.size(1))])32 F.binary_cross_entropy_with_logits(logits, labels).backward(); opt.step()3334enc.eval()35with torch.no_grad():36 z = enc(test.x, test.edge_index)37 auc = roc_auc_score(test.edge_label, score(z, test.edge_label_index).sigmoid())38print(f"test AUC {auc:.3f}")Use when
- +Heuristics need no training, scale to huge graphs and are strong on social and citation graphs.
- +GNN encoders use node features, so they work where structure is thin or nodes are new.
- +Subgraph and source-conditioned GNNs (SEAL, NBFNet) learn heuristics and beat both on many benchmarks.
Avoid when
- −Heuristics ignore features and fail on graphs without triadic closure (e.g. bipartite user–item graphs).
- −Dot-product GNN decoders cannot tell automorphic nodes apart.
- −Subgraph methods extract one subgraph per pair, which is slow at inference over many candidates.
Check yourself
In the figure, leaking the test edges into the graph sends Katz to AUC 1.000 but hardly changes common neighbours. Why?
Check yourself
You raise the number of negatives per positive from 1 to 20. What happens to AUC and MRR?
Remember
- ✓Edge-level task: score pairs; train and evaluate on held-out positives against sampled non-edges.
- ✓Heuristics (common neighbours, Adamic–Adar, resource allocation, Katz) are the baselines every model must beat.
- ✓GNN recipe: encoder on message-passing edges → decoder or MLP → BCE with fresh negatives each epoch.
- ✓Remove validation and test edges from the encoder's graph; split by time for temporal data.
- ✓AUC ignores the number of negatives; MRR and Hits@K depend on it and on how hard the negatives are.
- ✓Plain node embeddings cannot separate automorphic nodes; SEAL's labelling trick and NBFNet condition on the pair.