Multiple Run Ensemble Learning with Low Dimensional Knowledge Graph Embeddings

Abstract

Knowledge graphs (KGs) represent facts about a domain in a structured form. Although KGs can be quantitatively huge and consist of millions of triples, their coverage is usually still only a small fraction of the available knowledge. Among the most promising recent approaches for tackling this incompleteness problem is link prediction using knowledge graph embedding models. Various embedding models have been proposed so far, among which, the RotatE model is reported to obtain stateof-the-art performance in such link prediction tasks. However, RotatE mainly outperforms other models when using a high embedding dimension (e.g. 1000). In this paper, we simulate such scenarios by studying the performance of different models using multiple low dimensions in different repetition rounds of the same model. For example, our studies show better results when instead of training a model one time with a high dimension of 1200, we repeat the training of the model 6 times in parallel with dimension of 200 and then combine the 6 models, This can improve results while maintaining the overall number of adjustable parameters is the same. In order to justify our findings, we perform experiments on various models including TransE, DistMult, RotatE and ComplEx. Experimental results on standard benchmark dataset show that multiple low-dimensional models outperform a single high dimensional model while the overall number parameters is same.

Keywords

• Graph Embedding
• Ensemble Learning
• Link Prediction

-

The advent of knowledge graph (KG) technology has propelled knowledge representation to the next level and influenced the untimate results of several AI-based applications such as question answering and recommendation systems [ 14,9 ]. Several KGs such as WordNet [ 8 ], FreeBase [ 2 ], and YAGO [ 10 ], have been published with different utilization purposes. In recent years, KG technology combined with the recent advances of hardware technologies such as GPU processing. Therefore, a new horizon for using machine learning approaches on structured data at scale has been opened up for leading science and industry.

Despite the advantages of KGs in down stream tasks, one of the main challenges of existing KGs is their incompleteness [ 11 ]. KG completion using link prediction approaches aims at addressing this problem. Among various link prediction approaches, KG embedding (KGE) has gained significant attention recently. A KGE model takes a KG in the form of triple facts (h, r, t) where h, t are entities (nodes) and r is a relation (link) between the entities. A d dimensional vector is then assigned to each element of a triple (h, r, t) in a KG and adjusts the vectors by optimizing a loss function. The likelihood of a triple is then measured by using a score function over the embedding vectors (h, r, t).

The score functions of models play an important role in the performance of the KGEs. After early proposals of novel KGE models, the research field has continued by designing and publishing new models with a focus on score functions. Among those, TransE is one of the primary models which computes the score of a triple by measuring the distance between the tail vector and the relation-specific translated head (i.e. h + r ≈ t). Several variants of TransE such as TransR [ 7 ], TransH [ 15 ], and TransD [ 4 ] have been proposed later to address the limitations of the original model such as the problem of not being able to encode one to N, symmetric and reflexive relations.

One of the recent state-of-the-art models is RotatE [ 12 ] which utilizes rotation in complex space to compute the score of triples. The rotation is performed from each element of the head vector by using relation specific angle to each element of the tail vector i.e. h ◦ r ≈ t (◦ is element-wise complex multiplication which induces rotation in complex space). The evaluations reported in the initial work introducing RotatE [ 12 ] as well as the ones studied afterwards [ 1 ], shows that RotatE obtains state-of-the-art in link prediction tasks by using a relatively high dimension (1000 on freebase datasets). QuatE [ 17 ] is another KGE model that outperforms other models by taking the advantage of quaternion space that contains four elements. Similar to RotatE, the high performance of QuatE is achieved by using an embedding dimension of 1000. Due to the quaternion design of ths model, the best performing setting with this high dimension results in 4000 adjustable parameters. A similar fact is observable in the ComplEx model which gets a high accuracy with dimension 1000 [ 6 ].

Such observations led us to a systematic evaluation of the state-of-the-art models that shows in most of these works, first a high dimension and, second multiple vectors for each entity/relation due to using either complex (with two elements of real and imaginary) or quaternion (with four elements) space. In other words, all the above-mentioned models use single model with a multi-part high dimensional embeddings (number of parameters is 1 × dh). In contrast to those models, we use the same model multiple (k) times in parallel trainings with low dimension (number of parameters is k × dl). In order to have a fair comparison, we enforce (1 × dh = k × dl). The experimental results show that the ensemble of the same model several times trained with low-dimensions, results in a better performance than training that model once with a high dimension while the overall numbers of adjustable parameters are same. 2

Related Work

Here we review the existing KGE models including TransE, RotatE, ComplEx, and DistMult. Each model defines a score function f (h, r, t) which takes the triple embeddings (h, r, t) and returns the degree of correctness of the triple. TransE [ 3 ] Given a triple (h, r, t), the TransE model computes the score by measuring the distance between relation-specific translated head (h + r) and the tail t as f (h, r, t) = −kh + r − tk to enforce h + r ≈ t (h, r, t ∈ Rd) for each positive triple (h, r, t) in the vector space.

