MöbiusE: Knowledge Graph Embedding on Möbius Ring

Graph or network structure can usually be used to model the intrinsic information behind data [1]. As an typical example, a knowledge graph (KG) is a collection of facts of the real world, related examples include DBpedia [2], YAGO [3] and Freebase [4]. These built KG database can be applied in many realistic engineering tasks, such as knowledge inference, question answering, and sample labeling. Driven by realistic applications, an intriguing and challenging problem for KG is: how to infer those unknown knowledge (or missing data) via the existing built KG database.

For any KG, the basic element of knowledge is represented by a triplet $(h,r,t)$, which composed of two entities $h,t$ and one relation $r$. In detail, $h$ is called the head, $r$ is called the tail, and $(h,r,t)$ means head $h$ maps to tail $t$ via the operation of relation $r$. For example, the entity $h=$ U.S.A projects to $t=$ DonaldTrump under the relation $h=$ ThePresidentOf, and the entity $h=$ U.S.A projects to $t=$ MikePence under the relation $h=$ TheVicePresidentOf. Based on these two triplets, and considering the fact of “the president and vice president of a country at the same time are colleagues”, one predicts the existence of the triplet $($DonaldTrump, IsColleagueOf, MikePence$)$ if such triplet is not contained in the given database. For realistic applications such as question answering, the core task is to predict those triplets which are not listed in the given database, such as task is called link prediction in KG.

There exists many types of method for link prediction in KG, among which translation-based methods treats each entity and relation as embedded vectors in some constructed algebraic space, and each true triplet can be translated to a simple constraint described by an algebraic expression $f(h,r,t)$. Using such a method, if some $(h,r,t)$ is not presented in KG but the corresponding algebraic constraint index $f(h,r,t)$ is very small, then it is reasonable to believe that $(h,r,t)$ is a missing fact. Due to the choosing of different algebraic space, many different translation-based models have be obtained. TransE [5] is the first translation-based model for link prediction tasks, in which it uses the Euclidean space $\mathbb{R}^{n}$ as the embedding space and the constraint quantity for each triplet is set as simple as $\|h+r-t\|$. TransR [6] builds the constraint equation by mapping the entities to a subspace derived by the relation vector. TansH [7] improves TransE in dealing with reflexive/ONE-TO-MANY/MANY-TO-ONE/MANY-TO-MANY cases in KG, such an improvement is caused by treating each relation as a translating operation on a hyperplane. DistMult [8] utilizes a simple bilinear formulation to model the constraint generated by triplets, in this way the composition of relation is characterized by matrix multiplication, which makes such a model good at capturing relational semantics. ComplEx [9] uses the standard dot product between embeddings and demonstrates the capability of complex-valued embeddings instead of real-valued numbers. TorusE [10] chooses a compact Lie group, a torus, as the embedding space, and is more scalable to large-size knowledge graphs because of its lower computational complexity. Other types of embedding methods include TransA [11], a locally and temporally adaptive translation-based approach; ConvE [12], a multi-layer convolutional network embedding model; TransF, an embedding strategy with flexibility in each triplet constraint; QuaternionE [13], an embedding method treats each relation as a quaternion in hypercomplex space.

Among the above embedding methods, the basic operation behind TorusE is a simple modulus operation and this operation automatically regularizes the calculated results to the given bounded area. In this way, there is no need to make an extra regularization operation in TorusE. Inspired by this property of TorusE, we move beyond one-dimensional modulus operation on Lie group and propose MöbiusE, which takes a Möbius ring (whose basic dimension is two) as the embedding space. This MöbiusE has the following major benefits for embedding tasks: At first, MöbiusE provides much more flexibility since each point on the surface of a Möbius ring has two different expressions; Second, the expressiveness of MöbiusE is much greater than TorusE due to the complex distance function built in Möbius ring; Third, MöbiusE also automatically truncates the training vectors to constraint space as that of TorusE; Finally, MöbiusE subsumes TorusE, and inherits all the attractive properties of TorusE, such as its ability to model symmetry/antisymmetry, inversion, and composition.

The rest of the paper is organized as follows: Section 2 revisits the idea of TorusE and proposes the basic idea of MöbiusE, especially, we discuss about how to define the distance function on a Möbius ring. Section 3 provides the experiment results for MöbiusE on datasets FB15K and WN18. Section 4 discuss about related works and compare MöbiusE with other embedding methods. Section 5 concludes this paper. In the end, Section 6 lists the proof for several key propositions on Möbius ring.

