Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering (2022)

Abstract: Recent works on knowledge base question answering (KBQA) retrieve subgraphs for easier reasoning. The desired subgraph is crucial as a small one may exclude the answer but a large one might introduce more noises. However, the existing retrieval is either heuristic or interwoven with the reasoning, causing reasoning on the partial subgraphs, which increases the reasoning bias when the intermediate supervision is missing. This paper proposes a trainable subgraph retriever (SR) decoupled from the subsequent reasoning process, which enables a plug-and-play framework to enhance any subgraph-oriented KBQA model. Extensive experiments demonstrate SR achieves significantly better retrieval and QA performance than existing retrieval methods. Via weakly supervised pre-training as well as the end-to-end fine-tuning, SR achieves new state-of-the-art performance when combined with NSM (He et al., 2021), a subgraph-oriented reasoner, for embedding-based KBQA methods. Codes and datasets are available online ( https://github.com/RUCKBReasoning/SubgraphRetrievalKBQA )

## introduction knowledge base question answering (kbqa) @xcite aims to seek answers to factoid questions from structured kbs such as freebase, wikidata, and dbpedia. kbqa has attracted a lot of attention, as the logically organized entities and their relations are beneficial for inferring the answer. semantic parsing-based (sp-based) methods @xcite @xcite and embedding-based methods @xcite @xcite are two mainstream methods for addressing kbqa. the former ones heavily rely on the expensive annotation of the intermediate logic form such as sparql. instead of parsing the questions, the later ones directly represent @xcite on webqsp @xcite and cwq @xcite . and rank entities based on their relevance to input questions. among them, the models which first retrieve a question-relevant subgraph and then perform reasoning on it @xcite @xcite reduce the reasoning space, showing superiority compared with reasoning on the whole kb @xcite @xcite (cf. subgraph retrieval is crucial to the overall qa performance, as a small subgraph is highly likely to exclude the answer but a large one might introduce noises that affect the qa performance. figure 1(a ) presents the answer coverage rates of the subgraphs with different sizes on two widely-used kbqa datasets, webqsp @xcite and cwq @xcite . we extract the full multi-hop topic-centric subgraph and control the graph size by the personalized pagerank (ppr) @xcite scores of entities. we also present the qa performance (hits@1) of nsm @xcite , a state-of-the-art embedding-based model, under the same sizes of the subgraphs in figure 1 @xcite . it is observed that although larger subgraphs are more likely to cover the answer, the qa performance drops dramatically when the subgraph includes more than 5,000 nodes. moreover, it is inefficient to extract such a full multi-hop subgraph for online qa. the results show that such heuris-tic retrieval is far from optimal. to improve the retrieval performance, pullnet @xcite proposes a trainable retriever, but the retrieving and the reasoning processes are intertwined. at each step, a lstm-based retriever selects new relations relevant to the question, and a gnn-based reasoner determines which tail entities of the new relations should be expanded into the subgraph. as a result, the inference as well as the training of the reasoner needs to be performed on the intermediate partial subgraph. since the intermediate supervision is usually unobserved, reasoning on partial subgraphs increases the bias which will eventually affect the answer reasoning on the final entire subgraph. this paper proposes a subgraph retrieval enhanced model for kbqa, which devises a trainable subgraph retriever (sr) decoupled from the subsequent reasoner. sr is devised as an efficient dual-encoder that can expand paths to induce the subgraph and can stop the expansion automatically. after that, any subgraph-oriented reasoner such as graft-net @xcite or nsm @xcite can be used to delicately deduce the answers from the subgraph. such separable retrieval and reasoning ensure the reasoning only on the final entire instead of the intermediate partial subgraphs, which enables a plug-and-play framework to enhance any subgraph-oriented reasoner. we systematically investigate the advantages of various training strategies for sr, including weakly supervised/unsupervised pre-training and end-toend fine-tuning with the reasoner. instead of the ground truth paths, we extract the shortest paths from a topic entity in the question to an answer as the weak supervision signals for pre-training. when the qa pairs themselves are also scarce, we construct pseudo (question, answer, path) labels for unsupervised pre-training. to further teach the retriever by the final qa performance, we enable the end-to-end fine-tuning, which injects the likelihood of the answer conditioned on a subgraph as the feedback from the reasoner into the prior distribution of the subgraph to update the retriever. we conduct extensive experiments on webqsp and cwq. the results reveal four major advantages: (1) sr, combined with existing subgraphoriented reasoners, achieves several gains (+0.4-9.7% hits@1 and 1.3-8.7% f1) over the same reasoner that is performed with other retrieval methods. moreover, sr together with nsm creates new state-of-the-art results for embedding-based kbqa models. (2) with the same coverage rate of the answers, sr can result in much smaller subgraphs that can deduce more accurate answers. (3) the unsupervised pre-training can improve about 20% hits@1 when none of the weak supervision data is provided. (4) the end-to-end fine-tuning can enhance the performance of the retriever as well as the reasoner. contributions. (1) we propose a trainable sr decoupled from the subsequent reasoner to enable a plug-and-play framework for enhancing any subgraph-oriented reasoner. (2) we devise sr by a simple yet effective dual-encoder, which achieves significantly better retrieval and qa results than the existing retrieval methods. (3) nsm equipped with sr, via weakly supervised pre-training and end-toend fine-tuning, achieves new sota performance for embedding-based kbqa methods. open-domain qa (openqa) aims to answer questions based on a large number of documents. most of the openqa models also consist of a retriever to identify the relevant documents and a reasoner to extract the answers from the documents. the retriever is devised as a sparse term-based method such as bm25 @xcite or a trainable dense passage retrieval method @xcite , and the reasoner deals with each document individually @xcite or fuses all the documents together @xcite . different from the documents in openqa, the subgraphs in kbqa can be only obtained by multi-hop retrieval and the reasoner should deal with the entire subgraph instead of each individual relation to find the answer. although some openqa research proposes multi-hop document retrieval @xcite , the focus is the matching of the documents rather than the relations to the questions in kbqa. thus the concrete solution for kbqa should be different from openqa. ## problem definition a knowledge base (kb) g organizes the factual information as a set of triples, i.e., @xmath0, r, e ′ )|e, e ′ ∈ e, @xmath1, where e and r denote the entity set and the relation set respectively. given a factoid question q, kbqa is to figure out the answers a q to the question q from the entity set e of g. the entities mentioned in q are topic entities denoted by e @xmath2, which are assumed to be given. this paper considers the complex questions where the answer entities are multi-hops away from the topic entities, called multi-hop kbqa. probabilistic formalization of kbqa. given a question q and one of its answers @xmath3, we formalize the kbqa problem as maximizing the probability distribution p(a|g, q). instead of directly reasoning on g, we retrieve a subgraph g ⊆ g and infer a on g. since g is unknown, we treat it as a latent variable and rewrite p(a|g, q) as: in the above equation, the target distribution p(a|g, q) is jointly modeled by a subgraph retriever p θ (g|q) and an answer reasoner p ϕ (a|q, g). the subgraph retriever p θ defines a prior distribution over a latent subgraph g conditioned on a question q, while the answer reasoner p ϕ predicts the likelihood of the answer a given g and q. the goal is to find the optimal parameters θ and ϕ that can maximize the log-likelihood of training data, i.e., ## subgraph retriever (sr) the retriever needs to calculate p θ (g|q) for any g, which is intractable as the latent variable g is combinatorial in nature. to avoid enumerating g, we propose to expand top-k paths relevant to q from the topic entities and then induce the subgraph following these paths. ## training strategies in this section, we discuss the pre-training and the end-to-end fine-tuning strategies to train the retriever. figure 3 illustrates the whole framework and the training procedure. ## conclusion we propose a subgraph retriever (sr) decoupled from the subsequent reasoner for kbqa. sr is devised as an efficient dual-encoder that can update the question when expanding the path as well as determining the stop of the expansion. the experimental results on two well-studied benchmarks show sr takes effect in improving the qa performance if injecting it before a subgraph-oriented reasoner. sr equipped with nsm creates new sota results for embedding-based kbqa methods if learning sr by weakly supervised pre-training as well as end-to-end fine-tuning.