Query Graph Generation for Answering Multi-hop Complex Questions from Knowledge Bases (2020)

Abstract: Previous work on answering complex questions from knowledge bases usually separately addresses two types of complexity: questions with constraints and questions with multiple hops of relations. In this paper, we handle both types of complexity at the same time. Motivated by the observation that early incorporation of constraints into query graphs can more effectively prune the search space, we propose a modified staged query graph generation method with more flexible ways to generate query graphs. Our experiments clearly show that our method achieves the state of the art on three benchmark KBQA datasets.

## introduction knowledge base question answering (kbqa) aims at answering factoid questions from a knowledge base (kb). it has attracted much attention in recent years @xcite @xcite @xcite . early work on kbqa focused on simple questions containing a single relation @xcite @xcite . however, real questions are often more complex and recently some studies looked into complex kbqa. two different types of complexity have been studied: (1) single-relation questions with constraints. for example, in the question "who was the first president of the u.s.?" there is a single relation "president of" between the answer entity and the entity "u.s.," but we also have the constraint "first" that needs to be satisfied. for this type of complex questions, a staged query graph generation method has been proposed, which first identifies a single-hop relation path and then adds constraints to it to form a query graph @xcite @xcite . (2) questions with multiple hops of relations. for example, for the question "who is the wife of the founder of facebook?" the answer is related to "facebook" through two hops of relations, namely, "wife of" and "founder of." to answer this type of multihop questions, we need to consider longer relation paths in order to reach the correct answers. the main challenge here is how to restrict the search space, i.e., to reduce the number of multi-hop relation paths to be considered, because the search space grows exponentially with the length of relation paths. one idea is to use beam search. for example, @xcite and @xcite proposed to consider only the best matching relation instead of all relations when extending a relation path. however, little work has been done to deal with both types of complexity together. in this paper, we handle both constraints and multi-hop relations together for complex kbqa. we propose to modify the staged query graph generation method by allowing longer relation paths. however, instead of adding constraints only after relation paths have been constructed, we propose to incorporate constraints and extend relation paths at the same time. this allows us to more effectively reduce the search space. on the complexwebquestions dataset, which has a high percentage of complex questions with both types of complexity, our method substantially outperforms existing methods with an improvement of 3.3 percentage points in prec@1 and 3.9 percentage points in f1. on two other benchmark kbqa datasets, our method also achieves the state of the art foot_0 . ## conclusion in this paper we proposed a modified staged query graph generation method to deal with complex questions with both multi-hop relations and constraints. by incorporating constraints into query graphs early, coupled with the help of beam search, we are able to restrict the search space. experiments showed our method substantially outperformed existing methods on the complexwebquestions dataset and also outperformed the previous state of the art on two other kbqa datasets.