# 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.

Source: https://www.mlfoundry.in/learn/link-prediction  
Section: Deep Learning › Graph Neural Networks (GNNs)  
Level: core · 8 min read · updated 2026-10-21

**Link prediction:** is the task of scoring a node pair $(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)$ with optional node features $X$. The output is a score $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 $\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

$$
\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}
$$

- $\Gamma(u),\ d_w$: neighbours of $u$; degree of $w$
- $\text{AA}$: Adamic–Adar (Adamic and Adar, 2003): a shared neighbour counts more when it has few other neighbours. Resource allocation uses $1/d_w$ instead
- $\beta$: Katz (1953) decay; the series converges for $\beta<1/\lambda_{\max}(A)$, giving $(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 $Z$. A decoder scores pairs, either with a dot product or with an MLP on $z_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.

> Figure: 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.

$$
\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^{+}$: supervision edges: positives the loss sees, held out of the message-passing graph when possible
- $E^{-}$: negatives, usually drawn uniformly from non-edges, resampled every epoch, often one per positive
- $z_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

$$
\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]
$$

- $\text{AUC}$: probability that a random positive outscores a random negative; independent of the number of negatives
- $\text{rank}_i$: position of positive i among itself and its own negatives (or, in OGB's Hits@K, against a shared negative set)
- $\text{Hits@}K$: share of positives in the top $K$; meaningless if each positive has fewer than $K$ 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

> Figure: 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

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

| 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 $|\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
import torch, torch.nn.functional as F
import torch_geometric.transforms as T
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv
from torch_geometric.utils import negative_sampling
from sklearn.metrics import roc_auc_score

data = Planetoid("data", "Cora")[0]
split = T.RandomLinkSplit(num_val=0.05, num_test=0.1, is_undirected=True,
                          add_negative_train_samples=False)
train, val, test = split(data)       # test.edge_index = train + val edges only

class Encoder(torch.nn.Module):
    def __init__(self, d_in, d_hid=128, d_out=64):
        super().__init__()
        self.c1, self.c2 = GCNConv(d_in, d_hid), GCNConv(d_hid, d_out)
    def forward(self, x, edge_index):
        return self.c2(self.c1(x, edge_index).relu(), edge_index)

enc = Encoder(data.num_features)
opt = torch.optim.Adam(enc.parameters(), lr=0.01)
score = lambda z, ei: (z[ei[0]] * z[ei[1]]).sum(-1)

for epoch in range(200):
    enc.train(); opt.zero_grad()
    z = enc(train.x, train.edge_index)
    pos = train.edge_label_index
    neg = negative_sampling(train.edge_index, num_nodes=data.num_nodes,
                            num_neg_samples=pos.size(1))      # fresh each epoch
    logits = torch.cat([score(z, pos), score(z, neg)])
    labels = torch.cat([torch.ones(pos.size(1)), torch.zeros(neg.size(1))])
    F.binary_cross_entropy_with_logits(logits, labels).backward(); opt.step()

enc.eval()
with torch.no_grad():
    z = enc(test.x, test.edge_index)
    auc = roc_auc_score(test.edge_label, score(z, test.edge_label_index).sigmoid())
print(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)

> **Leakage through message passing:** If a test edge stays in the graph the encoder runs on, the encoder can see it: one GCN layer already puts $u$ in $v$'s neighbourhood. Path-based scores are hit hardest. In the figure, Katz's $\beta A_{uv}$ term makes every leaked positive win, so AUC goes to 1.000. Remove validation and test edges before encoding at train time. At test time, run the encoder on train (and validation) edges only. Watch for undirected graphs stored as two directed edges: both directions must go.

> **Why node embeddings alone are not enough:** A GNN gives the same embedding to nodes that are automorphic, i.e. symmetric in the graph. Two such nodes then get the same score with $u$ even if one is $u$'s neighbour's neighbour and the other is far away. SEAL fixes this with a **labelling trick**: it marks $u$ and $v$ in the subgraph around them and labels each node by its distances to both, so the GNN learns pair-specific structure. Zhang et al. (NeurIPS 2021) proved that, with such a labelling, a sufficiently expressive GNN gives the most expressive representation of the pair. NBFNet (Zhu et al., NeurIPS 2021) gets the same effect by running message passing from the source node.

**Strengths**

- 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.

**Limitations**

- 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.

**Question:** In the figure, leaking the test edges into the graph sends Katz to AUC 1.000 but hardly changes common neighbours. Why?

- A. Katz is normalised and common neighbours is not
- B. Katz sums paths of every length, including the length-1 path that is the test edge itself; common neighbours counts only 2-hop paths
- C. Common neighbours is computed on the training graph only
- D. The random negatives happen to favour common neighbours

**Answer:** B. Katz sums paths of every length, including the length-1 path that is the test edge itself; common neighbours counts only 2-hop paths — Katz contains $\beta(A)_{uv}$, which is $\beta$ for every leaked positive and 0 for every negative, so positives win once longer paths are small. $\text{CN}(u,v)$ counts shared neighbours and never looks at $A_{uv}$. The edge still changes the neighbourhoods of other pairs, which is why CN's AUC moves a little.

**Question:** You raise the number of negatives per positive from 1 to 20. What happens to AUC and MRR?

- A. Both drop a lot
- B. AUC stays about the same, MRR drops
- C. MRR stays the same, AUC drops
- D. Both rise

**Answer:** B. AUC stays about the same, MRR drops — AUC estimates a pairwise probability, which does not depend on how many negatives are drawn. MRR uses the rank among the candidates, and with more negatives a positive is more likely to be beaten by one. In the figure: AUC 0.909 → 0.913, MRR 0.978 → 0.646. Only compare MRR or Hits@K numbers computed with the same negatives.

**Key points**

- 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 $z_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.

---

From MLFoundry (https://www.mlfoundry.in). The web page adds interactive figures and diagrams.
