Knowledge Graph Completion: Link Prediction

Type "Rohit Sharma" into a search engine and a knowledge panel appears instantly: born date, teams, achievements, related players. That panel is not assembled by a person editing a form. It is read off a knowledge graph — a database where facts are stored as (head, relation, tail) triples such as (Rohit Sharma, playsFor, Mumbai Indians) — and crucially, most of that graph was never typed in by anyone. Wikidata alone holds over 100 million entities; Google's internal knowledge graph is larger still. No editorial team writes every fact for every entity. Large stretches of the graph are simply missing — an actor's nationality unset, a drug's target protein unlinked, a company's parent-subsidiary edge absent — not because the fact is false, but because nobody entered it. The panel you see on screen is frequently the output of a model that looked at the shape of the graph around a gap and predicted what edge belongs there. That task — given a graph riddled with holes, rank the most plausible missing edges — is knowledge graph completion via link prediction, and it is the subject of this chapter.

Why knowledge graphs are structurally incomplete

A relational database usually operates under the closed-world assumption: if a row is not in the table, the fact is false. Knowledge graphs instead operate under the open-world assumption: if a triple is absent, its truth value is simply unknown. Wikidata not listing a birthplace for some entity does not mean that entity has no birthplace — it means nobody has recorded it yet. This single assumption is what makes knowledge graph completion a genuinely different problem from ordinary database lookups. You cannot train a classifier on "true triples" versus "false triples" scraped directly from the graph, because the graph contains almost no confirmed false triples — only a sea of unlabelled absences. Whatever method you build has to learn regularities from the triples that do exist and use them to score triples that do not, without ever having seen an explicit negative example. That constraint shapes every design decision in this chapter, starting with how negative training examples get manufactured at all (covered later, under negative sampling).

Formally, a knowledge graph is a set of triples (h, r, t) where h and t are entities from a set E and r is a relation from a set R. Unlike the plain graphs from your DSA course — one node type, one edge type, undirected or directed — a knowledge graph is multi-relational and directed by construction: the same pair of nodes can be connected by several different relation types simultaneously, and almost every relation is directional (playsFor(Rohit, MumbaiIndians) is not interchangeable with playsFor(MumbaiIndians, Rohit)). Link prediction is the task: given a query with one slot blank, either (h, r, ?) or (?, r, t), rank all candidate entities by how plausible they are as the missing element, using only the structure and content of the triples already present.

Scoring plausibility with vector translation: TransE

The dominant family of solutions, knowledge graph embeddings, sidesteps symbolic reasoning entirely and instead places every entity and every relation into a shared vector space, then defines a scoring function over that space. The simplest and most influential of these is TransE (Bordes et al., 2013). Its idea is disarmingly geometric: represent each entity as a vector, and represent each relation also as a vector, such that for every true triple, adding the relation vector to the head vector lands you approximately on the tail vector:

e(h) + e(r) ≈ e(t)

A relation is modeled as a fixed translation in the embedding space. To score how plausible a candidate triple is, you measure how far the translated head lands from the proposed tail — the L2 distance ‖e(h) + e(r) − e(t)‖ — and smaller distance means higher plausibility. Training adjusts every entity and relation vector so that known-true triples end up with small distance and corrupted (probably-false) triples end up with large distance. Once trained, answering (h, r, ?) is a nearest-neighbour search: compute e(h) + e(r), then rank every candidate entity by distance to that point.

Work through this by hand with toy two-dimensional embeddings — small enough to trace exactly, chosen for arithmetic clarity rather than fitted from real match data. Suppose training has already converged on these vectors for the relation playsFor and four entities:

e(Sachin)          = (1, 2)
e(Virat)           = (4, 1)
e(MumbaiIndians)   = (2, 5)
e(RCB)             = (5, 4)
r(playsFor)        = (1, 3)

Check these are consistent with two well-established facts. e(Sachin) + r = (1+1, 2+3) = (2, 5) = e(MumbaiIndians) — distance zero, a perfect fit for playsFor(Sachin, MumbaiIndians). e(Virat) + r = (4+1, 1+3) = (5, 4) = e(RCB) — perfect fit for playsFor(Virat, RCB). Both known triples score with zero error, exactly what a well-trained TransE model should produce.

