Crake: Causal-Enhanced Table-Filler for Question Answering over Large Scale Knowledge Base (2022)

Abstract: Semantic parsing solves knowledge base (KB) question answering (KBQA) by composing a KB query, which generally involves node extraction (NE) and graph composition (GC) to detect and connect related nodes in a query. Despite the strong causal effects between NE and GC, previous works fail to directly model such causalities in their pipeline, hindering the learning of subtask correlations. Also, the sequence-generation process for GC in previous works induces ambiguity and exposure bias, which further harms accuracy. In this work, we formalize semantic parsing into two stages. In the first stage (graph structure generation), we propose a causal-enhanced table-filler to overcome the issues in sequence-modelling and to learn the internal causalities. In the second stage (relation extraction), an efficient beam-search algorithm is presented to scale complex queries on large-scale KBs. Experiments on LC-QuAD 1.0 indicate that our method surpasses previous state-of-the-arts by a large margin (17%) while remaining time and space efficiency.

## introduction to incorporate knowledge in real-world questionanswering systems, knowledge base question answering (kbqa) utilizes a background knowledge base (kb) as the source of answers to factoid natural language questions. leveraging the versatility of kb query languages like sparql @xcite , many previous works @xcite adopted a semantic parsing paradigm for kbqa, in which questions are converted to equivalent sparql queries and answers are given by executing the queries in kb. regarding the intrinsic graph structure of sparqls, some works further reduced such procedure as generating the query graph of sparqls w.r. to address these, efforts were made on devising independent pipelines for query graph construction @xcite . as in figure 1 , these pipelines usually involve a node extraction (ne) module to detect the mentions of all nodes in query graph and link entity mentions, a graph composition (gc) module to connect related nodes given by ne, and a relation extraction (re) module deciding the kb predicate corresponding to each edge added in gc. in this framework, two drawbacks exist in previous works: 1) we observe strong causal effects between ne and gc, e.g. edges connected by gc are valid only between the node mentions extracted in ne, making gc decisions highly dependent on ne. to this regard, previous works @xcite that perform ne and gc separately without causal-modelling may fall short in deeply comprehending the correlated tasks and accurately generating query graphs. 2) gc is commonly modelled as a sequence-generation in prior methods, either through generative decoder @xcite or via stagetransition @xcite . however, sequence-modelling generally undergoes sequence ambiguity and exposure bias @xcite that harms model accuracy. in this work, we formalize the generation of query graph in a two-staged manner as in figure 1 . at the first stage, we tackle the aforesaid weaknesses by a novel causal-enhanced table-filling model to jointly complete ne and gc, resulting in a query graph structure representing the connectivity of all nodes. more specifically, inspired by @xcite , we utilize a label transfer mechanism to facilitate the acquisition of causality between ne and gc (which solves drawback 1 above). further, we apply a table-filler to decode all edges simultaneously, which naturally circumvents the ambiguity and bias of iterative decoding (and solves drawback 2). for the second stage, we propose a beam-search-based relation extraction algorithm to determine the predicate that binds to each graph edge. differ from prior works, we perform candidate predicate retrieval and ranking alternately for each edge, limiting the candidate scale linearly w.r.t. kb degree and making the algorithm scalable for large-scale kbs like dbpedia. in short, the major contributions of this paper are: 1) to our knowledge, we are the first to model gc as a table-filling process, which prevents the ambiguity and bias in prior works; 2) we model the intrinsic causal effects in kbqa to grasp subtask correlations and improve pipeline integrity; 3) our method outperforms previous state-of-the-arts on lc-quad 1.0, a prominent kbqa benchmark, by a large margin (∼17%), further experiments verifies the effectiveness of our approach. ## relation extraction (re) as shown in figure 4 , relation extraction (re) conducts candidate retrieval and ranking in turn for each edge in graph structure s to decide its predicate. for a question q, an edge e connecting nodes n 1 and n 2 with mention m 1 ,m 2 respectively, candidate retrieval recalls a set of predicates p that can be bound to e. note that unlike e, each predicate in p is directional. then, candidate ranking rank(p ,q,m 1 ,m 2 ) gives each predicate a score. this section details this procedure. candidate ranking for each p @xmath0, we encode it together with q,m 1 ,m 2 by a roberta encoder and pool them to 0 ≤ s @xmath1. if the direction of p i is n 1 → n 2 , we join q, m 1 , m 2 , p i sequentially by @xcite token as model input; otherwise (direction n 2 → n 1 ), the candidate retrieval zhang et al., 2021 proposed a straightforward way to retrieve candidates: if either n 1 or n 2 is a non-variable node, the predicates around that node in kb are viewed as candidates; otherwise, they trace n 1 or n 2 in other graph edges with non-variable nodes and view the predicates k-hop away from that node in kb as candidates (e.g. predicates 2-hop away from dbo:person are candidates for ?class-?person in figure 4 ). we view this as the baseline in latter experiments. however, this results in a candidate scale o(n k ) foot_1 , making it unscalable to multi-hop queries (k↑) and large kbs (n↑). here, we propose algorithm 1 to limit the scale to o(n). we start by selecting an edge between n a 1 and n b 1 containing a non-variable node (e.g. edge ?class-dbr:swinhoe's_crake in figure 4 ), retrieving all adjacent predicates of that node in kb and use rank to select the most proper predicate p 1 (e.g. dbp:named_by) of score s 1 , this forms a subgraph @xmath2,n b 1 ,p 1 )} with only one edge whose score is s 1 . then, we sample another edge between n a 2 and n b 2 (e.g. ?class-?person) and retrieve its candidates p based on g (e.g. g already entails ?@xmath3:bird, so all neighbors of dbr:bird forms p ), this process is denoted as retrieve(g, n a 2 , n b 2 ). now, we use rank to se-type methods p r f1 i nsqa @xcite .448 .458 .445 edgqa @xcite .505 .560 .531 ## experiments dataset we adopt lc-quad 1.0 @xcite , a predominant open-domain english kbqa benchmark based on dbpedia @xcite 2016-04, to test the performance of our system. we randomly sample 200 questions from train data as dev set and follow the raw test set, resulting in a 4800/200/1000 train/dev/test split. more details on the dataset can be found in appendix c. like zhang et al., 2021, we do not experiment on multiple datasets due to the high annotation cost involved, however, we conduct no dataset-specific optimizations in this work, so we consider the large improvements on lc-quad and detailed discussions sufficient to prove our effectiveness. annotation we annotate the dataset with the mention of each node in query graph, e.g. the mention "class" and "person" for the node ?class and dbo:person respectively in figure 1 . with the annotation, we obtain the gold data (g ne ,g gc ) to train our models. appendix d details the annotation process. ## conclusion in this work, we formalize the generation of query graphs in kbqa by two stages, namely graph structure generation (gsg) and relation extraction (re). in gsg, we propose a table-filling model for graph composition to avoid the ambiguity and bias of sequence-modelling, meanwhile, we encode the inherent causal effects among gsg by a labeltransfer block to improve the stage integrity. in re, we introduce an effective beam-search algorithm to retrieve and rank predicates in order for each edge, which turns out to be scalable for large kbs and multi-hop queries. consequently, our approach substantially surpasses previous state-of-the-arts in kbqa, revealing the effectiveness of our pipeline design. detailed experiments also validate the effects of all our contributions.