Improving Query Graph Generation for Complex Question Answering over Knowledge Base (2021)

Abstract: Most of the existing Knowledge-based Question Answering (KBQA) methods first learn to map the given question to a query graph, and then convert the graph to an executable query to find the answer. The query graph is typically expanded progressively from the topic entity based on a sequence prediction model. In this paper, we propose a new solution to query graph generation that works in the opposite manner: we start with the entire knowledge base and gradually shrink it to the desired query graph. This approach improves both the efficiency and the accuracy of query graph generation, especially for complex multi-hop questions. Experimental results show that our method achieves state-of-the-art performance on ComplexWebQuestion (CWQ) dataset.

## introduction knowledge-based question answering (kbqa) is the task of finding answers to questions by processing a structured knowledge base kb. a kb graph consists of general facts which are organized as entity-relation-entity triplets, with entities as vertices and relations as edges. to answer a simple question such as: "who is the president of the united states?", a typical kbqa system first identifies the entity (i.e., "united states") and the relation (i.e., "president") asked in the question, and then searches for the answer entity by matching the triplet fact @xmath0, president, ?> over kb @xcite @xcite @xcite . to answer a multi-hop question, multiple facts are extracted to form a structured representation, namely, a query graph @xcite . for example, the question "what was the name of the publisher for disney channel magazine's first cartoon?" corresponds to a query graph that consists of 3 facts with grounded (i.e., topic entity) and ungrounded entities (i.e., "?"): <?, publisher, disney channel magazine>, <?, cartoon, ?>, <?, published date, ?>, and a constraint: order by. the query graph can be converted to an executable query to find the answer in kb. generating the query graph accurately and efficiently is the key challenge in kbqa. while single-hop questions are easy to answer by searching for a single fact in kb, multi-hop questions are much harder to answer because the search space grows exponentially as the number of hops increases. the most common way to solve a multi-hop question is to first generate candidate query graphs and then validate and rank them down to one. previous works construct candidate query graphs by starting with the topic entity and progressively expanding the graph @xcite @xcite @xcite . they greedily determine what relation best fits the current incomplete query graph at each step, but fail to capture global properties of the complete query graph. at each step as the query graph grows, these step-wise models need to query the kb, measure semantic relevance, and update the model, which inevitably leads to high computational cost. for example, it takes more than two weeks to train the state-of-the-art model qgg @xcite on complexwebquestion dataset @xcite . to reduce the computation, these methods limit the maximum length of the search path to a small number, and use beam search to maintain only the top candidates at each step; thus causing some good candidates to be missed. we instead propose a novel query graph generation method that works in quite the opposite manner: we start with the entire kb and gradually shrink it to the desired query graph. in the candidate query graph generation stage, in contrast to existing works that use expensive semantic relevance features, we only rely on cheap global features that capture syntactic matches with the query or structure matches with kb. this allows us to quickly ## methodology first we introduce some definitions and notations. for a given knowledge base kb, its associated relation graph rg is the undirected graph whose vertices correspond to the edges in kb, and whose edges correspond to the edge adjacencies in kb (two nodes in rg are connected if the corresponding two edges in kb share a common entity node). a query graph g q is a subgraph of kb, which reveals the semantic structure and the topic entities of the input question q. one can translate a query graph into an executable sparql query and execute it against the kb to obtain the answer entities. a typical query graph consists of four types of nodes @xcite : the grounded entity corresponding to e topic ; existential variables e ung , which are ungrounded entities; the lambda variable e ans , which is an ungrounded entity rep-resenting the answer. it is also a common practice to define some aggregation functions nodes for g q , which represent set operations (e.g., argmax and order by) on e ung or e ans . to find the answer to a question q, our method shrinks kb down to g q in three stages: relation subgraph extractor predicts a relation subgraph rg q ⊂ rg for an input question q; query graph generator generates a set of candidate query graphs g q j ⊂ kb, @xmath1, 2, • • • ; query graph ranker ranks g q j and selects the top one as the answer. relation subgraph extractor: we first extract a relation subgraph rg q ⊂ rg for an input question q. rg q only captures relations relevant to q (see a running example in figure 1a ). the reason of considering a relation graph (with relations as nodes) instead of an entity graph (with entities as nodes) is that we want the graph size to be small, and in typical kb the number of relations is much smaller than the number of entities. we identify the relations in rg q for the given question with a multi-label classifier. specifically, we consider all annotated relations in the training data as potential labels and train binary relevance @xcite with logistic regression to determine the relevance of each relation. unigrams from the questions are used as features. because the given questions are very short, both extracting unigrams and running logistic regressions on sparse features are very fast. next we extract a subgraph rg q ⊂ rg whose nodes correspond to the predicted relevant relations. in effect, we narrow down the search space from the entire kb (38m entities) to a small relation graph of about 10-20 relations. query graph generator: we aim to get a set of candidate query graphs g q j ⊂ kb, @xmath2, 2, • • • . we start with the relation subgraph rg q ⊂ rg from previous stage, and further narrow down the search space by selecting some of its high-quality subgraphs rg q i ⊂ rg q , @xmath3, 2, • • • , which represent relevant relation query structures. we propose to find such rg q i that leads to answers with high f1 scores using a logistic regression model. in practice, we consider all subgraphs of rg q with up to 5 nodes as candidates (see examples of the top three rg q i in figure 1b ). four types of features are used to characterize each candidate subgraph rg q i : (1) shape of the graph (categorical): two graphs have the same shape if they are isomorphic; 15 different shapes are identified. (2) relation relevance score (numeric): for relations in rg q i , we use their relevance scores generated in the previous stage. for relations not in rg q i , the scores are set to 0. (3) relation pairs: the presence of each adjacent relation pair is used as a binary feature. (4) (relation, entity type, relation) triplets (binary): for each adjacent relation pair, we further combine it with the most common entity type of the connected node. in training, we integrate rg q i with labeled topic entities to build a query graph, and execute it to get the answer and measure answer f1 score. we generate training data for logistic regression by including all positive subgraphs with high f1 scores and randomly sample 30 negative subgraphs. we turn f1 scores into binary training labels based on a threshold 0.9. once the logistic regression model is trained using the extracted features, we can use it to score and rank rg q i . after selecting the top 50 rg q i , we couple them with topic entities e topic to build query graph candidates g q j . each rg q i can be mapped to multiple g q j by inserting different topic entities at different positions and assigning different relation directions (see an example of g q j in figure 1c ). after this step, the generated g q j only contains one topic entity. to build a query graph for a question with multiple topic entities, we merge the generated query graphs with similar relation structures but different entities. for example, e ung query graph ranker: we rank the candidate query graphs g q j , @xmath4, 2, • • • , and use the top one g q best to produce the final answer to the input question q. since there are only a small number of generated candidate query graphs, we can afford to evaluate them with a powerful and expensive model. we use the albert @xcite to compute the matching score between g q j and q. to represent g q j as a sequence of tokens and concatenate it with q, we locate the source node foot_0 and concatenate all paths starting from the source node to make a sequence. the example in figure 1c has source node e 0 and two paths that point to e topic and e 2 separately. we represent the ungrounded entities as their entity types. then the concatenation is sent to the albert model to get a matching score. following previous work @xcite , we further augment g q best with constraints based on a set of predefined rules. this is necessary for detecting time and number constraints in superlative and comparative questions. the rules consist of mappings from keywords to sparql constraints as shown in then, we execute the query against the kb to obtain the answer. because all nodes in g q best except the grounded entities and cvt nodes 2 can potentially be the answer node, in the last step we resolve the answer node using a simple heuristic: we compare g q best with all annotated query graphs in the training set to select graphs which are isomorphic to g q best . from the selected graphs, we choose cwq wqsp hr-bilstm @xcite 31.2 † 62.3 † graft-net @xcite 26.0 † 62.8 kbqa-gst @xcite 36.5 67.9 textray @xcite 33.9 60.3 uhop (chen et al., 2019) 29.8 † 68.5 † qgg (lan and jiang, 2020) 40.4 74.0 our method 46.2 66.0 (a) query graph generator ∆ coverage w/o shape of the graph -2.4% w/o relation relevance score -1.3% w/o relation pairs -0.4% w/o (relation, entity type, relation) triplets -4.5% query graph ranker ∆ f1 w/o query graph merge -3.5% w/o path encoding -1.4% w/o entity type encoding -4.5% w/o constraints modeling -1.3% w/ top 5 prediction +14.5% (b) cwq wqsp coverage upper bound f1 cardinality coverage upper bound f1 cardinality entity linking 0.732 -25.7 (#entities) 0.961 -2.3 (#entities) relation subgraph extractor -0.859 13.1 (#relations) -0.855 16.2 (#relations) query graph generator -0.741 83.6 (#query graphs) -0.771 20.6 (#query graphs) query graph ranker -0.462 1(#query graphs) -0.660 1(#query graphs) (c) the node (e.g., the top left node) which has most often been the answer node in the dataset. this heuristic achieves over 90% accuracy in practice. ## results and analysis we conduct experiments on two popular multi-hop kbqa datasets, complexwebquestion-1.1 (cwq) @xcite and webques-tionsp (wqsp) @xcite . cwq dataset has 34,689 complex questions (2-5 hops), while wqsp dataset contains 4,737 simple questions (1 or 2 hops). in this work, we use cwq for the main evaluation because our method is designed for complex questions. both datasets use freebase @xcite as the supporting knowledge base. we implement our model using networkx @xcite , pytorch-1.6.0 @xcite , and huggingface @xcite . for entity linking, we take a union of allennlp @xcite and stanford ner @xcite outputs in cwq experiments and use s-mart @xcite in wqsp experiments. we further build an uppercase detector to add uppercase words to the ensembling results. for entity type linking, we search for entity types from the freebase via two relations, ns:common.topic.notable_types and ns:type.object.name. for albert training, we initialize the model with pre-trained weights and fine-tune it on the corresponding kbqa dataset for 5 epochs. the model has 12 layers, 4096 hidden dimensions, and 64 attention heads. we set learning rate to 1e -5 and limit the maximum length of input sequence to 128 tokens. ## conclusion we propose a novel query graph generation method by gradually shrinking a kb to a desired query graph. compared to previous approaches, our approach is more computationally efficient. experiments show that our method delivers consistent performance on two kbqa datasets: it improves the state-of-the-art results by an absolute 5.8% in f1 on the multi-hop kbqa task cwq and produce competitive result on the single-hop / two-hop kbqa task wqsp. in contrast, while some baseline methods work somewhat better on simple single-hop / two-hop questions, their performance drops dramatically on complex multi-hop questions.