Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph (2020)

Abstract: Multi-hop reasoning has been widely studied in recent years to seek an effective and interpretable method for knowledge graph (KG) completion. Most previous reasoning methods are designed for dense KGs with enough paths between entities, but cannot work well on those sparse KGs that only contain sparse paths for reasoning. On the one hand, sparse KGs contain less information, which makes it difficult for the model to choose correct paths. On the other hand, the lack of evidential paths to target entities also makes the reasoning process difficult. To solve these problems, we propose a multi-hop reasoning model over sparse KGs, by applying novel dynamic anticipation and completion strategies: (1) The anticipation strategy utilizes the latent prediction of embedding-based models to make our model perform more potential path search over sparse KGs. (2) Based on the anticipation information, the completion strategy dynamically adds edges as additional actions during the path search, which further alleviates the sparseness problem of KGs. The experimental results on five datasets sampled from Freebase, NELL and Wikidata show that our method outperforms state-of-the-art baselines. Our codes and datasets can be obtained from https://github.com/THU-KEG/DacKGR .

## introduction knowledge graphs (kgs) represent the world knowledge in a structured way, and have been proven to be helpful for many downstream nlp tasks like query answering @xcite , dialogue generation @xcite and machine reading comprehension @xcite . despite their wide applications, many kgs still face serious incompleteness @xcite , which limits their further development and adaption for related downstream tasks. to alleviate this issue, some embedding-based models @xcite are proposed, most of which embed entities and relations into a vector space and make link predictions to complete kgs. these models focus on efficiently predicting knowledge but lack necessary interpretability. in order to solve this problem, @xcite and @xcite propose multihop reasoning models, which use the reinforce algorithm @xcite to train an agent to search over kgs. these models can not only give the predicted result but also an interpretable path to indicate the reasoning process. as shown in the upper part of figure 1 , for a triple query (olivia langdon, child, ?), multi-hop reasoning models can predict the tail entity susy clemens through a reasoning path (bold arrows). although existing multi-hop reasoning models have achieved good results, they still suffer two problems on sparse kgs: (1) insufficient information. compared with normal kgs, sparse kgs contain less information, which makes it difficult for the agent to choose the correct search direction. as the performance of most existing multi-hop reasoning methods drops significantly on sparse kgs, some preliminary efforts, such as cpl @xcite , explore to introduce additional text information to ease the sparsity of kgs. although these explorations have achieved promising results, they are still limited to those specific kgs whose entities have additional text information. thus, reasoning over sparse kgs is still an important but not fully resolved problem, and requires a more generalized approach to this problem. in this paper, we propose a multi-hop reasoning model named dackgr, along with two dynamic strategies to solve the two problems mentioned above: dynamic anticipation makes use of the limited information in a sparse kg to anticipate potential targets before the reasoning process. compared with multi-hop reasoning models, embeddingbased models are robust to sparse kgs, because they depend on every single triple rather than paths in kg. to this end, our anticipation strategy injects the pre-trained embedding-based model's predictions as anticipation information into the states of reinforcement learning. this information can guide the agent to avoid aimlessly searching paths. dynamic completion temporarily expands the part of a kg to enrich the options of path expan-sion during the reasoning process. in sparse kgs, many entities only have few relations, which limits the choice spaces of the agent. our completion strategy thus dynamically adds some additional relations (e.g., red dashed arrows in figure 1 ) according to the state information of the current entity during searching reasoning paths. after that, for the current entity and an additional relation r, we use a pre-trained embedding-based model to predict tail entity e. then, the additional relation r and the predicted tail entity e will form a potential action (r, e) and be added to the action space of the current entity for path expansion. we conduct experiments on five datasets sampled from freebase, nell and wikidata. the results show that our model dackgr outperforms previous multi-hop reasoning models, which verifies the effectiveness of our model. ## problem formulation in this section, we first introduce some symbols and concepts related to normal multi-hop reasoning, and then formally define the task of multi-hop reasoning over sparse kgs. knowledge graph kg can be formulated as @xmath0, r, t }, where e and r denote entity set and relation set respectively. @xmath1, r q , e o )} ⊆ e × r × e is triple set, where e s and e o are head and tail entities respectively, and r q is the relation between them. for every kg, we can use the average out-degree d out avg of each entity (node) to define its sparsity. specifically, if d out avg of a kg is larger than a threshold, we can say it is a dense or normal kg, otherwise, it is a sparse kg. given a graph kg and a triple query (e s , r q , ?), where e s is the source entity and r q is the query relation, multi-hop reasoning for knowledge graphs aims to predict the tail entity e o for (e s , r q , ?). different from previous kg embedding tasks, multi-hop reasoning also gives a supporting path {(e s , r 1 , e 1 ), (e 1 , r 2 , e 2 ) . . . , (e n-1 , r n , e o )} over kg as evidence. as mentioned above, we mainly focus on the multi-hop reasoning task over sparse kgs in this paper. ## methodology in this section, we first introduce the whole reinforcement learning framework for multi-hop reasoning, and then detail our two strategies designed for the sparse kgs, i.e., dynamic anticipation and dynamic completion. the former strategy intro- action space lstm lstm lstm ... " * ... new action space action probability ... ... ! ' " , ! ' ... policy netwrok triple query: (" & , ! ! , ? ) figure 2: an illustration of our policy network with dynamic anticipation and dynamic completion strategies. the vector of e p is the prediction information introduced in section 3.3. we use the current state to dynamically select some relations, and use the pre-trained embedding-based model to perform link prediction to obtain additional action space. the original action space will be merged with the additional action space to form a new action space. ## conclusion in this paper, we study the task that multi-hop reasoning over sparse knowledge graphs. the performance of previous multi-hop reasoning models on sparse kgs will drop significantly due to the lack of evidential paths. in order to solve this problem, we propose a reinforcement learning model named dackgr with two strategies (i.e., dynamic anticipation and dynamic completion) designed for sparse kgs. these strategies can ease the sparsity of kgs. in experiments, we verify the effectiveness of dackgr on five datasets. experimental results show that our model can alleviate the sparsity of kgs and achieve better results than previous multihop reasoning models. however, there is still some noise in the additional actions given by our model. in future work, we plan to improve the quality of the additional actions.