# Walk Wisely on Graph: Knowledge Graph Reasoning with Dual Agents via Efficient Guidance-Exploration

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Placed in Knowledge- and tool-augmented reasoning, one of 17 directions in LLM reasoning.
- Builds on 19 of its 59 references that are in the map.
- First posted on arXiv 3 Aug 2024.

## Placed in

- LLM reasoning / [Knowledge- and tool-augmented reasoning](https://mlsanity.com/lr/knowledge-and-tool-augmented-reasoning/)

## Builds on (most cited first, 19 of 19)

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Embedding Entities and Relations for Learning and Inference in Knowledge Bases](https://mlsanity.com/paper/1412.6575/) (2014)
- [Complex Embeddings for Simple Link Prediction](https://mlsanity.com/paper/1606.06357/) (2016)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [KG-BERT: BERT for Knowledge Graph Completion](https://mlsanity.com/paper/1909.03193/) (2019)
- [TuckER: Tensor Factorization for Knowledge Graph Completion](https://mlsanity.com/paper/1901.09590/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Inductive Relation Prediction by Subgraph Reasoning](https://mlsanity.com/paper/1911.06962/) (2019)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [Learning Symmetric Collaborative Dialogue Agents with Dynamic Knowledge Graph Embeddings](https://mlsanity.com/paper/1704.07130/) (2017)
- [Traversing Knowledge Graphs in Vector Space](https://mlsanity.com/paper/1506.01094/) (2015)
- [KBQA: Learning Question Answering over QA Corpora and Knowledge Bases](https://mlsanity.com/paper/1903.02419/) (2019)
- [M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search](https://mlsanity.com/paper/1802.04394/) (2018)
- [Dynamic Anticipation and Completion for Multi-Hop Reasoning over Sparse Knowledge Graph](https://mlsanity.com/paper/2010.01899/) (2020)
- [Quality-Diversity Actor-Critic: Learning High-Performing and Diverse Behaviors via Value and Successor Features Critics](https://mlsanity.com/paper/2403.09930/) (2024)
- [Recent Advances in Hierarchical Multi-label Text Classification: A Survey](https://mlsanity.com/paper/2307.16265/) (2023)
- [Reinforcement Learning-based Knowledge Graph Reasoning for Explainable Fact-checking](https://mlsanity.com/paper/2310.07613/) (2023)

## Built on by (most cited first, 2 of 2)

- [Learn A Flexible Exploration Model for Parameterized Action Markov Decision Processes](https://mlsanity.com/paper/2501.02774/) (2025)
- [Co-Evolving Structured Knowledge and Reasoning in Language Models](https://mlsanity.com/paper/2608.26386/) (2026)

## Abstract (arXiv)

Recent years, multi-hop reasoning has been widely studied for knowledge graph (KG) reasoning due to its efficacy and interpretability. However, previous multi-hop reasoning approaches are subject to two primary shortcomings. First, agents struggle to learn effective and robust policies at the early phase due to sparse rewards. Second, these approaches often falter on specific datasets like sparse knowledge graphs, where agents are required to traverse lengthy reasoning paths. To address these problems, we propose a multi-hop reasoning model with dual agents based on hierarchical reinforcement learning (HRL), which is named FULORA. FULORA tackles the above reasoning challenges by eFficient GUidance-ExpLORAtion between dual agents. The high-level agent walks on the simplified knowledge graph to provide stage-wise hints for the low-level agent walking on the original knowledge graph. In this framework, the low-level agent optimizes a value function that balances two objectives: (1) maximizing return, and (2) integrating efficient guidance from the high-level agent. Experiments conducted on three real-word knowledge graph datasets demonstrate that FULORA outperforms RL-based baselines, especially in the case of long-distance reasoning.