Simple Algorithm
Artificial Intelligence · Deep Layer · 26 min

Knowledge Graph Embeddings

TransE, link prediction and relational learning.

Large knowledge graphs are full of holes: most people in Freebase had no recorded place of birth. Embedding models fill the holes with geometry. Entities become vectors, relations become translations or rotations, and a missing edge is whichever candidate fits best. Which relations a geometry can express, and how to tell whether it works, are precise questions with precise answers.

What you’ll learn

  • Define link prediction and its filtered ranking metrics (MR, MRR, Hits@k), and recognize leakage and tie-handling pitfalls in benchmarks.
  • Derive the TransE, DistMult, ComplEx and RotatE scores, and prove which relation patterns (symmetry, antisymmetry, inversion, composition, 1-to-N) each can represent.
  • State full-expressiveness results, and read bilinear models as tensor factorizations.
  • Weigh training choices (losses, negatives, regularizers) against score functions, using the evidence on what drives progress.

Link prediction, precisely

Ties matter. If many candidates share the true answer's score, the rank must count them, or average over them; Sun et al. (2020) showed that some reported gains came from protocols that put the correct answer first among tied candidates. MRR is dominated by the top of the ranking and MR by the worst queries, which is why MRR and Hits@k became the standard.

Predict before you look

Four test queries give the true answers filtered ranks 1, 3, 2 and 20. What is the MRR?

Show the answer

0.47

14(1+13+12+120)=14⋅1.883≈0.47\frac14\big(1+\frac13+\frac12+\frac1{20}\big)=\frac14\cdot1.883\approx0.47. Hits@3 is 3/43/4 and the mean rank is 6.56.5. Had the last rank been 4 instead of 20, MRR would rise only to about 0.520.52, while MR would fall from 6.56.5 to 2.52.5: one bad query dominates MR.

Benchmarks have pitfalls of their own. In FB15k and WN18, the datasets of the TransE paper, many test triples had their inverse in the training set, such as a test triple (h, hypernym, t)(h,\ \text{hypernym},\ t) next to a training triple (t, hyponym, h)(t,\ \text{hyponym},\ h). Toutanova & Chen (2015) built FB15k-237 by removing near-inverse relations, and Dettmers et al. (2018) built WN18RR after showing that a simple rule-based model that exploits inverses scores at the state of the art on the original datasets.

Translations, bilinear forms and rotations

ModelScore f(h,r,t)f(h,r,t)Relation parametersPatterns it can represent
TransE (Bordes et al., 2013)−∥h+r−t∥-\lVert\mathbf h+\mathbf r-\mathbf t\rVertr∈Rd\mathbf r\in\R^dantisymmetry, inversion, composition
DistMult (Yang et al., 2015)∑ihiriti\sum_i h_ir_it_ir∈Rd\mathbf r\in\R^dsymmetry only
RESCAL (Nickel et al., 2011)h⊤Wr t\mathbf h^\top W_r\,\mathbf tWr∈Rd×dW_r\in\R^{d\times d}symmetry, antisymmetry, inversion, at d2d^2 parameters per relation
ComplEx (Trouillon et al., 2016)Re⁡∑ihiriti‾\operatorname{Re}\sum_i h_ir_i\overline{t_i}r∈Cd\mathbf r\in\C^dsymmetry, antisymmetry, inversion
RotatE (Sun et al., 2019)−∥h∘r−t∥-\lVert\mathbf h\circ\mathbf r-\mathbf t\rVert with ∣ri∣=1\lvert r_i\rvert=1phases θi\theta_isymmetry, antisymmetry, inversion, composition
Patterns as analyzed in the RotatE paper; ∘\circ is the elementwise product, and ComplEx and RotatE embed entities in Cd\C^d. In their exact forms, h+r=t\mathbf h+\mathbf r=\mathbf t and h∘r=t\mathbf h\circ\mathbf r=\mathbf t, translation and rotation send each head to a single tail, so 1-to-N relations need approximation; bilinear scores have no such problem.
DerivationProofs, and the cure in the complex plane
  1. ∥2r∥=∥(a+r−b)+(b+r−a)∥<2τ ⟹ ∥a+r−a∥=∥r∥<τ\lVert2\mathbf r\rVert=\lVert(\mathbf a+\mathbf r-\mathbf b)+(\mathbf b+\mathbf r-\mathbf a)\rVert<2\tau\ \Longrightarrow\ \lVert\mathbf a+\mathbf r-\mathbf a\rVert=\lVert\mathbf r\rVert<\tau

    (i) Add the two residual vectors and use the triangle inequality:

  2. a+r=b1,  a+r=b2 ⟹ b1=b2\mathbf a+\mathbf r=\mathbf b_1,\ \ \mathbf a+\mathbf r=\mathbf b_2\ \Longrightarrow\ \mathbf b_1=\mathbf b_2

    (ii) Subtract the two equations:

  3. f(h,r,t)=∑ihiriti=f(t,r,h)f(h,r,t)=\sum_ih_ir_it_i=f(t,r,h)

    DistMult errs the other way. Its score is symmetric in hh and tt, so parent of gets the same score in both directions:

  4. f(t,r,h)=Re⁡∑itirihi‾=Re⁡∑ihiri‾ ti‾=f(h,rˉ,t)f(t,r,h)=\operatorname{Re}\sum_it_ir_i\overline{h_i}=\operatorname{Re}\sum_ih_i\overline{r_i}\,\overline{t_i}=f(h,\bar r,t)

    ComplEx breaks the symmetry with a conjugate. Since Re⁡z=Re⁡zˉ\operatorname{Re}z=\operatorname{Re}\bar z, swapping head and tail conjugates the relation:

  5. symmetric  ⟺  θi∈{0,π},r2=r1−1  ⟺  θ(2)=−θ(1),r3=r1∘r2  ⟺  θ(3)=θ(1)+θ(2)\text{symmetric}\iff\theta_i\in\{0,\pi\},\qquad r_2=r_1^{-1}\iff\theta^{(2)}=-\theta^{(1)},\qquad r_3=r_1\circ r_2\iff\theta^{(3)}=\theta^{(1)}+\theta^{(2)}

    So a real r\mathbf r gives a symmetric relation, and a purely imaginary one (rˉ=−r\bar{\mathbf r}=-\mathbf r) an antisymmetric one, f(t,r,h)=−f(h,r,t)f(t,r,h)=-f(h,r,t). RotatE goes further: with ri=eiθir_i=e^{i\theta_i}, relations act as rotations, which invert by negating angles and compose by adding them:

