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.
Four test queries give the true answers filtered ranks 1, 3, 2 and 20. What is the MRR?
Show the answer
0.47
. Hits@3 is and the mean rank is . Had the last rank been 4 instead of 20, MRR would rise only to about , while MR would fall from to : 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 next to a training triple . 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
| Model | Score | Relation parameters | Patterns it can represent |
|---|---|---|---|
| TransE (Bordes et al., 2013) | antisymmetry, inversion, composition | ||
| DistMult (Yang et al., 2015) | symmetry only | ||
| RESCAL (Nickel et al., 2011) | symmetry, antisymmetry, inversion, at parameters per relation | ||
| ComplEx (Trouillon et al., 2016) | symmetry, antisymmetry, inversion | ||
| RotatE (Sun et al., 2019) | with | phases | symmetry, antisymmetry, inversion, composition |
(i) Add the two residual vectors and use the triangle inequality:
(ii) Subtract the two equations:
DistMult errs the other way. Its score is symmetric in and , so parent of gets the same score in both directions:
ComplEx breaks the symmetry with a conjugate. Since , swapping head and tail conjugates the relation:
So a real gives a symmetric relation, and a purely imaginary one () an antisymmetric one, . RotatE goes further: with , relations act as rotations, which invert by negating angles and compose by adding them:
Which model gives and the same score for every relation, and so cannot tell parent of from child of?
- TransE
- RotatE
- DistMult
- ComplEx
Show the answer
C. DistMult
DistMult's trilinear product is unchanged when and swap. ComplEx fixes exactly this by conjugating the tail embedding.
Expressiveness and the tensor view
A knowledge graph is a binary 3-way tensor with if and only if . Bilinear models factorize its slices. RESCAL writes , with one entity matrix shared by all relations. DistMult restricts to a diagonal, which forces every slice to be symmetric. ComplEx uses a complex diagonal, , 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, or , mirrors the Horn rule , 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 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 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), 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 parameters and RESCAL . With 1-N scoring, each query costs one matrix–vector product, .
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 () 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 ; 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.
For a query the true tail is ranked 4th among all entities, but two of the three entities above it are themselves known true tails of . What are its filtered rank and reciprocal rank?
- Rank 4, reciprocal rank 0.25
- Rank 1, reciprocal rank 1
- Rank 3, reciprocal rank 0.33
- 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 , reciprocal rank .
Which relation pattern can RotatE represent but ComplEx cannot, in the standard analysis of these models?
- Symmetry
- Composition
- Antisymmetry
- Inversion
Show the answer
B. Composition
Rotations compose by adding phases, so represents the composition of and . ComplEx's diagonal bilinear form has no such closure property; both models handle symmetry, antisymmetry and inversion.
Why can't TransE, with any threshold , represent a symmetric and irreflexive relation such as spouse of?
- Because the true triples and force , which makes score as true
- Because TransE normalizes entity vectors to unit length
- Because the norm is not differentiable
- Because symmetric relations need matrices, and TransE uses vectors
Show the answer
A. Because the true triples and force , which makes score as true
By the triangle inequality, , so : everyone would be their own spouse.
What did the large re-evaluation of knowledge-graph embedding training by Ruffinelli, Broscheit & Gemulla (2020) find?
- Only convolutional models benefit from hyperparameter search
- Filtered metrics overestimate accuracy by an order of magnitude
- Carefully tuned older models such as RESCAL and ComplEx were competitive with much newer ones
- 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).