Now use the model on a query it was never directly told the answer to: playsFor(Rohit, ?), with e(Rohit) = (1.5, 2.5) and three candidate tails — the two known teams plus a distractor, e(CSK) = (6, 6).

def transe_score(h, r, t):
    # returns negative L2 distance; higher score = more plausible
    diff = [h[i] + r[i] - t[i] for i in range(len(h))]
    dist = sum(d * d for d in diff) ** 0.5
    return -dist

h = (1.5, 2.5)        # Rohit
r = (1.0, 3.0)         # playsFor
candidates = {
    "MI":  (2.0, 5.0),
    "RCB": (5.0, 4.0),
    "CSK": (6.0, 6.0),
}

for team, t in candidates.items():
    print(team, round(transe_score(h, r, t), 3))

Trace it by hand before trusting the printout. h + r = (1.5+1, 2.5+3) = (2.5, 5.5). Against MI: diff = (0.5, 0.5), distance = √0.5 ≈ 0.707. Against RCB: diff = (-2.5, 1.5), distance = √8.5 ≈ 2.915. Against CSK: diff = (-3.5, -0.5), distance = √12.5 ≈ 3.536. So the loop prints, in insertion order:

MI -0.707
RCB -2.915
CSK -3.536

Ranked by score (highest first, least negative wins): MI, then RCB, then CSK. The model predicts playsFor(Rohit, MumbaiIndians) as the top-1 completion — geometrically, because the translated point e(Rohit) + r lands closest to MI's vector, not because anything was looked up.

The misconception: a translation vector cannot serve two masters

A common misconception, once a student sees the diagram above, is to assume TransE can represent any relation as long as enough training data is available — that the translation trick is a general-purpose mechanism limited only by data volume. It is not. TransE has a specific, provable geometric failure mode on relations that are one-to-many, and playsFor is exactly such a relation: a single IPL team fields more than a dozen players, so many different heads must map to the same tail under one relation vector.

Suppose the model is trained to convergence and perfectly fits two true triples that share a tail: playsFor(Sachin, MI) and playsFor(Pollard, MI), where Pollard is a different player who also played for Mumbai Indians. Perfect fit means both translations land exactly on MI's vector:

e(Sachin) + r = e(MI) and e(Pollard) + r = e(MI)

Subtract the two equations and the relation vector cancels out entirely: e(Sachin) − e(Pollard) = 0, which forces e(Sachin) = e(Pollard). Using the numbers from the worked example, e(Pollard) = e(MI) − r = (2,5) − (1,3) = (1,2) — identical, digit for digit, to Sachin's embedding. TransE has no mechanism to keep two genuinely different players apart once they share a team, because a fixed translation vector can only ever produce one output point per input point per relation. Push this further and every player on the same IPL squad collapses toward the same neighbourhood in embedding space, destroying exactly the information — which specific player is this — that the embedding was supposed to preserve. The same failure hits symmetric relations from the other direction: if spouseOf(A,B) and spouseOf(B,A) must both score well, you need e(A)+r≈e(B) and e(B)+r≈e(A) simultaneously, which forces r≈0 and then e(A)≈e(B) — again collapsing two distinct entities together. This is not a training bug to fix with more epochs; it is baked into the algebra of translation. Correcting the misconception matters because it explains, rather than merely asserts, why the field moved past TransE — TransH gives each relation its own hyperplane so the same base vectors can be translated differently depending on which hyperplane they're projected onto first, and bilinear models abandon translation altogether.

Beyond translation: DistMult and ComplEx

