TransMS: Knowledge Graph Embedding for Complex Relations by Multidirectional Semantics

1 Introduction

Knowledge graph, which is a semantic graph composed of triplets, has become a hot topic for its wide applications in information retrieval. As the basic unit for knowledge graph, the triplet in the form of (head, relation, tail ) - also abbreviated as (h, r , t ), consists of two entities (i.e., head and tail ) as nodes and one relation (relation) as edge from head to tail . Although knowledge graphs can consist of millions of entities and billions of relations for the facts of the world, they are still far from completeness, which results in that the prediction for new relations between entities according to the existing triplets in knowledge graph especially for the complex relations is an indispensable task of knowledge completion. Knowledge graph embedding has recently been regarded as an effective way of knowledge graph completion. In particular, the seminal model TransE [Bordes et al., 2013] has triggered increasing research in translation-based models for their simplicity and effectiveness. TransE first projects entities and relations onto low-dimension continuous spaces, formally as h, r, t ∈ Rk and then translates semantics from head to tail entities by relations, which requires h+ r ≈ t when triplet (h, r, t) holds. However, such a constraint is too strict to be practical in dealing with the complex relations of 1N, N-1 and N-N, and followup methods based on translation have been devised as improvements to overcome the shortcoming of TransE.

∗Yaohui Jin is corresponding author.

Specifically, TransH [Wang et al., 2014] interprets each relation as a translating operation on a hyperplane with a translation vector and a norm vector, and projects the entity vectors onto the hyperplane by the norm vector. However, TransR [Lin et al., 2015] supports that various relations focus on different aspects of entities which have multiple aspects. TransR first projects entities and relations onto entity spaces and relation spaces respectively, and then translates entities to relation spaces by a relational projection matrix. The method TransD [Ji et al., 2015] is based on the assumption that projection matrices of TransR should not be only related to relations but also to entities. While TranSparse [Ji et al., 2016] focuses on the heterogenenous which means some relations only link a few entity pairs but others not, and the unbalanced which means relations may link many head/tail entities and fewer tail/head entities, so that TranSparse sets parameters related the number of entities to the projection matrix. Gtrans [Tan et al., 2018], which does not believe that Trans (E, H, R and D) fully consider the complicacy of the entities, represents different semantic aspects of entities and relation respectively with two vectors.

Issues: Although these methods show improvements compared with previous methods, they have difficulty in dealing with the link prediction for complex relations, which we attribute to the following reasons:

i) They transform the entities embedding only by transmitting the semantics from relations to entities but not transmitting the semantics from head/tail entities to tail/head entities at the same time. Take Figure 1 for example, there are three right triplets: (tiger, eat,meat), (people, eat,meat) and (people, eat, fruit). These methods just transmit semantics from eat to people, tiger, fruit and meat while from the human cognition perspective, there are semantic transmissions between people and fruit, people and meat, tiger and fruit, tiger and meat, which may result in a wrong inference: (tiger, eat, fruit).

ii) They do not transform the relation embedding by transmitting the semantics from entities to relations neither. As in some academic, the triplets (h, r, t) could be regarded as the grammar structure of (subject, predicate, object), i.e. relation is the predicate owning an executor h and an enforcer t for each triplet, which means there are semantic transmissions from subject (h) and object (t) to predicate (r).

iii) They show poor scalability to the large-scale knowledge graph for having much more parameters than TransE. They usually have some additional vectors or matrices than TranE for each triplet, such as TransR having a additional projection matrix for each relation.

• iv) They transmit the semantics by linear transformation, which might be limited and shall be replaced by nonlinear transformation for better semantics translation.

v) From the mathematical point of view, when head/tail entity vector and relation vector are fixed, the left/right side of h⊥+r = t⊥ is fixed, i.e. no matter how linearly transform to get tail/head entity vector, the final tail/head entity vectors are distributing around one center, resulting in that tail/head entity vectors are close to each other when head/tail entity vector and relation vector are fixed.

