Link Prediction

Heuristics, embedding decoders, knowledge graph completion, negative sampling, evaluation pitfalls

Freebase contains 40 million entities — actors, movies, directors — and 100 million triples: (Christopher Nolan, directed, Inception), (Inception, hasGenre, SciFi), (Leonardo DiCaprio, actedIn, Inception). Most triples are missing. The graph is an incomplete snapshot of a much larger set of true facts. Link prediction asks: what missing triples are likely true? If a user likes Inception, knowledge graph link prediction can infer other Nolan films the user might like by finding films connected to Nolan through the "directed" relation.

Two traps define the field. First, structural heuristics often match or beat learned GNN models on homophilic networks, because triangle closure is the dominant link formation mechanism. Common Neighbors, Adamic-Adar, and Katz scores run in O(|E|) time with no training and are surprisingly competitive on social and citation graphs. Always establish a heuristic baseline before training a GNN. If the GNN doesn't beat Adamic-Adar, the model is learning nothing the structure doesn't already tell you.

Second, evaluation is easy to get wrong in ways that inflate reported accuracy without any genuine generalization. If test edge (A, B) has training edges (A, C) and (C, B) in the training graph, the GNN encodes C's embedding in both A's and B's representations. The dot product between A's and B's embeddings is high because both reflect the shared neighbor C — not because the model generalized. The correct procedure removes test edges from the training adjacency matrix before any GNN training.

NOT this. "Knowledge graphs require hand-crafted ontologies." Modern knowledge graphs are mostly extracted from text automatically using information extraction and OpenIE systems. Wikidata has 90 million-plus triples and is collaboratively maintained. The knowledge graph embedding literature — TransE, RotatE, ComplEx — focuses on how to learn representations from the triple structure, not how to curate the ontology. The curation question is upstream of the ML question, and for most research and production applications it is already solved.

Key points

• Structural heuristics run in O(|E|) time, require no training, and often outperform learned models on homophilic citation and social networks. Common Neighbors (CN): score(u,v) = |N(u) ∩ N(v)|. Adamic-Adar: Σ_{w∈N(u)∩N(v)} 1/log(|N(w)|) — downweights high-degree common neighbors that provide less specific signal. Katz index: Σ_{l=1}^∞ β^l |paths_{uv}^l| — counts all paths between u and v with exponential decay. Always establish a heuristic baseline before training a GNN; if the GNN doesn't beat Adamic-Adar, the model is not learning anything the structure doesn't already tell you.
• Dot product decoder: P(edge) = σ(z_u · z_v). Works when proximity in embedding space correlates with link existence. Simple, fast, and used in most GraphSAGE-based systems. The limitation: dot product only captures symmetric, linear similarity — it cannot model asymmetric relationships (A follows B without B following A) or nonlinear compatibility.
• Bilinear decoder: P(edge) = σ(z_u^T R z_v) where R ∈ ℝ^{d×d} is a learned relation matrix. More expressive — R captures asymmetric relationships (non-symmetric R means P(u→v) ≠ P(v→u)). For heterogeneous graphs with multiple relation types, use relation-specific R_r matrices (DistMult, RESCAL models). The cost: R adds d² parameters and can overfit on small graphs.
• Knowledge graph completion: KGs store (head, relation, tail) triples — but most triples are missing. TransE: h + r ≈ t, score = -‖h + r - t‖. Captures simple relational patterns but fails for symmetric relations (requires r=0, collapsing all entities). RotatE: models relations as rotations in complex space, handling symmetric, antisymmetric, inverse, and composition patterns. ComplEx: complex-valued embeddings handle asymmetric relations.
• Negative sampling strategy matters more than most practitioners realize. Random (u,v) pairs from the full node set are trivially easy negatives — nodes from entirely different domains don't connect. Better: corrupt head or tail of a positive triple randomly (KG completion standard). Hard negatives — sample near-positives in embedding space — provide the richest gradient but risk false negatives. k=5–20 negatives per positive is typical; too many easy negatives and the model learns nothing; too many hard negatives and training destabilizes.
• Evaluation metrics: AUC-ROC for binary link prediction, measuring overall discriminative performance. MRR (Mean Reciprocal Rank) and Hits@K (fraction of correct entities ranked in top K) for KG completion, where the task is ranking candidates. Filtered evaluation: when computing rank, remove all other known positive triples from the ranking list — otherwise the model is penalized for correctly ranking true triples above the target triple.
• Data leakage in link prediction: if edge (u,v) is the test edge but edges (u,w) and (w,v) are in training, then the GNN learns w's embedding and incorporates it into both u's and v's representations. The dot product z_u · z_v is high because both reflect the shared neighbor w. The model appears to predict (u,v) correctly, but only because it saw the triangle during training — not because it generalized to an unseen edge. Correct procedure: remove all test and validation edges from the training adjacency matrix before training.
• SEAL (Zhang & Chen, 2018): extracts the local enclosing subgraph around each candidate link (K-hop neighborhood of the pair), assigns structural labels (shortest-path distance to each endpoint), and trains a graph-level GNN classifier. By training on subgraph structure rather than global node embedding proximity, SEAL avoids the leakage problem and captures the structural pattern around the link directly. Achieves best results on citation and social network benchmarks partly for this reason.

Recap

• Link prediction = infer missing triples: KGs (Freebase 40M entities, 100M triples) are incomplete snapshots.
• Heuristics are strong baselines: Common Neighbors, Adamic-Adar, Katz run O(|E|), no training, often beat GNNs on homophilic graphs.
• If the GNN doesn't beat Adamic-Adar, it's learning nothing the structure doesn't already say.
• Decoders: dot product (symmetric, linear) → bilinear $z_u^T R z_v$ (asymmetric) → KG models TransE/RotatE/ComplEx.
• Negative sampling matters: k=5–20/positive; random = trivial, hard negatives = rich gradient but risk false negatives.
• Data leakage is the trap: if test edge $(u,v)$ has training path $u$-$w$-$v$, dot product is inflated by shared $w$ — remove test edges from the training adjacency.
• SEAL trains on the local enclosing subgraph (structural labels) → avoids leakage, captures link structure directly.

Check your understanding