Improving Multi-hop Question Answering over Knowledge Graphs using Knowledge Base Embeddings (2020)

Abstract: Knowledge Graphs (KG) are multi-relational graphs consisting of entities as nodes and relations among them as typed edges. Goal of the Question Answering over KG (KGQA) task is to answer natural language queries posed over the KG. Multi-hop KGQA requires reasoning over multiple edges of the KG to arrive at the right answer. KGs are often incomplete with many missing links, posing additional challenges for KGQA, especially for multi-hop KGQA. Recent research on multi-hop KGQA has attempted to handle KG sparsity using relevant external text, which isn’t always readily available. In a separate line of research, KG embedding methods have been proposed to reduce KG sparsity by performing missing link prediction. Such KG embedding methods, even though highly relevant, have not been explored for multi-hop KGQA so far. We fill this gap in this paper and propose EmbedKGQA. EmbedKGQA is particularly effective in performing multi-hop KGQA over sparse KGs. EmbedKGQA also relaxes the requirement of answer selection from a pre-specified neighborhood, a sub-optimal constraint enforced by previous multi-hop KGQA methods. Through extensive experiments on multiple benchmark datasets, we demonstrate EmbedKGQA’s effectiveness over other state-of-the-art baselines.

## introduction knowledge graphs (kg) are multi-relational graphs consisting of millions of entities (e.g., san jose, california, etc.) and relationships among them (e.g., san jose-cityinstate-california). examples of a few large kgs include wikidata @xcite , dbpedia @xcite , yago @xcite , and nell (mitchell in the incomplete kg makes it much harder to answer the input nl question, as the kgqa model potentially needs to reason over a longer path over the kg (marked by bold edges). existing multi-hop kgqa methods also impose heuristic neighborhood limits (shaded region in the figure), which often makes the true answer (crime in this example) out of reach. embedkgqa, our proposed method, overcomes these limitations by utilizing embeddings of the input kg during multi-hop kgqa. for more details, please refer figure 2 and section 4. @xcite . question answering over knowledge graphs (kgqa) has emerged as an important research area over the last few years @xcite . in kgqa systems, given a natural language (nl) question and a kg, the right answer is derived based on analysis of the question in the context of the kg. in multi-hop kgqa, the system needs to perform reasoning over multiple edges of the kg to infer the right answer. kgs are often incomplete, which creates additional challenges for kgqa systems, especially in case of multi-hop kgqa. recent methods have used an external text corpus to handle kg sparsity @xcite . for example, the method proposed in @xcite ) constructs a question-specific sub-graph from the kg, which is then augmented with supporting text documents. embedkgqa has three modules: (1) kg embedding module (section 4.2) learns embeddings for all entities in the input kg, (2) question embedding module (section 4.3) learns an embedding for the question, and (3) the answer selection module (section 4.4) selects the final answer by incorporating the question and relation similarity scores. embedkgqa's use of embeddings makes it more effective in handling kg sparsity. moreover, since em-bedkgqa considers all entities as candidate answers, it doesn't suffer from the limited neighborhood out-of-reach issues of existing multi-hop kgqa methods. please refer section 4 for detailed description of embedkgqa. graph cnn (kipf and welling, 2016) is then applied over this augmented sub-graph to arrive at the final answer. unfortunately, availability and identification of relevant text corpora is a challenge on its own which limits broad-coverage applicability of such methods. moreover, such methods also impose pre-specified heuristic neighborhood size limitation from which the true answer needs to be selected. this often makes the true answer out of reach of the model to select from. in order to illustrate these points, please consider the example shown in figure 1 . in this example, louis mellis is the head entity in the input nl question, and crime is the true answer we expect the model to select. if the edge has genre(gangster no. 1, crime) were present in the kg, then the question could have been answered rather easily. however, since this edge is missing from the kg, as is often the case with similar incomplete and sparse kgs, the kgqa model has to potentially reason over a longer path over the kg (marked by bolded edges in the graph). moreover, the kgqa model imposed a neighborhood size of 3-hops, which made the true answer crime out of reach. in a separate line of research, there has been a large body of work that utilizes kg embeddings to predict missing links in the kg, thereby reducing kg sparsity @xcite @xcite . kg embedding methods learn high-dimensional embeddings for entities and relations in the kg, which are then used for link prediction. in spite of its high relevance, kg embedding methods have not been used for multi-hop kgqa -we fill this gap in this paper. in particular, we propose embedkgqa, a novel system which leverages kg embeddings to perform multi-hop kgqa. we make the following contributions in this paper: embedkgqa is particularly effective in performing multi-hop kgqa over sparse kgs. we have made embedkgqa's source code available to encourage reproducibility. recently, there has been some work in which text corpus is incorporated as a knowledge source in addition to kg to answer complex questions on kgs @xcite . such approaches are useful in case the kg is incomplete. however, this leads to another level of complexity in the qa system, and text corpora might not always be available. kg completion methods: link prediction in knowledge graphs using kg embeddings has become a popular area of research in recent years. the general framework is to define a score function for a set of triples (h, r, t) in a kg and constraining them in such a way that the score for a correct triple is higher than the score for an incorrect triple. rescal @xcite and distmult @xcite learn a score function containing a bi-linear product between head entity and tail entity vectors and a relation matrix. complex @xcite represents entity vectors and relation matrices in the complex space. simple (kazemi and poole, 2018) and tucker @xcite are based on canonical polyadic (cp) decomposition @xcite and tucker @xcite respectively. transe @xcite embeds entities in high dimensional real space and relation as translation between the head and the tail entities. rotate @xcite on the other hand projects entities in complex space and relations are represented as rotations in the complex plane. conve @xcite utilizes convolutional neural networks to learn a scoring function between the head entity, tail entity and relation. interacte @xcite improves upon conve by increasing feature interaction. ## background in this section, we formally define a knowledge graph(kg) and then describe link prediction task on incomplete kgs. we then describe kg embeddings and explain the complex embedding model. ## experimental details in this section, we first describe the datasets that we evaluated our method on, and then explain the experimental setup and the results. ## conclusion in this paper, we propose embedkgqa, a novel method for multi-hop kgqa. kgs are often incomplete and sparse which poses additional challenges for multi-hop kgqa methods. recent recent for this problem have tried to address the incompleteness problem by utilizing an additional text corpus. however, the availability of a relevant text corpus is often limited, thereby reducing broad-coverage applicability of such methods. in a separate line of research, kg embedding methods have been proposed to reduce kg sparsity by performing missing link prediction. embedkgqa utilizes the link prediction properties of kg embeddings to mitigate the kg incompleteness problem without using any additional data. it trains the kg entity embeddings and uses it to learn question embeddings, and during the evaluation, it scores (head entity, question) pair again all entities, and the highest-scoring entity is selected as an answer. embedkgqa also overcomes the shortcomings due to limited neighborhood size constraint imposed by existing multi-hop kgqa methods. em-bedkgqa achieves state-of-the-art performance in multiple kgqa settings, suggesting that the link prediction properties of kg embeddings can be utilized to mitigate the kg incompleteness problem in multi-hop kgqa.