# Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning

arXiv: https://arxiv.org/abs/1711.05851 · HTML: https://mlsanity.com/paper/1711.05851/

## Key facts

- Cited by 161 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Nov 2017.

## Built on by (most cited first, 30 of 161)

- [Graph Retrieval-Augmented Generation: A Survey](https://mlsanity.com/paper/2408.08921/) (2024)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [Improving Multi-hop Knowledge Base Question Answering by Learning Intermediate Supervision Signals](https://mlsanity.com/paper/2101.03737/) (2021)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [TimeTraveler: Reinforcement Learning for Temporal Knowledge Graph Forecasting](https://mlsanity.com/paper/2109.04101/) (2021)
- [Temporal Knowledge Graph Forecasting with Neural ODE](https://mlsanity.com/paper/2101.05151/) (2021)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [Knowledge Graphs Meet Multi-Modal Learning: A Comprehensive Survey](https://mlsanity.com/paper/2402.05391/) (2024)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Search from History and Reason for Future: Two-stage Reasoning on Temporal Knowledge Graphs](https://mlsanity.com/paper/2106.00327/) (2021)
- [On the Explainability of Natural Language Processing Deep Models](https://mlsanity.com/paper/2210.06929/) (2022)
- [Neuro-Symbolic Inductive Logic Programming with Logical Neural Networks](https://mlsanity.com/paper/2112.03324/) (2021)
- [Continual Learning of Knowledge Graph Embeddings](https://mlsanity.com/paper/2101.05850/) (2021)
- [Survey on reinforcement learning for language processing](https://mlsanity.com/paper/2104.05565/) (2021)
- [Knowledge Base Question Answering by Case-based Reasoning over Subgraphs](https://mlsanity.com/paper/2202.10610/) (2022)
- [Answering Complex Logical Queries on Knowledge Graphs via Query Computation Tree Optimization](https://mlsanity.com/paper/2212.09567/) (2022)
- [AdaProp: Learning Adaptive Propagation for Graph Neural Network based Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.15319/) (2022)
- [Inductive Relation Prediction by BERT](https://mlsanity.com/paper/2103.07102/) (2021)
- [Neural Multi-Hop Reasoning With Logical Rules on Biomedical Knowledge Graphs](https://mlsanity.com/paper/2103.10367/) (2021)
- [Neurosymbolic Reinforcement Learning and Planning: A Survey](https://mlsanity.com/paper/2309.01038/) (2023)
- [KnowledgeNavigator: Leveraging Large Language Models for Enhanced Reasoning over Knowledge Graph](https://mlsanity.com/paper/2312.15880/) (2023)
- [Understanding Reasoning Ability of Language Models From the Perspective of Reasoning Paths Aggregation](https://mlsanity.com/paper/2402.03268/) (2024)
- [Benchmarking the Combinatorial Generalizability of Complex Query Answering on Knowledge Graphs](https://mlsanity.com/paper/2109.08925/) (2021)
- [Reinforcement learning on graphs: A survey](https://mlsanity.com/paper/2204.06127/) (2022)
- [Reinforcement Learning from Reformulations in Conversational Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2105.04850/) (2021)
- [Graph-based Approaches and Functionalities in Retrieval-Augmented Generation: A Comprehensive Survey](https://mlsanity.com/paper/2504.10499/) (2025)
- [Logic Embeddings for Complex Query Answering](https://mlsanity.com/paper/2103.00418/) (2021)
- [UNIQORN: Unified Question Answering over RDF Knowledge Graphs and Natural Language Text](https://mlsanity.com/paper/2108.08614/) (2021)
- [Learning to Walk with Dual Agents for Knowledge Graph Reasoning](https://mlsanity.com/paper/2112.12876/) (2021)

## Abstract (arXiv)

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.