Knowledge Graph Embeddings

Slide 3 recalls the previous lecture. A heterogeneous graph is a graph with multiple relation types. The example is the six-node directed graph A–F with edges coloured by relation \(r_1,r_2,r_3\) (B→A and D→A with \(r_1\), C→A with \(r_2\), and so on); A is the target node.

Slide 4 recalls R-GCN: learn from such a graph by using different neural network weights for different relation types. The figure shows A's computation graph: each edge passes through a box (a weight matrix) coloured by its relation, and the results are aggregated into A.

This lecture keeps the multi-relational setting but changes the tool. Instead of a GNN that computes node embeddings from neighbourhoods, it learns shallow embeddings (one free vector per entity and per relation) and asks a geometric question: what operation should a relation be, so that the logic of real relations can be expressed?

Slide 5 defines a knowledge graph (KG): knowledge in graph form. It captures entities, types and relationships:

• Nodes are entities.
• Nodes are labelled with their types.
• Edges between two nodes capture relationships between entities.

So a KG is an example of a heterogeneous graph. The small figure shows typed nodes connected by labelled arrows.

Two examples:

• Slide 6, bibliographic network. Node types: paper, title, author, conference, year. Relation types: pubWhere, pubYear, hasTitle, hasAuthor, cite. The schema figure puts Paper in the centre: Paper –pubWhere→ Conference, Paper –hasTitle→ Title, Paper –hasAuthor→ Author, Paper –pubYear→ Year, and a self-loop Paper –cite→ Paper.
• Slide 7, biomedical KG. Node types: drug, disease, adverse event, protein, pathways. Relation types: has_func, causes, assoc, treats, is_a. The figure is a graph of drugs, diseases and proteins with these labelled edges.

Slide 8, KGs in practice: Google Knowledge Graph, Amazon Product Graph, Meta Graph API, IBM Watson, Microsoft Satori, Project Hanover/Literome, LinkedIn Knowledge Graph, Yandex Object Answer.

Slide 9, application: serving information. The screenshot is a Bing search for "latest films by the director of Titanic". The search engine answers with a row of movie posters ("Movies featuring James Cameron"), which needs a chain of facts: Titanic → directed by → James Cameron → directed → films. That is a query over a KG, not keyword matching.

Slide 10 lists publicly available KGs: FreeBase, Wikidata, DBpedia, YAGO, NELL, etc. Their common characteristics:

• Massive: millions of nodes and edges.
• Incomplete: many true edges are missing.

Given a massive KG, enumerating all possible facts is intractable. So the question is: can we predict plausible but missing links?

Slide 11 gives numbers for Freebase: about 80 million entities, about 38K relation types, about 3 billion facts (triples). And it is very incomplete: 93.8% of persons in Freebase have no place of birth, and 78.5% have no nationality.

Research datasets: FB15k / FB15k-237, a complete subset of Freebase used by researchers to learn KG models. The table on the slide:

• FB15k: 14,951 entities, 1,345 relations, 592,213 total edges.
• FB15k-237: 14,505 entities, 237 relations, 310,079 total edges.

Why FB15k-237 exists: FB15k contains many inverse pairs (if (h, r, t) is in test, (t, r⁻¹, h) is often in train), so a model could "cheat" by memorising inverses. FB15k-237 removes these near-duplicate and inverse relations, which is why it has only 237 relations.

Slide 13 defines the task. Given an enormous KG, can we complete it? For a given (head, relation), we predict missing tails. This is slightly different from the link prediction task: there we score a pair of nodes; here the query fixes the head and the relation and ranks all candidate tails.

The example graph has authors (J.R.R. Tolkien, Stephen King, J.K. Rowling, Alan Poe, C.S. Lewis, Lloyd Alexander), genres (Science Fiction, Fantasy, Tragicomedy) and two relations, genre and Influence. The dashed red edge is the missing relation: predict the tail "Science Fiction" for ("J.K. Rowling", "genre").

Slide 14 recalls the simplest encoder from Lecture 2, the "shallow" encoding: the encoder is just an embedding lookup. The embedding matrix \(\mathbf{Z}\) has one column per node (the embedding vector of a specific node); its number of rows is the embedding dimension.

