summaries: The work utilizes relational background knowledge contained in logical rules to conduct multi-relational reasoning for knowledge graph (KG) completion. This is different from the superficial vector triangle linkage used in embedding models. It solves the KG completion task through rule-based reasoning rather than using rules to obtain better embeddings. Experiments on FB15K, WN18, and a new dataset FB15K-R demonstrate the effectiveness of the proposed model EM-RBR.  The paper seek to improve KG representation (e.g. for link prediction and question answering) by combining logical reasoning (logical rule templates) with statistical methods (TransE). Rules are mined from the KG using AMIE and recursive backward steps are taken, using the mined rules, to determine if a fact is true. The paper proposes a framework (EM-RBR) for doing Knowledge Base (KB) completion. Instead of the direct triple score from an embedding based method, EM-RBR allows the triple score to be calculated as a composition of the scores of the rules mined from the KB. EM-RBR uses a BFS type algorithm that recursively searches for reasoning paths connecting the triple while also updating the score.  The authors show that EM-RBR when used as an addendum to a translation-based embedding method (such as TrasnE, TransH) is able to outperform them. They show their results on FB15k and WN18. 
abstractText: Knowledge graph completion aims to predict the missing links among the knowledge graph (KG),i.e., predicting the possibility that a certain triple belongs to the knowledge graph. Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. Limited to the modeling of algebraic space, contradictory in expressing certain relational patterns usually exists in the embedding models. Therefore, the representation of the knowledge graph is incomplete and inaccurate. To solve this problem, in this paper, we propose a general framework, named EM-RBR(embedding and rulebased reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-art models of embedding. EM-RBR aims to utilize relational background knowledge contained in rules to conduct multi-relation reasoning link prediction. In this way, we can find the most reasonable explanation for a given triplet to obtain higher prediction accuracy. In experiments, we demonstrate that EM-RBR achieves better performance compared with previous models on FB15k, WN18 and our new dataset FB15k-R, especially the new dataset where our model perform futher better than those state-of-the-arts. We make the implementation of EM-RBR available at https://github.com/1173710224/ link-prediction-with-rule-based-reasoning.
references.authors: Antoine Bordes Jason Weston Ronan Collobert Yoshua Bengio
references.title: Learning structured embeddings of knowledge bases
references.venue: In Twenty-Fifth AAAI Conference on Artificial Intelligence,
references.authors: Antoine Bordes Nicolas Usunier Alberto Garcia-Duran Jason Weston Oksana Yakhnenko
references.title: Translating embeddings for modeling multi-relational data
references.venue: In Advances in neural information processing systems,
references.authors: Antoine Bordes Xavier Glorot Jason Weston Yoshua Bengio
references.title: A semantic matching energy function for learning with multi-relational data
references.venue: Machine Learning,
references.authors: Rajarshi Das Shehzaad Dhuliawala Manzil Zaheer Luke Vilnis Ishan Durugkar Akshay Krishnamurthy Alex Smola Andrew Mccallum
references.title: Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning
references.authors: Rajarshi Das Shehzaad Dhuliawala Manzil Zaheer Luke Vilnis Ishan Durugkar Akshay Krishnamurthy Alexander J. Smola Andrew McCallum
references.title: Go for a walk and arrive at the answer: Reasoning over paths in knowledge bases using reinforcement learning
references.venue: CoRR, abs/1711.05851,
references.authors: Tim Dettmers Pasquale Minervini Pontus Stenetorp Sebastian Riedel
references.title: Convolutional 2d knowledge graph embeddings
references.venue: AAAI Conference on Artificial Intelligence (AAAI-18),
references.authors: Xin Dong Evgeniy Gabrilovich Geremy Heitz Wilko Horn Ni Lao Kevin Murphy Thomas Strohmann Shaohua Sun Wei Zhang
references.title: Knowledge vault: A web-scale approach to probabilistic knowledge fusion
references.venue: In Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining,
references.authors: Luis Antonio Galárraga Christina Teflioudi Katja Hose Fabian Suchanek
references.title: Amie: association rule mining under incomplete evidence in ontological knowledge bases
references.venue: In Proceedings of the 22nd international conference on World Wide Web,
references.authors: Matt Gardner Partha Talukdar Jayant Krishnamurthy Tom Mitchell
references.title: Incorporating vector space similarity in random walk inference over knowledge bases
references.venue: In Proceedings of the 2014 conference on empirical methods in natural language processing (EMNLP),
references.authors: Jens Graupmann Ralf Schenkel Gerhard Weikum
references.title: The spheresearch engine for unified ranked retrieval of heterogeneous xml and web documents
references.authors: Shu Guo Quan Wang Lihong Wang Bin Wang Li Guo
references.title: Jointly embedding knowledge graphs and logical rules
references.venue: In Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing,
references.authors: Shu Guo Quan Wang Lihong Wang Bin Wang Li Guo
references.title: Knowledge graph embedding with iterative guidance from soft rules
references.venue: arXiv preprint arXiv:1711.11231,
references.authors: Frank L Hitchcock
references.title: The expression of a tensor or a polyadic as a sum of products
references.venue: Journal of Mathematics and Physics,
references.authors: Raphael Hoffmann Congle Zhang Xiao Ling Luke Zettlemoyer Daniel S. Weld
references.title: Knowledgebased weak supervision for information extraction of overlapping relations. In Proceedings of the 49th Annual Meeting of the Association for Computational Linguistics: Human Language Technologies - Volume 1, HLT
references.authors: Guoliang Ji Shizhu He Liheng Xu Kang Liu Jun Zhao
references.title: Knowledge graph embedding via dynamic mapping matrix
references.venue: 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),
references.authors: Rudolf Kadlec Ondrej Bajgar Jan Kleindienst
references.title: Knowledge base completion: Baselines strike back
references.venue: arXiv preprint arXiv:1705.10744,
references.authors: Seyed Mehran Kazemi David Poole
references.title: Simple embedding for link prediction in knowledge graphs
references.venue: In Advances in neural information processing systems,
references.authors: Stanley Kok Pedro Domingos
references.title: Statistical predicate invention
references.venue: In Proceedings of the 24th international conference on Machine learning,
references.authors: Timothée Lacroix Nicolas Usunier Guillaume Obozinski
references.title: Canonical tensor decomposition for knowledge base completion
references.venue: In ICML,
references.authors: Ni Lao William W. Cohen
references.title: Relational retrieval using a combination of path-constrained random walks
references.venue: Mach. Learn.,
references.authors: Ni Lao Tom Mitchell William W Cohen
references.title: Random walk inference and learning in a large scale knowledge base
references.venue: In Proceedings of the Conference on Empirical Methods in Natural Language Processing,
references.authors: Hailun Lin Yong Liu Weiping Wang Yinliang Yue Zheng Lin
references.title: Learning entity and relation embeddings for knowledge resolution
references.venue: Procedia Computer Science,
references.authors: Yankai Lin Zhiyuan Liu Maosong Sun Yang Liu Xuan Zhu
references.title: Learning entity and relation embeddings for knowledge graph completion
references.venue: In Twenty-ninth AAAI conference on artificial intelligence,
references.authors: Tomas Mikolov Ilya Sutskever Kai Chen Greg S Corrado Jeff Dean
references.title: Distributed representations of words and phrases and their compositionality
references.venue: In Advances in neural information processing systems,
references.authors: Dai Quoc Nguyen Tu Dinh Nguyen Dat Quoc Nguyen Dinh Phung
references.title: A novel embedding model for knowledge base completion based on convolutional neural network
references.venue: arXiv preprint arXiv:1712.02121,
references.authors: Dat Quoc Nguyen
references.title: An overview of embedding models of entities and relationships for knowledge base completion
references.venue: arXiv preprint arXiv:1703.08098,
references.authors: Maximilian Nickel Volker Tresp Hans-Peter Kriegel
references.title: A three-way model for collective learning on multi-relational data
references.venue: In Icml,
references.authors: Meng Qu Jian Tang
references.title: Probabilistic logic neural networks for reasoning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Tim Rocktäschel Sameer Singh Sebastian Riedel
references.title: Injecting logical background knowledge into embeddings for relation extraction
references.venue: In Proceedings of the 2015 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies,
references.authors: Ali Sadeghian Mohammadreza Armandpour Patrick Ding Daisy Zhe Wang
references.title: Drum: End-toend differentiable rule mining on knowledge graphs
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Richard Socher Danqi Chen Christopher D Manning Andrew Ng
references.title: Reasoning with neural tensor networks for knowledge base completion
references.venue: In Advances in neural information processing systems,
references.authors: Zhiqing Sun Zhi-Hong Deng Jian-Yun Nie Jian Tang
references.title: Rotate: Knowledge graph embedding by relational rotation in complex
references.venue: space. CoRR,
references.authors: Kristina Toutanova Danqi Chen
references.title: Observed versus latent features for knowledge base and text inference
references.venue: In The 3rd Workshop on Continuous Vector Space Models and their Compositionality,
references.authors: Théo Trouillon Johannes Welbl Sebastian Riedel Éric Gaussier Guillaume Bouchard
references.title: Complex embeddings for simple link prediction
references.authors: Pengwei Wang Dejing Dou Fangzhao Wu Nisansa de Silva Lianwen Jin
references.title: Logic rules powered knowledge graph embedding
references.authors: William Yang Wang William W Cohen
references.title: Learning first-order logic embeddings via matrix factorization
references.venue: In Ijcai,
references.authors: Zhen Wang Jianwen Zhang Jianlin Feng Zheng Chen
references.title: Knowledge graph embedding by translating on hyperplanes
references.venue: In Twenty-Eighth AAAI conference on artificial intelligence,
references.authors: Evgenia Wasserman Pritsker William Cohen Einat Minkov
references.title: Learning to identify the best contexts for knowledge-based WSD
references.venue: In Proceedings of the 2015 Conference on Empirical Methods in Natural Language Processing,
references.authors: Wenhan Xiong Thien Hoang William Yang Wang
references.title: Deeppath: A reinforcement learning method for knowledge graph reasoning
references.authors: Bishan Yang Wen-tau Yih Xiaodong He Jianfeng Gao Li Deng
references.title: Embedding entities and relations for learning and inference in knowledge bases
references.venue: arXiv preprint arXiv:1412.6575,
references.authors: Fan Yang Zhilin Yang William W Cohen
references.title: Differentiable learning of logical rules for knowledge base reasoning
references.venue: In Advances in Neural Information Processing Systems,
references.authors: Shuai Zhang Yi Tay Lina Yao Qi Liu
references.title: Quaternion knowledge graph embedding
references.authors: Yuyu Zhang Xinshi Chen Yuan Yang Arun Ramamurthy Bo Li Yuan Qi Le Song
references.title: Efficient probabilistic logic reasoning with graph neural networks
references.venue: arXiv preprint arXiv:2001.11850,
sections.text: Knowledge graph completion aims to predict the missing links among the knowledge graph (KG),i.e., predicting the possibility that a certain triple belongs to the knowledge graph. Most mainstream embedding methods focus on fact triplets contained in the given KG, however, ignoring the rich background information provided by logic rules driven from knowledge base implicitly. Limited to the modeling of algebraic space, contradictory in expressing certain relational patterns usually exists in the embedding models. Therefore, the representation of the knowledge graph is incomplete and inaccurate. To solve this problem, in this paper, we propose a general framework, named EM-RBR(embedding and rulebased reasoning), capable of combining the advantages of reasoning based on rules and the state-of-the-art models of embedding. EM-RBR aims to utilize relational background knowledge contained in rules to conduct multi-relation reasoning link prediction. In this way, we can find the most reasonable explanation for a given triplet to obtain higher prediction accuracy. In experiments, we demonstrate that EM-RBR achieves better performance compared with previous models on FB15k, WN18 and our new dataset FB15k-R, especially the new dataset where our model perform futher better than those state-of-the-arts. We make the implementation of EM-RBR available at https://github.com/1173710224/ link-prediction-with-rule-based-reasoning.
sections.heading: 1 INTRODUCTION
sections.text: Knowledge graph (KG) has the ability to convey knowledge about the world and express the knowledge in a structured representation. The rich structured information provided by knowledge graphs has become extremely useful resources for many Artificial Intelligence related applications like query expansion (Graupmann et al., 2005), word sense disambiguation (Wasserman Pritsker et al., 2015), information extraction (Hoffmann et al., 2011), etc. A typical knowledge representation in KG is multi-relational data, stored in RDF format, e.g. (Paris, Capital-Of, France). However, due to the discrete nature of the logic facts (Wang & Cohen, 2016), the knowledge contained in the KG is meant to be incomplete (Sadeghian et al., 2019). Consequently, knowledge graph completion(KGC) has received more and more attention, which attempts to predict whether a new triplet is likely to belong to the knowledge graph (KG) by leveraging existing triplets of the KG.
  Currently, the popular embedding-based KGC methods aim at embedding entities and relations in knowledge graph to a low-dimensional latent feature space. The implicit relationships between entities can be inferred by comparing their representations in this vector space. These researchers (Bordes et al., 2013; Mikolov et al., 2013; Wang et al., 2014; Ji et al., 2015; Lin et al., 2015; Nguyen et al., 2017) make their own contributions for more reasonable and competent embedding. But the overall effect is highly correlated with the density of the knowledge graph. Because embedding method always fails to predict weak and hidden relations which a low frequency. The embedding will converge to a solution that is not suitable for triplets owned weak relations, since the training set for embedding cannot contain all factual triplets.However, reasoning over the hidden relations can covert the testing target to a easier one. For example, there is an existing triplet (Paul, Leader-Of, SoccerTeam) and a rule Leader-Of(x,y) =⇒ Member-Of(x,y) which indicates the leader of a soccer
  team is also a member of a sport team. Then we can apply the rule on the triplet to obtain a new triplet (Paul, Member-of, SportTeam) even if the relation Member-of is weak in knowledge graph.
  Besides, some innovative models try to harness rules for better prediction. Joint models (Rocktäschel et al., 2015; Wang et al., 2019; Guo et al., 2016) utilize the rules in loss functions of translation models and get a better embedding representation of entities and relations. An optimization based on ProPPR (Wang & Cohen, 2016) embeds rules and then uses those embedding results to calculate the hyper-parameters of ProPPR. These efforts all end up on getting better embedding from rules and triplets, rather than solving completion through real rule-based reasoning, which is necessary to address weak relation prediction as mentioned before. Compared with them, EM-RBR can perform completion from the reasoning perspective.
  Usually, there are some contradictions in the mathematical space of existing embedding-based models. Take transE (Bordes et al., 2013) and RotatE (Sun et al., 2019) as examples. For the relation pattern R(x, y) ⇒ R(y, x), i.e., a symmetrical relation, transE cannot model it as described in Sun et al. (2019). While RotatE can not model some relation pattern. For example, transitive relation R, w.r.t R(x, y)∧R(y, z)⇒ R(x, z). We assume that the embedding of the relation R under RotatE is eiθR , abbreviated as r. Formula 1 is necessary and sufficient to transitivity. So we will get r2 = r, which means that eiθR = 1, so θR = 0, θR ∈ [0, 2π). θR = 0 denotes that R is a reflexive relation. That is all the embedding of the transitive relation will be trained to have the nature of the reflexive relation, which is out of our expect.
  x · r = y, y · r = z, x · r = z (1) In addition to the above problems, transE and RotatE models cannot model data that has multiple relations between two entities. TransR (Lin et al., 2015) can solve this problem by training the relationship as a transformation matrix. But none of them can solve the problem that an entity has the same relation with multiple other entities. For example, there are two triples (h, r, t1), (h, r, t2) in the knowledge graph(t1 6= t2). For the transE model, h+ r is a fixed result. So a wrong equation r1 = r2 will exist under transE model. The other two mathematical models are no exception.
  The above-mentioned shortcomings can be solved by defining the relation pattern in a rule directly. Morivated by this, We propose a novel framework EM-RBR combing embedding and rule-based reasoning, which is a heuristic search essentially. In the development of the joint framework EMRBR, we meet two challenges. On the one hand, we use AMIE (Galárraga et al., 2013) to auto-mine large amount of rules but not manually. However, these rules automatically mined sometimes are not completely credible. Therefore, it is necessary to propose a reasonable way to measure rules to pick proper rules when reasoning. On the other hand, it is known that traditional reasoningbased methods will give only 0 or 1 to one triplet to indicate acceptance or rejection for the given knowledge graph. This conventional qualitative analysis lacks the quantitative information as the embedding models. So the result of EM-RBR need to reflect the probability one triplet belonging to the knowledge graph.
  Three main contributions in EM-RBR are summarized as follows:
  • EM-RBR is flexible and general enough to be combined with a lot of embedding models. • We propose a novel reasoning algorithm, which can distinguish a given triplet with other
  wrong triplets better. • We propose a novel rating mechanism for auto-mined reasoning rules and each rule will be
  measured properly in our framework.
  In the remaining of this paper, we will explain how our model works in Section 2, experiments in Section 3 and related work in Section 4.