Check your understanding

Which model gives (h,r,t)(h,r,t) and (t,r,h)(t,r,h) the same score for every relation, and so cannot tell parent of from child of?

  1. TransE
  2. RotatE
  3. DistMult
  4. ComplEx
Show the answer

C. DistMult

DistMult's trilinear product ∑ihiriti\sum_ih_ir_it_i is unchanged when hh and tt swap. ComplEx fixes exactly this by conjugating the tail embedding.

Expressiveness and the tensor view

A knowledge graph is a binary 3-way tensor X∈{0,1}∣E∣×∣E∣×∣R∣\mathcal X\in\{0,1\}^{|\mathcal E|\times|\mathcal E|\times|\mathcal R|} with Xh,t,r=1\mathcal X_{h,t,r}=1 if and only if (h,r,t)∈G(h,r,t)\in G. Bilinear models factorize its slices. RESCAL writes X:,:,r≈EWrE⊤\mathcal X_{:,:,r}\approx EW_rE^\top, with one entity matrix EE shared by all relations. DistMult restricts WrW_r to a diagonal, which forces every slice to be symmetric. ComplEx uses a complex diagonal, X:,:,r≈Re⁡(Ediag⁡(r)Eˉ⊤)\mathcal X_{:,:,r}\approx\operatorname{Re}\big(E\operatorname{diag}(\mathbf r)\bar E^\top\big), which can fit asymmetric slices. The canonical polyadic (CP) decomposition gives each entity separate head and tail vectors.

Full expressiveness is a floor, not a guarantee: a model that can memorize any graph may still predict missing triples badly. What generalizes is an inductive bias that matches the data's regularities. Composition in TransE or RotatE, r3≈r1+r2\mathbf r_3\approx\mathbf r_1+\mathbf r_2 or r3≈r1∘r2\mathbf r_3\approx\mathbf r_1\circ\mathbf r_2, mirrors the Horn rule r1(x,y)∧r2(y,z)⇒r3(x,z)r_1(x,y)\wedge r_2(y,z)\Rightarrow r_3(x,z), which rule miners such as AMIE (Galárraga et al., 2013) learn explicitly, with confidence scores.

Path-based graph neural networks such as NBFNet (Zhu et al., 2021) take a third route. They compute a representation of the pair (h,t)(h,t) from the paths between them, so, unlike embedding tables, they can score entities never seen during training.

Training, evaluation and the frontier

Score functions get the headlines, but training decides the results. The main choices:

  • Loss. TransE's margin ranking loss; a logistic loss with sampled negatives; or 1-N scoring, a softmax cross-entropy over all entities as candidate tails, usually with a reciprocal relation r−1r^{-1} added for each relation so that head prediction becomes tail prediction (Dettmers et al., 2018; Lacroix et al., 2018).
  • Negatives. Uniformly corrupted heads or tails are often true triples in disguise when a relation is 1-to-N. Bernoulli corruption (Wang et al., 2014) corrupts the side less likely to produce one, and self-adversarial sampling (from the RotatE paper) weights hard negatives more.
  • Regularization. Norm constraints (TransE normalizes entity vectors), L2L_2 penalties, or the tensor nuclear 3-norm, N3, which made plain CP and ComplEx very strong (Lacroix et al., 2018).
  • Cost. TransE, DistMult, ComplEx and RotatE have O((∣E∣+∣R∣)d)\order{(|\mathcal E|+|\mathcal R|)d} parameters and RESCAL O(∣E∣d+∣R∣d2)\order{|\mathcal E|d+|\mathcal R|d^2}. With 1-N scoring, each query costs one matrix–vector product, O(∣E∣d)\order{|\mathcal E|d}.