To address these issues, we propose a novel method named TransMS which has merely one additional parameter α than TransE for each triplet as illustrated in Figure 2. First, entities are projected as ke-dimension vectors h, t ∈ Rke , relation as kr-dimension vectors r ∈ Rkr and a one-dimension variable α where ke = kr for each triplet (h, r, t) in our model. Then, we transform the tail entity embedding by transmitting the semantics from head entity h and relation r to tail entity t by a nonlinear function p(h, r), while transform the head entity embedding by transmitting the semantics from tail entity t and relation r to head entity h by p(-t, r) because it is in the opposite direction of relation. Due to the nonlinear transmissions from relation to entities, we just add a bias vector to the relation embedding r to prevent the nonlinear transmissions from canceling each other out, where the bias vector is α · g(h, t) related to both h and t. Therefore, our model not only conforms to human cognition in semantics, but also overcomes the shortcoming of one entity's vector learning around a center when the other entity and relation of a triplet are fixed in previous models.

Contribution: In general, the highlights of the paper are:

1. We propose a novel model TransMS that considers the semantic information not only from relations to entities, but also from the entities to relations and between entities;
2. ii) Our model has merely one additional parameter α than the simplest pioneered model (i.e. TransE) in contrast to peer methods having much more parameters for each triplet, such as TransR which has ke × kr more parameters than TransE, so our model has better scalability than the others;

iii) Our model has notable improvement on link prediction for complex relations against the baselines model, especially the Hit@10 for the head entity prediction for N-1 relations and the tail entity prediction for 1-N relations, which are improved by about 27.1% and 24.8% on FB15k [Bollacker et al., 2008], respectively.

2 RelatedWork

To facilitate the introduction of relate works, we briefly define notations used in this paper. We denote a triplet by (h, r, t), which belongs to knowledge graph, and their embedding vectors by the bold lower case letters (h, t, r); matrices by the bold upper case letters, such as M, and tensor whose dimension is no less than three by underlining the bold upper case letters, such as W. Score function is denoted by fr(h, t).

2.1 Translation-BasedMethods

TransE [Bordes et al., 2013]. As the seminal work for translation-based model, TransE first projects the triplets onto the low-dimension continuous space as h, r, t ∈ Rk , and then translates the semantics from head entities to tail entities by relations, formally as h + r ≈ t. Hence, the score function is fr(h, t) = ‖h + r - t‖ℓ1/2 . TransE is effective for simple 1-1 relations, but its strict constraint makes it less capable on complex relations (i.e. 1-N, N-1 and N-N).

TransH [Wang et al., 2014]. In order to overcome the shortcoming of TransE, TransH projects the entity embeddings h and t onto a relation-specific hyperplane to get h⊥ = h - w⊤ r hw and t⊥ = t - w⊤ r tw where w is a hyperplane normal vector, while the relation embedding is denoted as a translation vector r and a norm vector w. In this way, TransH enables every entity to have distributed embedding vectors corresponding to different relations. Finally, the score function of TransH turns into fr(h, t) = ‖h⊥ + r - t⊥‖ℓ1/2 .

TransR/CTransR [Lin et al., 2015]. TransE and TransH just project the entities and relations onto the same semantic space but not consider that every entity may have multiple attributes and different relations may focus on different attributes of entities. In this connection, TransH first

#Rel #Ent #Train #Valid #Test

FB15K 1,345 14,951 483,142 50,000 59,071

FB15K-237 237 14,541 272,115 17,535 20,466

18 40,943 141,442 5,000 5,000

WN18RR 11 40,943 86,835 3,034 3,134

projects the entities onto the entity embedding space different from the relation space onto which the relations are projected, and then the entity embedding vectors are projected onto the relation space by projection matrix Mr. Finally, the score function of TransR/CTransR turns into fr(h, t) = ‖Mrh + r - Mrt‖ℓ1/2 .

TransD [Ji et al., 2015]. Considering the diversity of both entities and relations at the same time, TransD sets vector-vector

multiplications to replace the projection matrix of TransR formally as Mh = rph⊤p +Ikr×ke for the head projection matrix where kr and ke are the dimension of relation and entity embedding vectors while the rp is related to relation r and hp is related to the head entity h, so that TranD has fewer parameters and better scalability for large-scale knowledge graph.