RotatE [ 12 ] RotatE aims at mapping each element of the head embedding (hi) to the corresponding tail embedding ti by using relation-specific rotation ri = eiθ. The score of each triple (h, r, t) is computed as f (h, r, t) = −kh ◦ r − tk where h, r, t ∈ Cd. This enforces h ◦ r ≈ t for each positive triple (h, r, t). DistMult [ 16 ] captures the interaction between elements that has the same index in h and t. The formulation of score function is fr(h, t) = h>diag(r)t = Pid=0 ri · hi · ti The model captures symmetric relation, but not antisymmetric. CompEx [ 13 ] was proposed as a more elegant way to solve the shortcoming of DistMult in modeling antisymmetric relation. Its main contribution is to embed KGs in complex space. The score function is defined as f (h, r, t) = Re(hr, h, ¯ti) where r, h, t ∈ Cd. Although effective, ComplEx is not expressive enough to model composition relations [ 12 ].

Several surveys have been reviewed the existing KGEs and reported about their performance from different aspects and settings. In [ 5 ], a set of KGEs combined evaluations have been done for multiple models and settings. It lifts the models intro one score function and combines them during the training phase, however, we focus on stretching and squeezing the dimensions of the same models which are trained separately and combined for testing. 3

Proposed Approach

Recent models such as RotatE, ComplEx, and QuatE obtain state-of-the-art performances in link prediction. They go beyond the real space and embed a KG into a Complex or Quaternion space. Therefore, the embedding vectors contain two (complex) or four (quaternion) parts. Consequently, designing KGE models with specific embeddings containing multiple parts (complex vectors with real and imaginary parts) has been shown to be effective in performance boosting. Based on this, we initiated the methodology of this research as follows: Hypothesis 1. Multiple combined slices of a KGE model in low-dimensions perform better than a single version of that model in high dimensions.

Our aim is to provide evidences in order to evaluate the hypothesis.

In contrast to the mentioned model which uses a single model with high dimension, in this part we propose a new approach which combines multiple models of the same type in which each model contains low-dimensional embeddings. Therefore, the overall number of adjustable parameters remains the same compared to the approaches using a single model with high dimensions. In order to formulate this scenario, let us have a model M (e.g. RotatE) with embedding dimension dl. We follow the steps below in our approach: (a) We first generate k times copies of an underlying model M. The jth slice of the model is denoted by Mj, j = 1, . . . , k, and the corresponding dl dimensional embeddings of (h, r, t) are denoted by (hj, rj, tj). The vectors are randomly initialized in the beginning of learning process. (b) We then train each of the models Mj, j = 1, . . . , k separately. (c) Finally, the testing is performed by using the following score function k f (h, r, t) = X fMj (hj, rj, tj), j=1 (1) where fMj (hj, rj, tj) is the score of a triple (h, r, t) computed by the jth copy of the model.

Note that all models are trained on a same KG and the only difference between the models is the initialization of the embedding vectors. To have a fair comparison with original models, we keep the overall number of adjustable parameters (embeddings) equal when comparing with the original single model, i.e. dh = k×dl. We will later show in the evaluation part that such a simple approach improves the performance of KGEs without additional cost. 4

Experiments

Dataset We use FB15k and FB15k-237 for evaluation. FB15k contains 483,142 triples in training set, 50,000 and 59,071 in validation and test set respectively. FB15k-237 contains 272,115, 17,535 and 20,466 triples in the training, validation and testing set respectively.

Evaluation Metric We use Mean Reciprocal Rank (MRR) and Hist@n (n=1,3,10) for evaluation. The detail process of computing these metrics can be found in [ 3 ]. Experimental Setup we evaluate our proposed approach by training TransE, RotatE, DistMult and ComplEx in both single model with high dimension and multiple models with low dimension. For single models with high dimensions, we set embedding dimension to dh = {2, 4, 6, 8, 10, 12} × 100. For models sliced in multiple versions with low dimensions, we set the number of models to k = 2, . . . , 6 and dimension dl = 200. Note that each single mode e.g. RotatE with dimension dh is compared with multiple models e.g. CRotatE (combination of k = 6 RotatE models) with dimension dl. Therefore the number of parameters in both models are the same i.e. k × dl = 1 × dh e.g. 6 × 200 = 1 × 1200. The implementation has been done by using Pytorch on GPU servers. We use RotatE loss for the models in the table 1. We use uniform negative sampling with only one negative sample.

Model

