A System for Reasoning-based Link Prediction in Large Knowledge Graphs

Abstract

This poster paper presents an e cient method R-Linker for link prediction in large knowledge graphs, based on rule learning. The scalability and e ciency is achieved by a combination of several optimisation techniques. Experimental results show that R-Linker is able to handle KGs with over 10 million of entities and more e cient than existing state-of-the-art methods including RLvLR and AMIE+ in rule learning stage for link prediction.

Introduction

In this poster paper, we further push the envelope by developing a more e cient method R-Linker for R-link prediction in large KGs. The scalability and e ciency of R-Linker is achieved by a combination of several optimisation techniques. First, we use an adapted embedding for rule learning; Second, we introduce a new strategy of sampling called Hierarchical Sampling ; Moreover, we develop new techniques of rule search and rule evaluation. As a result, we have implemented a new system R-Linker for link prediction with large KGs. Our experiments show that R-Linker is able to handle KGs of size over 10M and more e cient than other methods including RLvLR and AMIE+ in rule learning stage for link prediction. R-Linker is available at https: //www.dropbox.com/sh/c8ent25u3qp4vp1/AABc6Jl3zTRtOkdTwHaoDBDUa?dl=0 2

A Rule-based Model

Unlike other statistical relational models, we adopt rule-based models for link prediction, with the obvious advantage that the learned models (as sets of logical rules) are explainable and reusable. In what follows, we describe how we construct such models. 2.1 Embedding-based Rule Selection Inspired by [ 6 ], we learn such rule-based models via predicate embeddings; yet unlike [ 6 ] using matrix embeddings, we adopt TransE vector embeddings which can signi cantly improve learning e ciency. As we demonstrate in the experiments, adopt a simpler form of embeddings does not compromise the learning accuracy. In [ 2 ], vector embeddings r and e are constructed for each relation R and each entity e in the KG. When a fact R(e; e0) exists in the KG, the embeddings satisfy e + r e0. We extend it to an embedding characterisation for closed-path rules, that is, rst-order Horn rules of the form R1(x; z1) ^ R2(z1; z2) ^ : : : ^ Rn(zn 1; y) ! R(x; y) with x; y; z1; : : : ; zn 1 being variables. There are two aspects we hope to capture: (1) the composition of relations R1; : : : Rn associates entities (in place of x and y) similarly as relation R does; and (2) the co-occurrence of arguments in the positions of x; y; z1; : : : ; zn 1.

For (1), it requires for each pair of entities (e; e0), e+r1+ +rn e0 e+r e0. We de ne a measure sim(r1 + + rn; r); where sim is the L2 norm of vector distances. For (2), we use the notion of argumentation embeddings from [ 6 ]. More speci cally, for each relation R, two vector embeddings r1 and r2 are computed by averaging the entity embeddings (as vectors) of all the entities occurring in the position of respectively, the subject and object arguments of R. Then, for x occurring as the subject arguments of both R1 and R, y occurring as the object argument of both Rn and R, and zi (1 i n 1) occurring as the object argument of Ri and subject argument of Ri+1, we have the following measure sim(r11; r1) + sim(r2n; r2) + sim(r21; r12) + + sim(r2n 1; r1n): 2.2

Hierarchical Data Sampling A major challenge in the computation of embeddings is that existing methods cannot scale over large KGs, even for vector embeddings. Hence, we propose a new data sampling strategy, called hierarchical sampling, to reduce the sizes of input KGs by A System for Reasoning-based Link Prediction in Large Knowledge Graphs focusing on entities that are relevant to the link prediction task. Intuitively, for each link prediction task, the link (i.e., a relation) R is often given, and we sample entities (and facts) in the KG that are directly or indirectly related to R for embedding construction.

Consider a KG K = (E; F ) with E being the set of all entities and F being the set of all facts (i.e., triples) in K. Our sampling method selects a (small) subset E0 E that are relevant to R and focus on the facts F 0 only about E0 (not mentioning other entities). Since each rule in our model forms a path, our sampling method also deploys a breath- rst tree search. As shown in Figure 1 (a), the rst sampled entities E0 are those occurring in facts about R. Then, E1 are those entities that occur in any facts (not necessarily about R) mentioning entities from E0. Similarly, Ei+1 are those entities that occur in any facts mentioning entities from Ei, for each i 1 till a prescribed depth.

= 2 R1

R1 1 2 1 = 3

1 2 2

1 = 4 quite e ective. We compared our system with RLvLR, AMIE+ and Neural LP on rule learning and link prediction, on common benchmarks FB15K(-237), Wikidata, DBPedia 3.8, and YAGO2s.

For large KGs Wikidata, DBPedia 3.8, and YAGO2s, Table 1 shows our system outperforms both RLvLR and AMIE+ in learning e ciency, as shown by the average numbers of rules (#R) and quality rules (#QR, standard con dence over 0.7) learned per hour.

FB75K Wikidata Learner

MRR Hits@10 MRR Hits@10 R-Linker 0.37 59.0 0.33 39.3 RLvLR 0.34 43.4 0.29 38.9 Neural LP 0.13 25.7 -

References

1. Nickel , M. , Murphy , K. , Tresp , V. , Gabrilovich , E.: A Review of Relational Machine Learning for Knowledge Graph . Proceedings of IEEE , 1041 , 1 - 23 ( 2016 ).

2. Antoine , B. , Nicolas , U. , Alberto , G.D. , Jason , W. , Oksana , Y. : Translating embeddings for modeling multi-relational data . In: NIPS 26 , pp. 2787 { 2795 ( 2013 ).

3. Chen , Y. , Wang , D.Z. , Goldberg , S. : Scalekb: scalable learning and inference over large knowledge bases . The VLDB Journal 25 ( 6 ), 893 { 918 ( 2016 ).

4. Galarraga , L.A. , Te ioudi , C. , Hose , K. , Suchanek , F.M. : Fast rule mining in ontological knowledge bases with amie+ . The VLDB Journal 24 ( 6 ), 707 { 730 ( 2015 ).

5. Ho , V.T., Stepanova , D. , Gad-Elrab , M.H. , Kharlamov , E. , Weikum , G.: Rule learning from knowledge graphs guided by embedding models . In Proc. ISWC pp. 72 { 90 ( 2018 )

6. Omran , P.G. , Wang , K. , Wang , Z. : Scalable rule learning via learning representation . In Proc. AAAI , pp. 2149 { 2155 ( 2018 ).

7. Garc a-Duran, A. , Niepert , M. : Blrn: End-to-end learning of knowledge base representations with latent, relational, and numerical features . In: Proc. UAI , pp, 372 - 381 ( 2018 ).