TranSparse [Ji et al., 2016]. In consideration of the heterogeneity of different relations and the unbalanced quantities of head and tail entities for each relation, TranSparse replaces the projection matrices with adaptive sparse matrices whose sparse degrees are determined by the number of entity pairs or entities linked by relations. Its score function turns into fr(h, t) = ‖Mhr (θh r )h + r - Mtr (θtr )t‖ℓ1/2 , where Mhr (θh r ) and Mtr (θtr ) are adaptive sparse matrices for head entity h and tail entity t going with relation r in each triplet (h, r, t) respectively. Here θh r and θh r are their sparse degrees.

GTrans [Tan et al., 2018]. GTrans supports that Trans (E, H, R and D) underestimate the complicacy of entities and do not fully describe semantics of entities and that relation is an abstraction of entity facts (h, t) as these models following the similar score function fr(h, t) = ‖h⊥ + r - t⊥‖ℓ1/2 . GTrans projects each entity onto two states - eigenstate and minesis which reflect its intrinsic and exogenous attributes respectively, formally as ha, he, ta, te, ra, re ∈ Rk .

2.2 Other Methods

Structured Embedding (SE) [Bordes et al., 2011]. For each relation r in triplet (h, r, t), SE projects head entities and tail entities by two different matrices Mhr and Mtr respectively. Its score function is fr(h, t) = ‖Mhr h -Mtr t‖ℓ1/2 .

Semantic Matching Energy (SME) [Bordes et al., 2012; Bordes et al., 2014]. SME first projects entities and relations onto low-dimension spaces, and then constructs a neural network which acquires correlations between entities and relations by matrix operations including the linear form whose score function is fr(h, t) = -(Mh1 eh + Mh2 r + bh)⊤(Mt1 et +Mr2 r + bt) and the bilinear form whose score function is fr(h, t) = -[(Mh1 eh) ⊗ (Mh2 r) + bh]⊤[(Mt1 et) ⊗ (Mt2 r) + bt] and ⊗ is Hadamard product.

Latent Factor Model (LFM) [Jenatton et al., 2012]. LFM projects entities as column vectors (h, t) and the relations into matrices Mr. Its score function is fr(h, t) = h⊤Mrt.