Slide 15 sets up the KG representation:

• Edges in a KG are triples \((h,r,t)\): head \(h\) has relation \(r\) with tail \(t\).
• Key idea: model entities and relations in an embedding space \(\mathbb{R}^k\), and associate entities and relations with shallow embeddings. Note: we do not learn a GNN here.
• Given a true triple \((h,r,t)\), the goal is that the embedding of \((h,r)\) should be close to the embedding of \(t\).
• Two design questions: how to embed \((h,r)\)? How to define the score \(f_r(h,t)\)? The score \(f_r\) should be high if \((h,r,t)\) exists, and low otherwise.

Each model below is one answer to these two questions. Training is always contrastive: push true triples to high scores and corrupted triples to low scores.

Slide 16 is a timeline of KG embedding models from 2011 to 2020: above the axis, SE (2011), UM (2012), TransE (2013), TransH (2014), KG2E and TransR (2015), Poincaré (2017), TorusE (2018), RotatE (2019), BoxE (2020); below it, RESCAL (2011), NTN (2013), SME (2014), DistMult (2015), ComplEx (2016), ConvE and R-GCN (2018), TuckER (2019). Colour roughly separates distance/translation models (blue), bilinear/factorisation models (green) and neural models (orange).

Slide 17: we will study several of these shallow, transductive models. They differ in two ways:

• they are based on different geometric intuitions;
• they capture different types of relations: they have different expressivity.

The slide previews the summary table that the lecture fills in step by step (columns: model, score, embedding space, then whether it can model symmetric, antisymmetric, inverse, composition and 1-to-N relations). The full table is on slide 60.

"Transductive" means the model can only score entities it saw during training: a new entity has no embedding. That is the price of shallow embeddings (compare with inductive GNNs, and with KG foundation models in Lecture 15).

Slide 19 [Bordes et al., NeurIPS 2013]. Intuition: translation. For a triple \((h,r,t)\), let \(\mathbf{h},\mathbf{r},\mathbf{t}\in\mathbb{R}^k\) be embedding vectors (bold = embedding). TransE wants

Scoring function:

The figure: Obama + Nationality lands on U.S.A.

Slide 20 shows where the idea comes from: word embeddings. The parallelogram king → queen and man → woman: the "female" arrow is the same vector in both places, and the "royal" arrow (man → king, woman → queen) is also shared. A relation is a constant offset between entity vectors.

Slide 21, how to learn TransE (Algorithm 1 of the paper). Input: training set \(S=\{(h,r,t)\}\), entity set \(E\), relation set \(R\), margin \(\gamma\), embedding dimension \(k\).

1. Initialise each relation \(\mathbf{r}\leftarrow\mathrm{uniform}(-\frac{6}{\sqrt{k}},\frac{6}{\sqrt{k}})\) and normalise \(\mathbf{r}\leftarrow\mathbf{r}/\|\mathbf{r}\|\); initialise each entity \(\mathbf{e}\) uniformly in the same range.
2. Loop: normalise each entity \(\mathbf{e}\leftarrow\mathbf{e}/\|\mathbf{e}\|\); sample a minibatch \(S_{batch}\) of size \(b\).
3. For each \((h,r,t)\in S_{batch}\), sample a corrupted triplet \((h',r,t')\) that does not appear in the KG (replace the head or the tail), and add the pair \(((h,r,t),(h',r,t'))\) to \(T_{batch}\).
4. Update embeddings by gradient steps on the contrastive (margin) loss \[ \sum_{((h,r,t),(h',r,t'))\in T_{batch}}\big[\gamma+d(\mathbf{h}+\mathbf{r},\mathbf{t})-d(\mathbf{h}'+\mathbf{r},\mathbf{t}')\big]_+ , \] where \(d\) is the distance (negative of the score) and \([x]_+=\max(0,x)\).

The loss favours lower distance (higher score) for valid triplets and higher distance (lower score) for corrupted ones. It is zero once each true triple is closer than its corrupted partner by at least the margin \(\gamma\).

Why normalise entities each step? Without it, the loss could be reduced trivially by making all entity norms huge, which spreads corrupted triples far apart without learning anything.

Slide 22: relations in a heterogeneous KG have different properties. Examples:

• Symmetry: if (h, "Roommate", t) exists, then (t, "Roommate", h) should also exist.
• Inverse relation: if (h, "Advisor", t) exists, then (t, "Advisee", h) should also exist.

Can we categorise these patterns? And are KG embedding methods such as TransE expressive enough to model them?

Slide 23 gives the four categories (all statements hold for all entities):

• Symmetric: \(r(h,t)\Rightarrow r(t,h)\). Examples: Family, Roommate.
  Antisymmetric: \(r(h,t)\Rightarrow\neg r(t,h)\). Example: Hypernym, a word with a broader meaning (poodle vs. dog: "dog" is a hypernym of "poodle", not the other way).
• Inverse: \(r_2(h,t)\Rightarrow r_1(t,h)\). Example: (Advisor, Advisee).
• Composition (transitive): \(r_1(x,y)\wedge r_2(y,z)\Rightarrow r_3(x,z)\). Example: my mother's husband is my father.
• 1-to-N: \(r(h,t_1),r(h,t_2),\dots,r(h,t_n)\) are all true. Example: \(r\) is "StudentsOf".

"A model can model a pattern" means: there exist embeddings that make the score function respect the pattern. This is an expressiveness question, like Lecture 6's question about GNNs: if the geometry cannot represent a pattern, no amount of training will find it.

The five patterns are independent properties: symmetry does not imply 1-to-N, for example. So every model must be checked against each pattern separately.

Each slide takes one pattern and either constructs embeddings (✓) or derives a contradiction (✗).

• Slide 24, antisymmetric ✓: if \(\mathbf{h}+\mathbf{r}=\mathbf{t}\) with \(\mathbf{r}\neq0\), then \(\mathbf{t}+\mathbf{r}=\mathbf{h}+2\mathbf{r}\neq\mathbf{h}\). Going along \(\mathbf{r}\) twice does not bring you back.
• Slide 25, inverse ✓: if \(\mathbf{h}+\mathbf{r}_2=\mathbf{t}\), set \(\mathbf{r}_1=-\mathbf{r}_2\); then \(\mathbf{t}+\mathbf{r}_1=\mathbf{h}\). Advisee is "Advisor walked backwards".
• Slide 26, composition ✓: set \(\mathbf{r}_3=\mathbf{r}_1+\mathbf{r}_2\). If \(\mathbf{x}+\mathbf{r}_1=\mathbf{y}\) and \(\mathbf{y}+\mathbf{r}_2=\mathbf{z}\), then \(\mathbf{x}+\mathbf{r}_3=\mathbf{z}\). The figure shows the triangle x → y → z with \(\mathbf{r}_3\) as the third side.
• Slide 27, symmetric ✗: TransE can model it only if \(\mathbf{r}=0\) and \(\mathbf{h}=\mathbf{t}\). Proof: for all \(h,t\) with \(r(h,t)\), \(r(t,h)\) is also true, so \(\mathbf{h}+\mathbf{r}-\mathbf{t}=0\) and \(\mathbf{t}+\mathbf{r}-\mathbf{h}=0\). Adding gives \(2\mathbf{r}=0\), so \(\mathbf{r}=0\) and \(\mathbf{h}=\mathbf{t}\). But \(h\) and \(t\) are different entities and should be mapped to different locations.
• Slide 28, 1-to-N ✗: if \((h,r,t_1)\) and \((h,r,t_2)\) both exist (e.g. \(r\) = "StudentsOf"), then \(\mathbf{t}_1=\mathbf{h}+\mathbf{r}=\mathbf{t}_2\), although \(t_1\neq t_2\) are different entities: contradictory.

Slide 29 fills in the first row of the table: TransE, score \(-\|\mathbf{h}+\mathbf{r}-\mathbf{t}\|\), \(\mathbf{h},\mathbf{t},\mathbf{r}\in\mathbb{R}^k\): symmetric ✗, antisymmetric ✓, inverse ✓, composition ✓, 1-to-N ✗.

The pattern behind the results: a translation is an invertible, composable, non-self-inverse map. That gives inverse and composition for free, and makes symmetry and one-to-many impossible.

