Source-linked AI summary
PullNet: Open Domain Question Answering with Iterative Retrieval on Knowledge Bases and Text
Haitian Sun, Tania Bedrax-Weiss, William W. Cohen
TL;DR
Open-domain QA must answer multi-hop questions from corpora, incomplete KBs, or both. PullNet jointly learns iterative retrieval and graph-based reasoning over a question-specific heterogeneous subgraph using weak supervision from question-answer pairs. It improves prior systems, with especially large gains in multi-hop and corpus-plus-incomplete-KB settings.
Problem
Open-domain QA must retrieve and reason over corpus text and incomplete KBs for questions requiring non-trivial multi-hop reasoning.
Method
PullNet iteratively constructs a question-specific corpus–KB subgraph by learning graph-CNN-guided pull operations, then uses graph-CNN reasoning to extract the answer.
Results
PullNet improves prior state-of-the-art results across KB-only, text-only, and corpus-plus-incomplete-KB settings, with dramatic gains on multi-hop questions.
Takeaways & Limitations
Iterative hybrid retrieval supports reasoning over large KBs and text while producing small, high-recall subgraphs for multi-hop QA.
Takeaways & Limitations
In incomplete-KB settings, PullNet’s weak training uses shortest paths found in a complete KB rather than gold inference paths.
Abstract
from arXiv · showhide
We consider open-domain queston answering (QA) where answers are drawn from either a corpus, a knowledge base (KB), or a combination of both of these. We focus on a setting in which a corpus is supplemented with a large but incomplete KB, and on questions that require non-trivial (e.g., ``multi-hop'') reasoning. We describe PullNet, an integrated framework for (1) learning what to retrieve (from the KB and/or corpus) and (2) reasoning with this heterogeneous information to find the best answer. PullNet uses an {iterative} process to construct a question-specific subgraph that contains information relevant to the question. In each iteration, a graph convolutional network (graph CNN) is used to identify subgraph nodes that should be expanded using retrieval (or ``pull'') operations on the corpus and/or KB. After the subgraph is complete, a similar graph CNN is used to extract the answer from the subgraph. This retrieve-and-reason process allows us to answer multi-hop questions using large KBs and corpora. PullNet is weakly supervised, requiring question-answer pairs but not gold inference paths. Experimentally PullNet improves over the prior state-of-the art, and in the setting where a corpus is used with incomplete KB these improvements are often dramatic. PullNet is also often superior to prior systems in a KB-only setting or a text-only setting.
1 Introduction
Open-domain QA must handle incomplete knowledge bases, difficult natural-language retrieval, and compositional reasoning. PullNet learns iterative retrieval and reasoning over a unified corpus–KB subgraph, producing compact, high-recall structures for answer extraction.
- 1 Introduction: Open-domain QA draws answers from natural-language corpora, knowledge bases, or both, but each source has important limitations.Knowledge bases are incomplete, while corpus-based QA faces diverse natural language.
- 1 Introduction: PullNet integrates retrieval learning and heterogeneous reasoning for multi-hop questions with an incomplete KB supplemented by text.The framework restricts answers to KB entities and uses early fusion rather than separate corpus and KB systems.
- 1 Introduction: PullNet replaces GRAFT-Net’s heuristic subgraph construction, which can create oversized graphs that omit the answer, with learned retrieval.Both systems use graph-CNN reasoning, but PullNet learns which existing nodes to expand.
- 1 Introduction: The iterative process starts from the question and its entities, then retrieves likely-useful KB and corpus information to form smaller, high-recall subgraphs.This avoids naively expanding all corpus and KB elements within k hops, a particular challenge for multi-hop questions.
- 1 Introduction: 62.5% to 91.4% hits-at-one: PullNet improves 3-hop MetaQA performance in the KB-only setting.The introduction reports this as an example of a dramatic multi-hop improvement.
2 Related Work
Related work spans reading-comprehension and retrieve-and-read systems, text-only iterative retrieval, and KB-based QA. PullNet differs by combining iterative retrieval from both corpora and KBs with graph-based reasoning over their unified representation.
- 2 Related Work: Reading-comprehension systems encode a question and passage but generally cannot process a large corpus because of memory limitations.Retrieve-and-read pipelines address this limitation by separating retrieval from reading.
- 2 Related Work: SplitQA decomposes complex text-only questions into sequentially retrieved subquestions, but does not use a KB and has unclear generality beyond Complex WebQuestions.Its iterative retrieval therefore differs from PullNet’s hybrid corpus–KB approach.
- 2 Related Work: KB-based QA includes memory networks, semantic parsing, and reinforcement learning, while extending these methods to incorporate text is non-trivial.Hybrid systems have also stored text and KB facts in shared representations.
- 2 Related Work: GRAFT-Net performs multi-hop reasoning over KB facts and text with graph representations, whereas PullNet learns iterative retrieval instead of retrieving the entire graph at once.PullNet retains the same representation and reasoning scheme while changing graph construction.
- 2 Related Work: QA differs from knowledge-base completion because inference must be conditioned on a natural-language question.This conditioning creates distinct constraints on applicable methods.
3 The PullNet Model
PullNet iteratively constructs a heterogeneous question subgraph by selecting nodes for retrieval from a corpus and KB, then applies graph-CNN classification to extract an answer. Its weakly supervised retrieval process uses question-answer pairs and targets compact, high-recall subgraphs for multi-hop reasoning.
- Iterative retrieval: PullNet starts with question text and mentioned entities, then expands the subgraph over T iterations by retrieving documents and facts for selected entity nodes.Each iteration adds retrieved documents, facts, linked entities, and corresponding edges to the question graph.
- Question subgraph: The question subgraph contains entity, text, and fact nodes connected according to entity mentions and KB subject-object relations.Text nodes represent entity-linked corpus sentences, and fact nodes represent KB triples.
- Pull operations: Pull operations either retrieve corpus or KB information or extract entities from newly retrieved documents and facts.Corpus documents are ranked by IDF similarity to the question and constrained to link to the selected entity; KB facts are ranked using learned relation-question similarity.
- Graph classification: A graph-CNN classifier selects entity nodes for expansion, while a second classifier predicts the highest-scoring answer entity after construction.Retrieval classification chooses nodes above a probability threshold or among the highest-probability candidates; answer classification operates on the completed graph.
- Training: Weak supervision trains retrieval and similarity models without gold inference paths, using question-answer pairs and shortest-path-derived intermediate-entity labels.Training also uses teacher forcing and adds missed candidate intermediates to the graph; in incomplete-KB settings, these labels are derived from the complete KB.
4 Experiments and Results
MetaQA provides a movie-domain benchmark with more than 400k single- and multi-hop questions. The experiments use its vanilla queries together with the supplied WikiMovies KB and text corpus.
- Dataset: MetaQA contains more than 400k single- and multi-hop questions, including questions requiring up to 3 hops, in the movie domain.Its questions were constructed using the WikiMovies knowledge base.
- Dataset: The vanilla MetaQA version uses 1-hop questions that are exactly the same as WikiMovies.
- Experimental setup: Experiments use the KB and text corpus supplied with WikiMovies and run a simple exact-match procedure.
Complex WebQuestions 1.1 (Complex WebQ)
Complex WebQuestions extends WebQuestionsSP with more complex multi-hop questions and evaluates reasoning over knowledge-base and corpus information. Its questions span four stated types and require up to four KB hops and two corpus hops.
- Dataset construction: Complex WebQuestions is generated from WebQuestionsSP by extending question entities or adding answer constraints.
- Question types: The dataset contains composition and conjunction questions at 45% each, plus comparative and superlative questions at 5% each.
- Reasoning complexity: Questions require up to 4-hops of reasoning on the knowledge base and 2-hops on the corpus.
- Experimental setup: The experiments use the same KB and corpus as WebQuestionsSP and the same train, development, and test splits as GRAFT-Net.
- Dataset statistics: Table 1 reports statistics for all datasets used in the experiments.
4.2 Tasks
The experiments evaluate PullNet across complete-KB, corpus-only, incomplete-KB, and incomplete-KB-plus-text settings. The hybrid setting tests whether models can combine KB and corpus evidence when KB facts are missing.
- Tasks: The evaluation covers four settings: complete KB only, corpus only, incomplete KB only, and incomplete KB paired with the corpus.
- Complete KB only: In the complete-KB setting, every answer exists in the KB, making it easier but arguably less realistic than incomplete-KB QA.PullNet supports this setting by removing the document-pulling operation.
- Corpus only: The corpus-only setting removes KB fact pulling, leaving the corpus as the sole information source.
- Incomplete KB only: The incomplete-KB setting randomly drops each KB fact with probability p = 50%.
- Incomplete KB plus text: The incomplete-KB-plus-text setting pairs the damaged KB with the corpus, allowing strategies that back off to text or combine text and KB inferences.These hybrid strategies can apply to both simple 1-hop and multi-hop or conjunctive queries.
- Training caveat: Training labels in incomplete-KB settings are derived from shortest paths in a complete KB, making the supervision intermediate between distant supervision and gold inference paths.
4.3 Baselines
The evaluation compares PullNet with KVMem and GRAFT-Net, the only identified baselines supporting both text and knowledge bases. Because these models have limited memory, retrieval is performed separately as preprocessing.
- KVMem and GRAFT-Net are selected because they support question answering over both text and knowledge bases.These are described as the only models known to the authors with both information sources.
- Both baselines are limited in how many facts and text passages can fit into memory.
- The experiments therefore add a separate retrieval process before applying the baseline models.The retrieval step is introduced as preprocessing and discussed separately.
- KVMem stores KB facts and text as key-value pairs, encoding text with a bidirectional LSTM and using linked entities as values.Its implementation achieves comparable performance to previously reported results on WikiMovies.
- GRAFT-Net is evaluated using the authors’ published implementation on data differing somewhat from the paper’s described setting.
4.4 Subgraph Retrieval for Baseline Models
The baseline retrieval procedure combines IDF-based text retrieval with PageRank-Nibble-based KB retrieval, then collects facts connecting retrieved entities. It provides high coverage on MetaQA but reaches only 64% recall on ComplexWebQuestions despite a graph of nearly 2000 nodes.
- KB retrieval cannot include every fact within k hops because the number of facts grows exponentially, and no standard subset-selection heuristic exists.This contrasts with the available IDF-based heuristic for text retrieval.
- PageRank-Nibble selects the top m entities, after which entities within k hops of question entities and connecting KB facts are collected.The method uses a personalized PageRank seeded from the question rather than the unavailable answer.
- 64% recall is obtained for ComplexWebQuestions even with nearly 2000 graph nodes, reflecting the difficulty of multi-hop retrieval in a multi-million-entity KB.
- The MetaQA retrieval table reports recall together with the number of entities in the graph, using 500 PageRank-Nibble entities.
- The WebQuestionsSP and Complex WebQuestions retrieval table reports recall together with graph size, using 2000 PageRank-Nibble entities.
4.5 Main Results
PullNet performs strongly across KB-only, text-only, and incomplete-KB-plus-text settings, with especially large gains on multi-hop questions and consistent advantages on incomplete-KB tasks.
- MetaQA: PullNet shows large improvements over baselines on 2-hop and 3-hop MetaQA questions in the KB-only setting.
- MetaQA: PullNet improves substantially over baselines in text-only and incomplete-KB-plus-text settings, with the hybrid setting outperforming either source alone.
- WebQuestionsSP: On WebQuestionsSP, PullNet is comparable to GRAFT-Net with a complete KB, slightly worse on text-only questions, and consistently better in incomplete-KB settings.
- Complex WebQuestions: PullNet significantly improves over GRAFT-Net and KVMem across all four Complex WebQuestions development settings, with additional gains from pairing incomplete KBs with text.
- Complex WebQuestions: On Complex WebQuestions test data, text-only and KB-only results are comparable to development results, at 13.8% versus 13.1% and 45.9% versus 47.2%, respectively.The test set permits only limited submissions.
4.6 Further Results
Further analyses show that PullNet retrieves smaller, higher-recall subgraphs than competing retrieval methods and benefits from iterative retrieval, while training is slower initially but eventually surpasses GRAFT-Net.
- Retrieval Performance of PullNet: PullNet retrieves far fewer entities than PageRank-Nibble while obtaining higher recall on multi-hop questions with a complete KB.
- Retrieval Performance of PullNet: PullNet with multiple retrieval iterations obtains higher recall than single-iteration IDF-based retrieval on MetaQA 3-hop and Complex WebQuestions.
- Retrieval Performance of PullNet: PullNet’s question-subgraph recall saturates after 10–20,000 examples, approximately 10–20% of one training epoch.
- Training Efficiency: Interleaving learning and retrieval may slow training, but PullNet’s smaller final subgraphs may make subsequent learning faster.
- Training Efficiency: GRAFT-Net averages 31.9 minutes per epoch, whereas PullNet takes about 114 minutes per epoch in the Complex WebQuestions KB-only experiment.
- Training Efficiency: PullNet initially performs better, GRAFT-Net dominates temporarily, and PullNet surpasses GRAFT-Net in hits-at-one after about 6 hours, or 3 epochs.
5 Conclusions
PullNet learns to retrieve and reason over a small, question-specific graph from a KB and/or corpus, targeting difficult multi-hop questions. It improves over prior state-of-the-art systems, with especially large gains on several multi-hop benchmarks.
- PullNet learns which nodes to expand through iterative graph-CNN-guided retrieval from the KB and/or corpus, then reasons over the resulting subgraph.The framework integrates retrieval learning with heterogeneous-information reasoning.
- The iterative process retrieves a small graph containing information relevant to a multi-hop question.
- 62.5% to 91.4% hits-at-one on 3-hop MetaQA with a KB, and 32.8% to 47.2% on Complex WebQuestions with a KB.These are reported improvements over prior state-of-the-art results.