Single Layer Model (SLM) [Socher et al., 2013]. As a base model of Neural Tensor Network, the model SLM designs its score function as fr(h, t) = u⊤r tanh(Mr1h +Mr2t + br with a nonlinear neural network, where Mr1,Mr2, and br are parameters related to relation r.

Neural Tensor Network (NTN) [Socher et al., 2013]. To account for the second-order correlations, NTN extends the SLM by using nonlinear transformation neural networks. Its score function is fr(h, t) = u⊤r tanh(h⊤Wr t +Mr1h + Mr2t+br, whereMr1,Mr2, and br are parameters related to relation r besides Wr which is the 3-way tensor.

3 The ProposedMethod

3.1 Motivation

As mentioned in the introduction, the head entity of the triplet can be interpreted as subject, the relation as predicate and the tail entity as object. Hence we can easily get that what the head entity, tail entity and relation are to each triplet as what subject, object and predicate are to a subject-predicate sentence. Intuitively, there is not only semantic information from the relation r to the entities h (or t), but also between h and t for each triplet (h, r, t). Previous methods mainly consider the former semantic information, which results in their poor capability on link prediction for complex relations. To overcome this shortcoming, our method transmits the semantic information from both entities h (or t) and relations r to entities t (or h). In addition, we believe that nonlinear functions are more efficient than linear functions to translate semantics, so we use nonlinear functions to replace the linear functions p(r), formally as p(e, r) for the semantic transmission from both h and r to t and get final tail entity embedding vectors formally as t⊥ = P(p(h, r), t). Given that the semantic transmission from t to h is in the opposite direction of r, we define the semantic transmission function from t and r to h as p(-e, r) and get final head entity embedding vectors formally as h⊥ = P(p(-t, r), h).

In addition, it is common that every predicate r always owns its executors and enforcers, and subjects h are the executors of predicates while objects t are enforcers of predicates, so it is significant to transmit the semantic information from subjects h and objects t to predicates r. Although the semantic information of r is transmitted to h and t for each triplet respectively by the nonlinear function p(e, r), the semantic information of h and t is not transmitted to r. To carry out this transmission, we structure bias vectors which is defined as α·g(h, t) to r, where α is the one added dimension for relation and g(h, t) is the function related to both h and t and get final relation embedding vectors formally as r⊥ = G(r, α · g(h, t)). Figure 2 illustrates our approach.

In line with TransE, our model follows the similar translation-based constraint for triplet embedding vectors (h⊥, t⊥, r⊥): h⊥ + r⊥ ≈ t⊥, and the score function should be fr(h, t) = ‖r⊥ + h⊥ - t⊥‖ℓ1/2 .

3.2 The Proposed TransMS

Inspired by the above motivation, we propose a novel model named TransMS (translates and transmits multidirectional semantics) to deal with link prediction for complex relations (i.e. 1-N, N-1 and N-N relations). We first project every head entity h as an entity embedding vector h ∈ Rke , tail entity t as an entity embedding vector t ∈ Rke , and relation r as a relation vector r ∈ Rkr and a variable α ∈ R1 , while we can think of α as an added one dimension for relation embedding vectors where ke and kr + 1 are the dimension of entity and relation embedding vectors respectively, and ke = kr ≜ k in our model. Then, we transmit the semantic information from tail (or head) entities t (or h) and relations r to head (or tail) entities h (or t) by nonlinear functions p(e, r) ( or p(-e, r)). In particular, tanh is empirically found the optimal one in our experiments on function p(e, r) among {tanh, softmax, ReLu, atan, tan, sin, cos}. Hence, entity vectors with semantic information are specified as:

where ⊗ means the Hadamard product.

And then, we transmit the semantic information from head entities h and tail entities t to relations r by adding a bias vectors constructed with multiplying the Hadamard product between head vectors h ∈ Rk and tail vectors t ∈ Rk with α:

where · means the scalar multiplication.

Finally, the score function of our model is

The score is expected to be lower for golden triplets (the triplets from the knowledge graph) than for negative triplets (the triplets outside the knowledge graph).

3.3 Learning of TransMS

Before training, it is important to obtain negative triplets and devising the loss function. In our model, we set every triplet (hi, ri, ti) has a label yi which equals to 1 when the triplet is golden or -1 when the triplet is negative. And then, we denote the golden triplet set as D = {(hi, ri, ti)|yi = 1} and negative triplet set as D′ = {(h′i , ri, ti)|yi = -1} ⋃{(hi, ri, t′i )|yi = -1} where h′i or t′i is corrupted (but not both corrupted at the same time) by randomly sampling in two means: i) uniform sampling from all entities with the equal probability denoted as 'unif' as in [Bordes et al., 2013], and ii) Bernoulli sampling from all entities with different probabilities which depend on the projecting property of the relations denoted as 'bern' as in [Wang et al., 2014]. The embedding vector for each given entity is a uniquely projected vector whether it is head or tail entity.

We use the following margin-based ranking loss function for our training as in [Bordes et al., 2013].

where [x]+ :≜ max(0, x) aims to get the maximum between x and 0, and γ which is the margin separating golden and negative triplets could keep far from each other between golden and negative candidates. As in previous models, we enforce constraints on the normalization of vectors h, r, t. i.e. ∀(h, r, t) ∈ D ⋃ D′ , ‖h‖2 ≤ 1, ‖r1:k‖2 ≤ 1, ‖t‖2 ≤ 1.

We adopt Adam [Kingma and Ba, 2015] to minimize the above loss with additional sparse norm regularizer on entities'

embeddings. All embedding vectors for entities and relations are first initialized following the random procedure in [Glorot and Bengio, 2010]. Then, the entity embedding vectors e ∈ Rk and the relation embedding vectors r ∈ Rk are normalized at each main iteration except the additional dimension α. The set of golden triplets are randomly traversed multiple times followed by the construction of negative triplets.