sections.heading: 2 METHOD
sections.text: Our motivation is to use rules to make up for the shortcomings of embedding model. When the mathematical space of a certain embedding model is not enough to represent a certain relation pattern, the relation pattern can be declared through rules. For example, for the symmetric relationship R, we declare a rule R(x, y) ⇒ R(y, x). When scoring a certain triple (a,R, b) under transE model, we can take min(s(a,R, b), s(b, R, a)) as the The final score of the triple. This is equivalent
  to finding another triple that can explain the rationality of this triple through rules. Although the relation between the new triplet and the original triplet cannot be expressed in the algebraic space of embedding, the most reasonable explanation can be found through rules to solve the defects of the model.
  The core idea of our framework is to conduct multi-relation path prediction in deeper context from reasoning perspective, that is in the form of heuristic search. Before explaining the concrete reasoning algorithm, let’s take an overview of our framework in Section 2.1.
sections.heading: 2.1 OVERVIEW
sections.text: Definition 2.1. Rule: A rule in our framework is in the form of B1(x, z) ∧ B2(z, y) =⇒ H(x, y) or B(x, y) =⇒ H(x, y).
  We model a knowledge graph as a collection of facts G = {(h, r, t)|h, t ∈ E , r ∈ R}, where E and R represent the set of entities and relations in the knowledge graph, respectively. The steps of our framework are as follows corresponding to Figure 1.
  Step 1. We invoke an embedding model to get a set Ξ ∈ R(|E|+|R|)×k containing the k-dimensional embedding of entities and relations in G.
  Step 2. We apply AMIE (Galárraga et al., 2013) on G to get the reasoning rule set Ω, where each rule meets Definition 2.1.
  Step 3. The reasoning rules are measured based on the embedding of relations contained in the rule, which will explained in Secion 2.2.2.
  Step 4. Reasoning is conducted for a given triplet (h, r, t), which will be described in Section 2.2.
