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

Abstract: Multi-hop reasoning approaches over knowledge graphs infer a missing relationship between entities with a multi-hop rule, which corresponds to a chain of relationships. We extend existing works to consider a generalized form of multi-hop rules, where each rule is a set of relation chains. To learn such generalized 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 standard single-chain approaches, justifying both our formulation of generalized rules and the effectiveness of the proposed learning framework.

## introduction knowledge graphs (kgs) represent knowledge of the world as relationships between entities, i.e., triples with the form (subject, predicate, object) @xcite @xcite @xcite . such knowledge resource provides clean and structured evidence for many downstream applications such as question answering. kgs are usually constructed by human experts, which is time-consuming and leads to highly incomplete graphs @xcite . therefore automatic kg completion @xcite @xcite @xcite 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 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 tensor approximations @xcite @xcite @xcite @xcite @xcite . ours approach utilizes the second type of information, reasoning path of tuples that can be deduced to the target tuple @xcite @xcite . here a reasoning path starts with the head entity h and ends with the tail entity despite advantages and success of the multi-hop reasoning approach @xcite @xcite @xcite , a target relationship may not be perfectly inferred from a single relation chain. there could exist multiple weak relation chains that correlate with the target relation. figure 1 gives examples of such cases. these multiple chains could be leveraged in following ways: (1) the reasoning process naturally relies on the logic conjunction of multiple chains (figure 1b ); (2) more commonly, there are instances for which none of the chains is accurate, but aggregating multiple pieces of evidence improves the confidence (figure 1c ), as also observed in the case-based study works @xcite . inspired by these observations, we propose the concept of multi-chain multi-hop rule set. here, instead of treating each single multihop chain as a rule, we learn rules consisting of a small set of multi-hop chains. therefore the inference of target relationships becomes a joint scoring of such a set of chains. we treat each set of chains as one rule and, since different query pairs can follow different rules, together we have a set of rules to reason each relation. learning the generalized multi-hop rule set is a combinatorial search problem. we address this challenge with a game-theoretic approach inspired by @xcite @xcite . our approach consists of two steps: (1) selecting a generalized multi-hop rule set by employing a multi-layer perceptron (mlp) over the candidate chains; (2) reasoning with the generalized rule set, which uses another mlp to model the conditional probability of the target relationship given the selected relation chains. the nonlinearity of mlp as reasoner provides the potential to model the logic conjunction among the selected chains in the rule set. we demonstrate the advantage of our method on kg completion tasks in fb15k-237 and nell-995. our method outperforms existing single-chain approaches, showing that our defined generalized rules are necessary for many reasoning tasks. for a given query ( ĥi , r, ti ), the i-th sample in r, we extract a set of relation chains in the experiments, we represent each relation chain rn with only relation names. our task is to find such s for a target relation r over each query pair ĥi and ti , and estimate the confidence p (r|s). note that s and r depend on query sample ( ĥi , r, ti ) but for notation simplicity we omit i and r from s r i and r r i . relation chains extraction to obtain the set of candidate relation chains r for a target relation r, we take the following extraction steps. first, we extract a fixed hop k sub-graph from the original kb. each sub-graph starts with an entity ĥ with relation r, ends with an entity t, and satisfies that ( ĥ, r, t) ∈ g. the sub-graph consists of a list of m-hop paths connecting the two ends, where high k values can result in an intractable number of chains while low k values may not have sufficient coverage. here we extract chains with length up to @xmath0, and for r with a large number of chains (|r| ≥ 10 4 ), we filter out extracted chains with a set threshold (proportional to count of relation chains) in the positive training data for that relation. ## a game-theoretic approach for mcmh rule learning a three-player game for rule learning finding a set of chains as the rule is a combinatorial search problem in r. for example, given an input of 1,000 chains between a training entity pair, the selection of a set-rule of 4 chains corresponds to a search space of 10 12 . hence, we propose a gametheoretic approximation to learn to generate predictive chains and reduce the learning complexity. our method is inspired by the line of rationalization works @xcite . specifically, our input is a set of chains r i ⊂ r for relation r and each training sample ( ĥi , r, ti ). our method consists of three submodels: (1) a rule set generator that selects the set of chains s i as a rule, (2) a reasoner that predicts the probability of ri based on s i , and (3) a complement predictor that predicts the probability of r based on s c @xmath1. during training, the predictor and the complement predictor aim to minimize the cross-entropy loss for predicting the existence of r. while the generator is optimized to make the predictor perform well, while decreasing the complement predictor's accuracy. in other words, the generator plays a cooperative game with the predictor to make the selected rule set s i be useful for inferring the target relationship r. at the same time it plays an adversarial game with the complement predictor to ensure that no critical information is left, i.e., to ensure the comprehensiveness of the selected s i . an example of the workflow is given in figure 2 . predictors the predictor estimates probability of r being true conditioned on s i , denoted as p(r|s i ). the complement predictor estimates probability of r conditioned on s c i , denoted as pc (r|s c i ). the two models are optimized as follows: we encode the inputs s i and s c i as binary vectors v s i and v s c i , respectively 1 , which are both of dimension |r i |, with each dimension corresponding to one relation chain in the candidate set r i . the j-th component of v s i is set to 1 if and only if the j-th chain is selected in s i , i.e., r @xmath2, and similarly for v s c i . the input vectors are fed into a 3-layer mlp to predict whether r holds for ( ĥi , ti ). ## empirical evaluation we evaluate our model with mcmh rules on two datasets, fb15k-237 @xcite and nell-995 @xcite . we follow the existing setting of treating each target relationship as a separate task and training and evaluating relationship-specific reasoning models, and use the standard data splits @xcite . ## conclusion we propose a new approach of multi-chain multihop rule learning for knowledge graph completion tasks. first, we formalize the concept of multi-