Table 2 lists the score functions and the total number of parameters for some typical translation-based models and our model TransMS. It can be obviously seen that for each triplet, the number of parameters in our model is only one more than the simplest TransE while much fewer than the others, which indicates the cost-effectiveness of our approach.

4 Experiments and Analysis

4.1 Datasets and Protocols

We mainly evaluate our model on two typical knowledge graphs, which are built with WordNet [Miller, 1995] and Freebase [Bollacker et al., 2008] databases used in previous models. WordNet regarded as sysnets which groups English words into sets of synonyms is a lexical database for English. In this paper, we use one subset of WordNet: WN18 [Bordes et al., 2014], which has 40943 entities and 18 relations. Freebase is composed of general human knowledge. For instance, the triplet (Obama,was a president of,America), which means Obama was a president of America, is a fact in the real world. In this paper, we employ one subset of Freebase: FB15K [Bordes et al., 2014]. FB15K has 14951 entities and 1345 relations. WH18 and FB15K are two typical subsets of Knowledge graph as they have simple or complex relations respectively. In addition, we perform comparative experiments on the WN18RR [Dettmers et al., 2017] and FB15K-237 [Toutanova and Chen, 2015] datasets in contrast with ConvE [Dettmers et al., 2017] which is a deep learning model for knowledge graph embedding. FB15K237 which has 237 relations and 14541 entities is a subset of FB15K. WN18RR which has 11 relations and 40943 entities is a subset of WN18. The four databases consist of training, validation and testing sets which have been well constructed as Table 1.

We use link prediction for evaluation in line with [Bordes et al., 2013]. The prediction for new relations between head and tail entities when the head and tail entities are given is equivalent to the prediction for tail/head entities when the head/tail entities and relations are given.In knowledge graph, the purpose of link prediction is to predict head/tail entities when tail/head entities and relations are given. For example, for the triplet (Obama,was a president of,America) in Freebase, link prediction aims to predict missing head entity of (∗, was a president of ,America) or missing tail entity of (Obama,was a president of, ∗). Link prediction emphasizes the rank of the origin golden entity in knowledge graph but not focus on the best candidate entity as there may be more than one suitable candidate. In particular, there are two popular metrics: i) MeanRank. The mean rank of correct entities; ii) Hit@10. The ratio of correct entities ranked in top 10.

The MeanRank evaluation contains two parts. One is to evaluate the head entity prediction, the other is to evaluate the tail entity prediction. For the head entity prediction, the head entity for each triplet in testing set is first removed and replaced by the entities of entity set R to construct the corrupted triplets. Next, the scores of these corrupted triplets whose relations and tail entities are the same as each other are computed by the score function and sorted by ascending order. Then, the ranks of the correct entities are stored. Finally, the mean rank of head entity predictions is computed and denoted as MeanRank evaluation for the head entity prediction. The whole procedure is repeated while the tail entities are replaced instead of the head entities for the tail entity prediction. The final MeanRank is the average of the MeanRank for the head and tail entity prediction among all triplets in testing set. Generally, the better model is followed by the lower MeanRank.

As MeanRank, the Hit@10 evaluation also has two parts: evaluation for the head entity prediction and evaluation for the tail entity prediction. For the head entity prediction, we count the number of the correct head entities ranked in top 10, and then the number is divided by the total number of triplets in testing set. The ratio is denoted as Hit@10 evaluation for the head entity prediction. Similarly, the Hit@10 evaluation for the tail entity prediction is calculated with the same method, and the final Hit@10 is the average of the Hit@10 for the head and tail entity prediction among all triplets in testing set. Generally, the higher Hit@10 means the better model, the higher Hit@10 is followed by the lower MeanRank. It is a flaw that the MeanRank evaluation will be abnormal as there are abnormal ranks of correct triplets such that the Hit@10 is the better metric than the MeanRank.

In addition, given that some corrupted triplets ranked above the right triplets in testing set may be golden ones in training, validation or testing sets, the MeanRank and Hit@10 should be divided into two types: One is the Filter representing statistics that the correct triplets belonged to training, validation or testing sets are first filtered out from the corrupted triplets and then the scores of another corrupted triplets are ranked, the other is the Raw representing the original statistics that scores of all corrupted triplets are ranked.