sections.heading: 2.2 REASONING ALGORITHM
sections.text: Definition 2.2. initial state: Initial state is represented as a set consisting of a single triplet, i.e.{(h, r, t)}. state: According to the initial state and the state’s expansion method described in Section 2.2.1, each state is represented as a set a triples.
  This reasoning algorithm is the core of our framework and it’s a heuristic search. The input of this algorithm is a triplet (h, r, t). State in the search space is as Definition 2.2. Each state has two
  scores, i.e. H and L. H is the heuristic score of state and L is the score of the state. The calculation of scores is explained in Section 2.2.2.
  The target of search is to compute Φ∼(h,r,t) = minstate∈S{L∼state(h, r, t)} for a specific triple (h, r, t). The score Φ of a triplet meets Φ ≥ 1. The smaller Φ is, the triplet belongs to knowledge graph with greater probability.
  The pseudo code of search is as shown in Appendix B. We use a priority queue Q to store states in ascending order of H. The initial state is the target triplet itself, whose H is 1. Push the initial state into Q and then begin the loop until Q is empty.
  During the search process, pop the top of Q as the current state scur. It will not be extended if Hscur ≥ Φ, otherwise we will extend it by matching rules to get new states. For each new state snew, compute its scoreHsnew and Lsnew . IfHsnew < Lscur , the state will then be pushed into Q.