Key takeaways

  • Link prediction ranks every candidate entity: report filtered MRR and Hits@k, count ties honestly, and use leakage-free benchmarks such as FB15k-237 and WN18RR.
  • TransE (h+r≈t\mathbf h+\mathbf r\approx\mathbf t) cannot represent symmetric-irreflexive or exact 1-to-N relations; DistMult makes every relation symmetric; ComplEx's conjugate adds antisymmetry; RotatE's rotations capture symmetry, antisymmetry, inversion and composition.
  • Bilinear models are tensor factorizations. ComplEx and SimplE are fully expressive with dimension at most ∣E∣⋅∣R∣|\mathcal E|\cdot|\mathcal R|; TransE and DistMult are not. Expressiveness is necessary for generalization, not sufficient.
  • Training choices (losses, negatives, regularizers, reciprocal relations) can matter as much as the score function.
  • The frontier: inductive and transferable models, complex logical queries, honest evaluation, and knowledge graphs as grounding for language models.

Check yourself

In the interactive lesson these are scored with your confidence, and what you miss comes back for review.

Question 1

For a query (h,r,?)(h,r,?) the true tail is ranked 4th among all entities, but two of the three entities above it are themselves known true tails of (h,r,?)(h,r,?). What are its filtered rank and reciprocal rank?

  1. Rank 4, reciprocal rank 0.25
  2. Rank 1, reciprocal rank 1
  3. Rank 3, reciprocal rank 0.33
  4. Rank 2, reciprocal rank 0.5
Show the answer

D. Rank 2, reciprocal rank 0.5

Filtering removes the two known true tails from the candidates, which leaves one wrong entity above the answer: rank 1+1=21+1=2, reciprocal rank 0.50.5.

Question 2

Which relation pattern can RotatE represent but ComplEx cannot, in the standard analysis of these models?

  1. Symmetry
  2. Composition
  3. Antisymmetry
  4. Inversion
Show the answer

B. Composition

Rotations compose by adding phases, so r3=r1∘r2r_3=r_1\circ r_2 represents the composition of r1r_1 and r2r_2. ComplEx's diagonal bilinear form has no such closure property; both models handle symmetry, antisymmetry and inversion.

Question 3

Why can't TransE, with any threshold τ\tau, represent a symmetric and irreflexive relation such as spouse of?

  1. Because the true triples (a,r,b)(a,r,b) and (b,r,a)(b,r,a) force ∥r∥<τ\lVert\mathbf r\rVert<\tau, which makes (a,r,a)(a,r,a) score as true
  2. Because TransE normalizes entity vectors to unit length
  3. Because the L1L_1 norm is not differentiable
  4. Because symmetric relations need matrices, and TransE uses vectors
Show the answer

A. Because the true triples (a,r,b)(a,r,b) and (b,r,a)(b,r,a) force ∥r∥<τ\lVert\mathbf r\rVert<\tau, which makes (a,r,a)(a,r,a) score as true

By the triangle inequality, ∥2r∥≤∥a+r−b∥+∥b+r−a∥<2τ\lVert2\mathbf r\rVert\le\lVert\mathbf a+\mathbf r-\mathbf b\rVert+\lVert\mathbf b+\mathbf r-\mathbf a\rVert<2\tau, so ∥a+r−a∥=∥r∥<τ\lVert\mathbf a+\mathbf r-\mathbf a\rVert=\lVert\mathbf r\rVert<\tau: everyone would be their own spouse.

Question 4

What did the large re-evaluation of knowledge-graph embedding training by Ruffinelli, Broscheit & Gemulla (2020) find?

  1. Only convolutional models benefit from hyperparameter search
  2. Filtered metrics overestimate accuracy by an order of magnitude
  3. Carefully tuned older models such as RESCAL and ComplEx were competitive with much newer ones
  4. TransE becomes fully expressive when trained long enough
Show the answer

C. Carefully tuned older models such as RESCAL and ComplEx were competitive with much newer ones

With one uniform, extensive search over losses, negatives, regularizers and optimizers, much of the apparent progress between 2013 and 2019 disappeared. Training choices matter as much as score functions.

Further reading

  • A. Bordes, N. Usunier, A. García-Durán, J. Weston & O. Yakhnenko, "Translating embeddings for modeling multi-relational data," Advances in Neural Information Processing Systems (2013).
  • T. Trouillon, J. Welbl, S. Riedel, É. Gaussier & G. Bouchard, "Complex embeddings for simple link prediction," ICML (2016).
  • Z. Sun, Z.-H. Deng, J.-Y. Nie & J. Tang, "RotatE: Knowledge graph embedding by relational rotation in complex space," ICLR (2019).
  • D. Ruffinelli, S. Broscheit & R. Gemulla, "You CAN teach an old dog new tricks! On training knowledge graph embeddings," ICLR (2020).
  • Q. Wang, Z. Mao, B. Wang & L. Guo, "Knowledge graph embedding: a survey of approaches and applications," IEEE Transactions on Knowledge and Data Engineering 29(12) (2017).