Knowledge Graph Embedding by Translating on Hyperplanes

By Zach Hadgraft |

Paper Summary

This is a summary of Knowledge Graph Embedding by Translating on Hyperplanes by Wang et al etc.

Abstract

We deal with embedding a large scale knowledge graph com- posed of entities and relations into a continuous vector space. TransE is a promising method proposed recently, which is very efficient while achieving state-of-the-art predictive per- formance. We discuss some mapping properties of relations which should be considered in embedding, such as reflex- ive, one-to-many, many-to-one, and many-to-many. We note that TransE does not do well in dealing with these proper- ties. Some complex models are capable of preserving these mapping properties but sacrifice efficiency in the process. To make a good trade-off between model capacity and efficiency, in this paper we propose TransH which models a relation as a hyperplane together with a translation operation on it. In this way, we can well preserve the above mapping properties of relations with almost the same model complexity of TransE. Additionally, as a practical knowledge graph is often far from completed, how to construct negative examples to reduce false negative labels in training is very important. Utilizing the one-to-many/many-to-one mapping property of a relation, we propose a simple trick to reduce the possibility of false negative labeling. We conduct extensive experiments on link prediction, triplet classification and fact extraction on bench- mark datasets like WordNet and Freebase. Experiments show TransH delivers significant improvements over TransE on predictive accuracy with comparable capability to scale up.

Introduction

A knowledge graph is a multi-relational graph composed of entities as nodes and relations as different types of edges. An instance of edge is a triplet of fact (head entity, relation, tail entity) (denoted as $(h, r, t)$).

Two major difficulties are: (1) A knowledge graph is a symbolic and logical system while applications often involve numerical computing in continu- ous spaces; (2) It is difficult to aggregate global knowledge over a graph. The traditional method of reasoning by formal logic is neither tractable nor robust when dealing with long range reasoning over a real large scale knowledge graph. Recently a new approach has been proposed to deal with the problem, which attempts to embed a knowledge graph into a continuous vector space while preserving certain properties of the original graph (Socher et al. 2013; Bordes et al. 2013a; Weston et al. 2013; Bordes et al. 2011; 2013b; 2012; Chang, Yih, and Meek 2013). For example, each entity $h$ (or $t$) is represented as a point $\mathbf{h}$ (or $\mathbf{t}$) in the vector space while each relation $r$ is modeled as an operation in the space which is characterized by an a vector $\mathbf{r}$, such as translation, projection, etc. The representations of entities and relations are obtained by minimizing a global loss function involving all entities and relations. As a result, even the embedding representation of a single entity/relation encodes global information from the whole knowledge graph. Then the embedding representations can be used to serve all kinds of applications. A straightforward one is to complete missing edges in a knowledge graph. For any candidate triplet $(h, r, t)$, we can confirm the correctness simply by checking the compatibility of the representations $\mathbf{h}$ and $\mathbf{t}$ under the operation characterized by $\mathbf{r}$.

Generally, knowledge graph embedding represents an entity as a $k$-dimensional vector $\mathbf{h}$ (or $\mathbf{t}$) and defines a scoring function $f_r(\mathbf{h}, \mathbf{t})$ to measure the plausibility of the triplet $(h, r, t)$ in the embedding space. The score function implies a transformation $\mathbf{r}$ on the pair of entities which characterizes the relation $r$. For example, in translation based method (TransE) (Bordes et al. 2013b), $f_r(\mathbf{h},\mathbf{t}) \triangleq \| \mathbf{h} + \mathbf{r} - \mathbf{t} \|_{\ell_{1/2}}$, i.e., relation $\mathbf{r}$ is characterized by the translat- ing (vector) $\mathbf{r}$. With different scoring functions, the implied transformations vary between simple difference (Bordes et al. 2012), translation (Bordes et al. 2013b), affine (Chang, Yih, and Meek 2013), general linear (Bordes et al. 2011), bilinear (Jenatton et al. 2012; Sutskever, Tenenbaum, and Salakhutdinov 2009), and nonlinear transformations (Socher et al. 2013). Accordingly the model complexities (in terms of number of parameters) vary significantly.

TransE (Bordes et al. 2013b) is a promising one as it is simple and efficient while achieving state-of-the-art predictive performance. However, we find that there are flaws in TransE when dealing with relations with mapping properties of reflexive/one-to-many/many- to-one/many-to-many.

Some advanced models with more free parameters are capable of preserving these mapping properties, however, the model complexity and running time is significantly increased accordingly. Moreover, the overall predictive performances of the advanced models are even worse than TransE (Bordes et al. 2013b). This motivates us to propose a method which makes a good trad-off between model complexity and efficiency so that it can overcome the flaws of TransE while inheriting the efficiency.

In this paper, we start by analyzing the problems of TransE on reflexive/one-to-many/many-to-one/many-to- many relations. Accordingly we propose a method named translation on hyperplanes (TransH) which interprets a relation as a translating operation on a hyperplane. In TransH, each relation is characterized by two vectors, the norm vector (wr ) of the hyperplane, and the translation vector (dr ) on the hyperplane. For a golden triplet (h, r, t), that it is correct in terms of worldly facts, the projections of h and t on the hyperplane are expected to be connected by the translation vector dr with low error. This simple method overcomes the flaws of TransE in dealing with reflexive/one-to-many/many-to-one/many-to-many rela- tions while keeping the model complexity almost the same as that of TransE. Regarding model training, we point out that carefully constructing negative labels is important in knowledge embedding. By utilizing the mapping properties of relations in turn, we propose a simple trick to reduce the chance of false negative labeling. We conduct extensive experiments on the tasks of link prediction, triplet clas- sification and fact extraction on benchmark datasets like WordNet and Freebase, showing impressive improvements on different metrics of predictive accuracy. We also show that the running time of TransH is comparable to TransE.

TransE has been discussed

Unstructured

Unstructured is a simplified case of TransE, which con- siders the graph as mono-relational and sets all translations $r = 0$, i.e., the scoring function is $\|\mathbf{h} − \mathbf{t}\|$. It is used as a naive baseline in (Bordes et al. 2012; 2013b). Obviously it cannot distinguish different relations.

So, this is really scoring by how close $h$ is to $t$; for example, for Paris we might have the relations captial_of, located_in, and founded_in and the score of each of this is simply how close $\mathbf{t}$ is to $\mathbf{h}$.

Distant Model

Distant Model (Bordes et al. 2011) introduces two inde- pendent projections to the entities in a relation. It represents a relation by a left matrix $W_{rh}$ and a right matrix $W_{rt}$. Dis- similarity is measured by $L_1$ distance between $W_{rh}\mathbf{h}$ and $W_{rt} \mathbf{t}$. As pointed out by (Socher et al. 2013), this model is weak in capturing correlations between entities and relations as it uses two separate matrices.

So, for each relation we have relation two matrices $\in \mathbb{R}^{k \times d}$ and embeddings $\mathbf{r}$ and $\mathbf{d}$ $\in \mathbb{R}^d$.

And dissimilarity score of:

$$ \begin{gather} f(h, r, t) = \| W_{rh} \mathbf{h} - W_{rt} \mathbf{t} \|_1 \end{gather} $$

$h$, $r$, and $t$ are more independent than with TransE where we have $h \stackrel{r}{\longrightarrow} t$

Sources