In practice the equalities are only approximate, so TransE can partly cope with 1-to-N by putting all tails near \(\mathbf{h}+\mathbf{r}\) (slide 60 calls this a "weaker notion of 1-to-N"). But then those tails become nearly identical in every other relation too.

Slide 31 [Lin et al., AAAI 2015]. TransE models the translation of every relation in the same embedding space. Can we design a new space for each relation and translate in a relation-specific space? TransR: model entities as vectors in the entity space \(\mathbb{R}^d\), and each relation as a vector in a relation space, \(\mathbf{r}\in\mathbb{R}^k\), with a projection matrix \(\mathbf{M}_r\in\mathbb{R}^{k\times d}\).

Slide 32: use \(\mathbf{M}_r\) to project from the entity space \(\mathbb{R}^d\) into the relation space \(\mathbb{R}^k\):

The figure has two panels: the entity space with points h and t, an arrow \(\mathbf{M}_r\), and the relation space where \(\mathbf{h}_\perp+\mathbf{r}\) lands on \(\mathbf{t}_\perp\).

The key new power: \(\mathbf{M}_r\) can be non-injective. Different entities can collapse to the same point in relation space while staying different in entity space.

• Slide 33, symmetric ✓: take \(\mathbf{r}=0\) and learn \(\mathbf{M}_r\) with \(\mathbf{h}_\perp=\mathbf{M}_r\mathbf{h}=\mathbf{M}_r\mathbf{t}=\mathbf{t}_\perp\). We map \(h\) and \(t\) to the same location in the space of relation \(r\); they are still different in the entity space. Different symmetric relations may have different \(\mathbf{M}_r\).
• Slide 34, antisymmetric ✓: with \(\mathbf{r}\neq0\), \(\mathbf{M}_r\mathbf{h}+\mathbf{r}=\mathbf{M}_r\mathbf{t}\); then \(\mathbf{M}_r\mathbf{t}+\mathbf{r}\neq\mathbf{M}_r\mathbf{h}\) (same argument as TransE, now inside the relation space).
• Slide 35, 1-to-N ✓: if \((h,r,t_1)\) and \((h,r,t_2)\) exist, learn \(\mathbf{M}_r\) so that \(\mathbf{t}_\perp=\mathbf{M}_r\mathbf{t}_1=\mathbf{M}_r\mathbf{t}_2\). Note that \(\mathbf{t}_1\) does not need to equal \(\mathbf{t}_2\): we only need \(\mathbf{t}_1-\mathbf{t}_2\in\ker\mathbf{M}_r\).
• Slide 36, inverse ✓: set \(\mathbf{r}_2=-\mathbf{r}_1\) and \(\mathbf{M}_{r_1}=\mathbf{M}_{r_2}\). Then \(\mathbf{M}_{r_1}\mathbf{t}+\mathbf{r}_1=\mathbf{M}_{r_1}\mathbf{h}\) and \(\mathbf{M}_{r_2}\mathbf{h}+\mathbf{r}_2=\mathbf{M}_{r_2}\mathbf{t}\).

