From One Point to a Manifold: Knowledge Graph Embedding for Precise Link Prediction

1 Introduction

Knowledge is critical to artificial intelligence, and the embedded representation of knowledge offers an efficient basis of computing over symbolic knowledge facts. More specifically, knowledge graph embedding projects entities and relations into a continuous high-dimension vector space by optimizing well-defined objective functions. A variety of methods have been proposed for this task, including TransE [Bordes et al., 2013], PTransE [Lin et al., 2015a] and KG2E [He et al., 2015].

A fact of knowledge graph is usually represented by a triple (h↪ r↪ t), where h↪ r↪ t indicate the head entity, the relation and the tail entity, respectively. The goal of knowledge graph embedding is to obtain the vectorial representations of triples, i.e., (h↪ r↪ t), with some well-defined objective functions. As a key branch of embedding methods, translation-based methods, such as TransE [Bordes et al., 2013], PTransE [Lin et al., 2015a] and KG2E [He et al., 2015], treat the triple as a relation-specific translation from the head entity to the tail entity, or formally as h + r = t.

Despite the success of previous methods, none of previous studies has addressed the issue of precise link prediction, which finds the exact entity given another entity and the relation. For a specific query fact, most existing methods would extract a few candidate entities that may contain correct answers, but there is no mechanism to ensure that the correct answers rank ahead the candidate list.

Generally speaking, precise link prediction would improve the feasibility of knowledge completion, the effectiveness of knowledge reasoning, and the performance of many knowledge-related tasks. Taking knowledge completion as example, when we want to know about the birth place of Martin R.R., what we expect is the exact answer "U.S.", while a few other candidates do not make any sense.

The issue of precise link prediction is caused by two reasons: the ill-posed algebraic system and the over-strict geometric form. First, from the algebraic perspective, each fact can be treated as an equation of hr + r = tr 1 if following the translation-based principle, embedding could be treated as a solution to the equation group. In current embedding methods, the number of equations is more than that of free variables, which is called an ill-posed algebraic problem as defined in [Tikhonov and Arsenin, 1978]. More specifically, hr + r = tr indicates d equations as hi + ri = ti where d is the dimension of embedding vector and i denotes each dimension. Therefore, there are T ⇤ d equations where T is the number of facts, while the number of variables are (E+R)⇤d, where E↪R are the number of entities and relations, respectively. As is the case that triples are much more than the sum of entities and relations, the number of variables are much less than the number of equations, which is typically an illposed algebraic system. Mathematically, an ill-posed algebraic system would commonly make the solutions imprecise and unstable. In this paper, we propose to address this issue by replacing the translation-based principle hr + r = tr by a manifold-based principle M(h↪ r↪ t) = D2 r where M is the manifold function. With the manifold-based principle, our model can make a nearly well-posed algebraic system by taking d ≥ T E+R so that the number of equations (T) is no more than that of the free parameters ((E +R) ⇤ d).

Second, from the geometric perspective, the position of the golden facts in existing methods is almost one point, which is too strict for all relations and is more insufficient for complex relations such as many-to-many relations. For example, for entity American Revolution, there exist many triples such as (American Revolution, Has Part, Battle Bunker Hill), (American Revolution, Has Part, Battle Cowpens). When many tail entities compete for only one point, there would be a major loss of objective function. Some previous work such as TransH [Wang et al., 2014] and TransR [Lin et al., 2015b] address this problem by projecting entities and relations into some relation-specific subspaces. However, in each subspace, the golden position is also one point and the over-strict geometric form is still existing. As can be seen from Fig.1, the translation-based geometric principle involves too much noise. However, ManifoldE alleviates this issue by expanding the position of golden triples from one point to a manifold such as a high-dimensional sphere. By this mean, ManifoldE avoids much noise to distinguish the true facts from the most possible false ones, and improves the precision of knowledge embedding as Fig.1 shows.

1 More generally speaking, hr and tr are embedding vectors projected w.r.t the relation space, and r is the relation embedding vector.

To summarize, our contributions are two-fold: (1)We have addressed the issue of precise link prediction and uncover the two reasons: the ill-posed algebraic system and the over-strict geometric form. To our best knowledge, this is the first time to address this issue formally. (2)We propose a manifoldbased principle to alleviate this issue and design a new model, ManifoldE, which achieves remarkable improvements over the state-of-the-art baselines in experiments, particularly for precise link prediction. Besides, our methods are also very efficient.

