GMH : A General Multi-hop Reasoning Model for KG Completion (2021)

Abstract: Knowledge graphs are essential for numerous downstream natural language processing applications, but are typically incomplete with many facts missing. This results in research efforts on multi-hop reasoning task, which can be formulated as a search process and current models typically perform short distance reasoning. However, the long-distance reasoning is also vital with the ability to connect the superficially unrelated entities. To the best of our knowledge, there lacks a general framework that approaches multi-hop reasoning in mixed long-short distance reasoning scenarios. We argue that there are two key issues for a general multi-hop reasoning model: i) where to go, and ii) when to stop. Therefore, we propose a general model which resolves the issues with three modules: 1) the local-global knowledge module to estimate the possible paths, 2) the differentiated action dropout module to explore a diverse set of paths, and 3) the adaptive stopping search module to avoid over searching. The comprehensive results on three datasets demonstrate the superiority of our model with significant improvements against baselines in both short and long distance reasoning scenarios.

## introduction knowledge graphs (kgs) have become the preferred technology for representing, sharing and adding factual knowledge to many natural language processing applications like recommendation @xcite and question answering @xcite . kgs store triple facts (head entity, relation, tail entity) in the form of graphs, where entities are represented as nodes and relations are represented as labeled edges between entities (e.g., figure 1 (a) ). although popular kgs already contain millions of facts, e.g., yago @xcite and freebase @xcite , they are far from being complete considering the amount of existing facts and the scope of continuously appearing new knowledge. this has become the performance bottleneck of many kg-related applications, triggering research efforts on the multi-hop reasoning task. the multi-hop reasoning task can be formulated as a search process, in which the search agent traverses a logical multi-hop path to find the missing tail entity of an incomplete triple in kg. as shown in figure 1 @xcite , where denotes the missing tail entity. multi-hop reasoning methods @xcite have been proposed to model the search process as a sequential decision problem in reinforcement learning (rl) framework. @xcite further optimized the reward function of rl framework based on @xcite . however, these works have only scratched the surface of multi-hop reasoning as they focus only on short distance reasoning scenarios (e.g., the two-hop case in figure 1 (b) ). we observe that the long distance reasoning scenarios are vital in the development of multi-hop reasoning and kg-related applications, because two superficially unrelated entities may be actually deeply connected over a long distance. with the significant expansion of kgs, the incompleteness of kg becomes more prominent, and long distance scenarios are rapidly increasing. as shown in figure 1 (c), the missing entity james harden in the incomplete triple @xcite is inferred by a long reasoning process, i.e., a fourhop path. moreover, in practice, the long and short distance reasoning scenarios are mixed. the ideal multi-hop reasoning model should be competent the dotted lines refer to the relations of incomplete triples and solid lines refer to existing relations. the green, blue and black boxes represent the entities of the incomplete triples, the entities in the reasoning paths and the unrelated entities, respectively. as it can be seen, the long distance reasoning is needed and more complex than the short distance reasoning. best viewed in color. on mixed short and long distances. specifically, we argue that there are two key issues in the traverse of kg that need to be resolved: to this end, we propose a general multi-hop reasoning model, termed gmh, which solves the two above-listed issues in three steps: 1) the localglobal knowledge fusion module fuses the local knowledge learnt from history path and the global knowledge learnt from graph structure; 2) the differentiated action dropout module forces the search agent to explore a diverse set of paths from a global perspective; and 3) the adaptive stopping search module uses a self-loop controller to avoid over searching and resource wasting. we train the policy network with rl and optimize the reward to find the target entity effectively. in summary, the main contributions of this work are as follows: ## related work in this section, we summarize the related work and discuss their connections to our model. firstly, we introduce the two lines of work on the kg completion task: multi-hop reasoning and kg embedding. the multi-hop reasoning task focuses on learning logical multi-hop paths reasoned from kg. the multi-hop reasoning models distill deep information from paths thereby generating further directly interpretable results. @xcite @xcite predicted the missing relations of incomplete triples based on pre-computed paths. @xcite ) firstly adopted the rl framework to improve the reasoning performance. the task of finding a missing entity is orthogonal to the prediction of the missing relation in a complementary manner. @xcite used the history path to facilitate the search agent finding the missing entity and @xcite optimized the reward function of rl framework based on @xcite . @xcite adopted the meta learning framework for multi-hop reasoning over few-shot relations. these works are conditioned in short distance scenarios, and tend to rapidly lose effectiveness as the distance increases. in contrast, we propose a general model which can be sufficiently utilized in both the short and long distance reasoning scenarios. the kg embedding task is another line of work carried to alleviate the incompleteness of kg. embedding-based models project kgs in the embedding space and estimate the likelihood of each triple using scoring functions. @xcite @xcite defined additive scoring functions based on the translation assumption. @xcite defined multiplicative scoring functions based on linear map assumption. moreover, recent models introduce special neural networks like neural tensor network @xcite , convolution neural network @xcite and graph convolutional network @xcite . due to the neglection of deep information within multi-hop paths, the results of the embedding-based models lack interpretability, which is critical for kg-related applications. however, embedding-based models are less sensitive to the reasoning distance because they learn kg structure from the global perspective. thus, we take advantage of this strength to learn the global knowledge from graph structure and retain the interpretability by reasoning from the history paths. secondly, we discuss the community research on long distance reasoning scenarios. @xcite formed a transition matrix for reasoning over six-hop path in kg for the conversational reasoning task. it is however not suitable for large-scale kgs, because the matrix multiplication requires large calculation space. @xcite proposed a long-term sequential pattern to encode long distance paths for the recommendation task. because there is no real reasoning process for the long distance paths, it is not suitable for the kg completion. to summary, we are the first to study long distance reasoning scenarios in the kg completion. we propose a general model that tackles both short and long distance reasoning scenarios and works effectively on large-scale kgs. ## methodology figure 2 illustrates the entire process of the gmh model. the input involves the head entity and relation of the incomplete triple with the background kg. the output is the missing tail entity. we systematize the model in three steps: 1) the local-global knowledge fusion module to integrate knowledge of history paths and graph structure; 2) the differentiated action dropout module to diversify the reasoning paths; and 3) the adaptive stopping search module to formulate the optimal steps of searching. the local-global knowledge fusion and differentiated action dropout modules facilitate the agent to address the issue of where to go. the adaptive stopping search module controls the search steps to resolve the issue of when to stop. ## conclusions we have studied the multi-hop reasoning task in long distance scenarios and proposed a general model which could tackle both short and long distance reasoning scenarios. extensive experiments showed the effectiveness of our model on three benchmarks. we will further consider the feasibility of applying our model to complex real-world datasets with more long distance reasoning scenarios and more relation types. besides, we have noticed that there are other "interference" in long distance reasoning. for example, noise from the kg itself, i.e., the fact that it lacks validity. these noises can gradually accumulate during long distance reasoning and affect the result confidence. we leave the further investigation to future work.