Semantic Structure Based Query Graph Prediction for Question Answering over Knowledge Graph (2022)

Abstract: Building query graphs from natural language questions is an important step in complex question answering over knowledge graph (Complex KGQA). In general, a question can be correctly answered if its query graph is built correctly and the right answer is then retrieved by issuing the query graph against the KG. Therefore, this paper focuses on query graph generation from natural language questions. Existing approaches for query graph generation ignore the semantic structure of a question, resulting in a large number of noisy query graph candidates that undermine prediction accuracies. In this paper, we define six semantic structures from common questions in KGQA and develop a novel Structure-BERT to predict the semantic structure of a question. By doing so, we can first filter out noisy candidate query graphs by the predicted semantic structures, and then rank the remaining candidates with a BERT-based ranking model. Extensive experiments on two popular benchmarks MetaQA and WebQuestionsSP (WSP) demonstrate the effectiveness of our method as compared to state-of-the-arts.

## introduction knowledge graph (kg) is a graph structured database @xcite , in which nodes represent entities (e.g., hedgehog in the fog, sergei kozlov), and edges reflect the relations between entities (e.g., hedgehog in the fog -written_by -sergei kozlov). users can get crisp answers by querying kgs with natural language questions, and this process is called question answering over knowledge graph @xcite . recently, consumer market witnesses a widespread application of this technique in a variety of virtual assistants, such as apple siri, google home, amazon alexa, and microsoft cortana, etc. early works @xcite on kgqa mainly focus on simple questions, such as where is the hometown of obama? this question only involves in one relation path (e.g., hometown or birth-place) in kg, and is relatively easy to solve. however, many questions in daily qa sessions are often more complex, manifested by multi-hop reasoning or questions with multiple constraints. therefore, recently there is a flurry of interests on complex kgqa @xcite . there are two types of complexity when dealing with complex kgqa, i.e., multi-hop questions and questions with multiple constraints (see figure 1 for example). question 1 in figure 1 is a typical multi-hop question, to which the answer is related to yuriy norshteyn with twohop relations: directed.by.reverse and written.by. in response to this challenge, @xcite enhances the traditional key-value memory neural networks (kv-memnns) @xcite for multi-hop question answering. they design a query updating strategy to decompose the question and predict the relevant relation paths at each hop. transfernet @xcite is an effective and transparent model for multi-hop questions; it attends to different parts of the question at each hop and computes activated scores for relation path prediction. despite the promising results, it's still challenging for these models to predict relation paths accurately at each hop, and thus suffer from error propagation over multi-hop reasoning. similarly, question 2 in figure 1 is an example of question with constraints. apparently, there is a single relation path between the topic entity cher and the answer chaz bono, but the constraint of person.@xmath0. to handle this type of complex questions, many works built on the idea of query ranking are proposed @xcite @xcite , which rank candidate queries by the similarity scores between question and candidate queries. specifically, these ranking methods use query graphs to represent queries, and explore various strategies to generate candidate query graphs for ranking. typical strategies assume the answers are within n hops of topic entity, and enumerate all the relation paths within n hops to generate candidate query graphs. although this candidate generation strategy can yield all valid query graphs from a topic entity, they have two main limitations: (1) the generated candidate query graphs are very noisy. as shown in figure 2 (a), a candidate query graph with an incorrect structure is presented; this candidate query graph is generated by the traditional enumeration strategy but lacks of the constraint on person.gender, which can incur considerable error in query graph ranking (see to mitigate the aforementioned issues, this paper proposes sskgqa, a semantic structure based framework for complex kgqa. we represent both the multi-hop questions and questions with constraints in a way similar to query graphs 1 and rank the generated candidate query graphs by the simi-1 for example, one candidate query graph for question 1 in figure 1 can be written as y uriy.n @xmath1.by.@xmath2.@xmath3. queen isabella isabel de portugal female parent queen isabella juan ii de castilla toro question: what is the birth place of queen isabella 's mother? gender birth place parent lisboa (a) (b) answer: lisboa birth place figure 2: example two-hop candidate query graphs for a question with constraints. (a) a candidate query graph with an incorrect semantic structure, (b) a candidate query graph with a correct semantic structure. specifically, we define six semantic structures based on the question topology that is introduced by @xcite . with the defined semantic structures, our sskgqa processes a natural language question in two stages. in the first stage, we develop a novel structure-bert to predict the semantic structure of a natural language question, which is then used to filter out noisy candidate query graphs and produce a set of query graph candidates that match the predicted structure. in the second stage, we rank the remaining candidate query graphs of a question by a bert-based ranking model and identify the top-1 candidate query graph, which is then issued to retrieve the final answer from a kg. our experiments demonstrate that this semantic structure based query graph prediction strategy is very effective and enables sskgqa to outperform state-of-the-art methods. our main contributions are summarized as follows. (1) we propose sskgqa, a semantic structure based method to predict query graphs from natural language questions. sskgqa can handle both multi-hop questions and questions with constraints and is a unified framework for complex kgqa. (2) we develop a novel structure-bert to predict the semantic structure of each question, and a bert-based ranking model with a triplet loss to identify the top-1 query graph candidate. (3) compared to state-of-the-arts methods, our sskgqa demonstrates superior performance on two popular complex kgqa benchmarks. ## the proposed method we first provide an overview of sskgqa, and then discuss its main components: (1) structure-bert and (2) query graph ranking in details. ## experiments we evaluate the performance of sskgqa on two popular kgqa benchmarks: metaqa and we-bquestionssp (wsp), and compare it with seven state-of-the-arts methods. ablation study is also conducted to understand the effectiveness of different components of sskgqa. our pytorch source code is provided at https: //github.com/toneli/sskgqa . all our experiments are performed on nvidia rtx gpus. ## conclusions this paper introduces sskgqa, a semantic structure based method to predict query graphs from natural language questions. compared to prior query graph prediction based methods, sskgqa filters out noisy candidate query graphs based on the semantic structures of input questions. to this end, we define six semantic structures from common questions of the kgqa benchmarks. a novel structure-bert classifier is then introduced to predict the semantic structure of each question, and a bert-based ranking model with a triplet loss is proposed for query graph ranking. extensive experiments on metaqa and wsp demonstrate the superior performance of sskgqa over seven state-of-the-art methods. as for future work, we plan to investigate techniques to design additional semantic structures to cover the remaining 22.98% of questions in wsp. we would like also to improve structure-bert's accuracy on wsp by addressing the class imbalance and data scarcity issues of wsp.