2 RelatedWork

2.1 Translation-BasedMethods

As a pioneering work of knowledge graph embedding, TransE [Bordes et al., 2013] opens a line of translation-based methods. TransE treats a triple (h↪ r↪ t) as a relation-specific translation from a head entity to a tail entity, say h+ r = t and the score function has a form of ♣♣h+ r - t♣♣22 . Following this principle, a number of models have been proposed. For instance, TransH [Wang et al., 2014] adopts a projection transformation, say hr = h-w> r hwr, tr = t -w> r twr, while TransR [Lin et al., 2015b] applies a rotation transformation, say hr =Mrh,tr =Mrt. Similar work also includes TransD [Ji et al., ] and TransM [Fan et al., 2014]. Other approaches take into consideration extra information such as relation-type [Wang et al., 2015], paths with different confidence levels (PTransE) [Lin et al., 2015a], and semantic smoothness of the embedding space [Guo et al., 2015]. KG2E [He et al., 2015] is a probabilistic embedding method for modeling the uncertainty in knowledge base. Notably, translation-based models demonstrate the state-of-the-art performance.

2.2 Other Methods

The Unstructured Model (UM) [Bordes et al., 2012] is a simplified version of TransE, which ignores relation information and the score function is reduced to fr(h↪ t) = ♣♣h - t♣♣22 . The Structured Embedding (SE) model [Bordes et al., 2011] transforms the entity space with the head-specific and tail-specific matrices and the score function is defined as fr(h↪ t) = ♣♣Mh↪rh-Mt↪rt♣♣. The Semantic Matching Energy (SME) model [Bordes et al., 2012] [Bordes et al., 2014] can enhance SE by considering the correlations between entities and relations with different matrix operators, as follows:

where M1↪M2↪M3 and M4 are weight matrices, ⌦ is the Hadamard product, b1 and b2 are bias vectors. The Single Layer Model (SLM) applies neural network to knowledge graph embedding and the score function is defined as fr(h↪ t) = u>r g(Mr↪1h+Mr↪2t) where Mr↪1↪Mr↪2 are relation-specific weight matrices. The Latent Factor Model (LFM) [Jenatton et al., 2012], [Sutskever et al., 2009] makes use of the second-order correlations between entities by a quadratic form and the score function is as fr(h↪ t) = h>Wrt. The Neural Tensor Network (NTN) model [Socher et al., 2013] defines a very expressive score function to combine the SLM and LFM: fr(h↪ t) = u>r g(h>W··rt +Mr↪1h +Mr↪2t + br), where ur is a relation-specific linear layer, g(·) is the tanh function, W 2 Rd⇥d⇥k is a 3-way tensor. Besides, RESCAL is a collective matrix factorization model which is also a common method in knowledge graph embedding [Nickel et al., 2011], [Nickel et al., 2012].

3 Methods

In this section, we introduce the novel manifold-based principle and then we analyze these methods from the algebraic and geometric perspectives.

3.1 ManifoldE : aManifold-Based Embedding Model

Instead of adopting the translation-based principle h + r = t, we apply the manifold-based principle M(h↪ r↪ t) = D2 r for a specific triple (h↪ r↪ t). When a head entity and a relation are given, the tail entities lay in a high-dimensional manifold. Intuitively, our score function is designed by measuring the distance of the triple away from the manifold:

where Dr is a relation-specific manifold parameter. M : E⇥ L⇥E -! R is the manifold function, where E, L are the entity set and relation set and R is the real number field.

Sphere. Sphere is a very typical manifold. In this setting, all the tail (or head) entities for a specific fact such as (h↪ r↪ ⇤) are supposed to lay in a high-dimensional sphere where h + r is the center and Dr is the radius, formally stated as below:

Obviously, this is a straight-forward extension of translation-based models in which Dr is zero. From the geometric perspective, the manifold collapses into a point when applying the translation-based principle.

Reproducing Kernel Hilbert Space (RKHS) usually provides a more expressive approach to represent the manifolds, which motivates us to apply the manifold-based principle with kernels. To this point, kernels are involved to lay the sphere in a Hilbert space (an implicit high-dimensional space) as below:

where ' is the mapping from the original space to the Hilbert space, and K is the induced kernel by '. Commonly, K

could be Linear kernel (K(a↪ b) = a>b), Gaussian kernel (K(a↪ b) = e- ♣♣a-b♣♣22 σ2 ), Polynomial Kernel (K(a↪ b) = (a>b + d)p , and so on. Obviously, if applying the linear kernel, the above function is reduced to the original sphere manifold.

Hyperplane. As shown in Fig.2, we could see that when two manifolds are not intersected, there may be a loss in embedding. Two spheres would intersect only under some strict conditions, while two hyperplanes would intersect if their normal vectors are not in parallel. Motivated by this fact, we apply a hyperplane to enhance our model as below:

where rhead and rtail are two specific relation embeddings. From the geometric perspective, given the head entity and the relation, the tail entities lay in the hyperplane whose direction is h + rhead and the bias corresponds to D2 r . In practical cases, since the two vectors e1 + r1↪head and e2 + r2↪head are not likely to be parallel, there would be more chance to lead two intersected hyperplanes than two intersected spheres. Therefore, there would be more solutions provided by the intersection of hyperplanes.

Motivated by enlarging the number of precisely predicted tail entities for the same head and relation, we apply the absolute operators as M(h↪ r↪ t) = ♣h + rhead♣>♣t + rtail♣ where ♣w♣ ▷= (♣w1♣↪ ♣w2♣↪ ♣w3♣↪ ▷▷▷↪ ♣wn♣). For an instance of onedimensional case that ♣h+rhead♣♣t+rtail♣ = D2 r , the absolute operator would double the solution number of t, meaning that two tail entities rather than one could be matched precisely to this head for this relation. For this reason, the absolute operator would promote the flexibility of embedding.

We also apply the kernel trick to the Hyperplane setting, as below:

3.2 Algebraic Perspective

The ill-posed equation system that posses more equations than free variables always leads to some undesired properties such as instability, which may be the reason why the translation-based principle performs not so well in precise link prediction. To alleviate this issue, manifold-based methods model embedding within a nearly well-posed algebraic framework, since our principle indicates only one equation for one fact triple. Taking an example of sphere as Pdi=1 (hi + ri - ti)2 = D2 r , we could conclude that if d ≥ #Equation E+R = T E+R , our embedding system would be more algebraically stable and this condition is easy to achieve by just enlarging the embedding dimension to a suitable degree. In theory, larger embedding dimension provides more solutions to embedding equations, which makes embedding more flexible. When the suitable condition is satisfied, the stable algebraic solution would lead the embedding to a fine characterization, therefore the precise link prediction would be promoted.

3.3 Geometric Perspective

The translation-based principle allocates just one position for a golden triple. We extend one point to a whole manifold such as a high dimensional sphere. For instance, all tail entities for a 1-N relation could lay on a sphere, which applies h + r as the center and Dr as the radius. Obversely, it would be more suitable in a manifold setting than in a point setting.

3.4 Training

We train our model with the rank-based hinge loss, which means to maximize the discriminative margin between the golden triples and the false ones.

where L is the loss function which should be minimized, γ is the margin, and [·]+ ▷= max(0↪ ·) is the hinge loss. The false triples are sampled with the Bernoulli Sampling Method as introduced in [Wang et al., 2014]. We initialize the embedding vectors by the similar methods used in deep neural network [Glorot and Bengio, 2010]. Stochastic gradient descent (SGD) is applied to solve this problem.

In theory, our computation complexity relative to TransE is bounded by a very small constant, as O(λ ⇥ O(TransE)) where λ ≥ 1. This small constant λ is caused by manifoldbased operations and kernelization. Commonly, TransE is the most efficient among all the translation-based methods, while ManifoldE could be comparable to TransE in efficiency, hence faster than other translation-based methods.

4 Experiments

Our experiments are conducted on four public benchmark datasets that are the subsets of Wordnet [Miller, 1995] and Freebase [Bollacker et al., 2008]. The statistics of these datasets are listed in Tab.1. Experiments are conducted on two tasks : Link Prediction and Triple Classification. To further demonstrate how the proposed model performs the manifold-based principle, we present the visualization comparison between translation-based and manifold-based models in the section 4.3. Finally, we conduct error analysis to further understand the benefit and limits of our models.

4.1 Link Prediction

Reasoning is the focus of knowledge computation. To verify the reasoning performance of embedding, link prediction task is conducted. This task aims to predict the missing entities. An alternative of the entities and the relation are given when the embedding methods infer the other missing entity. More specifically, in this task, we predict t given (h↪ r↪ ⇤), or predict h given (⇤↪ r↪ t) . The WN18 and FB15K are two benchmark datasets for this task. Notably, many AI tasks could be enhanced by "Link Prediction", such as relation extraction [Hoffmann et al., 2011].

Evaluation Protocol. We adopt the same protocol used in previous studies. Firstly, for each testing triple (h↪ r↪ t), we corrupt it by replacing the tail t (or the head h) with every entity e in the knowledge graph. Secondly, we calculate a probabilistic score of this corrupted triple with the score function fr(h↪ t). By ranking these scores in descending order, we then obtain the rank of the original triple. The evaluation metric is the proportion of testing triple whose rank is not larger than N (HITS@N). HITS@10 is applied for common reasoning ability and HITS@1 concerns the precise embedding performance. This is called "Raw" setting. When we filter out the corrupted triples that exist in the training, validation, or test datasets, this is the"Filter" setting. If a corrupted triple exists in the knowledge graph, ranking it ahead the original triple is also acceptable. To eliminate this case, the "Filter" setting is more preferred. In both settings, a higher HITS@N means better performance. Note that we do not report the results of "raw" setting for HITS@1, because they are too small to make a sense. Notably, we actually run each baseline in the same setting for five times, and average the running time as the results.

Implementation. As the datasets are the same, we directly reproduce the experimental results of several baselines from the literature for HITS@10. As to HITS@1, we request the results from the authors of PTransE and KG2E. We acknowledge these authors Yankai Lin and Shizhu He. We have attempted several settings on the validation dataset to get the best configuration. Under the "bern." sampling strategy, the optimal configurations of ManifoldE are as follows. For sphere, ↵ = 0▷001, k = 100, γ = 3▷0, Linear kernel, on WN18; ↵ = 0▷0005, k = 800, γ = 1▷0, Polynomial kernel(p = 2↪ d = 2) on FB15K. For hyperplane, learning rate ↵ = 0▷01, embedding dimension k = 800, margin γ = 0▷2, Linear kernel, on WN18; ↵ = 0▷01, k = 1000, γ = 0▷2, Linear kernel, on FB15K. The experimental environment is a common PC with i7-4790 CPU, 16G Memory and Windows 10. Note that all the symbols are introduced in "Methods".

Results. Evaluation results on WN18 and FB15K are reported in Tab.2 and Tab.3. We observe that:

1. ManifoldE beats all the baselines in all the sub-tasks, yielding the effectiveness and efficiency of the manifoldbased principle.
2. From the algebraic perspective, it's reasonable to measure the algebraic ill-posed degree with the radio T◁(E + R) because with the translation-based principle, Td is the number of equations and (E + R)d is the number of free variables, a larger radio means more ill-posed. Since the manifold-based principle alleviates this issue, ManifoldE(Sphere) would make a more promotion relatively to the comparable baselines (TransE) under a larger radio. As to the metric HITS@1, on WN18, the radio is 3.5 while TransE achieves 29.5% and ManifoldE(Sphere) achieves 55%, leading to a relative improvement of 85.1%. On FB15K the radio is 30.2 while TransE achieves 24.4% and ManifoldE(Sphere) achieves 64.1%, leading to a relative improvement of 162.7%. This comparison illustrates manifold-based methods could stabilize the algebraic property of embedding system, by which means, the precise embedding could be approached much better.
3. From the geometric perspective, traditional models attempt to express all the matched entities into one position, which leads to unsatisfactory performance on complex relations. Meanwhile, manifold-based model could perform much better for these complex relations as we discussed. As to the metric HITS@1, the simple relation

1-1 improves relatively by 87.8% by ManifoldE(Sphere) than TransE while the complex relations such as 1-N, N-1, N-N improve relatively by 266.5%, 36.2% and 215.7% respectively. This comparison demonstrates manifold-based method that extends the golden position from one point to a manifold could better characterize the true facts, especially for complex relations.

4.2 Triple Classification

In order to present the discriminative capability of our method between true and false facts, triple classification is conducted. This is a classical task in knowledge base embedding, which aims at predicting whether a given triple (h↪ r↪ t) is correct or not. WN11 and FB13 are the benchmark datasets for this task. Note that evaluation of classification needs negative samples, and the datasets have already been built with negative triples.

Evaluation Protocol. The decision process is very simple as follows: for a triple (h↪ r↪ t), if fr(h↪ t) is below a threshold σr, then positive; otherwise negative. The thresholds ¶σr♦ are determined on the validation dataset. This task is somehow a triple binary classification.

Implementation. As all methods use the same datasets, we directly re-use the results of different methods from the literature. We have attempted several settings on the validation dataset to find the best configuration. The optimal configurations of ManifoldE are as follows with "bern" sampling. For sphere, ↵ = 0▷001, k = 100, γ = 10▷0, Linear kernel on WN18; ↵ = 0▷00005, k = 1000, γ = 0▷3, Gaussian kernel (σ = 1▷0) on FB13. For hyperplane, learning rate ↵ = 0▷01, embedding dimension k = 500, margin γ = 1▷0, Linear kernel, on WN18; ↵ = 0▷001, k = 1000, γ = 3▷0, Polynomial kernel (p = 2↪ d = 2), on FB13.

Results. Accuracies are reported in Tab.5. We observe that:

1. Overall, ManifoldE yields the best performance. This illustrates our method could improve the embedding.
2. More specifically, onWN11, the relation "Type Of" that is a complex one, improves from 71.4% of TransE to 86.3% of ManifoldE(Sphere) while on FB13, the relation "Gender" that is an extreme N-1 relation, improves from 95.1% to 99.5%. This comparison shows manifold-based methods could handle complex relations better.

4.3 Visualization Comparison between Translation-Based and Manifold-Based Principle

As the Fig.1 shows, the translation-based principle involves too much noise near the center where is supposed to lay the true facts. We attribute such issues to the precise link prediction issue as introduced previously, However, manifold-based principle alleviates this issue to enhance precise knowledge embedding, which could be seen from the visualization results.

4.4 Error Analysis

To analyze the errors in Link Prediction, we randomly sample 100 testing triples that could not rank at the top positions by ManifoldE (Hyperplane) and three categories of errors are summarized. Notably, we call the predicted top rank triple, which is not the golden one, as "top rank triple".

1. True Facts (29%): The top rank triple is correct though it is not contained in the knowledge graph, thus ranking it before the golden one is acceptable. This category is caused by incompleteness of the dataset. For example, reflexive semantics as (Hot↪ Similar To↪Hot), general expression as (Animal Scientist↪ Type Of↪ Individual), professional knowledge as (Crescentia↪ Type Of ↪ Plant) and so on.
2. Related Concepts (63%): The top rank triple is a related concept, but the corresponding fact is not exactly correct. This category is caused by the relatively simple manifolds applied by ManifoldE. For example, puzzled place membership as (Afghanistan↪Has Part↪Hyderabad), similar mentions as (New Haven↪ Part Of↪One Star State), similar concepts as (Sea↪Has Instance↪Aleutian Islands), possible knowledge as (Accent↪Type Of↪ Individual) and so on. We could further exploit complex manifolds to enhance the discriminative ability.
3. Others (8%): There are always some top rank triples that are difficult to interpret.

5 Conclusions

In this paper, we study the precise link prediction problem and reveal two reasons to the problem: the ill-posed algebraic system and the over-restricted geometric form. To alleviate these issues, we propose a novel manifoldbased principle and the corresponding ManifoldE models (Sphere/Hyperplane) inspired by the principle. From the algebraic perspective, ManifoldE is a nearly well-posed equation system and from the geometric perspective, it expands point-wise modeling in the translation-based principle to manifold-wise modeling. Extensive experiments show our method achieves substantial improvements against the stateof-the-art baselines.

This work was partly supported by the National Basic Research Program (973 Program) under grant No.2012CB316301 / 2013CB329403, and the National Science Foundation of China under grant No.61272227 / 61332007.