Link Prediction in a Graph, Explained

Link prediction asks which edges that are absent from the graph today are most likely to appear tomorrow, or to have been there all along and gone unrecorded. The classical answer is a family of scores computed from nothing but who each pair of nodes has in common, and they are simple enough to work through completely.

It is a ranking problem, not a classification

The framing that Liben-Nowell and Kleinberg set out in The Link Prediction Problem for Social Networks (Cornell, 2003) is the one still in use: take a graph as it stood at time t, produce a score for every pair of nodes not already joined, sort descending, and check how many of the top-scoring pairs became real edges by time t'. Note what that is not. You are not deciding, per pair, edge or no edge. You are producing an ordering over a very large candidate set and only the head of it will ever be looked at.

That distinction decides everything downstream — which metric to use, how to split the data, and how to think about the failure modes. Get it wrong and you will build a classifier that reports 99.99% accuracy while surfacing nothing.

Four scores on one small graph

Here is the graph. Eight edges, six nodes:

A - C     C - D
A - D     C - E
B - C     D - F
B - D     E - F
B - E

neighbourhoods
  N(A) = {C, D}          degree 2
  N(B) = {C, D, E}       degree 3
  N(C) = {A, B, D, E}    degree 4
  N(D) = {A, B, C, F}    degree 4
  N(E) = {B, C, F}       degree 3
  N(F) = {D, E}          degree 2

A and B are not joined. Should they be? Every classical score is a function of the two neighbourhoods, so take the intersection first: N(A) ∩ N(B) = {C, D}, and the union is {C, D, E}.

Common neighbours    CN(A,B) = |N(A) ∩ N(B)|
                             = 2

Jaccard              J(A,B)  = |N(A) ∩ N(B)| / |N(A) ∪ N(B)|
                             = 2 / 3 = 0.667

Adamic-Adar          AA(A,B) = Σ  1 / log |N(z)|      for z in the intersection
                             = 1/ln 4 + 1/ln 4
                             = 0.721 + 0.721 = 1.443

Preferential attach. PA(A,B) = |N(A)| · |N(B)|
                             = 2 · 3 = 6

Now do the same for the pair (A, E), which is also unjoined. N(A) ∩ N(E) = {C} only, so CN = 1, Jaccard = 1/4 = 0.25, Adamic-Adar = 1/ln 4 = 0.721, and preferential attachment = 2 · 3 = 6.

Three of the four scores rank (A, B) above (A, E). Preferential attachment ties them, because it never looks at the intersection at all — it is a pure popularity prior, the graph equivalent of recommending whatever is trending. That is exactly its known behaviour and it is why preferential attachment is usually a baseline rather than a method: it will happily score a pair with no shared neighbours above a pair with three, provided both endpoints are hubs.

Why the hub discount matters

Adamic-Adar comes from Adamic and Adar’s 2003 paper in Social Networks, and the whole of it is the 1 / log |N(z)| term. A shared neighbour is evidence in proportion to how selective it is. Two people who both know a recluse with three contacts are far more likely to know each other than two people who both follow an account with three million followers.

Put numbers on it. If the shared node z has degree 4, it contributes 1/ln 4 = 0.721. At degree 50 it contributes 1/ln 50 = 0.256. At degree 4,000 it contributes 1/ln 4000 = 0.121. A single high-degree hub is worth about a sixth of a single low-degree neighbour, which is roughly the discount you would apply by eye.

The base of the logarithm is a common source of confusion and it does not matter. Changing base multiplies every term by the same constant, so the ranking is identical whether you use natural log or log base 10. What does matter is degree 1: log 1 = 0, so a shared neighbour of degree 1 divides by zero. A shared neighbour necessarily has degree at least 2 (it touches both endpoints), so this cannot arise in an undirected graph — but it very much can if you have computed neighbourhoods directionally and forgotten. The resource-allocation index of Zhou, Lü and Zhang (2009) uses 1 / |N(z)| instead of the log, which discounts hubs harder; on our graph it gives 1/4 + 1/4 = 0.5 for (A, B) against 0.25 for (A, E), the same ordering with a wider gap.

Accuracy is meaningless here

A graph with n nodes has n(n-1)/2 possible undirected edges. A real social or transaction graph has a tiny fraction of them. Take a modest example and do the arithmetic in the open: 100,000 nodes gives 4,999,950,000 candidate pairs. If the graph has 1,000,000 edges and 10,000 new ones appear in the next period, the positive rate among candidates is 10,000 / 4,999,950,000 ≈ 0.0000020, or one in half a million.

A model that predicts “no edge” for every pair scores 99.9998% accuracy. So does a model that is genuinely useful. The metric cannot distinguish them, and neither can ROC-AUC in any way you should trust: with that imbalance, an enormous number of false positives moves the false-positive rate almost not at all, so AUC stays high while the top of your ranked list is junk.

• Precision at k — of the top 100 (or 1,000) scored pairs, how many became edges. This is the number that matches what you will actually do with the output.
• Average precision / area under the precision-recall curve — sensitive to the head of the ranking in the way AUC is not.
• A temporal split, never a random one. Hide edges by timestamp, not at random. A random split leaks: if you hide edge (u,v) but keep (u,w) and (w,v) from the same later period, the structure you are predicting is partly still in the training graph.

Where neighbourhood scores return zero

Every score above is zero when the intersection is empty, and there are whole graph shapes where that is always true.

The important one is bipartite graphs — users on one side, items on the other, edges only between the sides. A user and an item can never share a neighbour, because a neighbour of a user is an item and a neighbour of an item is a user. Common neighbours is identically zero for every pair you care about. The fix is to count paths of length three rather than two, or to project one side onto itself first; this is the mechanism behind graph-based recommendation and it is why that page exists separately.

The second is a new node. A node with one edge has one neighbour, so almost every pair involving it scores zero and it never appears near the top of the list — the cold-start case, which needs attributes rather than topology. The third is any graph where the real signal is more than two hops away, where you want Katz (a damped sum over all path lengths) or a learned representation from random-walk node embeddings, whose similarity is nonzero for pairs that share no neighbour at all.