sections.heading: 2.2.1 MATCHING AND EXTENSION
sections.text: State is a set of triplets, the initial state is the target triplet itself. Intermediate states are extended from the initial state. So essentially, the extension of a state is extension of the triplets in the state. For a triplet (h, r, t), the process of matching and extension is roughly as follows:
  1. Find rules ω ∈ Ω in the form of B1(x, z) ∧B2(z, y) =⇒ H(x, y)1, where H = r. 2. Assign entities to variables in the rule, i.e. x = h, y = t. 3. Find all z0 that satisfy (x,B1, z0) ∈ G or (z0, B2, y) ∈ G, where x = h, y = t. 4. (h, r, t) is extended to {(h,B1, z0), (z0, B2, t)}. A triplet always has multiple extensions.
  For example, we expand the target triplet in the initial state. There are two triplets in the sub-state, and either of them must be in the knowledge graph. When the sub-state is further expanded, the triplet in the knowledge graph need not to be expanded. Therefore, there should be m+ 1 triplets in each sub-state after extending m times. And at least m of them belong to the knowledge graph.
sections.heading: 2.2.2 COMPUTATION OF H AND L
sections.text: H∼O(h, r, t) denotes the heuristic score of triplet (h, r, t) when extended to stateO andL∼O(h, r, t) is the corresponding state score.
  H∼O(h, r, t) = ∏
  (B1∧B2⇒H)∈∆Path
  ω(B1, B2, H) w.r.t, ω(B1, B2, H)← e ||B1+B2−H|| k (2)
  H∼O(h, r, t) is defined as Equation 2 indicating the product of the scores of all the rules. ∆Path represents the set of the rules used in the extension from the initial state to the current state. ω(B1, B2, H) is the score of rules in the shape of B1 ∧B2 ⇒ H .
  L∼O(h, r, t) = H∼O(h, r, t) ∗ ∏
  (Oh,Or,Ot)∈O
  s∼transX(Oh,Or,Ot) (3)
  L∼O(h, r, t) is defined as Equation 3 indicating the product of H∼O(h, r, t) and the scores of all the triplets in the state. O denotes the state and (Oh,Or,Ot) is a triplet belongs to O. s∼transX(Oh,Or,Ot) is the embedding score of this triplet as defined in Equation 4.
  s∼transX(Oh,Or,Ot) = {
  1 if (Oh,Or,Ot) ∈ G ||Oh +Or −Ot||/k + 1 if (Oh,Or,Ot) /∈ G (4)
  Rule’s score To evaluate the score of rule B1(x, z) ∧ B2(z, y) =⇒ H(x, y), we visualize the three triplets of this rule in a two-dimensional space in Figure 3 of Appendix A. In our model, if a rule has a high confidence, it should satisfy ‖x+H−y‖ ≈ ‖x+B1−z+z+B2−y‖. We have H ≈ B1 +B2, so we can use ‖B1 + B2 −H‖ to evaluate the score of the rule. k is the dimension of embedding.
  1The rules we analyzed here are in the form of B1(x, z) ∧ B2(z, y) =⇒ H(x, y). As for rules like B(x, y) =⇒ H(x, y), the process is similar and will not be overtalked here.
  The smaller score, the higher confidence. To make the dimension in the calculation uniform, we divide the score of the rule by k. And then perform the e exponential transformation to get the form in the Equation 2. The reason for this transformation will be explained in section 2.4.
  Triplet’s score ||Oh +Or −Ot|| is the score of triplet (Oh,Or,Ot) in transE model2. The smaller the value, the more likely the triplet is in G. When (Oh,Or,Ot) ∈ G, the score is assumed to be 0. The same to rule’s score, we also perform a certain transformation on the scores of the triplets, which is to divide by k and add 1.
sections.heading: 2.3 EXAMPLE
sections.text: Assumption 2.1. We put all the necessary message in Table 3 and 4. Apart from that, we make two assumptions. One is that we use the same symbol ri to represent a rule’s symbol and rule’s score. Another is that we define some data relations as Equation 5.
  r1r3r5 > L∼s3(h, r, t) & H∼s7(h, r, t) > Φ∼(h,r,t) (5)
  In this section, we use an example to illustrate our algorithm as shown in Figure 23. The initial state s0 only contains one triplet (h, r, t), and its state score and heuristic score are both 1. At the beginning, the priority queueQ has only one element, i.e. the initial state with its scores. The search process is as follows, and the necessary message is defined in Assumption 2.1.
  I. s0 matches r1 and r2 and extends to s1 and s2 respectively. s2 is a termination state for the triplets in s2 are all in G. We use L∼s2(h, r, t) to update Φ∼(h,r,t) and push s1 into Q.
  II. Pop the top of queue s1. Use it to update Φ∼(h,r,t) and then extend it to three new states which will be pushed to Q.
  2Here we take transE as an example, so we use ||Oh +Or −Ot||. If the combined model changes, this formula should change to the form in the combined model, too.
  3There will be some conflicts in the usage of symbols. For these symbols, it’s only valid in this example.
  III. Pop the top of queue s3 to update Φ∼(h,r,t) and extend it with matching the rule r5. Since r1r3r5 > L∼s3(h, r, t), i.e. the solution produced by this path will not be the global minimum. As a consequence, this state is no longer extended.
  IV. Pop the top of queue s4 to update Φ∼(h,r,t) and extend to get two new states s6, s7.
  V. Pop the top of queue s6 to update Φ∼(h,r,t) and extend to s8, s9 after the rule r7.
  VI. Pop the top of queue s7 and nowH∼s7(h, r, t) > Φ∼(h,r,t). So s7 and the remaining states in Q need not extend. Therefore, all the remaining states in Q become termination states. The search stops.
sections.heading: 2.4 ANALYSE
sections.heading: IS THE ALGORITHM SURE TO BE EFFECTIVE?
sections.text: For three real number a, b, c(a, b, c > 1), it’s possible that c > a ∗ b ∗ 1. Consider triplet (h, r, t) and ruleB1(x, z)∧B2(z, y) =⇒ H(x, y) ,w.r.t r = H . If c represents the score of (h, r, t), a represents the score of the rule, b represents the score of the expanded new triplet that not in the knowledge graph, and 1 represents the score of the expanded new triplet that in the knowledge graph. Then the score of (h, r, t) will be reduced to a ∗ b, i.e. we use the new expanded triplets and the rule to evaluate (h, r, t).
  Of course, this optimization will be effective only on the correct triplets. For the wrong triplets, another wrong triplet with a large score will be obtained after rule matching. So c > a ∗ b in this occasion is a very unlikely event. As a result, the correct triplets are optimized, and the wrong triplets will generally not be optimized. Therefore, from a macro perspective, the ranking of the correct triplets will increase.
sections.heading: IS THIS ALGORITHM A TERMINATING ALGORITHM?
sections.text: The heuristic score of a state is the product of scores of all the rules along the reasoning path. The scores of the rules are all number greater than 1, so when a search path is long enough, H must be greater than Φ. So the search must be able to stop.
  WHAT IS THE PRINCIPLE WHEN DESIGNING THE CALCULATION OF RULES AND TRIPLETS?
  From the above, we require that the scores of rules and triplets are greater than 1 and close to 1. Given that each dimension of embedding obtained by the translation model is a number less than 1 and close to 0, we divide the score by the corresponding dimension k and then add 1 to meet our requirements. In addition, in order to highlight the importance of rules in the calculation, we use exponential changes for rules instead of plus 1.
sections.heading: 3 EXPERIMENT
sections.text: We would like to prove two things. One is that EM-RBR is a valid reinforced model, i.e. EMRBR(X) model always performs better than X model. Another is that EM-RBR will beat all of the current state-of-the-arts on a data set with rich rules.
sections.heading: 3.1 EXPERIMENT SETUP
sections.text: Dataset: We evaluate EM-RBR on FB15k, WN18 (Bordes et al., 2013), FB15k237 (Toutanova & Chen, 2015) and WN18RR (Dettmers et al., 2017). We propose a new data set FB15k-R, whose test set contains rich rule information as described in Appendix D.
  Metrics: We use a number of commonly used metrics, including Mean Rank (MR), Mean Reciprocal Rank (MRR), and Hit ratio with cut-off values n = 1,10. MR measures the average rank of all correct entities and MRR is the average inverse rank for correct entities. Hits@n measures the proportion of correct entities in the top n entities. MR is always greater or equal to 1 and the lower MR indicates better performance, while MRR and Hits@n scores always range from 0.0 to 1.0 and
  higher score reflects better prediction results. We use filtered setting protocol (Bordes et al., 2013), i.e., filtering out any corrupted triples that appear in the KB to avoid possibly flawed evaluation.
  Baseline: To demonstrate the effectiveness of EM-RBR, we compare with a number of competitive baselines: TransE (Bordes et al., 2013), TransH (Wang et al., 2014), TransR (Lin et al., 2015), TransD (Ji et al., 2015), RUGE (Guo et al., 2017), ComplEx (Trouillon et al., 2016), DistMult (Kadlec et al., 2017) and MINERVA (Das et al., 2017a). Among these state-of-arts, TransE, TransH, TransR and TransD are combined with our reasoning framework. These 8 models are evaluated on 4 standard datasets to prove that our framework is a real reinforced framework. In the end, all the baselines and combined models are evaluated on FB15k-R.
  Implementation: For TransE, TransH, TransR and TransD, we set the same parameters, i.e., the dimensions of embedding k = 100, learning rate λ = 0.001, the margin γ = 1. We traverse all the training triplets for 1000 rounds. Other parameters of models are set as the same with the parameters in the published works (Bordes et al., 2013; Wang et al., 2014; Lin et al., 2015)4. For RUGE, we set the embedding dimension k = 100 and other hyper-parameters are the same with Guo et al. (2017)5. For ComplEx and DistMult, all the parameters are consistent with Trouillon et al. (2016)6. For MINERVA, we use the implementation of Das et al. (2017a)7.
sections.heading: 3.2 EXPERIMENT RESULTS
sections.text: Firstly, we compare EM-RBR(X) with transX model on FB15k, WN18, FB15k237 and WN18RR. Experimental Results are shown in Table 6. Among the four datasets, the performance on WN18RR is not optimized much cause this dataset is too sparse and its result is shown in E.
  When evaluating on FB15k ,WN18 and FB15k-237, our model has improved all the metrics compared with the translation model in the baseline, especially MRR and Hits@1 on each dataset. For example, EM-RBR(D) improve Hits@1 on WN18 from 0.296 to 0.752 compared to transD. While our EM-RBR doesn’t have obvious optimization on WN18RR, cause the dataset is too sparse. We have show the experiment result in Appendix E.
  Secondly, we compare all the baselines mentioned above on FB15k-R, each triplet in this data set can match a lot of rules so that they can be optimized extremely under EM-RBR. The result is in Table 2. Among those baselines, MINERVA shows the best performance for the test set is rich in rules. While the performance is further optimized compared to MINERVA.
  4https://github.com/thunlp/Fast-TransX 5https://github.com/iieir-km/RUGE 6https://github.com/ttrouill/complex 7https://github.com/shehzaadzd/MINERVA
sections.heading: 3.3 RESULT ANALYSIS
sections.text: Actually, only a small part of triples in the test set is optimized. In FB15k, the ratio of this optimization is 1/6. Various metrics have been improved much even with this small ratio. The capabilities of our model can be fully demonstrated on the FB15k-R, because each triplet in this set has many rules that can be matched to obtain a good optimization effect. We have recorded each triple’s rank under transX and EMRBR(X) respectively as shown in Appendix F.
sections.heading: 4 RELATED WORK
sections.text: For the path-based methods, Lao et al. (2011) uses Path Ranking Algorithm (PRA) (Lao & Cohen, 2010) to estimate the probability of an unseen triplet as a combination of weighted random walks. Zhang et al. (2020) and (Qu & Tang, 2019) are both the combination of Markov logic network and embedding. Kok & Domingos (2007) is mainly a clustering algorithm, clustering entity sets under multiple relationship categories. Gardner et al. (2014) makes use of an external text corpus to increase the connectivity of KB. The Neural LP model (Yang et al., 2017) compiles inferential tasks into differentiable numerical matrix sequences. Besides, many studies have modeled the path-finding problem as a Markov decision-making process, such as the DeepPath model (Xiong et al., 2017) and MINERVA (Das et al., 2017b). For the embedding methods, Nguyen (2017) has organized the existing work. Our paper divides all embedding methods into four categories, which are: translation, Bilinear & Tensor, neural network and complex vector. Firstly, for translation, the Unstructured model (Bordes et al., 2014) assumes that the head and tail entity vectors are similar without distinguishing relation types. The Structured Embedding (SE) model (Bordes et al., 2011) assumes that the head and tail entities are similar only in a relation-dependent subspace. Later, there are transE, transR, transH (Bordes et al., 2013; Lin et al., 2015; Wang et al., 2014), etc. Sadeghian et al. (2019) mines first-order logical rules from knowledge graphs and uses those rules to solve KBC. Additionally, other work (Yang et al., 2017; Galárraga et al., 2013) can extract some highquality rules from knowledge base. For the second type, DISTMULT (Yang et al., 2014) is based on the Bilinear model (Nickel et al., 2011) where each relation is represented by a diagonal matrix rather than a full matrix. SimplE (Kazemi & Poole, 2018) extends CP models (Hitchcock, 1927) to allow two embeddings of each entity to be learned dependently. The third method is to implement embedding with a neural network. Apart from the models mentioned in Section 1, NTN (Socher et al., 2013) and ER-MLP (Dong et al., 2014) also belong to this method. Fourthly, instead of embedding entities and relations in real-valued vector space, ComplEx (Trouillon et al., 2016) is an extension of DISTMULT in the complex vector space. ComplEx-N3 (Lacroix et al., 2018) extends ComplEx with weighted nuclear 3-norm. Also in the complex vector space, RotatE (Sun et al., 2019) defines each relation as a rotation from the head entity to the tail entity. QuatE (Zhang et al., 2019) represents entities by quaternion embeddings (i.e., hypercomplex-valued embeddings) and models relations as rotations in the quaternion space.
sections.heading: 5 CONCLUSION & FUTURE WORK
sections.text: This paper introduces an innovative framework called EM-RBR combining embedding and rulebased reasoning, which can be easily integrated with any translation based embedding model. Unlike
  previous joint models trying to get better embedding results from rules and triplets, our model allows solving completion from the reasoning perspective by conducting multi-relation path prediction, i.e. a breadth first search. We also demonstrate that EM-RBR can efficiently improve the performance of embedding methods for KGC. This makes the existing translation based embedding methods more suitable and reliable to be used in the real and large scale knowledge inference tasks.
  There are two possible directions in the future. On one hand, we will combine our model with more embedding models, not just the translation-based embedding model. On the other hand, we are going to extract more and more reliable association rules to optimize our work. As mentioned above, only a part of triples are optimized when evaluating on FB15k. The fundamental reason for the rest is that there is no corresponding rule for matching. If these two problems are solved, EM-RBR can be better improved.
sections.heading: A RULE’S VISUALIZATION
sections.heading: B PSEUDO CODE
sections.text: Algorithm 1 EM-RBR Input: (h, r, t) Output: Φ∼(h,r,t)
sections.heading: C DATA MESSAGE IN EXAMPLE
sections.text: state triplets s1 (h,B1,m1)
  ? (m1, B2, t) s2 (h,B3,m2) (m2, B4, t) s3 (h,B5,m3)
  ? (m3, B6,m1) (m1, B2, t) s4 (h,B5,m4)
  ? (m4, B6,m1) (m1, B2, t) s5 (h,B7,m5)
  ? (m5, B8,m1) (m1, B2, t) s6 (h,B9,m6) (m6, B10,m4)
  ? (m4, B6,m1) (m1, B2, t) s7 (h,B11,m7) (m7, B12,m4)
  ? (m4, B6,m1) (m1, B2, t) s8 (h,B9,m6) (m6, B13,m8)
  ? (m8, B14,m4) (m4, B6,m1) (m1, B2, t) s9 (h,B9,m6) (m6, B13,m9) (m9, B14,m4) ? (m4, B6,m1) (m1, B2, t)
sections.heading: D DATASET USED IN OUR EXPERIMENT
sections.text: Some triples in the test set of FB15k are selected to make up of a new test set named FB15k-R. We construct the new test set with the following steps. Firstly, sort all triples in the test set by some indicator, denoted as Z(h, r, t). Secondly, randomly select triples within different ranking ranges with a certain probability distribution, until 1,000 triples are selected. The probability distribution is described as Equaion 6.
  P (event) =  0.1, event← select a triple whose Z = 0 0.2, event← select a triple whose ranking ≤ 10000 0.3, event← select a triple with ranking τ, τ > 10000 & τ ≤ 30000 0.4, event← select a triple whose ranking ≥ 30000 & Z 6= 0 (6)
  Z(h, r, t) can be calculated as one of the candidates in the following.
  • The number of rules each triple can match, and the matching method is the same to that in Section 2.2.1.
  • The number of valid rules each triple can match. A valid rule meets ω < s∼transE(h, r, t), where ω denotes the score of a rule and s∼transE(h, r, t) denotes the score of the triple under transE.
  • The maximum s∼transE(h, r, t)− ωrule for each triple, and rule ∈ rule(h,r,t). rule(h,r,t) is the set of rules (h, r, t) can match.
  • s∼transE(h, r, t) − s∼reasoning(h, r, t), where s∼reasoning(h, r, t) denotes the score of (h, r, t) under EM-RBR(transE).
  In our formal experiment, we choose the last strategy to generate FB15k-R.
sections.heading: E EXPERIMENT RESULT OF WN18RR
sections.text: The metrics reported in this table is not better than that reported in other work8. The different hyperparameters result in this. This experiment is a verification of the enhancement effect, so it makes sense only when comparing transX and EM-RBR(X).
  8https://github.com/thunlp/OpenKE
sections.heading: F SINGLE TRIPLE RANKING ANALYSIS
sections.text: In order to better understand the specific situation being optimized on each triplet. We respectively analyzed the corresponding ranking of each triplet under the translation model and the EM-RBR model when the head entity replacement and tail entity replacement were performed. The results were displayed in Table 7. The data item in the table is the result of sorting from largest to smallest value of s∼trans − s∼ER, where s∼trans is the ranking under the corresponding translation model and s∼E−R is the ranking under the corresponding EM-RBR model.
sections.heading: 9 18355 2 4525 R 55951 2 3699 L 25500 1 585 R
sections.heading: 8 14035 2 4862 L 13358 5 3741 R 54283 52 674 L
sections.heading: 7 30883 2 5674 R 47722 2 3977 R 38773 1 640 L
sections.heading: 6 33243 2 5883 R 33004 1 4490 L 55951 2 673 L
sections.heading: 5 33004 1 6253 L 24243 1 4547 L 32849 1 701 L
sections.heading: 4 36133 2 6884 L 47722 2 4569 L 24314 1 714 R
sections.heading: 3 18355 2 7525 L 18355 2 7231 R 34891 2 733 R
sections.heading: 2 47722 2 13900 L 32966 3 8551 L 42675 1 868 R
sections.heading: 1 47722 2 14141 R 18355 2 12689 L 15105 2 966 L