DistMult replaces translation with a bilinear form: score(h,r,t) = Σᵢ hᵢ · rᵢ · tᵢ, an elementwise product of head, relation, and tail vectors, summed. This handles one-to-many relations far better than TransE, because there is no forced collapse — but it introduces its own blind spot. Because ordinary multiplication commutes, Σᵢ hᵢrᵢtᵢ = Σᵢ tᵢrᵢhᵢ exactly, for every relation, always. DistMult therefore scores parentOf(A,B) identically to parentOf(B,A) — it is structurally incapable of telling an antisymmetric relation apart from its reverse, which is a serious problem for a knowledge graph full of directional facts. ComplEx (Trouillon et al., 2016) fixes exactly this by moving the embeddings into complex vector space and defining score(h,r,t) = Re(Σᵢ hᵢ · rᵢ · conj(tᵢ)), taking the real part of a product that conjugates only the tail. Because conjugation is not symmetric between the head and tail slots, swapping h and t now genuinely changes the score, which restores the ability to model antisymmetric relations while keeping the collapse-resistant bilinear structure that made DistMult an improvement over TransE in the first place. Modern production systems increasingly use graph neural network encoders (relation-aware message passing, such as R-GCN) that compute entity representations from local graph structure before applying one of these same scoring functions on top — the scoring-function question this section answers stays relevant even inside those larger architectures.

Training without negatives: corruption and margin loss

Recall the open-world problem from the start of this chapter: a knowledge graph contains essentially no confirmed-false triples to train against. TransE-style models solve this by manufacturing negatives through corruption — take a true triple (h, r, t) and replace either the head or the tail with a randomly chosen entity to produce (h', r, t) or (h, r, t'), on the (usually safe, occasionally wrong) assumption that a random substitution is probably not also a true fact. Training then uses a margin ranking loss:

# illustrative pseudocode, not runnable as-is —
# corrupt is an assumed helper, not shown
loss = 0
for (h, r, t) in true_triples:
    h_neg, t_neg = corrupt(h, r, t)          # flip one side at random
    d_pos = distance(h, r, t)
    d_neg = distance(h_neg, r, t_neg)
    loss += max(0, margin + d_pos - d_neg)

The max(0, ...) means the model pays a penalty only when the true triple is not already at least margin units closer than the corrupted one — once that separation is achieved, that example stops contributing gradient, and training focuses effort on the pairs it is still getting wrong. This single design choice — synthesizing negatives instead of collecting them — is why link prediction sits closer to self-supervised representation learning than to ordinary supervised classification.

Evaluating link prediction: Mean Reciprocal Rank and Hits@k

A trained model is tested by holding out real triples, deleting the tail, asking the model to rank every entity in the graph as a candidate completion, and recording where the true answer landed in that ranked list. Two entities in the standard reporting: Mean Reciprocal Rank (MRR), the average of 1/rank across all test triples, and Hits@k, the fraction of test triples where the correct answer appeared within the top k positions. Suppose three held-out test triples come back at ranks 1, 3, and 4. MRR = (1/1 + 1/3 + 1/4) / 3 = (1 + 0.333 + 0.25) / 3 = 1.583 / 3 ≈ 0.528. Hits@3 counts how many of those three ranks are ≤ 3: ranks 1 and 3 qualify, rank 4 does not, giving 2/3 ≈ 0.667. One subtlety trips up nearly every first attempt at this metric: a candidate list for (h, r, ?) can legitimately contain other true triples besides the one being tested — a player who has genuinely played for more than one franchise over a career, for instance. If those other true completions rank above the specific one being scored, the raw rank looks artificially bad even though the model made no error. Standard practice, following the original TransE evaluation protocol, is to report the filtered setting: strip every other known-true tail out of the candidate list before computing the rank of the held-out triple, so the model is only penalised for outranking a genuine false candidate, never for correctly scoring a different true fact highly.

Where this runs in production

E-commerce catalogues use exactly this mechanism to predict compatibleWith edges between products — flagging that a specific phone case fits a specific phone model even when no one has manually tagged that pairing, which is what powers "works with your device" recommendations on a listing page with an incomplete accessory graph. Search engines run link prediction over their knowledge graphs to flag high-confidence candidate facts for editorial review rather than publishing them outright, precisely because a plausible-looking triple is a ranked guess, not a verified one — the same distinction this chapter has been drawing between geometric plausibility and ground truth. Biomedical knowledge graphs score candidate treats and interacts edges between drugs, proteins, and diseases using this identical scoring-function machinery to shortlist repurposing candidates for lab verification, a use case covered in depth in this site's drug discovery chapter — the modelling technique underneath is the one built here.

