Definition
Knowledge graph embedding assigns a vector to every entity and every relation of a knowledge graph, a set of triples such as (Paris, capital_of, France), together with a score that should be high for true triples. The main models are TransE (Bordes, Usunier, García-Durán, Weston and Yakhnenko, NeurIPS 2013), DistMult (Yang, Yih, He, Gao and Deng, ICLR 2015), ComplEx (Trouillon, Welbl, Riedel, Gaussier and Bouchard, ICML 2016) and RotatE (Sun, Deng, Nie and Tang, ICLR 2019).
The task is knowledge-graph completion. Freebase and Wikidata hold millions of facts but miss many more: a person's nationality or a film's director is often absent. Given a query or , the model ranks every entity as a candidate answer. This is Link prediction on a multi-relational graph: an edge type matters, and the same pair can be linked by several relations.
Two things make it hard. The graph is incomplete, so a missing triple is not necessarily false. Relations also behave differently: "borders" is symmetric, "parent_of" is antisymmetric, "has_part" is the inverse of "part_of", and "born_in" followed by "city_of" gives "nationality". Before learned embeddings, systems mined such rules explicitly. RESCAL (Nickel, Tresp and Kriegel, ICML 2011) factorised the adjacency tensor with a full matrix per relation, .
Score functions
- head, relation and tail embeddings; real in TransE and DistMult, complex () in ComplEx and RotatE
- complex conjugate; it makes the ComplEx score change when and swap
- element-wise product; with each coordinate of is rotated by
TransE models a relation as a translation: , the same geometry as the Word2Vec analogy . It keeps entity vectors at unit norm. A symmetric relation needs and , so and . A one-to-many relation forces all tails onto one point. TransH (Wang et al., AAAI 2014) and TransR (Lin et al., AAAI 2015) project entities into a relation-specific space to ease this.
DistMult is RESCAL with a diagonal . It has parameters per relation instead of , but its score is symmetric in and , so it predicts (France, capital_of, Paris) as readily as the true triple. ComplEx moves to complex vectors and conjugates the tail. A real gives a symmetric relation and an imaginary an antisymmetric one. RotatE constrains every to the unit circle. Symmetry is , an inverse relation is the conjugate rotation, and composition adds angles.
| Model | Symmetry | Antisymmetry | Inversion | Composition |
|---|---|---|---|---|
| TransE | ✗ | ✓ | ✓ | ✓ |
| DistMult | ✓ | ✗ | ✗ | ✗ |
| ComplEx | ✓ | ✓ | ✓ | ✗ |
| RotatE | ✓ | ✓ | ✓ | ✓ |
Training
Only positive triples are given. Negatives are made by corrupting the head or the tail of a true triple with a random entity. TransE minimises the margin ranking loss . RotatE uses a log-sigmoid loss with self-adversarial sampling, which weights each negative by how plausible the current model finds it:
- the distance ; the score is
- a fixed margin
- sampling temperature; the weights are treated as constants (no gradient)
Easy negatives such as (Paris, capital_of, Banana) give almost no gradient after a few epochs. Weighting by plausibility spends the update on hard ones like (Paris, capital_of, Belgium).
Evaluation: filtered ranks
- a tail query and a head query for every test triple
- position of the true entity among all entities, after removing every other entity that forms a known true triple (train, validation or test): the filtered setting of Bordes et al.
Without filtering, a model that ranks Lyon first for (?, located_in, France) is penalised even though Lyon is a correct answer. Filtered MRR is the headline number in most papers, usually with Hits@1, @3 and @10.
| Query | Prediction | Nearest entities (distance) | Raw rank | Filtered rank |
|---|---|---|---|---|
| (Paris, located_in, ?) → France | h + r = (1, 1) | France 0.141, Rome 0.860 | 1 | 1 |
| (Madrid, located_in, ?) → Spain | h + r = (1, −1) | Spain 0.224, Italy 0.894 | 1 | 1 |
| (Rome, located_in, ?) → Italy | h + r = (1.3, 0.5) | France 0.447, Italy 0.707 | 2 | 2 |
| (?, located_in, France) → Paris | t − r = (0.1, 0.9) | Lyon 0.100, Paris 0.141 | 2 | 1 (Lyon is known) |
| Metrics over the 4 queries | MRR 0.75, Hits@1 0.50 | MRR 0.875, Hits@1 0.75 |
Benchmarks and results
- FB15k-237
- Toutanova and Chen (2015): 14,541 entities, 237 relations; 272,115 / 17,535 / 20,466 train / valid / test triples
- WN18RR
- Dettmers et al. (AAAI 2018): 40,943 WordNet synsets, 11 relations; 86,835 / 3,034 / 3,134 triples
- Why the new splits
- in the older FB15k and WN18, many test triples are inverses of training triples, so a simple inverse-relation rule scored near the top; the -237 and RR versions remove such relations
- DistMult / ComplEx
- filtered MRR 0.241 / 0.247 on FB15k-237 and 0.43 / 0.44 on WN18RR, as reported by Dettmers et al. (2018)
- RotatE
- filtered MRR 0.338, Hits@10 0.533 on FB15k-237; MRR 0.476, Hits@10 0.571 on WN18RR (Sun et al., 2019, with self-adversarial sampling)
Connection to graph neural networks
All four models are shallow: the encoder is a lookup table, as in DeepWalk (see Graph representation learning). A GNN can replace it. The Relational GCN (Schlichtkrull et al., ESWC 2018) computes entity vectors by message passing with one weight matrix per relation and scores triples with a DistMult decoder; CompGCN (Vashishth et al., ICLR 2020) also embeds the relations and composes them with entities using TransE-, DistMult- or circular-correlation operators. Message passing lets an entity with few facts borrow evidence from its neighbours, at the cost of a far more expensive forward pass.
1import numpy as np23# score functions: higher = more plausible4transe = lambda h, r, t: -np.linalg.norm(h + r - t, axis=-1)5distmult = lambda h, r, t: np.sum(h * r * t, axis=-1)6complex_ = lambda h, r, t: np.real(np.sum(h * r * np.conj(t), axis=-1))7rotate = lambda h, theta, t: -np.linalg.norm(h * np.exp(1j * theta) - t, axis=-1)89rng = np.random.default_rng(0)10d = 5011h, t = rng.normal(size=(2, d))12hc, tc = rng.normal(size=(2, d)) + 1j * rng.normal(size=(2, d))13r = rng.normal(size=d)1415print(np.isclose(distmult(h, r, t), distmult(t, r, h))) # True: DistMult is always symmetric16print(np.isclose(complex_(hc, r + 0j, tc), complex_(tc, r + 0j, hc))) # True: real r -> symmetric17print(np.isclose(complex_(hc, 1j * r, tc), -complex_(tc, 1j * r, hc))) # True: imaginary r -> antisymmetric18th = np.full(d, np.pi) # rotation by pi is its own inverse19print(np.isclose(rotate(hc, th, -hc), 0), np.isclose(rotate(-hc, th, hc), 0)) # True True: h -> -h and back2021def filtered_rank(scores, truth, known):22 """Rank of the true entity among all candidates, ignoring other known true answers."""23 mask = np.ones_like(scores, dtype=bool)24 mask[list(known - {truth})] = False25 return 1 + int(np.sum(scores[mask] > scores[truth]))2627# the worked example: TransE in 2-D, r = located_in = (1, 0)28names = ["Paris", "Lyon", "Madrid", "Rome", "France", "Spain", "Italy"]29E = np.array([[0, 1], [0.1, 0.8], [0, -1], [0.3, 0.5], [1.1, 0.9], [0.9, -1.2], [1.4, -0.2]])30loc = np.array([1.0, 0.0])31ranks = [32 filtered_rank(transe(E[0], loc, E), 4, set()), # (Paris, located_in, ?) -> France33 filtered_rank(transe(E[2], loc, E), 5, set()), # (Madrid, located_in, ?) -> Spain34 filtered_rank(transe(E[3], loc, E), 6, set()), # (Rome, located_in, ?) -> Italy35 filtered_rank(transe(E, loc, E[4]), 0, {1}), # (?, located_in, France) -> Paris; Lyon is known36]37ranks = np.array(ranks)38print(ranks, "MRR", (1 / ranks).mean(), "Hits@1", (ranks <= 1).mean()) # [1 1 2 1] MRR 0.875 Hits@1 0.75Where it's used
Knowledge-base completion
Suggesting missing facts in Freebase-, Wikidata- or enterprise-scale graphs for human review.
Biomedical discovery
Ranking drug–target or drug–disease links in graphs of genes, proteins, compounds and diseases, e.g. for drug repurposing.
Recommendation and search
Item and user embeddings that respect typed relations (bought, belongs_to, made_by) and feed retrieval or ranking models.
Check yourself
Why can DistMult not model the relation parent_of correctly?
Check yourself
For (?, located_in, France), the true answer Paris is ranked 2nd, behind Lyon, which is also located in France and appears in the training set. What is the filtered rank?
Remember
- ✓A KG embedding is a lookup table for entities and relations plus a score ; completion ranks all entities for and .
- ✓TransE: , translations; cannot express symmetry ( forces ) and struggles with one-to-many relations.
- ✓DistMult: , cheap but always symmetric. ComplEx: , adds antisymmetry and inversion.
- ✓RotatE: with ; rotations give symmetry (), inversion (conjugate) and composition (adding angles).
- ✓Train with corrupted negatives (margin loss, or log-sigmoid with self-adversarial weights); report filtered MRR and Hits@k on FB15k-237 and WN18RR, not the leaky FB15k and WN18.
- ✓Training protocol matters as much as the score function; GNN encoders such as R-GCN can replace the lookup table.