A KG is described by a set of triples $\Delta$, where each $l=(h,r,t)\in\Delta$ contains $h$, $r$, and $t$ as head entity, relation, and tail entity, respectively. Denote $E=\{h,t|(h,r,t)\in\Delta\}$ and $R=\{r|(h,r,t)\in\Delta\}$ as the set of entities and relations of $\Delta$. Let $f$ be the scoring function, the task of KGE is to find vectors $\mathbf{h},\mathbf{r},\mathbf{t}$ corresponding to $h,r,t$ which minimize:

where

and $l=(h,r,t)\in\Delta$, $\gamma$ is a margin hyperparameter. The function $[\cdot]_{+}$ is defined by $[x]_{+}=\max(0,x)$ for $x\in\mathbb{R}$.

Suppose $l=(h,r,t)$ be a positive triple, the trueness of $l$ assessed by $f$ is given by

In general, we use the value ${\rm rank}_{l}$ to evaluate the trueness of a candidate triplet.

In order to begin with the following description, we give two critical functions $\mathbbm{m}_{k}(\cdot)$ and $\mathbbm{d}_{k}(\cdot)$.

For any $u\in\mathbb{R}$ and $k\in\mathbb{Z}^{+}$, $\mathbbm{m}_{k}(u)$ is defined as¹¹1$\mathbbm{m}_{1}(u)$ is equivalent to $[u]$ in [10].

$\mathbbm{d}_{k}(u)$ is defined as

Based on these definitions, for any $u\in\mathbb{R}$, it is not difficult to verify that $\mathbbm{m}_{k}(u)=\mathbbm{m}_{k}(u\pm k)$, $\mathbbm{m}_{k}(-u)=k-\mathbbm{m}_{k}(u)$, $\mathbbm{d}_{k}(-u)=\mathbbm{d}_{k}(u)$, and $\mathbbm{d}_{k}(u)=\mathbbm{d}_{k}(u\pm k)$. In particular, $\mathbbm{d}_{k}(u)$ can be reformulated as $\mathbbm{d}_{k}(u)=\min_{i\in\mathbb{Z}}|u+ik|$.

The performance of the proposed MöbiusE is tested on two datasets: FB15K and WN18 [5], which are extracted from realistic knowledge graphs. The basic properties on these two datasets is given in Tab. 2.

We conduct the link prediction task by using the same method reported in [5]. For each test triplet (which is a positive sample), we replace its head (or tail) to generate a corrupted triplet, then the score of each corrupted triplet is calculated by the scoring function $f(\cdot)$, and the ranking of the test triplet is obtained according to these scores, i.e., the definition of ${\rm rank}_{l}$ in (5). It should be noted from (4) that the set of generated corrupted elements excludes the positive triplets $\Delta$, we call such a set be “filtered” [10], and the ranking values in our experiments are all obtained on the “filtered” set.

We choose stochastic gradient descent algorithm to optimize the objective (1). In order to generate the negative sample in (1), we employ the “Bern” method [7] for negative sampling because of the datasets only contains positive triplets.

To evaluate our model, we use Mean Rank (MR), Mean Reciprocal Rank (MRR) and HIT@m as evaluating indicators [5]. MR is calculated by ${\rm mean}_{l\in\Delta}({\rm rank}_{l})$ with $\Delta$ be the set of triplet data and ${\rm rank}_{l}$ is defined in (5), MRR is calculated by ${\rm mean}_{l\in\Delta}(1/{\rm rank}_{l})$, HIT@m is defined by $|\{l\in\Delta:{\rm rank}_{l}\leq m\}|/|\Delta|$.

We conduct a grid search to find a set of optimal hyper-parameters for each dataset, the searching area for margin $\gamma$ in (1) is $\{2000,1000,500,200,100\}$ and the searching area for learning rate $\alpha$ in stochastic gradient descent is $\{0.002,0.001,$ $0.0005,0.0002,0.0001\}$. Finally, the learning rate $\alpha$ is set to $0.0005$ both for WN18 and FB15K, the margin $\gamma$ is set to $2,000$ for WN18 and $500$ for FB15K.

