Source-linked AI summary
Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning
Rajarshi Das, Shehzaad Dhuliawala, Manzil Zaheer, Luke Vilnis, Ishan Durugkar, Akshay Krishnamurthy, Alex Smola, Andrew McCallum
TL;DR
Incomplete knowledge bases require answering queries when the relation and one entity are known but the destination is missing, a setting not directly handled by many path-based methods. MINERVA uses query-conditioned reinforcement learning to navigate from the source to an answer, achieving state-of-the-art results across multiple benchmark tasks without pretraining or initial supervision.
Problem
Many prior path-based methods assume both entities are known or evaluate all candidate destinations, whereas practical query answering must infer the missing entity efficiently.
Method
MINERVA trains a reinforcement-learning agent to walk a knowledge graph from the known entity, conditioning each decision on the query and path history.
Results
MINERVA achieves state-of-the-art results on multiple benchmark knowledge-base completion tasks and is reported to be robust while learning long reasoning chains.
Takeaways & Limitations
The approach provides query-specific graph search with no pretraining or initial supervision, while its reasoning paths provide interpretable provenance for predictions.
Takeaways & Limitations
Earlier path-based models use initially collected paths independent of the query relation, limiting their suitability for diverse query types.
Abstract
from arXiv · showhide
Knowledge bases (KB), both automatically and manually constructed, are often incomplete --- many valid facts can be inferred from the KB by synthesizing existing information. A popular approach to KB completion is to infer new relations by combinatory reasoning over the information found along other paths connecting a pair of entities. Given the enormous size of KBs and the exponential number of paths, previous path-based models have considered only the problem of predicting a missing relation given two entities or evaluating the truth of a proposed triple. Additionally, these methods have traditionally used random paths between fixed entity pairs or more recently learned to pick paths between them. We propose a new algorithm MINERVA, which addresses the much more difficult and practical task of answering questions where the relation is known, but only one entity. Since random walks are impractical in a setting with combinatorially many destinations from a start node, we present a neural reinforcement learning approach which learns how to navigate the graph conditioned on the input query to find predictive paths. Empirically, this approach obtains state-of-the-art results on several datasets, significantly outperforming prior methods.
1 INTRODUCTION
The paper targets query answering in incomplete knowledge bases, where the relation and source entity are known but the answer entity must be inferred. MINERVA uses query-conditioned reinforcement learning to navigate predictive paths, offering flexible, efficient, and interpretable reasoning.
- Motivation: Knowledge bases are incomplete, so systems must infer unstored facts by combining information along paths between entities.The motivating example answers Malala Yousafzai’s Nobel-related question by traversing a logical path through the knowledge graph.
- Motivation: Earlier path-based methods commonly assume both entities are known, making them unsuitable when query answering must infer the destination entity.The paper contrasts this task with fact prediction and methods that select paths between fixed entity pairs.
- MINERVA: MINERVA learns with reinforcement learning to traverse a knowledge graph from a source entity toward an answer, conditioning decisions on the query and path history.The agent chooses labeled relation edges sequentially and receives reward for reaching the correct answer node.
- MINERVA: MINERVA supports variable-length reasoning, trains from scratch without pretraining or extra supervision, searches locally, and yields interpretable reasoning paths.These properties address complex chains, reduce computation relative to ranking all entities, and provide provenance for predictions.
- Evaluation: The paper evaluates MINERVA against logical, embedding-based, and reinforcement-learning baselines and extends it to partially structured natural-language queries.The comparisons include Neural Theorem Provers, Neural LP, DistMult, ComplEx, ConvE, and DeepPath.
2 TASK AND MODEL
The task is to answer a missing-object query by navigating a knowledge graph. MINERVA formulates this as finite-horizon reinforcement learning with a history-dependent LSTM policy trained by REINFORCE.
- Task: The knowledge base becomes a directed labeled multigraph whose nodes are entities and whose edges represent binary relations, including inverse edges.Inverse relations are added so the agent can traverse backward along observed facts.
- Task: Query answering predicts the missing entity in a triple such as (e1,r,?), avoiding the cost of evaluating every candidate entity.This distinguishes query answering from fact prediction, which evaluates whether a proposed complete triple is true.
- Environment: MINERVA starts at the source entity and follows graph edges for a fixed horizon, selecting outgoing relations and destinations while the answer remains hidden.The environment is deterministic and partially observed; a NO OP action lets the agent remain at a node for easier queries.
- Training: Training maximizes expected terminal reward with REINFORCE, rewarding only trajectories that end at the correct answer node.The implementation uses empirical training averages, 20 rollouts per example, a moving-average baseline, and entropy regularization.
- Policy network: The policy uses an LSTM to encode action-observation history and a feedforward network to produce a query-conditioned distribution over available edges.Each action combines the outgoing edge’s relation and destination embeddings, while the policy is invariant to edge ordering.
3 EXPERIMENTS
The experiments assess MINERVA across benchmark knowledge-base query-answering settings, including small and large graphs, path-based comparisons, natural-language queries, and reasoning robustness.
- Evaluation goals: The experiments test whether MINERVA performs competitively on query answering over both small and large knowledge bases.The evaluation plan explicitly includes separate studies for small and large KBs.
- Evaluation goals: The evaluation compares MINERVA with path-based models that search inefficiently or do not train query-specific models.This tests the claimed value of query-conditioned graph navigation.
- Evaluation goals: Additional experiments examine partially structured natural-language queries and MINERVA’s ability to reason over long chains.The stated evaluation plan also includes robustness analysis.
3.1 KNOWLEDGE BASE QUERY ANSWERING
MINERVA is evaluated for knowledge-base query answering across small and large datasets, where the task is to rank possible answers for a known entity-relation pair. Its performance is competitive across several benchmarks, but varies with dataset structure, evaluation suitability, and the availability of recurring predictive paths.
- Task and evaluation: The query-answering task ranks candidate entities for queries of the form (e1,r,?), unlike fact checking, where both entity directions may be ranked.This evaluation difference reflects that the second entity is unknown in query answering.
- Experimental setup: MINERVA is compared with embedding-based models, logical-rule models, and other query-answering approaches using HITS@1, HITS@3, HITS@10, and MRR.The larger-dataset table includes WN18RR, FB15K-237, and NELL-995; NeuralLP does not scale to NELL-995.
- Smaller datasets: On COUNTRIES, MINERVA compares favorably with or outperforms most baselines, with especially prominent gains on S3, the hardest task.NTP-λ and ConvE outperform MINERVA on S2, with higher variance across runs.
- Smaller datasets: On KINSHIP and UMLS, embedding methods perform much better overall, while MINERVA outperforms NeuralLP and NTP on KINSHIP and matches NTP’s UMLS HITS@10.These datasets were not designed specifically to test logical-rule learning, and their small size favors embedding methods.
- Larger datasets: On WN18RR, MINERVA achieves the highest HITS@1, whereas embedding methods dominate on FB15K-237 and MINERVA is competitive with embedding models on NELL-995.NeuralLP significantly outperforms MINERVA on WN18RR HITS@10 and ConvE outperforms MINERVA on NELL-995 HITS@10.
- Larger datasets: FB15K-237 contains many 1-to-M relations and few frequently recurring path types, limiting MINERVA because the evaluation targets one entity and predictive paths are harder to learn.The average tail-to-head ratio for 1-to-M relations is 13.39, while the evaluation scheme is not suited to such relations.
3.2 COMPARISON WITH PATH BASED MODELS
MINERVA is compared with random-walk path models and DeepPath, which address related path-based reasoning settings. It significantly outperforms the random-path baseline and matches or exceeds DeepPath while using one model across query relations.
- With Random Walk Models: The random-path baseline samples 100 paths of maximum length 3, encodes them with LSTMs and max pooling, then predicts the answer entity.The resulting features are combined with the source entity and query-relation vectors.
- With Random Walk Models: MINERVA significantly outperforms the random-path baseline on all three evaluated datasets.The baseline can lose important paths or aggregate many paths irrelevant to the query.
- With Random Walk Models: MINERVA conditions each navigation step on the query relation, reducing the search space and focusing on paths relevant to the answer.This contrasts with randomly sampled paths that may omit useful evidence or include irrelevant information.
- With DeepPath: A single MINERVA model for all query relations is competitive with separately trained DeepPath models, while per-relation MINERVA also outperforms DeepPath.The single-model setup is desirable because per-relation training is cumbersome and does not scale to thousands of relation types.
- With DeepPath: MINERVA outperforms or achieves comparable MAP performance to DeepPath for all query relations on NELL-995.The comparison uses maximum path length T = 3 and ranks answer entities against DeepPath’s negative examples.
3.3 PARTIALLY STRUCTURED QUERIES
The paper extends MINERVA from structured triples to partially structured natural-language questions using WikiMovies. It links entities by string matching and represents question relations by averaging word embeddings learned from scratch.
- Partially Structured Queries: WikiMovies supplies template-generated natural-language questions together with a knowledge base that can answer them.This provides a first test of MINERVA beyond queries represented directly as triples.
- Partially Structured Queries: The question encoder represents the query relation by averaging its word embeddings, which are learned from scratch without pretrained embeddings.The entity mentioned in the question is linked to the knowledge base through simple string matching.
- Partially Structured Queries: On WikiMovies, a maximum path length of T = 1 sufficed, suggesting that the dataset is not a strong testbed for multihop reasoning.The authors describe the experiment as a promising first step toward answering natural-language questions with KBs.
3.4 GRID WORLD PATH FINDING
The grid-world experiment tests whether MINERVA can navigate to an answer cell by following query-specified directions. The agent assigns action probabilities conditioned on the query relation and outperforms NeuralLP for longer paths.
- Grid World Path Finding: The synthetic 16-by-16 grid-world task requires navigating from a random start cell to an answer cell using directions specified by the query relation.The task evaluates reasoning over paths of varying length in a controlled setting.
- Grid World Path Finding: MINERVA significantly outperforms NeuralLP for longer path lengths in the grid-world experiment.This comparison directly tests performance as the required reasoning chain becomes longer.
- Grid World Path Finding: The agent assigns different action probabilities according to the query relation, including in partially structured WikiMovies questions.The figure illustrates that query-conditioned decisions alter which outgoing edges receive higher probability.
3.5 FURTHER ANALYSIS
Further analyses examine MINERVA’s efficiency, query-conditioned decisions, robustness, path-history memory, and variable-length navigation. The results show faster convergence and inference than DistMult, stable runs, and substantial dependence on remembering path history.
- Training Time: MINERVA converges to a higher HITS@10 score much faster than DistMult during training.It also performs better during early training, when it is effectively taking random walks near the source entity.
- Inference Time: MINERVA searches local neighborhoods at inference time, whereas embedding methods rank all entities in the graph with running time O(|E|).Its inference cost is primarily computing probabilities for outgoing edges along the selected path.
- Inference Time: MINERVA’s median inference time is O(1) across power-law degree distributions and is independent of the number of entities.On WN18RR, DistMult takes 211s versus 63s for MINERVA; on NELL-995, the times are 115s and 35s, respectively.
- Query based Decision Making: Query-conditioned action probabilities differ across relations, such as assigning higher probability to CoachesTeam than AthletePlaysInLeague for WorksFor.Similar query-dependent behavior appears for WikiMovies questions represented by words rather than fixed schema relations.
- Model Robustness: Low deviations across three independent runs indicate that MINERVA’s highest scores were easy to reproduce.The robustness analysis reports means and standard deviations across runs.
- Effectiveness of Remembering Path History: Removing path-history information decreases KINSHIP HITS@1 by 27 percentage points and HITS@10 by 13 percentage points.Grid-world accuracy falls to 0.23 for path lengths 2-4 and 0.04 for lengths 8-10, while FB15K-237 HITS@10 falls from 0.456 to 0.408.
- NO-OP and Inverse Relations: NO-OP edges let MINERVA remain at a node, supporting variable-length paths when an answer is reached before the maximum length.Inverse relations additionally allow the agent to undo a potentially wrong decision.
4 RELATED WORK
Prior KB reasoning methods learn rules, embeddings, or paths, but face limitations in complex inference, path precomputation, or unknown-answer settings. MINERVA instead learns to search query-conditioned paths without precomputing them, while related work also explores natural-language navigation and neural theorem proving.
- Embedding-based methods are popular for KB reasoning but cannot capture complex inference patterns found by following multi-hop paths.
- Path-based approaches can rely on heuristic or precomputed paths, whereas MINERVA learns to search efficiently conditioned on the input query relation.
- ILP and statistical relational learning learn logical rules from examples or background knowledge, but negative examples are often difficult to obtain in knowledge bases.
- WikiNav and Wikispeedia study reinforcement-learning navigation through graphs whose nodes and edges are represented using natural-language content.
- Neural Theorem Provers use soft matching for proof paths, which can create large computation graphs because scores can be computed between any two vectors.
- DeepPath requires the target entity during path finding, while MINERVA searches for the answer entity and functions as a complete query-answering system.
5 CONCLUSION
The paper presents MINERVA as a query-conditioned agent that walks through knowledge graphs to answer queries. It reports state-of-the-art benchmark results, long-chain reasoning, robustness, and no need for pretraining or initial supervision.
- MINERVA trains an agent to walk through a knowledge graph to an answer node conditioned on the input query.
- MINERVA achieves state-of-the-art results on multiple benchmark knowledge-base completion tasks.
- MINERVA is reported to learn long chains of reasoning and remain robust during training.
- MINERVA requires no pretraining or initial supervision, while future work includes more sophisticated reinforcement learning and direct work on textual queries and documents.
6 APPENDIX
The appendix records implementation settings, tuned reinforcement-learning hyperparameters, and additional NELL results. It also includes tables documenting hyperparameters and experiments on tasks not previously reported for comparison.
- The experiments use 200-dimensional relation and entity embeddings, a three-layer LSTM with hidden size 400, and an MLP hidden size of 400.
- The model uses Adam with default REINFORCE parameters, while β and λ are tuned as entropy-regularization and moving-average constants.
- Table 11 lists the best hyperparameters for all datasets.
- MINERVA is evaluated on two additional NELL tasks whose scores were not reported previously and therefore lacked DeepPath comparisons.