Active recall

Attempt each question before reading its answer.

1. Two true triples (A, worksAt, X) and (C, worksAt, X) are both perfectly fit by a trained TransE model. Prove algebraically what this forces about e(A) and e(C).
2. Given e(P) = (0,0), r = (3,1), and three candidate tails T1=(3,1), T2=(2,2), T3=(4,0), compute the L2 distance from e(P)+r to each and rank them.
3. Why can a knowledge graph completion model never be trained on database-style true/false labelled examples the way a spam classifier can?
4. A test query's correct answer sits at raw rank 4, but two of the three triples ranked above it are also independently true facts. What is the filtered rank, and why does filtered MRR give a fairer picture of the model than raw MRR here?
5. Explain, using the algebraic symmetry of the bilinear form, why DistMult cannot distinguish parentOf(A,B) from parentOf(B,A), and state in one sentence what ComplEx changes to fix this.
6. You are training a link predictor for compatibleWith(phoneCase, ?) on an e-commerce product graph using uniform-random corruption for negatives. Why might this produce mostly "easy" negatives, and what change to the sampling would force the model to learn finer distinctions?

Answers.

1. Perfect fit means e(A) + r = e(X) and e(C) + r = e(X). Subtracting the two equations cancels r and e(X), leaving e(A) − e(C) = 0, i.e. e(A) = e(C). Any two entities that share a one-to-many relation's tail are forced to identical embeddings — the collapse problem worked through numerically earlier in the chapter.

2. e(P)+r = (3,1). Distance to T1: √((3−3)²+(1−1)²) = 0. Distance to T2: √((3−2)²+(1−2)²) = √2 ≈ 1.414. Distance to T3: √((3−4)²+(1−0)²) = √2 ≈ 1.414. Ranking: T1 first (exact match, distance 0), then T2 and T3 tied for second at ≈1.414 — a genuine tie the model cannot break with this scoring function alone.

3. Knowledge graphs operate under the open-world assumption: an absent triple means "unknown," not "false." A supervised classifier needs both positive and negative labelled examples, but a raw knowledge graph provides only positives — there is no reliable pool of confirmed-false triples to draw negative labels from, which is exactly why corruption-based negative sampling exists as a workaround rather than a convenience.

4. The two higher-ranked triples above it are themselves true, so under the filtered protocol they are removed from the candidate list before rank is computed, dropping the target's filtered rank to 2. Filtered MRR credits 1/2 = 0.5 instead of raw MRR's 1/4 = 0.25. Filtering is fairer because it stops penalising the model for correctly recognising other genuine facts as highly plausible — the raw score conflates "wrong" with "also right about something else."

5. DistMult's score is Σᵢ hᵢrᵢtᵢ, and because scalar multiplication commutes, Σᵢ hᵢrᵢtᵢ = Σᵢ tᵢrᵢhᵢ identically for any vectors — swapping the head and tail slots never changes the value, so parentOf(A,B) and parentOf(B,A) always receive the same score no matter how training proceeds. ComplEx fixes this by embedding in complex space and conjugating only the tail vector before multiplying, which breaks the head/tail symmetry.

6. Uniform-random corruption picks a replacement tail from the entire product catalogue, so most corrupted triples end up wildly unrelated to a phone case — groceries, furniture — which the model can reject on category alone without ever learning to distinguish an iPhone 14 case from an iPhone 15 case. Restricting corruption to type-constrained or hard negatives — swapping in only other phone accessories, or other cases within the same brand — forces the model to actually learn the fine-grained compatibility boundary instead of a coarse category filter.

Think About It

Think about this: How would you explain knowledge graph completion: link prediction to a friend who has never seen a computer? What real-world analogy would you use? Imagine you had to build a system using these concepts — what would be your first step? Try this: before moving on, write down three things you learned and one question you still have.

Key Takeaways — Summary and Recap

Let us recap what we covered: the core ideas behind knowledge graph completion: link prediction, how they connect to real-world applications, and why they matter for your journey in computer science. Remember these key points as you move forward. For competitive exam preparation (CBSE, JEE, BITSAT), focus on understanding the WHY behind each concept, not just the WHAT.