Results Results are shown in Table 1 and Table 2. Table 1 presents the results on FB15k and FB15k-237. As can be seen, multiple models with low dimension (started with "C" such as CTransE) outperforms single models with high dimensions. For example, on FB15K, the single ComplEx model with dimension 800 obtains 0.698, 0.585, 0.789 and 0.864 respectively on MRR, Hist@1,3,10 respectively. Whereas CComplEx with k = 4, dl = 200 obtains 0.705, 0.583, 0.807, 0.882. Therefore, in all metrics except Hits@1 CComplEx outperforms ComplEx while both of the models use same number of parameters (4 × 200 = 1 × 800). 5

Conclusion

In this paper, we compare performance of a single model using high dimension with multiple combined models using low dimension (for each model). Our experimental evaluation on FB15k and FB15k-237 show that instead of using a single model with dh dimension, using k models with dl = dh/k dimension results in a higher accuracy.

Acknowledgement This work is supported by the EC Horizon 2020 grant LAMBDA (GA no. 809965), the CLEOPATRA project (GA no. 812997), and the German national funded BmBF project MLwin.

References

1. F. Akrami , M. S. Saeef , Q. Zhang , W. Hu, and C. Li . Realistic re-evaluation of knowledge graph completion methods: An experimental study . In Proceedings of the 2020 ACM SIGMOD International Conference on Management of Data , pages 1995 - 2010 , 2020 .

2. K. Bollacker , C. Evans , P. Paritosh , T. Sturge , and J. Taylor . Freebase: a collaboratively created graph database for structuring human knowledge . In Proceedings of the 2008 ACM SIGMOD international conference on Management of data , pages 1247 - 1250 . AcM, 2008 .

3. A. Bordes , N. Usunier , A. Garcia-Duran , J. Weston , and O. Yakhnenko . Translating embeddings for modeling multi-relational data . In Advances in neural information processing systems , pages 2787 - 2795 , 2013 .

4. G. Ji , S. He , L. Xu , K. Liu , and J. Zhao . Knowledge graph embedding via dynamic mapping matrix. In Proceedings of the 53rd annual meeting of the association for computational linguistics and the 7th international joint conference on natural language processing (volume 1: Long papers ), pages 687 - 696 , 2015 .

5. D. Krompaß and V. Tresp . Ensemble solutions for link-prediction in knowledge graphs . In Proceedings of the 2nd Workshop on Linked Data for Knowledge Discovery , Porto, Portugal, pages 1 - 10 , 2015 .

6. T. Lacroix , N. Usunier , and G. Obozinski . Canonical tensor decomposition for knowledge base completion . arXiv preprint arXiv:1806.07297 , 2018 .

7. Y. Lin , Z. Liu , M. Sun , Y. Liu , and X. Zhu . Learning entity and relation embeddings for knowledge graph completion . In Twenty-ninth AAAI conference on artificial intelligence , 2015 .

8. G. A. Miller . Wordnet: a lexical database for english . Communications of the ACM , 38 ( 11 ): 39 - 41 , 1995 .

9. M. Nickel , K. Murphy , V. Tresp , and E. Gabrilovich . A review of relational machine learning for knowledge graphs . Proceedings of the IEEE , 104 ( 1 ): 11 - 33 , 2015 .

10. M. Nickel , V. Tresp , and H.-P. Kriegel . Factorizing yago: scalable machine learning for linked data . In Proceedings of the 21st international conference on World Wide Web , pages 271 - 280 . ACM, 2012 .

11. H. Paulheim . Knowledge graph refinement: A survey of approaches and evaluation methods . Semantic web , 8 ( 3 ): 489 - 508 , 2017 .

12. Z. Sun , Z.-H. Deng , J.-Y. Nie , and J. Tang . Rotate: Knowledge graph embedding by relational rotation in complex space . arXiv preprint arXiv:1902.10197 , 2019 .

13. T. Trouillon , J. Welbl , S. Riedel, É. Gaussier, and G. Bouchard . Complex embeddings for simple link prediction . In International Conference on Machine Learning , pages 2071 - 2080 , 2016 .

14. Q. Wang , Z. Mao , B. Wang , and L. Guo . Knowledge graph embedding: A survey of approaches and applications . IEEE Transactions on Knowledge and Data Engineering , 29 ( 12 ): 2724 - 2743 , 2017 .

15. Z. Wang , J. Zhang , J. Feng, and Z. Chen . Knowledge graph embedding by translating on hyperplanes . In Aaai , volume 14 , pages 1112 - 1119 , 2014 .

16. B. Yang , W.-t. Yih, X. He , J. Gao , and L. Deng . Embedding entities and relations for learning and inference in knowledge bases . arXiv preprint arXiv:1412.6575 , 2014 .

17. S. Zhang , Y. Tay , L. Yao , and Q. Liu . Quaternion knowledge graph embeddings . In Advances in Neural Information Processing Systems , pages 2735 - 2745 , 2019 .