We conduct our experiments on the augmented Möbius ring $\mathbb{M}^{q/p}_{n}$ as defined in (28), and we choose three different types of Möbisu ring for embedding, i.e., $\mathbb{M}^{2/1}_{n}$, $\mathbb{M}^{3/1}_{n}$, $\mathbb{M}^{3/2}_{n}$. In choosing the distance function in $\mathbb{M}^{q/p}_{n}$, we choose $\|\cdot\|_{\tau}=\|\cdot\|_{1}$ in ${\rm dist}(\cdot)$ in (30). We call the above corresponding MöbiusE be MöbiusE(2,1), MöbiusE(3,1), MöbiusE(3,2) in Tab. 3 and Tab. 4. The value of $n$ in $\mathbb{M}^{q/p}_{n}$ is set to $5,000$, which means in each embedding vector we have $10,000$ parameters to be trained. The dimensions for other types of models in Tab. 3 and Tab. 4 are all set to $10,000$.

As shown in Tab. 3, Möbius(3,1) outperforms the other models in 4 of the 5 critical indicators. In Tab. 4, Möbius(2,1) outperforms the other models also in 4 of the 5 critical indicators.

The key for different types of KGE strategies is the choosing of embedding spaces, and in turn different addition operations and different scoring functions, i.e., different $f(\cdot)$ in (1). As the first work in KGE, TranE [5] uses the basic algebraic addition to generate the score function, and regularizes the obtained vectors via a normalized condition. In TransE, the left (right) entity and the relation uniquely defines the right (left) entity. However, for realistic KG, it may have the following properties: a). ONE-TO-MANY mapping, given any fixed relation $r$, the left (right) entity corresponding to a the right (left) entity is not unique; b): MANY-TO-ONE mapping, given any fixed entities $h$ and $t$, the relation between $h$ and $t$ may not be unique. The original TransE cannot resolve the above two drawbacks in the beginning.

As an improvement of TransE to overcome the above drawback a), TransR [6] maps each relation $r$ to a vector and a matrix, the corresponding scoring function is derived by the image of such a relation matrix. In this sense, different entities may be mapped to a same vector in the image space and the drawback a) of TransE is resolved. Similar to TransR, TransH [7] uses a single vector to obtain the image of each entities. As further generalization of TransR and TransH, TransD [15] uses a dynamic matrix which is determined both by relation and entities to generate the above mapping matrix. As another solution to the drawbacks of TransE, TransM [16] introduces a relation-based adjust factor to the scoring function in TransE, such a factor will be much smaller in MANY-TO-MANY case than that of ONE-TO-ONE case and hence penalizing effects works.

Introducing flexibility in the scoring function in some extent enhances the generalization capability of KGE. As an implementation of such an idea, TransF [17] uses a flexible scoring function in KGE, in which the matching degree is desribed by the inner products of desired entities and given relation. Increasing the complexity in the scoring function enhances the nonlinear representative capability of KGE, RESCAL [14] and DistMult [8] uses a matrix-induced inner product to represent the scoring function in KGE, and ComplEx [9] applies the similar but embeds both relation and entities to a complex-valued space. TransA [11] combines the idea of TransE and RESCAL and incorporates the residue vector in TransE to the vector-based norm in RESCAL, such a strategy can adaptively find the loss function according to the structure of knowledge graphs.

MöbiusE is inspired from TorusE [10], however, MöbiusE differs from TorusE in the following aspects: The minimal dimension of Torus ring is $1$, but the minimal dimension of Möbius ring is $2$; The addition in Torus ring chooses an unique value for modulus operation (generally $1$), but the addition in Möbius ring chooses different values (generally $p$ and $q$ in $\mathbbm{M}^{q/p}$); The distance function is Möbius ring is strongly nonlinear (see, (30)), which is much more complicated than that of Torus ring. These major difference guarantees the strong expressiveness of MöbiusE.

A novel KGE strategy is proposed by taking advantage of the intertwined rotating property of Möbius ring. As a first step, we defined the basic addition operation on Möbius ring and discussed its related properties. Next, in order to obtain an appropriate scoring function based on Möbius ring, we built a distance function on Möbius ring and constructed the corresponding distance-induced scoring function. Finally, a complete KGE strategy is obtained via the above constructions, which outperforms several key KGE strategies in our conducted experiments.