Link prediction

Link prediction scores node pairs for a missing or future edge: hide test edges from message passing, sample non-edges as negatives, and rank. Heuristics (common neighbours, Adamic–Adar, Katz) are strong baselines; the metric depends on the negatives.

8 min read804 wordscore0 viewsupdated 2026-10-21

Definition

Link prediction is the task of scoring a node pair (u,v)(u,v) 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 G=(V,E)G=(V,E) with optional node features XX. The output is a score s(u,v)s(u,v) for any pair, so the task sits at the edge level: one prediction per pair, not per node or per graph. There are (n2)\binom{n}{2} 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

CN(u,v)=∣Γ(u)∩Γ(v)∣,AA(u,v)=∑w∈Γ(u)∩Γ(v)1log⁡dw,Katz(u,v)=∑l=1∞βl (Al)uv\text{CN}(u,v)=|\Gamma(u)\cap\Gamma(v)|,\qquad \text{AA}(u,v)=\sum_{w\in\Gamma(u)\cap\Gamma(v)}\frac{1}{\log d_w},\qquad \text{Katz}(u,v)=\sum_{l=1}^{\infty}\beta^l\,(A^l)_{uv}
Γ(u), dw\Gamma(u),\ d_w
neighbours of uu; degree of ww
AA\text{AA}
Adamic–Adar (Adamic and Adar, 2003): a shared neighbour counts more when it has few other neighbours. Resource allocation uses 1/dw1/d_w instead
β\beta
Katz (1953) decay; the series converges for β<1/λmax⁡(A)\beta<1/\lambda_{\max}(A), giving (I−βA)−1−I(I-\beta A)^{-1}-I

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 ZZ. A decoder scores pairs, either with a dot product or with an MLP on zu⊙zvz_u\odot z_v. 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.

Link prediction: hide some edges, learn on the rest, rank the hidden ones above non-edges1 · split the edgesABCDEFmessage passing (6)held-out positive (2)sampled negative (4)2 · encodeGNN encodersolid edges onlyZ ∈ ℝ^(6×d)z_Az_Bz_Cz_Dz_Ez_F(shades illustrative)3 · decode + lossscore s_uv:z_uᵀ z_v (dot)or MLP(z_u ⊙ z_v)p_uv = σ(s_uv)BCE on labels:y = 1: B–C, D–Ey = 0: 4 negativesfresh negativeseach epoch; testedges never seen4 · evaluate: rank all 6 candidates by score (here Adamic–Adar on the solid edges)1. B–C 2.892. A–D 2.353. D–E 0.914. A–E 0.915. B–E 06. A–F 0AUC = P(positive > negative) = 6.5 / 8 = 0.8125 (the D–E vs A–E tie counts ½)Hits@1 = 1/2: only B–C beats the best negative (A–D)
fig.The pipeline on six nodes. (1) The 8 edges are split: 6 stay for message passing and 2 (B–C, D–E) are held out as positives; 4 non-edges are sampled as negatives. (2) The encoder sees only the 6 solid edges. (3) A decoder scores pairs, trained with BCE. (4) Evaluation ranks the candidates. With Adamic–Adar on the solid edges, B–C is first, but the negative A–D (2.35) beats D–E (0.91): AUC = 6.5/8 = 0.8125.
L=−∑(u,v)∈E+log⁡σ(suv)−∑(u,v)∈E−log⁡(1−σ(suv)),suv=zu⊤zv  or  MLP(zu⊙zv)\mathcal L=-\sum_{(u,v)\in E^{+}}\log\sigma\big(s_{uv}\big)-\sum_{(u,v)\in E^{-}}\log\big(1-\sigma(s_{uv})\big),\qquad s_{uv}=z_u^\top z_v\ \text{ or }\ \mathrm{MLP}(z_u\odot z_v)
E+E^{+}
supervision edges: positives the loss sees, held out of the message-passing graph when possible
E−E^{-}
negatives, usually drawn uniformly from non-edges, resampled every epoch, often one per positive
zuz_u
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

AUC=1∣P∣∣N∣∑p∈P∑n∈N([sp>sn]+12[sp=sn]),MRR=1∣P∣∑i∈P1ranki,Hits@K=1∣P∣∑i∈P[ranki≤K]\text{AUC}=\frac{1}{|P||N|}\sum_{p\in P}\sum_{n\in N}\Big([s_p>s_n]+\tfrac12[s_p=s_n]\Big),\qquad \text{MRR}=\frac{1}{|P|}\sum_{i\in P}\frac{1}{\text{rank}_i},\qquad \text{Hits@}K=\frac{1}{|P|}\sum_{i\in P}[\text{rank}_i\le K]
AUC\text{AUC}
probability that a random positive outscores a random negative; independent of the number of negatives
ranki\text{rank}_i
position of positive i among itself and its own negatives (or, in OGB's Hits@K, against a shared negative set)
Hits@K\text{Hits@}K
share of positives in the top KK; meaningless if each positive has fewer than KK 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
40 nodes · 126 message-passing edges · 15 held-out positives × 10 negatives each— — test positive (click one)··· its 10 negatives (u, w)test edges removed from the graph before scoringROC, pooled (150 negatives)TPR 1FPR 1common neighbours |N(u) ∩ N(v)|AUC0.916MRR0.759Hits@30.933selected (5, 19): score 2rank 2 of 11 candidates (ties count ½)negatives ≥ it: 1 (max 3)
score
negatives
fig.A 40-node graph with two clusters and local clustering; 15 edges are held out (seed 1, 126 message-passing edges left). Default: common neighbours, 10 uniform negatives per positive: AUC 0.916, MRR 0.759, Hits@3 0.933. Switch to hard negatives (non-neighbours 2 hops from u) and the same scores give AUC 0.800, MRR 0.596, Hits@3 0.667. With 1 negative MRR is 0.978, with 20 it is 0.646, while AUC barely moves (0.909, 0.913). Turn on leakage: Katz, which includes the length-1 path, jumps to 1.000 on every metric, and the untrained GCN from AUC 0.893 to 0.972; common neighbours ignores the edge itself (0.923).

Worked example

PairLabelCommon nbrsCNJaccardAdamic–Adar
B–C1A, D20.6672.885
D–E1C10.3330.910
A–D0B, C21.0002.353
A–E0C10.3330.910
B–E0none000
A–F0none000
AUC0.7500.6880.813
The six-node graph of the diagram, scored on its 6 message-passing edges (degrees A 2, B 2, C 3, D 2, E 2, F 1; 1/ln 2 = 1.443, 1/ln 3 = 0.910). AUC compares the 2 positives with the 4 negatives, 8 pairs

Jaccard normalises by ∣Γ(u)∪Γ(v)∣|\Gamma(u)\cup\Gamma(v)|, 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.

python
1import torch, torch.nn.functional as F
2import torch_geometric.transforms as T
3from torch_geometric.datasets import Planetoid
4from torch_geometric.nn import GCNConv
5from torch_geometric.utils import negative_sampling
6from sklearn.metrics import roc_auc_score
7
8data = 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 only
12
13class 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)
19
20enc = 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)
23
24for epoch in range(200):
25 enc.train(); opt.zero_grad()
26 z = enc(train.x, train.edge_index)
27 pos = train.edge_label_index
28 neg = negative_sampling(train.edge_index, num_nodes=data.num_nodes,
29 num_neg_samples=pos.size(1)) # fresh each epoch
30 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()
33
34enc.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}")
GCN encoder + dot-product decoder on Cora with a leakage-free split (PyTorch Geometric; not run here, since this environment has no torch)

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 zu⊤zvz_u^\top z_v 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.
← back to Deep Learning roadmap