Source-linked AI summary
Subgraph Retrieval Enhanced Model for Multi-hop Knowledge Base Question Answering
Jing Zhang, Xiaokang Zhang, Jifan Yu, Jian Tang, Jie Tang, Cuiping Li, Hong Chen
TL;DR
KBQA subgraph retrieval must avoid both missing answers in small graphs and noise in large ones, while existing approaches can entangle retrieval with reasoning on partial graphs. The paper introduces a decoupled trainable subgraph retriever that supports plug-and-play reasoning and reports stronger QA results, including new state-of-the-art embedding-based KBQA performance with NSM.
Problem
Existing KBQA subgraph retrieval can be heuristic or intertwined with reasoning, creating a need for retrieval that avoids reasoning on incomplete intermediate subgraphs.
Method
SR is a trainable dual-encoder that expands paths into subgraphs, stops expansion automatically, and remains decoupled from the subsequent subgraph-oriented reasoner.
Results
SR improves retrieval and QA performance over existing methods, while SR with NSM achieves new state-of-the-art results for embedding-based KBQA.
Takeaways & Limitations
SR provides a plug-and-play way to enhance subgraph-oriented reasoners, with weakly supervised pre-training and end-to-end fine-tuning improving the combined system.
Takeaways & Limitations
The value of some key parameters that seriously impact the model’s performance is unknown.
Abstract
from arXiv · showhide
Recent works on knowledge base question answering (KBQA) retrieve subgraphs for easier reasoning. A 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, SRl achieves new state-of-the-art performance when combined with NSM, a subgraph-oriented reasoner, for embedding-based KBQA methods.
1 Introduction
KBQA subgraph retrieval must balance answer coverage against noise, while prior trainable retrieval can entangle retrieval with reasoning on partial subgraphs. The paper introduces a decoupled trainable retriever and reports stronger retrieval and QA performance, including new embedding-based KBQA state of the art with NSM.
- Motivation: Larger subgraphs improve answer coverage but can reduce NSM’s QA performance because they introduce noise.Figure 1 evaluates answer coverage and Hits@1 on WebQSP and CWQ while varying subgraph size.
- Motivation: PullNet intertwines retrieval and reasoning, requiring training and inference on intermediate partial subgraphs despite usually unobserved intermediate supervision.Its retriever selects relations while its reasoner determines which tail entities to expand.
- Approach: SR decouples trainable subgraph retrieval from subsequent reasoning, allowing reasoning only on the final entire subgraph.The dual-encoder expands paths and automatically stops expansion, after which models such as GRAFT-Net or NSM can reason.
- Training: SR supports weakly supervised and unsupervised pre-training using shortest or pseudo question-answer-path labels, followed by end-to-end fine-tuning from QA feedback.The feedback updates the retriever’s prior distribution over subgraphs.
- Results: +0.4-9.7% Hits@1 and 1.3-8.7% F1 are achieved over the same reasoners using other retrieval methods.The experiments cover WebQSP and CWQ and report new state-of-the-art embedding-based KBQA results when SR is combined with NSM.
2 Related Work
KBQA methods use either semantic parsing or embeddings, while OpenQA retrieval focuses on documents. Multi-hop KBQA instead requires relation-level subgraph retrieval and reasoning over the entire retrieved subgraph.
- KBQA Methods: KBQA solutions are categorized into semantic parsing-based and embedding-based methods.Semantic parsing methods execute question-derived logic forms, whereas embedding-based methods embed entities and rank them by relevance.
- KBQA Methods: Semantic parsing methods require expensive logic-form supervision or are limited to narrow domains with few logical predicates.This passage contrasts their supervision and domain requirements with embedding-based approaches.
- OpenQA Comparison: OpenQA retrievers identify relevant documents, but KBQA must obtain subgraphs through multi-hop retrieval and reason over the entire subgraph.The paper therefore distinguishes KBQA solutions from document-matching approaches in OpenQA.
3 Problem Definition
The paper models multi-hop KBQA as answer inference from a latent retrieved subgraph rather than directly from the full knowledge base. Retrieval and reasoning are represented as separate probabilistic components that can be trained sequentially or jointly instantiated with subgraph-oriented reasoners.
- KBQA Definition: A knowledge base stores factual information as entity-relation-entity triples, and multi-hop KBQA seeks answers several hops from given topic entities.Entities and relations are denoted by E and R, while question topic entities are assumed given.
- Probabilistic Formalization: The model retrieves a latent subgraph G from the knowledge base and infers an answer a from G and question q.This replaces direct reasoning over the full knowledge base with subgraph-based inference.
- Probabilistic Formalization: The retriever pθ(G|q) defines a question-conditioned prior over subgraphs, while the reasoner pφ(a|q,G) models answer likelihood.Together they model the target answer distribution.
- Optimization: The retriever and reasoner can be decoupled by training the retriever first and then training the reasoner on its sampled subgraphs.The reasoner can be instantiated by subgraph-oriented models such as GRAFT-Net and NSM.
4 Subgraph Retriever (SR)
SR avoids enumerating combinatorial subgraphs by expanding high-scoring relation paths from topic entities, inducing trees, and merging them into a unified subgraph.
- Path Expansion: SR expands top-K question-relevant relation paths from topic entities and induces a tree for each path.The retriever uses beam search to obtain multiple candidate paths rather than relying on a single path.
- Path Expansion: Relation relevance is computed from dot-product embeddings of the question and relation, using RoBERTa representations.The question representation incorporates previously expanded relations to condition later expansion decisions.
- Path Expansion: Expansion stops when no candidate relation exceeds the virtual END threshold, while otherwise selecting the top-1 relation above 0.5.The END relation supplies an adaptive stopping criterion for each path.
- Path Expansion: From each topic entity, SR obtains K paths through top-K beam search, producing nK paths and corresponding instantiated trees across n topic entities.Beam search reduces dependence on the single highest-scoring path.
- Subgraph Construction: SR merges trees from different topic entities by identifying shared entities and retaining the traced paths connecting roots to leaves.This merging constrains the final subgraph and reduces the answer-reasoning space.
5 Training Strategies
SR is trained with weakly supervised or unsupervised path pre-training and can then be fine-tuned end to end using answer likelihood feedback from the reasoner.
- Weakly Supervised Pre-Training: Weakly supervised pre-training uses shortest paths from question topic entities to answers because ground-truth subgraphs are difficult to obtain.The paths are derived from question–answer pairs and serve as retriever supervision.
- Unsupervised Pre-Training: When question–answer pairs are scarce, unsupervised pre-training constructs pseudo labels from chained NYT relation-extraction instances.Concatenated sentences form the question, while concatenated relations form the corresponding path.
- End-to-End Fine-Tuning: End-to-end fine-tuning optimizes posterior path probabilities that combine the retriever prior with the reasoner’s answer likelihood.The posterior is approximated by summing probabilities over the nK paths and applying Bayes’ rule path-wise.
- End-to-End Fine-Tuning: The reasoner estimates answer likelihood on each individual path-induced tree so its feedback can be assigned to the corresponding retriever path.The same reasoner is used for likelihood estimation on individual trees and the fused subgraph.
- End-to-End Fine-Tuning: Although retriever and reasoner are jointly trained, reasoning remains performed on the retrieved entire subgraph at each epoch.This preserves the separation from intermediate partial-subgraph reasoning during training.
6 Experiments
Experiments on WebQSP and CWQ evaluate SR’s QA impact, retrieved-subgraph quality, training strategies, and compatibility with existing reasoners. SR improves retrieval and QA performance, produces smaller higher-quality subgraphs, and benefits from weak supervision and end-to-end fine-tuning.
- Experimental Settings: Experiments use WebQSP and CWQ, evaluating answer coverage, Hits@1, and F1 for retrieval and QA.Answer coverage measures whether retrieved paths contain an answer; QA uses top-1 correctness and F1 for multiple-answer questions.
- Overall QA Evaluation: SR improves existing subgraph-oriented reasoners by 0.4-9.7% Hits@1 and 1.3-8.7% F1, with SR+NSM achieving state-of-the-art embedding-based KBQA performance.On CWQ, SR+NSM improves over NSM by 3.9% Hits@1 and 4.7% F1, while SR+GRAFT-Net improves CWQ by 9.7% Hits@1 and 8.7% F1.
- Quality of Retrieved Subgraph: At the same subgraph size, SR achieves higher answer coverage than PPR, while at the same coverage rate its subgraphs yield higher NSM Hits@1.These comparisons evaluate both retrieval coverage and downstream QA quality under controlled subgraph size or answer coverage.
- Retriever Strategy Ablations: Removing question updating reduces Hits@1 by 4.3-15.0%, while replacing learned path ending with fixed length reduces it by 2.1-18.5%.The fixed path length is optimally set to 3 on both WebQSP and CWQ.
- Training Strategy Evaluation: Unsupervised pre-training improves the original SR by about 20% Hits@1 without weakly supervised data, while weakly supervised performance grows consistently with more generated data.The unsupervised strategy is presented as an alternative when QA pairs are scarce.
- Training Strategy Evaluation: End-to-end fine-tuning improves retrieval by 2-10.6% Hits@1 and improves QA Hits@1 by 0.6% for SR+NSM on WebQSP and 1.5-2.5% for SR+GRAFT-Net.The reported results indicate that answer likelihood feedback from the reasoner can improve the retriever and, through updated subgraphs, the reasoner.
7 Conclusion
SR is a decoupled, efficient dual-encoder retriever for KBQA that improves downstream subgraph reasoning. Combined with NSM and trained with weak supervision plus end-to-end fine-tuning, it achieves new state-of-the-art embedding-based KBQA results.
- SR is decoupled from the subsequent reasoner and designed to enhance subgraph-oriented KBQA reasoners in a plug-and-play framework.
- SR uses an efficient dual-encoder that updates questions during path expansion and determines when expansion should stop.
- SR improves QA performance when inserted before a subgraph-oriented reasoner on two established benchmarks.
- NSM with SR achieves new state-of-the-art results for embedding-based KBQA when SR uses weakly supervised pre-training and end-to-end fine-tuning.
A.1 Interpretability of Retrieved Paths.
The paper presents top-ranked paths retrieved by SR for questions from WebQSP and CWQ. These paths can make the inferred answers interpretable, including paths discovered beyond the datasets’ ground-truth paths.
- The table presents the top-nK paths learned by SR for several WebQSP and CWQ questions.
- Each path is represented by its topic entity before the colon.
- An asterisk marks a path discovered by SR beyond the ground-truth path provided by WebQSP and CWQ.
- The retrieved paths provide explanations for why an answer is inferred for a question.
A.2 Training Algorithm.
Training proceeds in stages: pre-train the retriever, train the reasoner on retrieved subgraphs, and then jointly fine-tune both components end to end.
- Algorithm 1 first pre-trains the retriever using weakly supervised or unsupervised signals, including only 20% weakly supervised signals in one option.
- The reasoner is then trained on the subgraphs retrieved by the pre-trained retriever.
- End-to-end training repeatedly samples a subgraph for each question–answer pair while the joint objective is optimized until convergence.
7 end
The implementation warms up the retriever and reasoner before end-to-end training, uses RoBERTa-base, and retrieves ten relations per step. SR’s online inference can be faster than PPR-based retrieval pipelines.
- General Setting: RoBERTa-base has 12 layers, a 768-dimensional hidden size, 12 attention heads, and 110M parameters.
- Supervised Training: WebQSP supervised training uses 3,098 question–path instances decomposed into 5,394 question–relation instances.
- Weakly supervised Pre-training: Weakly supervised pre-training extracts shortest paths between topic entities and answers when ground-truth paths are unavailable.
- Unsupervised Pre-training: Unsupervised pre-training creates 100,000 sentence–path pseudo-instances from NYT and can then adapt SR to various KBQA datasets.
- End-to-End Training: The retriever is warmed up by weakly supervised or unsupervised pre-training, while the reasoner is warmed up with supervised question–answer training before joint optimization.
- Inference: 10 relevant relations are retrieved at each step, producing 10 paths per topic entity, with online retrieval and reasoning taking within 1 second on average.
- Inference: PPR-based GRAFT-Net and NSM pipelines take about 2 to 3 seconds, or even 7 to 8 seconds for some dense subgraphs.