MCMH: Learning Multi-Chain Multi-Hop Rules for Knowledge Graph Reasoning

Findings of the Association for Computational Linguistics: EMNLP 2020, pages 3948–3954 November 16 - 20, 2020. c⃝2020 Association for Computational Linguistics 3948 MCMH: Learning Multi-Chain Multi-Hop Rules for Knowledge Graph Reasoning Lu Zhang ♣ Mo Yu ♥ Tian Gao ♥ Yue Yu ♣ ♣ Lehigh University ♥ IBM Research luz319@lehigh.edu {yum, tgao}@us.ibm.com yuy214@lehigh.edu Abstract Multi-hop reasoning approaches over knowl- edge graphs infer a missing relationship be- tween entities with a multi-hop rule, which cor- responds to a chain of relationships. We ex- tend existing works to consider a generalized form of multi-hop rules, where each rule is a set of relation chains. To learn such gen- eralized rules efficiently, we propose a two- step approach that first selects a small set of relation chains as a rule and then evaluates the confidence of the target relationship by jointly scoring the selected chains. A game- theoretical framework is proposed to this end to simultaneously optimize the rule selection and prediction steps. Empirical results show that our multi-chain multi-hop (MCMH) rules result in superior results compared to the stan- dard single-chain approaches, justifying both our formulation of generalized rules and the effectiveness of the proposed learning frame- work. 1 Introduction Knowledge graphs (KGs) represent knowledge of the world as relationships between entities, i.e., triples with the form (subject, predicate, object) (Bollacker et al., 2008; Suchanek et al., 2007; Vrandeˇci´c and Kr¨otzsch, 2014; Auer et al., 2007; Carlson et al., 2010). Such knowledge resource provides clean and structured evidence for many downstream applications such as question answer- ing. KGs are usually constructed by human ex- perts, which is time-consuming and leads to highly incomplete graphs (Min et al., 2013). Therefore automatic KG completion (Nickel et al., 2011; Bor- des et al., 2013; Yang et al., 2014; Chen et al., 2018; Socher et al., 2013; Lao et al., 2011) is proposed to infer a missing link of relationship r between a head entity h and a tail entity t. Existing KG completion work mainly makes use of two types of information: 1) co-occurrence of Figure 1: Examples of reasoning with multiple paths. (a) A standard multi-hop example. The target can be sufficiently inferred with one chain. (b) An example that requires a rule as the conjunction of two chains (the stadium hosts two teams but only one from NBA). (c) An example where multiple chains cannot sufficiently infer the target but improves its confidence. entities and relations and 2) deducible reasoning paths of tuples. KG embeddings encode entities and relations, the first type of information, together into continuous vector space with low-rank ten- sor approximations (Bordes et al., 2013; Dettmers et al., 2017; Lin et al., 2015; Neelakantan et al., 2015; Shi and Weninger, 2017; Trouillon et al., 2016; Wang et al., 2014; Xie et al., 2016; Yang et al., 2014). Ours approach utilizes the second type of infor- mation, reasoning path of tuples that can be de- duced to the target tuple (Lao and Cohen, 2010; Xiong et al., 2017; Das et al., …

Content truncated to 500 words