Slide 37: TransR can also model composition, \(r_1(x,y)\wedge r_2(y,z)\Rightarrow r_3(x,z)\) (my mother's husband is my father). High-level intuition: TransR models a triple with linear functions, and linear functions are chainable: if \(f(x)=ax+b\) and \(g(x)=cx+d\), then \(f(g(x))=a(cx+d)+b\) is again linear.

Slide 38, background: the kernel of a matrix \(\mathbf{M}\) is \(\ker\mathbf{M}=\{\mathbf{h}:\mathbf{M}\mathbf{h}=\mathbf{0}\}\). The figure shows a blob \(\ker(\mathbf{M})\) that \(\mathbf{M}\) sends to 0.

Slide 39, the proof, step 1. Assume vectors \(\mathbf{g}_1,\mathbf{g}_2\) with \(\mathbf{M}_{r_1}\mathbf{g}_1=\mathbf{r}_1\) and \(\mathbf{M}_{r_2}\mathbf{g}_2=\mathbf{r}_2\).

• If \(r_1(x,y)\) exists: \(\mathbf{M}_{r_1}\mathbf{x}+\mathbf{r}_1=\mathbf{M}_{r_1}\mathbf{y}\Rightarrow\mathbf{M}_{r_1}(\mathbf{y}-\mathbf{x})=\mathbf{r}_1\Rightarrow\mathbf{y}-\mathbf{x}\in\mathbf{g}_1+\ker\mathbf{M}_{r_1}\Rightarrow\mathbf{y}\in\mathbf{x}+\mathbf{g}_1+\ker\mathbf{M}_{r_1}\).
• Same for \(r_2(y,z)\): \(\mathbf{z}\in\mathbf{y}+\mathbf{g}_2+\ker\mathbf{M}_{r_2}\).
• Then \(\mathbf{z}\in\mathbf{x}+\mathbf{g}_1+\mathbf{g}_2+\ker\mathbf{M}_{r_1}+\ker\mathbf{M}_{r_2}\).

Slide 40, step 2. Construct \(\mathbf{M}_{r_3}\) such that \(\ker\mathbf{M}_{r_3}=\ker\mathbf{M}_{r_1}+\ker\mathbf{M}_{r_2}\). It exists because \(\dim\ker\mathbf{M}_{r_3}\ge\dim\ker\mathbf{M}_{r_1}\) and \(\mathbf{M}_{r_3}\) has the same shape as \(\mathbf{M}_{r_1}\). Set \(\mathbf{r}_3=\mathbf{M}_{r_3}(\mathbf{g}_1+\mathbf{g}_2)\). Then \(\mathbf{z}-\mathbf{x}-(\mathbf{g}_1+\mathbf{g}_2)\in\ker\mathbf{M}_{r_3}\), so

Why the existence claim holds: a \(k\times d\) matrix with a prescribed kernel \(K\) exists iff its rank \(d-\dim K\) is at most \(k\). Since \(\dim(K_1+K_2)\ge\dim K_1\), the required rank \(d-\dim(K_1+K_2)\) is at most \(\operatorname{rank}\mathbf{M}_{r_1}\le k\). Bigger kernel = smaller rank = always achievable.

Slide 41 updates the table with the TransR row: score \(-\|\mathbf{M}_r\mathbf{h}+\mathbf{r}-\mathbf{M}_r\mathbf{t}\|\), \(\mathbf{h},\mathbf{t}\in\mathbb{R}^d\), \(\mathbf{r}\in\mathbb{R}^k\), \(\mathbf{M}_r\in\mathbb{R}^{k\times d}\): ✓ for all five patterns.

The price: \(\mathbf{M}_{r_3}\) must "forget" every direction that \(\mathbf{M}_{r_1}\) or \(\mathbf{M}_{r_2}\) forgets, so long compositions lose information quickly. TransR also has \(k\times d\) parameters per relation, which is costly with thousands of relations (the same issue as R-GCN in Lecture 9).

Slide 43 [Yang et al., ICLR 2015]. So far the score \(f_r(h,t)\) was the negative of an L1/L2 distance (TransE, TransR). New idea: bilinear modelling,

Problem: this is too general and prone to overfitting: the matrix \(\mathbf{A}\) is too expressive (\(k^2\) parameters per relation; this full version is RESCAL from the timeline). Fix: limit \(\mathbf{A}\) to be diagonal. This is called DistMult.

Slide 44: entities and relations are vectors in \(\mathbb{R}^k\), and

The figure: the three vectors \(\mathbf{h}\), \(\mathbf{r}\), \(\mathbf{t}\) are multiplied coordinate by coordinate (Product), and the products are summed (Sum) into \(f_r(h,t)\).

Slide 45, intuition: the score is a cosine similarity between \(\mathbf{h}\cdot\mathbf{r}\) and \(\mathbf{t}\), where \(\mathbf{h}\cdot\mathbf{r}\) is the Hadamard (element-wise) product, \([\mathbf{h}\cdot\mathbf{r}]_i=\mathbf{h}_i\cdot\mathbf{r}_i\):

Example (figure): \(\mathbf{t}_2\) points to the same side as \(\mathbf{h}\cdot\mathbf{r}\), so \(f_r(h,t_2)>0\); \(\mathbf{t}_1\) points to the other side, so \(f_r(h,t_1)<0\). The dashed line is the hyperplane orthogonal to \(\mathbf{h}\cdot\mathbf{r}\).

Intuition: \(\mathbf{r}\) is a per-dimension "importance and sign" mask. It reweights the features of \(h\), and then asks whether \(t\) agrees with the reweighted vector.

• Slide 46, 1-to-N ✓: if \((h,r,t_1)\) and \((h,r,t_2)\) exist, we can have \(\langle\mathbf{h},\mathbf{r},\mathbf{t}_1\rangle=\langle\mathbf{h},\mathbf{r},\mathbf{t}_2\rangle\) with \(\mathbf{t}_1\neq\mathbf{t}_2\): both tails just need the same projection on \(\mathbf{h}\cdot\mathbf{r}\) (figure: \(\mathbf{t}_1\), \(\mathbf{t}_2\) at equal angle and height relative to \(\mathbf{h}\cdot\mathbf{r}\)).
• Slide 47, symmetric ✓, naturally: \(f_r(h,t)=\sum_i\mathbf{h}_i\mathbf{r}_i\mathbf{t}_i=\langle\mathbf{t},\mathbf{r},\mathbf{h}\rangle=f_r(t,h)\), due to the commutative property of multiplication.
• Slide 48, antisymmetric ✗: by the same identity, \(r(h,t)\) and \(r(t,h)\) always have the same score. DistMult cannot tell the head from the tail, so every relation is modelled as symmetric, even antisymmetric ones.
• Slide 49, inverse ✗: suppose DistMult models inverse relations: \(f_{r_2}(h,t)=\langle\mathbf{h},\mathbf{r}_2,\mathbf{t}\rangle=\langle\mathbf{t},\mathbf{r}_1,\mathbf{h}\rangle=f_{r_1}(t,h)\). For example \(\mathbf{r}_2=\mathbf{r}_1\) solves this (other solutions with \(\mathbf{r}_2\neq\mathbf{r}_1\) also exist). But semantically this does not make sense: the embedding of "Advisor" should not be the same as that of "Advisee". The point: with a symmetric score, "inverse" carries no information, because each relation already equals its own inverse.
• Slide 50, composition ✗: intuition: the product is commutative (\(a\cdot b=b\cdot a\)), so DistMult does not distinguish head and tail entities, and it cannot model composition. Unlike a translation or a projection, the DistMult score is not a map from \(h\) to \(t\) that can be chained.

Slide 51 adds the DistMult row: score \(\langle\mathbf{h},\mathbf{r},\mathbf{t}\rangle\), \(\mathbf{h},\mathbf{t},\mathbf{r}\in\mathbb{R}^k\): symmetric ✓, antisymmetric ✗, inverse ✗, composition ✗, 1-to-N ✓.

So DistMult and TransE are almost complements: DistMult does symmetric and 1-to-N; TransE does antisymmetric, inverse and composition. ComplEx keeps DistMult's form but breaks its symmetry.

Slide 53 [Trouillon et al., ICML 2016]. Based on DistMult, ComplEx embeds entities and relations in a complex vector space \(\mathbb{C}^k\). A complex vector is \(\mathbf{u}=\mathbf{a}+\mathbf{b}i\) with \(\mathbf{a},\mathbf{b}\in\mathbb{R}^k\); its conjugate is \(\bar{\mathbf{u}}=\mathbf{a}-\mathbf{b}i\) (in the figure, \(\bar{\mathbf{u}}\) is the mirror image of \(\mathbf{u}\) across the real axis). Complex multiplication: \((a+ib)(c+id)=(ac-bd)+i(ad+bc)\). The example on the slide: \((3+4i)(2+3i)=-6+17i\), drawn as a scaling by 2 plus a "scale and rotate" by \(3i\), added together. Multiplying by a complex number scales and rotates.

Slide 54, score function:

The figure mirrors DistMult's: element-wise product of \(\mathbf{h}\), \(\mathbf{r}\), \(\bar{\mathbf{t}}\), then sum, then take the real part. The only changes are complex numbers and the conjugate on the tail.

Slide 55 expands it into real DistMult-like terms (writing \(\mathbf{h}_i=\mathrm{Re}(\mathbf{h}_i)+i\,\mathrm{Im}(\mathbf{h}_i)\) etc.):

Read it this way: the first two terms (with \(\mathrm{Re}\,\mathbf{r}\)) are symmetric in \(h\) and \(t\). The last two (with \(\mathrm{Im}\,\mathbf{r}\)) change sign when \(h\) and \(t\) swap: \(\langle\mathrm{Re}\,\mathbf{h},\mathrm{Im}\,\mathbf{r},\mathrm{Im}\,\mathbf{t}\rangle-\langle\mathrm{Im}\,\mathbf{h},\mathrm{Im}\,\mathbf{r},\mathrm{Re}\,\mathbf{t}\rangle\) is antisymmetric. So \(\mathrm{Re}\,\mathbf{r}\) is the symmetric part of the relation and \(\mathrm{Im}\,\mathbf{r}\) is the antisymmetric part.

• Slide 56, antisymmetric ✓: the model is expressive enough to learn a high \(f_r(h,t)=\mathrm{Re}(\sum_i\mathbf{h}_i\mathbf{r}_i\bar{\mathbf{t}}_i)\) and a low \(f_r(t,h)=\mathrm{Re}(\sum_i\mathbf{t}_i\mathbf{r}_i\bar{\mathbf{h}}_i)\), thanks to the asymmetric modelling with the complex conjugate.
• Slide 57, symmetric ✓: when \(\mathrm{Im}(\mathbf{r})=0\), \[ f_r(h,t)=\mathrm{Re}\Big(\sum_i\mathbf{h}_i\mathbf{r}_i\bar{\mathbf{t}}_i\Big)=\sum_i\mathbf{r}_i\,\mathrm{Re}(\mathbf{h}_i\bar{\mathbf{t}}_i)=\sum_i\mathbf{r}_i\,\mathrm{Re}(\bar{\mathbf{h}}_i\mathbf{t}_i)=\sum_i\mathrm{Re}(\mathbf{r}_i\bar{\mathbf{h}}_i\mathbf{t}_i)=f_r(t,h), \] using that a complex number and its conjugate have the same real part.
• Slide 58, inverse ✓: set \(\mathbf{r}_1=\bar{\mathbf{r}}_2\). The complex conjugate of \(\mathbf{r}_2=\arg\max_{\mathbf{r}}\mathrm{Re}(\langle\mathbf{h},\mathbf{r},\bar{\mathbf{t}}\rangle)\) is exactly \(\mathbf{r}_1=\arg\max_{\mathbf{r}}\mathrm{Re}(\langle\mathbf{t},\mathbf{r},\bar{\mathbf{h}}\rangle)\). Reason: \(\mathrm{Re}(\langle\mathbf{t},\bar{\mathbf{r}},\bar{\mathbf{h}}\rangle)=\mathrm{Re}\big(\overline{\langle\bar{\mathbf{t}},\mathbf{r},\mathbf{h}\rangle}\big)=\mathrm{Re}(\langle\mathbf{h},\mathbf{r},\bar{\mathbf{t}}\rangle)\): conjugating the relation is the same as swapping head and tail.
• Slide 59, composition ✗ and 1-to-N ✓: ComplEx shares these properties with DistMult. It cannot model composition relations, and it can model 1-to-N relations.

In one sentence: ComplEx = DistMult + an antisymmetric part. That one change buys antisymmetry and inverses, while keeping symmetry and 1-to-N. Composition still fails, because the score is still a "one-shot" bilinear test rather than a chainable map.

Slide 60 gives the complete expressiveness table (S = symmetric, A = antisymmetric, I = inverse, C = composition, N = 1-to-N):

• TransE: \(-\|\mathbf{h}+\mathbf{r}-\mathbf{t}\|\), \(\mathbf{h},\mathbf{t},\mathbf{r}\in\mathbb{R}^k\). S ✗, A ✓, I ✓, C ✓, N ✗.
• TransR: \(-\|\mathbf{M}_r\mathbf{h}+\mathbf{r}-\mathbf{M}_r\mathbf{t}\|\). S ✓, A ✓, I ✓, C ✓, N ✓. (On this slide the dimensions are written \(\mathbf{h},\mathbf{t}\in\mathbb{R}^k\), \(\mathbf{r}\in\mathbb{R}^d\), \(\mathbf{M}_r\in\mathbb{R}^{d\times k}\): the letters \(d,k\) are swapped relative to slides 31–41, but the meaning is the same.)
• DistMult: \(\langle\mathbf{h},\mathbf{r},\mathbf{t}\rangle\), \(\mathbb{R}^k\). S ✓, A ✗, I ✗, C ✗, N ✓.
• ComplEx: \(\mathrm{Re}(\langle\mathbf{h},\mathbf{r},\bar{\mathbf{t}}\rangle)\), \(\mathbb{C}^k\). S ✓, A ✓, I ✓, C ✗, N ✓.
• RotatE: \(-\|\mathbf{h}\circ\mathbf{r}-\mathbf{t}\|\), \(\mathbf{h},\mathbf{t},\mathbf{r}\in\mathbb{C}^k\). S ✓, A ✓, I ✓, C ✓, N ✗.

Here \(\circ\) is the Hadamard product; the slide's example: \(\begin{bmatrix}3&5&7\\4&9&8\end{bmatrix}\circ\begin{bmatrix}1&6&3\\0&2&9\end{bmatrix}=\begin{bmatrix}3\times1&5\times6&7\times3\\4\times0&9\times2&8\times9\end{bmatrix}\). RotatE is "TransE in complex space": each coordinate of the head is multiplied by a complex number. In the RotatE paper each \(\mathbf{r}_i\) has modulus 1, so the relation is a rotation of every coordinate. Rotations are invertible (inverse = rotate back), composable (angles add), and a rotation by \(\pi\) is its own inverse (symmetry). The slide's footnote: TransE and RotatE both satisfy a weaker notion of 1-to-N: many tails can be equidistant to \(\mathbf{r}\circ\mathbf{h}\) or \(\mathbf{r}+\mathbf{h}\), even if they cannot all be exactly there.

Slide 61 [Sun et al., ICLR 2019], KG embeddings in practice:

1. Different KGs may have drastically different relation patterns.
2. There is no general embedding that works for all KGs; use the table to select models.
3. Try TransE for a quick run if the target KG does not have many symmetric relations.
4. Then use more expressive models, e.g. ComplEx or RotatE (TransE in complex space).

Slide 62, empirical comparison (MR = mean rank, lower is better; MRR = mean reciprocal rank and H10 = Hits@10, higher is better). The TransR row is empty.

• FB15k-237: TransE MR 357, MRR .294, H10 .465; DistMult 254, .241, .419; ComplEx 339, .247, .428; RotatE 177, 0.338, 0.533.
• WN18RR: TransE MR 3384, MRR .226, H10 .501; DistMult 5110, .43, .49; ComplEx 5261, .44, .51; RotatE 3340, 0.476, 0.571.

Read the table with the expressiveness lens. WN18RR (from WordNet) is full of hierarchical, antisymmetric relations (hypernym) and some symmetric ones; TransE's MRR is lowest there, and RotatE, which handles all of S/A/I/C, is best on both datasets. MR and MRR can disagree (DistMult has the best MR among the non-RotatE models on FB15k-237 but the worst MRR), because MR is dominated by the worst-ranked queries while MRR is dominated by the top positions.

Slide 63 summarises:

• Link prediction / graph completion is one of the prominent tasks on knowledge graphs.
• We introduced TransE / TransR / DistMult / ComplEx, models with different embedding spaces and different expressiveness (plus RotatE in the final table).
• Next: reasoning in knowledge graphs.

From the notes (Chapter 11, not on these slides). The notes continue directly into multi-hop reasoning, which builds on this lecture's embeddings. KG completion is 1-hop reasoning: "is \(t\) the answer to \((h,r)\)?". A path query \(q=(v_a,(r_1,\dots,r_n))\) starts at an anchor entity and follows \(n\) relations; e.g. "what protein is associated with the adverse event caused by Fulvestrant?" is (e:Fulvestrant, (r:Causes, r:Assoc)). Just traversing the KG fails because the KG is incomplete; completing the KG first and then traversing fails because the completed probabilistic KG is dense, and traversal cost grows exponentially with the path length.