We conduct experiments on four knowledge graph subsets: WN18, FB15k, WN18RR and FB15K-237, and compare with methods listed in Table 2 and ConvE. We directly report the results of those methods from the literature as in [Wang et al., 2014; Ji et al., 2016; Zhang, 2017; Dettmers et al., 2017; Tan et al., 2018]. We conduct 200 iterations of training on FB15k-237 and 500 iterations of training on the other three databases. The learning rate β for Adam is set among {0.1, 0.01, 0.001}, the margin γ among {1.0, 1.5, 2.0, 4.0}, the dimension of vectors d among {50, 100, 150, 200}, the minibatch size b among{200, 1200, 4800} and additional regularizers among {ℓ1, ℓ2}. For both WN18 and FB15K, the optimal configurations are: β = 0.001, γ = 2.0, d = 200, b = 4800 and L = ℓ1 on both corrupted means: 'unif' and 'bern', which are same as the optimal configurations of WN18RR and FB15K-237 on 'unif'.

4.2 Results and Analysis

Experimental results on both FB15K and WN18 are shown in Table 3. On FB15K, by the means of both 'unif' and 'bern', our model improves Hit@10 and MeanRank with both Raw method and Filter methods, especially our model performs better than the SE, SME and Trans(E, H, R) which are usually used as comparison because they have better scalability than the others, while on WN18, our model improves Hit@10 with Raw and Filter methods.

Regarding Hit@10 for diverse relations, Table 4 lists the results by projecting properties of relations on FB15K. We can find that Hit@10s of the head prediction are improved for 1-1, N-1 and N-N relations by the means of 'unif' while improved for 1-1 and N-1 relations by the means of 'bern', and the Hit@10s of the tail prediction are improved for 1-1, 1-N and N-N relations by the means of 'unif' while improved for 1-1 relations by the means of 'bern'. There are significant improvements for the Hit@10 of the head prediction for N1 relations and the tail prediction for 1-N relations by about 27.1% and 24.8% respectively while both predictions always are the tough nut to crack for long time.

In Table 3, TransMS outperforms the peer methods except the MeanRank metric on WN18. We get the more Hit results showed in Figure 3, which reveales that the results of entity prediction are mainly distributed in Hit@20 and there are less than 5% outside the Hit@20. Therefore, it is reasonable for the worse MeanRank on WN18 because the MeanRank will fluctuate abnormally as abnormal ranks of corrupted triplets.

Experimental results on both FB15K-237 and WN18RR are shown in Table 5. It can be seen that our model performs better than ConvE on WN18RR as MeanRank on FB15K237 while the Hit@10 is only slightly lower than ConvE on FB15K-237. Given that ConvE is modelled by fullyconnected and convolutional layers, our model not only has better scalability than ConvE but also has similar performance to ConvE.

In addition, we also evaluate our model on FB15K and WN18 datasets when the parameter γ changes according to relations or is a constant for different relations. In these experiments, the hyperparameters remain equal as in the part Datasets and Protocols. As we can see from the results listed in Table 6, the performance will be better when the parameter γ varies with relations than when α keeps a same value for different relations.

There are two relations with top-5 similar relations on cosine similarity metric by relation embedding vectors respectively in Table 7. We can find that such candidate symbolic relations have similar semantics to the base relations. These results indicate that the semantic translations among head entities, tail entities and relations are significant for the knowledge graph representation.

5 Conclusion

We have presented a novel model named TransMS that takes the multidirectional semantic information into account. Our model transmits i) the semantics from the head/tail entity and relation to the tail/head entity by a nonlinear function and ii) the semantics from entities to relation by adding a bias vector to relation embedding vector for each triplet. TransMS has better scalability than the peer models because it only has one more parameter than the simplest translation-based embedding model (i.e. TransE) but fewer than the others. In future, we will explore the best methods to translate semantics within triplets to improve the performance of link prediction for complex relations in large-scale knowledge graphs.

Acknowledgements

This work is supported by National Key Research and Development Program of China (2018YFC0830400), (2016YFB1001003) and STCSM(18DZ1112300).