Knowledge Graph Embeddings

Learning a vector for every entity and relation of a knowledge graph so that true triples score above false ones. TransE derived in full (translation as the score, the margin loss over corrupted triples, its gradient and the unit-norm constraint), with proofs that exact translation collapses symmetric and one-to-many relations; DistMult and the proof that it cannot tell a triple from its reverse; ComplEx, with the proof that every real square matrix is the real part of a normal matrix; RotatE in outline; filtered MRR and Hits@k defined exactly, with ties; and the test leakage through reversed triples that produced FB15k-237 and WN18RR. TransE and DistMult are trained in NumPy over 30 seeds on WN18RR and on this site's own graph, where DistMult's symmetry and a one-line reverse-link rule do best on the links whose reverse is already known. Worked problems take one gradient step by hand, check ComplEx's antisymmetry, compute filtered and tie-aware ranks, and price the reverse rule.

The site graph of Knowledge Graphs holds 9,631 links between pages, and by the estimate made there about one in ten of the links its pages' own words call for is missing. Remove a tenth of the links and ask a model to put them back: given a page and the relation links_to, rank every entity of the graph by how likely it is to be the missing tail. A model that ranks the removed pages high has learned something about the graph that its edges do not state. This article asks how such a model is built, what it can and cannot represent, and how its rankings should be measured.

A knowledge graph embedding assigns a vector to every entity and every relation, together with a score function $f(h, r, t)$ computed from the three vectors, such that true triples score higher than false ones. Training adjusts the vectors on the triples the graph contains. The task of ranking candidates for a missing head or tail is called link prediction or knowledge graph completion. Hogan and colleagues (2021, §5.2) survey the families of models; this article derives four of them.

Here is the route. First we derive TransE, the model in which a relation is a translation, with its loss, its gradient and the sampling of false triples, and we prove which relations a translation cannot represent. Then we derive DistMult, which multiplies instead of adding and pays for it with symmetry, and ComplEx, which recovers direction with complex numbers. RotatE is given in outline. Next we define the evaluation exactly, including the case of tied scores, and describe the leakage through reversed triples that made two standard benchmarks too easy. Finally we train TransE and DistMult on WN18RR and on the site graph and report what 30 seeds of each show. The article assumes Knowledge Graphs for the data model and Contrastive Training for Retrieval for the idea of training by comparison with negatives. The numbers come from tools/experiments/knowledge-stores/, where kge.py implements both models in NumPy with the gradients derived below written out by hand.

Relations as translations

Bordes and colleagues (2013) started from a picture. Embed a tree in the plane with siblings side by side and each generation one row lower; then "parent of" is a fixed step downward, the same vector for every pair. They also cite the observation that word vectors trained on text represent some one-to-one relations, such as "capital of", approximately as translations (§1). TransE makes this the whole model: if $(h, r, t)$ holds, the tail's vector should be close to the head's vector plus a vector for the relation.

The model. Each entity $e$ has a vector $\vec{e} \in \mathbb{R}^d$ and each relation $r$ a vector $\vec{r} \in \mathbb{R}^d$. The energy of a triple is the distance $D(h, r, t) = \lVert \vec{h} + \vec{r} - \vec{t} \rVert$, in the $L_1$ or the $L_2$ norm, and the score is its negative, $f(h, r, t) = -D(h, r, t)$. An entity has one vector whether it appears as head or as tail (Bordes et al., 2013, §2).

False triples. A knowledge graph lists only true triples, so the negatives are made. For a training triple $(h, r, t)$ the set of corrupted triples is

$$S'_{(h,r,t)} = \{(h', r, t) : h' \in \mathcal{E}\} \cup \{(h, r, t') : t' \in \mathcal{E}\},$$

the triple with its head or its tail, not both, replaced by an entity (Bordes et al., 2013, equation 2). Some corrupted triples are true. The paper's definition does not exclude them, and neither does our implementation of TransE; DistMult's training below does.

The loss. TransE asks each true triple to have lower energy than its corruptions by at least a margin $\gamma > 0$:

$$\mathcal{L} = \sum_{(h,r,t) \in S} \ \sum_{(h',r,t') \in S'_{(h,r,t)}} \big[\gamma + D(h, r, t) - D(h', r, t')\big]_+ ,$$

where $S$ is the training set and $[x]_+ = \max(x, 0)$ (equation 1). The pair contributes nothing once the true triple is closer by $\gamma$; otherwise it pushes the true triple's energy down and the corrupted triple's up. This is the margin ranking loss of the ranking SVM, applied to triples instead of documents.

The constraint. Algorithm 1 of the paper normalizes every entity vector to unit $L_2$ norm before each minibatch and leaves the relation vectors free. The authors give the reason: without it, training could "trivially minimize" the loss by "artificially increasing entity embeddings norms" (§2). Here is the argument in full. Scale every entity and relation vector by $c > 0$. Every energy scales by $c$, so each term becomes $[\gamma + c\,(D - D')]_+$. If the true triple is already closer than its corruption ($D < D'$), the term reaches 0 for any $c \ge \gamma / (D' - D)$. So the margin alone constrains nothing: every term with $D < D'$ vanishes once the embedding is blown up enough, however small the gap, and only the terms with $D' \le D$ remain, such as the pair of a triple with itself, which $S'$ contains (replacing the head by the head). Fixing the entities' norms makes the margin a real requirement.

It also caps the margin. With unit entity vectors and the $L_2$ distance, a tail corruption changes $\vec{u}$ to $\vec{u}' = \vec{u} + (\vec{t} - \vec{t}')$, so $|D' - D| = \big|\lVert \vec{u}' \rVert - \lVert \vec{u} \rVert\big| \le \lVert \vec{t} - \vec{t}' \rVert \le 2$, and a head corruption gives the same bound. For $\gamma \ge 2$ every term is then active (except where $D' - D = 2$ exactly), the loss is linear in the energies, and $\gamma$ drops out of the gradient: every margin of 2 or more trains the same model.

The algorithm. Bordes and colleagues train by minibatch stochastic gradient descent with a constant learning rate (Algorithm 1):

  1. Draw every coordinate of every entity and relation vector uniformly from $[-6/\sqrt{d}, 6/\sqrt{d}]$, and normalize each relation vector once.
  2. Repeat: normalize every entity vector; draw a minibatch of training triples; for each, draw one corrupted triple by replacing its head or its tail by a uniformly drawn entity; take one gradient step on the loss of those pairs.

The full sum over $S'$ in the loss is never computed. One sampled corruption per triple per step, with the side chosen with probability 1/2 and the entity uniformly, is an unbiased estimate of the average over the $2n_e$ corruptions with head and tail counted separately (the triple itself appears twice in that list), up to the constant factor $2n_e$.

The gradient

The loss is a sum of hinge terms, so its gradient is the sum of the gradients of the active terms, those with $\gamma + D - D' > 0$. (At the kink, where the term equals 0, any value between the two one-sided derivatives is a valid subgradient; we use 0.) For one active pair write $\vec{u} = \vec{h} + \vec{r} - \vec{t}$ and $\vec{u}' = \vec{h}' + \vec{r} - \vec{t}'$, so the term is $\gamma + \lVert \vec{u} \rVert - \lVert \vec{u}' \rVert$.

The derivative of the norm with respect to its argument is all we need.

  • For $L_2$: $\partial \lVert \vec{u} \rVert_2 / \partial \vec{u} = \vec{u} / \lVert \vec{u} \rVert_2$, the unit vector along $\vec{u}$ (for $\vec{u} \ne 0$), because $\partial (\sum_i u_i^2)^{1/2} / \partial u_j = u_j / (\sum_i u_i^2)^{1/2}$.
  • For $L_1$: $\partial \lVert \vec{u} \rVert_1 / \partial u_j = \operatorname{sign}(u_j)$, taken as 0 where $u_j = 0$.

Call this derivative $\vec{g} = \partial \lVert \vec{u} \rVert / \partial \vec{u}$, and $\vec{g}'$ the same for $\vec{u}'$. Since $\vec{u}$ depends on $\vec{h}$ with coefficient $+1$, on $\vec{r}$ with $+1$ and on $\vec{t}$ with $-1$, the chain rule gives, for one active pair,

$$\frac{\partial \mathcal{L}}{\partial \vec{h}} \mathrel{+}= \vec{g}, \qquad \frac{\partial \mathcal{L}}{\partial \vec{t}} \mathrel{+}= -\vec{g}, \qquad \frac{\partial \mathcal{L}}{\partial \vec{h}'} \mathrel{+}= -\vec{g}', \qquad \frac{\partial \mathcal{L}}{\partial \vec{t}'} \mathrel{+}= \vec{g}', \qquad \frac{\partial \mathcal{L}}{\partial \vec{r}} \mathrel{+}= \vec{g} - \vec{g}'.$$

When the corruption replaced the tail, $h' = h$ and the head receives both $\vec{g}$ and $-\vec{g}'$; the increments add. The step moves the true triple's head toward $\vec{t} - \vec{r}$ and the false tail away from $\vec{h} + \vec{r}$. In $L_2$ every step has length at most the learning rate per occurrence, since $\vec{g}$ and $\vec{g}'$ are unit vectors; in $L_1$ each occurrence of a vector in an active pair moves every coordinate by exactly the learning rate or not at all, so a coordinate moves by an integer multiple of the learning rate (by twice it, for example, where the head receives $\vec{g}$ and $-\vec{g}'$ with opposite signs). Worked Problem 1 takes one step by hand. Our code checks the $L_2$ gradient against finite differences.

Is TransE the same as a dot-product model? In part. Expanding the squared $L_2$ energy, Bordes and colleagues show that with unit-norm entities it equals $\lVert \vec{r} \rVert^2 + 2 - 2\big(\vec{h}^\top \vec{t} + \vec{r}^\top (\vec{t} - \vec{h})\big)$, and the term $\lVert \vec{r} \rVert^2$ cancels between a triple and its corruption (§3). Ranking by squared $L_2$ energy is therefore ranking by $\vec{h}^\top \vec{t} + \vec{r}^\top(\vec{t} - \vec{h})$: an entity-entity similarity plus a relation-specific direction. The expansion is the one in Similarity Measures for Embeddings, which proves that distance and dot product rank alike when the vectors have one length.

What a translation cannot represent

A translation is a function: from $\vec{h}$ it leads to exactly one point $\vec{h} + \vec{r}$. That simple fact decides which relations TransE can represent exactly. Say that TransE represents a set of triples exactly if $\vec{h} + \vec{r} = \vec{t}$ for each of them.

Theorem 1 (collapse under exact translation).

  1. If a relation $r$ holds in both directions between $a$ and $b$, that is $(a, r, b)$ and $(b, r, a)$, then exact translation forces $\vec{r} = \vec{0}$ and $\vec{a} = \vec{b}$.
  2. If $(h, r, t_1)$ and $(h, r, t_2)$ (one head, two tails), exact translation forces $\vec{t}_1 = \vec{t}_2$. If $(h_1, r, t)$ and $(h_2, r, t)$, it forces $\vec{h}_1 = \vec{h}_2$.
  3. The approximate versions hold with explicit bounds. If both energies in part 1 are at most $\varepsilon$, then $\lVert \vec{r} \rVert \le \varepsilon$ and $\lVert \vec{a} - \vec{b} \rVert \le \varepsilon$. If both energies in part 2 are at most $\varepsilon$, then $\lVert \vec{t}_1 - \vec{t}_2 \rVert \le 2\varepsilon$ (and $\lVert \vec{h}_1 - \vec{h}_2 \rVert \le 2\varepsilon$).

Proof. (1) Add $\vec{a} + \vec{r} = \vec{b}$ and $\vec{b} + \vec{r} = \vec{a}$ to get $2\vec{r} = \vec{0}$; then the first equation gives $\vec{a} = \vec{b}$. (2) Both tails equal $\vec{h} + \vec{r}$. For two heads, both equal $\vec{t} - \vec{r}$. (3) Let $\vec{u}_1 = \vec{a} + \vec{r} - \vec{b}$ and $\vec{u}_2 = \vec{b} + \vec{r} - \vec{a}$, with norms at most $\varepsilon$. Then $2\vec{r} = \vec{u}_1 + \vec{u}_2$, so by the triangle inequality $\lVert \vec{r} \rVert \le \varepsilon$. And $\vec{u}_1 - \vec{u}_2 = 2(\vec{a} - \vec{b})$, so $\lVert \vec{a} - \vec{b} \rVert \le (\lVert \vec{u}_1 \rVert + \lVert \vec{u}_2 \rVert)/2 \le \varepsilon$; the bound is attained with $\vec{r} = \vec{0}$ and $\vec{u}_1 = -\vec{u}_2$ of norm $\varepsilon$. For part 2, $\vec{t}_1 - \vec{t}_2 = (\vec{h} + \vec{r} - \vec{t}_2) - (\vec{h} + \vec{r} - \vec{t}_1)$, a difference of two vectors of norm at most $\varepsilon$, so its norm is at most $2\varepsilon$; the two-heads case is the same computation with $\vec{t} - \vec{r}$. Every step holds in any norm, $L_1$ or $L_2$. $\square$

The theorem is the formal version of what the RotatE paper says of TransE, that "any symmetric relation will be represented by a 0 translation vector" (Sun et al., 2019, §3.2), and of Hogan and colleagues' remark that TransE "will, in this case, aim to give similar vectors to all such target locations" when one head has many tails (§5.2.1). It is a statement about fitting exactly; training fits approximately, and part 3 says how the collapse degrades gracefully. WN18RR, the benchmark below, has relations of both kinds. In its training set _derivationally_related_form, _verb_group, _similar_to and _also_see are reciprocated for 0.932, 0.931, 0.925 and 0.637 of their pairs, and _hypernym is many-to-one: 0.877 of its 34,796 training triples share their tail with another, and one tail has 363 heads.

Translations do well on other patterns, and the proofs are one line each.

Proposition 2 (inversion and composition). If $\vec{r}_2 = -\vec{r}_1$, then $\vec{h} + \vec{r}_1 = \vec{t}$ implies $\vec{t} + \vec{r}_2 = \vec{h}$: the relation and its inverse are represented together. If $\vec{r}_3 = \vec{r}_1 + \vec{r}_2$, then $\vec{x} + \vec{r}_1 = \vec{y}$ and $\vec{y} + \vec{r}_2 = \vec{z}$ imply $\vec{x} + \vec{r}_3 = \vec{z}$: composed relations add.

Proof. Rearrange the first equation to $\vec{t} - \vec{r}_1 = \vec{h}$. Add the two equations of the second to get $\vec{x} + \vec{r}_1 + \vec{r}_2 = \vec{z}$. $\square$

These are the reasons the RotatE paper's Table 2 credits TransE with inversion and composition but not symmetry (Sun et al., 2019).

DistMult: multiplying instead of adding

Yang and colleagues (2015) placed TransE and several earlier models in one framework, in which a relation acts on the entity vectors by a linear map, a bilinear form or both (§3). Their simplest bilinear model scores a triple by $\vec{h}^\top M_r \vec{t}$ with a diagonal matrix $M_r = \operatorname{diag}(\vec{r})$:

$$f(h, r, t) = \langle \vec{h}, \vec{r}, \vec{t} \rangle = \sum_{i=1}^{d} h_i\, r_i\, t_i .$$

They named the model DistMult, a multiplicative counterpart to TransE's additive "DistAdd", with the same number of parameters per relation (§4). Hogan and colleagues note that it amounts to a CP tensor decomposition in which an entity uses one vector as both head and tail (§5.2.2).

Training. Yang and colleagues minimize a margin ranking loss with margin 1, $\sum \max\{f(\text{neg}) - f(\text{pos}) + 1, 0\}$, over negatives formed by corrupting the head or the tail and excluding triples of the training set (equation 3). They draw two negatives per training triple, one with each end corrupted, train with AdaGrad, renormalize entity vectors to unit length after each step, and put an $L_2$ penalty on the relation parameters (§4). The gradient of one active term follows from the product rule. Since $\partial f / \partial h_i = r_i t_i$, and similarly for the other two,

$$\frac{\partial f}{\partial \vec{h}} = \vec{r} \odot \vec{t}, \qquad \frac{\partial f}{\partial \vec{r}} = \vec{h} \odot \vec{t}, \qquad \frac{\partial f}{\partial \vec{t}} = \vec{h} \odot \vec{r},$$

where $\odot$ is the elementwise product. An active term adds $+\nabla f$ at the negative triple's vectors and $-\nabla f$ at the positive's.

Theorem 3 (DistMult is symmetric). For every relation and every pair of entities, $f(h, r, t) = f(t, r, h)$. Consequently, if a DistMult model ranks a true triple $(h, r, t)$ above some threshold, it ranks the reverse $(t, r, h)$ above the same threshold, whether or not the reverse is true.

Proof. $\sum_i h_i r_i t_i = \sum_i t_i r_i h_i$ because multiplication of real numbers is commutative. $\square$

Yang and colleagues state the limitation themselves: the diagonal model cannot encode "the difference between a relation and its inverse" (§4.1). Hypernymy, "part of" and "cites" are antisymmetric, and DistMult must give them a symmetric score. On many datasets this costs less than it seems. Sun and colleagues explain why for FB15k: most of its relations join entities of different types, so the reversed triple, such as (USA, nationality, Obama), is ruled out by types the model has learned, even though it receives the same score as the true one (Sun et al., 2019, §4.2). On a graph where both ends are pages, as on this site, nothing rules the reversed link out. The experiment below shows what that does.

ComplEx: direction from complex conjugation

Trouillon and colleagues (2016) kept DistMult's diagonal form and moved it into the complex numbers. Entities and relations get vectors in $\mathbb{C}^d$, and the score is

$$f(h, r, t) = \operatorname{Re}\Big( \sum_{k=1}^{d} r_k\, h_k\, \overline{t_k} \Big),$$

where $\overline{z}$ is the complex conjugate (equations 9 and 10). The conjugate on the tail is the whole change. Writing every number by its real and imaginary parts gives four real trilinear terms (equation 11):

$$f = \langle \operatorname{Re}\vec{r}, \operatorname{Re}\vec{h}, \operatorname{Re}\vec{t} \rangle + \langle \operatorname{Re}\vec{r}, \operatorname{Im}\vec{h}, \operatorname{Im}\vec{t} \rangle + \langle \operatorname{Im}\vec{r}, \operatorname{Re}\vec{h}, \operatorname{Im}\vec{t} \rangle - \langle \operatorname{Im}\vec{r}, \operatorname{Im}\vec{h}, \operatorname{Re}\vec{t} \rangle .$$

To check it, multiply out one coordinate. With $r = a + bi$, $h = c + ei$ and $\overline{t} = p - qi$, the real part of $(a + bi)(c + ei)(p - qi)$ is $acp + aeq + bcq - bep$, the four terms in order.

Proposition 4 (symmetric and antisymmetric parts). If $\vec{r}$ is real, $f(h, r, t) = f(t, r, h)$. If $\vec{r}$ is purely imaginary, $f(h, r, t) = -f(t, r, h)$. In general $f$ is the sum of a symmetric part from $\operatorname{Re}\vec{r}$ and an antisymmetric part from $\operatorname{Im}\vec{r}$.

Proof. In the four-term form, swapping $h$ and $t$ leaves the first two terms unchanged (each is symmetric in its two entity factors) and exchanges the last two, $\langle \operatorname{Im}\vec{r}, \operatorname{Re}\vec{h}, \operatorname{Im}\vec{t} \rangle$ and $-\langle \operatorname{Im}\vec{r}, \operatorname{Im}\vec{h}, \operatorname{Re}\vec{t} \rangle$, which changes their sum's sign. With $\operatorname{Im}\vec{r} = 0$ only the symmetric terms remain; with $\operatorname{Re}\vec{r} = 0$ only the antisymmetric ones. $\square$

Trouillon and colleagues make the same observation after equation 11. A relation can therefore be symmetric, antisymmetric or anything between, while each entity keeps a single vector. Inversion is representable too: the conjugate relation $\overline{\vec{r}}$ scores $(t, \overline{r}, h)$ exactly as $\vec{r}$ scores $(h, r, t)$, since $\operatorname{Re}(\overline{r}\, t\, \overline{h}) = \operatorname{Re}(\overline{r\, h\, \overline{t}}) = \operatorname{Re}(r\, h\, \overline{t})$.

How expressive is it? For one relation, the scores of all pairs of entities form a real matrix $X$, with $X_{st}$ the score of $(s, r, t)$. ComplEx writes $X = \operatorname{Re}(E W E^*)$, where row $s$ of $E$ is entity $s$'s vector, $W = \operatorname{diag}(\vec{r})$ and $E^*$ is the conjugate transpose. The question is which $X$ arise.

Theorem 5 (Trouillon et al., 2017, Theorem 2 and Corollary 1). Every real square matrix $X$ is the real part of a normal matrix, and therefore $X = \operatorname{Re}(E W E^*)$ for some unitary $E$ and diagonal $W$.

Proof. Let $Z = X + iX^\top$. Its real part is $X$. Its conjugate transpose is $Z^* = X^\top - iX = -i\,(X + iX^\top) = -iZ$. Hence $ZZ^* = Z(-iZ) = -iZ^2$ and $Z^*Z = (-iZ)Z = -iZ^2$, so $ZZ^* = Z^*Z$: $Z$ is normal. By the spectral theorem for normal matrices, which we cite, a complex square matrix is unitarily diagonalizable, $Z = E W E^*$ with $E$ unitary and $W$ diagonal, exactly when it is normal (Trouillon et al., 2017, Theorem 1). So $X = \operatorname{Re}(Z) = \operatorname{Re}(E W E^*)$. $\square$

The script confirms the construction on a random $6 \times 6$ matrix. With $n_e$ entities this uses $d = n_e$ complex dimensions, so it says that a single relation is never beyond ComplEx's reach, not that a small $d$ suffices. Trouillon and colleagues also show that a matrix of rank $k$ needs only $2k$ dimensions (Corollary 2), and, for $m$ relations at once, that dimension $n_e m$ always suffices (Theorem 4). They leave open whether a single unitary $E$ with at most $n_e$ columns can serve every family of relations (§3.2). On WN18 they report a filtered MRR of 0.941 for ComplEx against 0.822 for DistMult and 0.454 for TransE in their own reimplementations (Trouillon et al., 2016, Table 2).

RotatE in outline

Sun and colleagues (2019) combined the translation picture with complex numbers. Each relation is an elementwise rotation: with $\vec{h}, \vec{r}, \vec{t} \in \mathbb{C}^d$ and every $|r_i| = 1$, a true triple should have $\vec{t} = \vec{h} \odot \vec{r}$, and the distance is $\lVert \vec{h} \odot \vec{r} - \vec{t} \rVert$ (equations 2 and 3). Since $r_i = e^{i\theta_{r,i}}$, a relation turns each coordinate of the head by an angle.

The relation patterns of the previous sections now fit together (Lemmas 1 to 3, proved in its appendices). If $(x, r, y)$ and $(y, r, x)$ both hold exactly, then $\vec{y} = \vec{r} \odot \vec{x}$ and $\vec{x} = \vec{r} \odot \vec{y}$, so $\vec{r} \odot \vec{r} \odot \vec{x} = \vec{x}$ and $r_i^2 = 1$ wherever $x_i \ne 0$, that is $r_i = \pm 1$. Unlike TransE's $\vec{r} = \vec{0}$, this does not force $\vec{x} = \vec{y}$: a coordinate with $r_i = -1$ keeps them apart. Any $\vec{r}$ with some $r_i \ne \pm 1$ makes the relation antisymmetric at those coordinates. The inverse of a rotation is its conjugate, and composition multiplies: $\vec{r}_1 = \vec{r}_2 \odot \vec{r}_3$. The paper also trains with a sigmoid loss over several negatives and self-adversarial sampling, which weights each negative by a softmax of its current score so that hard negatives count more (equations 4 to 6), the same idea as mining hard negatives for dense retrievers. On WN18RR it reports a filtered MRR of 0.476 and Hits@10 of 0.571 (Table 5).

Bordes and colleagues set the protocol that later papers follow (§4.2). For each test triple $(h, r, t)$, replace the tail by every entity, score all the candidates, and find the rank of the true tail; then do the same for the head. With $T$ test triples this gives $2|T|$ queries. Two refinements matter, and the second is often left implicit.

Filtering. Some candidates are true triples in their own right: $(h, r, t')$ may be in the training, validation or test set. Ranking such a candidate above $t$ is not an error. Bordes and colleagues therefore remove from the candidate list every triple that appears in any of the three sets, except the test triple itself, and call this the filtered setting, the original being raw (§4.2). All results in this article are filtered.

Ties. Dettmers and colleagues define the rank as one plus the number of filtered candidates that score strictly higher (2018, section "Evaluation Metrics" of the appendix). That places the true entity first among candidates with an equal score. Sun and colleagues (2020) found that some published models gave thousands of candidates exactly the true triple's score; one FB15k-237 query had 8,520 of 14,541 candidates tied with it (§3.2). They compared three protocols, placing the true entity at the top of its tied group, at the bottom or at random, and recommended the random one (§4).

Definition (filtered, tie-aware rank). For one query, let $b$ be the number of filtered candidates whose score exceeds the true entity's and $s$ the number with the same score. Under random tie-breaking the true entity is equally likely to be at each of the ranks $b + 1, \ldots, b + s + 1$. Its expected reciprocal rank and expected Hits@$k$ are

$$\mathrm{RR} = \frac{1}{s + 1} \sum_{j = b+1}^{b+s+1} \frac{1}{j}, \qquad \mathrm{Hits@}k = \frac{\big|\{b+1, \ldots, b+s+1\} \cap \{1, \ldots, k\}\big|}{s+1},$$

and the expected rank is $b + 1 + s/2$. The mean reciprocal rank (MRR) is the mean of RR over the $2|T|$ queries, Hits@$k$ likewise, and the mean rank (MR) the mean of the expected ranks. With no ties ($s = 0$) these are the usual $1/(b+1)$ and $[b + 1 \le k]$.

Why these formulas. Each of the $s + 1$ positions has probability $1/(s+1)$, so the expectation of $1/\text{rank}$ is the average of $1/j$ over the positions, and the expectation of the indicator of rank $\le k$ is the share of positions that are at most $k$. The mean of the positions $b+1, \ldots, b+s+1$ is their midpoint, $b + 1 + s/2$. $\square$

The reciprocal rank here is the one in ranked retrieval evaluation, where the course defines MRR for queries with one relevant document. Its example there, that MRR is not the reciprocal of the mean rank, applies here too; MR is dominated by a few very bad ranks, MRR by the good ones. Worked Problem 4 computes all of this for one query.

Test leakage: when the answer is already in the training set

Toutanova and Chen (2015) asked how much of FB15k and WN18, the two benchmarks Bordes and colleagues introduced, could be answered without learning anything. They counted the test triples $(e_1, r, e_2)$ for which the training graph already links the same two entities, as $(e_1, r', e_2)$ or $(e_2, r', e_1)$ under some relation $r'$: almost 81% for FB15k and 94.0% for WN18 (their Table 5). An "observed features" model that uses only such direct links outperformed the latent feature models on both in MRR. On WN18 the cause is plain: WordNet stores many relations together with their inverses, such as hypernym and hyponym, so a test triple $(s, \text{hyponym}, o)$ often has $(o, \text{hypernym}, s)$ in training. Their remedy for FB15k kept the 401 most frequent relations, removed relations whose entity pairs were near-duplicates or inverses of another's (at least 97% overlap), leaving 237, and dropped from validation and test every triple whose two entities were directly linked in training. The dataset became known as FB15k-237.

Dettmers and colleagues (2018) measured the severity. Their inverse model learns no vectors: it detects pairs of relations that are inverses in training and ranks a test triple's answer by whether its inverse is in training. In the authors' words it "achieves state-of-the-art on many different metrics for both FB15k and WN18": a filtered MRR of 0.963 on WN18, above every model in their Table 3, and 0.660 on FB15k, where ComplEx's 0.692 and two other models' MRRs were higher, while the inverse model's Hits@1 of 0.658 was exceeded by only one model in the table (0.692). For WordNet they built WN18RR by the same procedure as FB15k-237: 93,003 triples, 40,943 entities and 11 relations. They noted that the procedure "does not remove certain symmetric relationships, for example 'similar to'", which explains the inverse model's filtered MRR of 0.35 on WN18RR (Table 4), and they recommended against further use of FB15k and WN18.

That remnant is measurable. Of WN18RR's 3,134 test triples, 1,086 have their reverse, with the same relation, in the training set, 0.35 of them, and 1,011 of those are _derivationally_related_form, a relation that is reciprocated for 0.932 of its training pairs. In the training set _verb_group is reciprocated for 0.931 of its pairs, _similar_to for 0.925 and _also_see for 0.637, while hypernymy and the part-whole relations are never reciprocated. So a third of WN18RR's test is still answerable by reversing a training triple. Our site graph has the same property, more strongly, and the experiment separates the two kinds of test link.

Experiment: TransE and DistMult on WN18RR and on the site graph

Data. WN18RR is taken from the authors' repository at a fixed commit and checked by its SHA-256 hash (beginning 1eb9152f804c140d). It has 86,835 training, 3,034 validation and 3,134 test triples. 40,559 of its 40,943 entities occur in training, and 210 test triples involve an entity that does not; such an entity keeps its random initial vector, and those triples stay in the test set and are ranked with that vector, as in the published protocol. The site graph is the one built in Knowledge Graphs, read from the same pinned commit: 39,157 triples over 10,105 entities and 8 relations. A fixed tenth of its links_to triples, 963 drawn with seed 2026, is held out as the test set, and the other 38,194 triples of every relation are the training set. Of the 963 test links, 358 (0.37) have their reverse link in the training set; we call these reciprocated and the other 605 one-way.

Models and settings. Both are implemented in kge.py with the gradients above.

  • TransE, as Bordes and colleagues' Algorithm 1: one uniform corruption per triple, constant learning rate 0.01, 100 minibatches per epoch. The distance, dimension and margin were chosen on WN18RR's validation set with seed 0 and 100 epochs from $L_1$ or $L_2$, $d \in \{20, 50\}$ and $\gamma \in \{1, 2, 10\}$, the grid of Bordes and colleagues except for its learning rates. In $L_2$ the margins 2 and 10 train identical models, as shown above, so the $L_2$ grid had two effective margins, and the tuning runs for $\gamma = 2$ and $\gamma = 10$ came out identical. $L_2$ with $d = 50$ and $\gamma = 1$ was best, at a validation MRR of 0.133; the best $L_1$ setting reached 0.024, and two $L_1$ settings with $d = 50$ were not run once $L_1$ trailed by that much.
  • DistMult, as Yang and colleagues describe it: $d = 100$, two filtered negatives per triple, AdaGrad with initial learning rate 0.1, $\lambda = 0.0001$ on the relation vectors, 10 minibatches per epoch.

Scale. The brief for these experiments limits a run to about thirty minutes on a laptop processor, and 30 seeds per configuration. So TransE trains for 100 epochs and DistMult for 50, against the 1,000 epochs with early stopping of Bordes and colleagues and Yang and colleagues' 300 on WordNet. Neither model is stopped early or tuned on the site graph, where both use the WN18RR settings. A run took a median of 2.2 minutes of training for TransE and 1.7 for DistMult on WN18RR, on a machine shared with other jobs, and about 0.4 and 0.8 minutes on the site graph. The numbers below describe these runs and are not estimates of what the methods reach when trained to convergence.

Results on WN18RR (filtered, tie-aware; median over seeds 0 to 29, with the interquartile range):

Model MRR Hits@1 Hits@10 MR
TransE 0.130 (0.128 to 0.136) 0.034 (0.027 to 0.039) 0.297 (0.285 to 0.317) 6,965 (6,818 to 7,110)
DistMult 0.401 (0.400 to 0.403) 0.380 (0.378 to 0.382) 0.443 (0.441 to 0.445) 6,660 (6,456 to 6,772)

DistMult is far ahead, and both spreads over the seeds are narrow. Two features of the table need explaining. The mean ranks are in the thousands for both models although their Hits@10 is near 0.3 and 0.44: the queries a model gets wrong get ranks in the thousands among 40,943 candidates (an entity never seen in training, as in 210 test triples, keeps a random vector), and the mean rank is ruled by them, as the course's MRR example warns. And DistMult's Hits@1, 0.380, is almost its Hits@10, 0.443: it either puts the answer first or puts it far down.

The leakage section predicts where DistMult's first places come from, and the seed-0 models confirm it. Split the test triples by whether their reverse is in training. DistMult's MRR is 0.996 on the 1,086 that are and 0.081 on the other 2,048; TransE's is 0.313 and 0.039. By Theorem 3, DistMult scores $(h, r, t)$ exactly as the training triple $(t, r, h)$, which training has pushed to the top, so on those triples it is in effect the reverse rule. On the rest of WN18RR both models are weak at this scale.

For context, the published filtered MRRs on WN18RR are 0.226 for TransE (as reported by Sun et al., 2019, Table 5, from Nguyen and colleagues), 0.43 for DistMult and 0.44 for ComplEx (from Dettmers et al., 2018), and 0.476 for RotatE. Those runs used other losses, dimensions and training lengths; the comparison shows only that our scaled runs land in the same region or below it.

Theorem 1 in the trained model. The seed-0 TransE model shows the collapse the theorem predicts. The three small, mostly reciprocated relations, _verb_group, _similar_to and _also_see, end with relation vectors of norm 0.066, 0.080 and 0.090, against 1.241 for _hypernym and 1.224 for _has_part; _derivationally_related_form, reciprocated for 0.932 of its pairs but joining nouns to verbs, has 0.510. The two ends of a _verb_group triple lie a mean distance 0.357 apart and those of a _hypernym triple 1.088 apart (entity vectors have length 1). The consequence for ranking is direct. A query $(h, r, ?)$ with $\vec{r} \approx \vec{0}$ is answered best by $h$ itself, and the triple $(h, r, h)$ is in no split, so filtering leaves it in the list. On the 2,344 queries of the four mostly reciprocated relations, the best candidate is the query's own entity 0.863 of the time, against 0.149 on the other relations. Wherever that happens the true answer is at best second, and on those 2,344 queries Hits@1 is 0.049 while Hits@3 is 0.502.

Results on the site graph.

Ranker MRR, all 963 MRR, 358 reciprocated MRR, 605 one-way
TransE 0.125 (0.122 to 0.126) 0.163 (0.159 to 0.167) 0.101 (0.100 to 0.103)
DistMult 0.152 (0.151 to 0.154) 0.204 (0.201 to 0.207) 0.121 (0.120 to 0.125)
Reverse-link rule 0.165 0.443 0.001
Degree (in-degree for tails, out-degree for heads) 0.041 0.013 0.058

The reverse-link rule, which learns nothing, has the best MRR of the four, and all of it comes from the 358 reciprocated links: 0.443 there, with the true page in its top 10 for 0.925 of the queries, and 0.001 on the one-way links. DistMult is the better of the two trained models on both kinds of link, and its advantage is largest on the reciprocated ones, 0.204 against 0.163, as Theorem 3 leads one to expect. On the one-way links, the ones that leakage cannot answer, both models beat the rules: 0.121 and 0.101 against 0.058 for ranking by degree.

TransE's median Hits@1 is 0. Its links_to vector ends with norm 0.058 in the seed-0 model, consistent with Theorem 1 for a relation of which 0.43 of the pairs are reciprocated; in_topic, never reciprocated but joining pages that mostly link to each other, ends shorter still, at 0.043, so the trained norms show the collapse without isolating its cause. For every one of the 1,926 test queries the best candidate is the query page itself, never a true answer. The seed-0 DistMult model does the same for 0.877 of the queries: its score of $(h, r, h)$ is $\sum_i r_i h_i^2$, which is large whenever $\vec{r}$ weights the coordinates where $\vec{h}$ is large. A system that used either model to suggest links would have to exclude the page itself, a rule the filtered protocol does not apply because the self-link is not in the data. These are observations on one graph, one split and these scaled runs; they do not rank the methods in general, and nothing here tests whether the site's search would gain from such a model.

What is proved here, what is cited, what the experiment shows

Proved on this page. That scaling the vectors defeats an unconstrained margin loss, and that under unit-norm entities with the $L_2$ distance every margin of 2 or more trains the same model; TransE's gradient in both norms; the collapse of symmetric and one-to-many relations under exact translation, with the bounds for approximate translation (Theorem 1); inversion and composition by translation (Proposition 2); DistMult's symmetry (Theorem 3); ComplEx's four-term form and its symmetric and antisymmetric parts (Proposition 4), and inversion by conjugation; that every real square matrix is the real part of a normal matrix (Theorem 5, after Trouillon and colleagues); RotatE's condition $r_i = \pm 1$ for symmetry; the expected reciprocal rank, Hits@$k$ and rank under random tie-breaking.

Cited. The spectral theorem for normal matrices; ComplEx's rank bounds for one and for several relations; every published result (the scores on WN18, FB15k, FB15k-237 and WN18RR, the leakage shares of Toutanova and Chen, the inverse model of Dettmers and colleagues, the tie counts of Sun and colleagues); the training procedures of the four papers.

What the experiment shows. How two models, implemented as derived and trained at the stated scale, rank held-out triples on WN18RR and on this site's link graph, over 30 seeds. It does not compare the methods at convergence, and it does not test ComplEx or RotatE.

Worked problems

These units have no course assignments, so the problems are posed on small exact cases and on the article's two datasets; the script checks each number.

Problem 1 (one TransE step). In $d = 2$ with the $L_1$ distance, margin $\gamma = 2$ and learning rate 0.01, take the unit vectors $\vec{h} = (0.6, 0.8)$ and $\vec{t} = (0.8, 0.6)$ for a true triple, the relation vector $\vec{r} = (0.2, -0.1)$, and the corrupted tail $\vec{t}' = (0, 1)$. Compute the loss of the pair, its gradient, one step, and the loss after the step.

Solution. $\vec{u} = \vec{h} + \vec{r} - \vec{t} = (0, 0.1)$, so $D = 0.1$; $\vec{u}' = \vec{h} + \vec{r} - \vec{t}' = (0.8, -0.3)$, so $D' = 1.1$. The term is $[2 + 0.1 - 1.1]_+ = 1$, active. The $L_1$ derivatives are $\vec{g} = \operatorname{sign}(\vec{u}) = (0, 1)$, taking $\operatorname{sign}(0) = 0$, and $\vec{g}' = \operatorname{sign}(\vec{u}') = (1, -1)$. The corruption replaced the tail, so $h' = h$ and the head collects $\vec{g} - \vec{g}'$:

Vector Gradient After the step (learning rate 0.01)
$\vec{h}$ $\vec{g} - \vec{g}' = (-1, 2)$ $(0.61, 0.78)$
$\vec{r}$ $\vec{g} - \vec{g}' = (-1, 2)$ $(0.21, -0.12)$
$\vec{t}$ $-\vec{g} = (0, -1)$ $(0.80, 0.61)$
$\vec{t}'$ $\vec{g}' = (1, -1)$ $(-0.01, 1.01)$

After the step $\vec{u} = (0.02, 0.05)$ and $\vec{u}' = (0.83, -0.35)$, so $D = 0.07$, $D' = 1.18$ and the term is $2 + 0.07 - 1.18 = 0.89$, down from 1. The head's norm is now 0.990, and the next minibatch begins by normalizing it back to 1. The step also illustrates the $L_1$ geometry: every coordinate that moved, moved by exactly 0.01 per unit of its gradient.

Problem 2 (which patterns fit). For each of TransE, DistMult, ComplEx and RotatE, say whether it can represent exactly a relation that is (a) symmetric between two distinct entities, (b) antisymmetric, (c) the inverse of another relation. Justify each answer from the results above.

Solution.

  • (a) TransE cannot: Theorem 1 forces $\vec{a} = \vec{b}$, so the two entities are not distinct as vectors, and every other relation sees them as one. DistMult can, since every DistMult relation is symmetric (Theorem 3). ComplEx can, with a real $\vec{r}$ (Proposition 4). RotatE can, with $r_i = \pm 1$, and a coordinate with $r_i = -1$ keeps $\vec{a} \ne \vec{b}$.
  • (b) TransE can: with $\vec{r} \ne \vec{0}$, if $\vec{h} + \vec{r} = \vec{t}$ then $\vec{t} + \vec{r} = \vec{h} + 2\vec{r} \ne \vec{h}$, so the reverse has positive energy. DistMult cannot, by Theorem 3: the reverse scores the same. ComplEx can, with a purely imaginary $\vec{r}$, which makes the reverse's score the negative of the triple's. RotatE can, with some $r_i \ne \pm 1$: then $r_i^2 \ne 1$ and $\vec{r} \odot \vec{r} \odot \vec{x} \ne \vec{x}$ wherever $x_i \ne 0$.
  • (c) TransE can, with $\vec{r}_2 = -\vec{r}_1$ (Proposition 2). DistMult can only trivially: its inverse relation is the relation itself, which is right only for symmetric relations. ComplEx can, with $\overline{\vec{r}}$. RotatE can, with $\overline{\vec{r}}$, which for $|r_i| = 1$ is $\vec{r}^{-1}$.

Problem 3 (ComplEx by hand). In $d = 1$, let the head be $h = 1$ and the tail $t = i$. Write $r$ for the relation's single coordinate. Score the triple and its reverse for $r = i$. Then do the same for $r = 1 + i$ with the tail $t = 1 + i$, and split the score into its symmetric and antisymmetric parts.

Solution. With $r = i$: $f(h, r, t) = \operatorname{Re}(i \cdot 1 \cdot \overline{i}) = \operatorname{Re}(i \cdot (-i)) = 1$, and $f(t, r, h) = \operatorname{Re}(i \cdot i \cdot \overline{1}) = \operatorname{Re}(-1) = -1$. The relation is purely imaginary, and the two scores are negatives, as Proposition 4 says.

With $r = 1 + i$ and $t = 1 + i$: $f(h, r, t) = \operatorname{Re}\big((1 + i) \cdot 1 \cdot (1 - i)\big) = \operatorname{Re}(2) = 2$, and $f(t, r, h) = \operatorname{Re}\big((1 + i)(1 + i) \cdot 1\big) = \operatorname{Re}(2i) = 0$. The symmetric part comes from $\operatorname{Re} r = 1$ and equals $\operatorname{Re} r \cdot \operatorname{Re}(h\, \overline{t}) = 1 \cdot 1 = 1$ in both directions; the antisymmetric part is $+1$ forward and $-1$ backward. The sums, $1 + 1 = 2$ and $1 - 1 = 0$, are the two scores. This relation prefers one direction without forbidding the other.

Problem 4 (filtered and tie-aware ranks). A tail query has ten candidates besides the true tail $t$, which scores 5. The others, named by capital letters, score A: 7, B: 5, C: 5, D: 9, E: 3, F: 5, G: 1, H: 8, I: 2. The triples with tails A and C are in the training set. Compute the raw and the filtered expected reciprocal rank, the filtered reciprocal rank under the top and bottom tie protocols, the filtered expected Hits@3, and both expected ranks.

Solution. Raw: $b = 3$ candidates score higher (A, D, H) and $s = 3$ tie (B, C, F), so the true tail is equally likely at ranks 4 to 7 and

$$\mathrm{RR}_{\text{raw}} = \tfrac{1}{4}\big(\tfrac14 + \tfrac15 + \tfrac16 + \tfrac17\big) = \tfrac{319}{1680} = 0.190.$$

Filtered: A and C are removed, leaving $b = 2$ (D, H) and $s = 2$ (B, F), ranks 3 to 5:

$$\mathrm{RR}_{\text{filt}} = \tfrac{1}{3}\big(\tfrac13 + \tfrac14 + \tfrac15\big) = \tfrac{47}{180} = 0.261.$$

The top protocol puts $t$ at rank 3, reciprocal rank 0.333; the bottom protocol at rank 5, 0.200. The random protocol's 0.261 lies between them, as it must, being their positions' average. Hits@3: of the equally likely ranks 3, 4 and 5, one is at most 3, so the expected Hits@3 is $1/3 = 0.333$. The expected rank is $b + 1 + s/2$: 5.5 raw and 4 filtered.

Problem 5 (pricing the reverse rule). The reverse-link rule scores a candidate tail $c$ for the query $(h, \texttt{links\_to}, ?)$ as 1 if the training set has the link $c \to h$, and 0 otherwise. On a reciprocated test link, where $t \to h$ is in training, suppose $s$ other filtered candidates also link to $h$. What is the expected reciprocal rank? What is it on a one-way link?

Solution. On a reciprocated link the true tail scores 1, as do the $s$ others, and nothing scores higher, so $b = 0$ and

$$\mathrm{RR} = \frac{1}{s + 1} \sum_{j=1}^{s+1} \frac{1}{j} = \frac{H_{s+1}}{s + 1},$$

with $H_n$ the $n$-th harmonic number: 1 for $s = 0$, 0.75 for $s = 1$ and 0.457 for $s = 4$. The rule's whole skill is in how few pages link to $h$. On a one-way link the true tail scores 0, tied with every candidate that does not link to $h$, so its expected rank is about half the number of entities and its reciprocal rank near 0. That is the pattern of the experiment's reverse-rule row, which is good exactly where the test leaks.

What we have learned

A knowledge graph embedding turns each entity and relation into a vector and each triple into a score. TransE scores by translation, and a translation is a function: exact translation collapses a symmetric relation to the zero vector and the tails of a one-to-many relation to one point, and the trained models show that collapse in their relation norms and in which candidate they rank first. DistMult scores by a trilinear product and so cannot tell a triple from its reverse. ComplEx recovers direction through complex conjugation and can represent any single relation, and RotatE makes each relation a rotation, which fits symmetry, inversion and composition together. Measuring them needs filtered ranks with ties handled, and benchmarks without reversed copies of their test triples. WN18RR still has such copies for a third of its test, and the models' scores there are mostly scores on those copies; on this site's links a one-line rule that reverses known links has a higher MRR than either model, all of it on reciprocated links, and on one-way links only the trained models do better than ranking by degree.

The embeddings here hold the graph's structure in their parameters, and link prediction reads it back out. The next article in the unit's order, Generative Retrieval, takes the same step for documents: a model trained to produce a document's identifier, so that the index itself is in the weights.

References

  • Bordes, A., Usunier, N., Garcia-Durán, A., Weston, J., and Yakhnenko, O. (2013). Translating embeddings for modeling multi-relational data. In Advances in Neural Information Processing Systems 26, 2787–2795. record · 3 pages
  • Dettmers, T., Minervini, P., Stenetorp, P., and Riedel, S. (2018). Convolutional 2D knowledge graph embeddings. In Proceedings of the AAAI Conference on Artificial Intelligence, 32(1). doi:10.1609/aaai.v32i1.11573. arXiv:1707.01476. record
  • Hogan, A., Blomqvist, E., Cochez, M., d'Amato, C., de Melo, G., Gutierrez, C., Kirrane, S., Labra Gayo, J. E., Navigli, R., Neumaier, S., Ngonga Ngomo, A.-C., Polleres, A., Rashid, S. M., Rula, A., Schmelzeisen, L., Sequeda, J., Staab, S., and Zimmermann, A. (2021). Knowledge graphs. ACM Computing Surveys, 54(4), 1–37. doi:10.1145/3447772. arXiv:2003.02320. record · 2 pages
  • Sun, Z., Deng, Z.-H., Nie, J.-Y., and Tang, J. (2019). RotatE: Knowledge graph embedding by relational rotation in complex space. In International Conference on Learning Representations (ICLR 2019). arXiv:1902.10197. record
  • Sun, Z., Vashishth, S., Sanyal, S., Talukdar, P., and Yang, Y. (2020). A re-evaluation of knowledge graph completion methods. In Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, 5516–5522. doi:10.18653/v1/2020.acl-main.489. record
  • Toutanova, K., and Chen, D. (2015). Observed versus latent features for knowledge base and text inference. In Proceedings of the 3rd Workshop on Continuous Vector Space Models and their Compositionality, 57–66. doi:10.18653/v1/W15-4007. record
  • Trouillon, T., Welbl, J., Riedel, S., Gaussier, É., and Bouchard, G. (2016). Complex embeddings for simple link prediction. In Proceedings of the 33rd International Conference on Machine Learning (ICML 2016), Proceedings of Machine Learning Research 48, 2071–2080. arXiv:1606.06357. record
  • Trouillon, T., Dance, C. R., Gaussier, É., Welbl, J., Riedel, S., and Bouchard, G. (2017). Knowledge graph completion via complex tensor factorization. Journal of Machine Learning Research, 18(130), 1–38. arXiv:1702.06879. record
  • Yang, B., Yih, W., He, X., Gao, J., and Deng, L. (2015). Embedding entities and relations for learning and inference in knowledge bases. In International Conference on Learning Representations (ICLR 2015). arXiv:1412.6575. record