Knowledge Graph Embeddings: TransE and How Entities Become Vectors

TransE is a two-line model: give every entity a vector, give every relation a vector, and require that the head plus the relation lands near the tail. It is old, it is beaten on every benchmark, and it is still the right thing to learn first because its failure modes are derivable on paper and every successor is defined by which one it fixes.

The data: triples, not tables

A knowledge graph is a set of statements of the form (head, relation, tail): (Paris, capital_of, France), (Curie, born_in, Warsaw), (Warsaw, located_in, Poland). Entities are nodes, relations are typed edges, and the same pair of entities can be joined by several relations at once. This is a heterogeneous, multi-relational graph, and the plain node embeddings of node2vec and DeepWalk have nowhere to put the edge type — they would treat capital_of and born_in as the same kind of adjacency.

The task these embeddings are trained for is completion: given (Paris, capital_of, ?), rank every entity in the graph by how plausible it is as the tail. Real knowledge graphs are enormously incomplete, so this is not an academic exercise.

The scoring function, worked

TransE (Bordes et al., NeurIPS 2013) embeds entities and relations in the same k-dimensional space and scores a triple by how far the translated head is from the tail:

d(h + r, t) = || h + r − t ||        with either the L1 or the L2 norm

lower is better — this is a dissimilarity, not a similarity

Take k = 2 so the arithmetic is visible, and suppose training has produced these vectors:

h = Paris        = (2.0, 1.0)
r = capital_of   = (1.0, 3.0)
h + r            = (3.0, 4.0)

t = France       = (3.2, 3.9)   → L1 = |3.0−3.2| + |4.0−3.9| = 0.2 + 0.1 = 0.3
t = Spain        = (3.0, 3.2)   → L1 = |3.0−3.0| + |4.0−3.2| = 0.0 + 0.8 = 0.8
t = Germany      = (0.5, 4.5)   → L1 = |3.0−0.5| + |4.0−4.5| = 2.5 + 0.5 = 3.0

France scores 0.3, Spain 0.8, Germany 3.0, so the ranked completion of (Paris, capital_of, ?) is France, Spain, Germany. Notice what the relation vector is doing: (1.0, 3.0) is the same offset for every capital-of triple in the graph, so the model is asserting that all capital cities sit in the same direction and at the same distance from their countries. That single geometric commitment is where all the power and all the failures come from.

Ranking loss and the norm constraint

Training uses a margin-based ranking loss over corrupted triples. For each true triple, replace either the head or the tail with a random entity to make a negative, and require the true triple to score lower than the corrupted one by at least a margin γ:

L = Σ  Σ  [ gamma + d(h + r, t) − d(h' + r, t') ]₊

[x]₊ means max(0, x) — no loss once the margin is satisfied

Apply it to the numbers above with γ = 1:

corrupt with Germany (d = 3.0)
  loss = [ 1 + 0.3 − 3.0 ]₊ = [ −1.7 ]₊ = 0
  → margin already satisfied, zero gradient, nothing to learn

corrupt with Spain (d = 0.8)
  loss = [ 1 + 0.3 − 0.8 ]₊ = [ 0.5 ]₊ = 0.5
  → gradient pulls France toward (3.0, 4.0) and pushes Spain away

That is the entire training signal, and it explains why negative sampling quality dominates results. Draw negatives uniformly and almost all of them look like Germany: far away, already satisfying the margin, contributing exactly zero gradient. The model spends most of its compute on triples it has already learned. Every later system in this family spends effort on producing hard negatives for this reason.

There is one more piece and it is not decoration. TransE constrains every entity embedding to have L2 norm 1, re-normalising after each update; relation embeddings are not constrained. Without it the loss has a trivial escape: inflate all the entity norms and the distances to corrupted triples grow without bound, satisfying every margin while learning nothing. The constraint removes the scale degree of freedom so the only way to reduce the loss is to arrange the directions correctly. Embeddings are initialised uniformly in a small range around zero and normalised, and the paper reports results at k = 20 and k = 50 dimensions — small numbers, because the model has very little to express per entity.

Three relation types it provably cannot model

These are not empirical weaknesses; they follow from the equation in two lines each.

Symmetric relations. Suppose (a, r, b) and (b, r, a) are both true and both perfectly fitted. Then a + r = b and b + r = a. Add the two equations: a + b + 2r = a + b, so r = 0. Substituting back gives a = b. A symmetric relation forces its relation vector to zero and then forces every pair of entities it connects to occupy the same point. Married_to, sibling_of and is_adjacent_to are all in this class.

One-to-many and many-to-one. Suppose (h, r, t1) and (h, r, t2) are both true. Both want t = h + r, so t1 = t2. A relation like country_has_city forces every city of a country into the same vector, which destroys those entities for every other relation they participate in. This is the limitation the paper itself flags, and it is why TransE scores far worse on one-to-many relations than on one-to-one ones.

Reflexive relations. If (a, r, a) holds, then a + r = a, so r = 0 again, and by the symmetric argument every pair the relation touches collapses. This analysis is set out in Knowledge Graph Embedding by Translating on Hyperplanes (Wang et al., AAAI 2014), which introduces TransH precisely to escape it: project the entities onto a relation-specific hyperplane before translating, so a single entity can occupy different positions for different relations.

The lineage after that is a sequence of answers to the same question. TransR gives each relation its own projection matrix. DistMult uses a bilinear product but is inherently symmetric, so it has the opposite problem. ComplEx moves to complex-valued embeddings so that the Hermitian product is asymmetric. RotatE (Sun et al., ICLR 2019) makes each relation a rotation in complex space, which represents symmetry (rotation by π), inversion and composition simultaneously — and its paper tabulates exactly which patterns each earlier model can and cannot express.

Evaluating, and what replaced it

Completion is evaluated by ranking. For a test triple, corrupt the tail with every entity in the graph, score all of them, and record where the true tail landed. Report mean rank, mean reciprocal rank, and Hits@k — the fraction of test triples whose true answer appeared in the top k.

The one detail that must not be skipped is filtered ranking. Some corrupted triples are true statements that happen to be in your training set; scoring them above the test triple is correct behaviour being punished as an error. Filtered evaluation removes every corruption that appears anywhere in the dataset before ranking, and the difference between raw and filtered numbers is large enough that comparing across the two is meaningless.