# Learning to Walk with Dual Agents for Knowledge Graph Reasoning

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

## Key facts

- Cited by 16 papers in the map (data through 14 Oct 2026).
- Builds on 18 of its 51 references that are in the map.
- First posted on arXiv 23 Dec 2021.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [PyTorch: An Imperative Style, High-Performance Deep Learning Library](https://mlsanity.com/paper/1912.01703/) (2019)
- [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)
- [Convolutional 2D Knowledge Graph Embeddings](https://mlsanity.com/paper/1707.01476/) (2017)
- [A Survey on Knowledge Graphs: Representation, Acquisition and Applications](https://mlsanity.com/paper/2002.00388/) (2020)
- [DeepPath: A Reinforcement Learning Method for Knowledge Graph Reasoning](https://mlsanity.com/paper/1707.06690/) (2017)
- [Go for a Walk and Arrive at the Answer: Reasoning Over Paths in Knowledge Bases using Reinforcement Learning](https://mlsanity.com/paper/1711.05851/) (2017)
- [Embedding Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/1806.01445/) (2018)
- [Multi-Hop Knowledge Graph Reasoning with Reward Shaping](https://mlsanity.com/paper/1808.10568/) (2018)
- [Modeling Relation Paths for Representation Learning of Knowledge Bases](https://mlsanity.com/paper/1506.00379/) (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)
- [SSP: Semantic Space Projection for Knowledge Graph Embedding with Text Descriptions](https://mlsanity.com/paper/1604.04835/) (2016)
- [Job2Vec: Job Title Benchmarking with Collective Multi-View Representation Learning](https://mlsanity.com/paper/2009.07429/) (2020)
- [Reasoning on Knowledge Graphs with Debate Dynamics](https://mlsanity.com/paper/2001.00461/) (2020)
- [Learning Disentangled Representations for Time Series](https://mlsanity.com/paper/2105.08179/) (2021)
- [Efficient Parallel Translating Embedding For Knowledge Graphs](https://mlsanity.com/paper/1703.10316/) (2017)

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

- [A Survey of Knowledge Graph Reasoning on Graph Types: Static, Dynamic, and Multimodal](https://mlsanity.com/paper/2212.05767/) (2022)
- [Neural-Symbolic Models for Logical Queries on Knowledge Graphs](https://mlsanity.com/paper/2205.10128/) (2022)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [SARF: Aliasing Relation Assisted Self-Supervised Learning for Few-shot Relation Reasoning](https://mlsanity.com/paper/2304.10297/) (2023)
- [Message Intercommunication for Inductive Relation Reasoning](https://mlsanity.com/paper/2305.14074/) (2023)
- [Structure Guided Multi-modal Pre-trained Transformer for Knowledge Graph Reasoning](https://mlsanity.com/paper/2307.03591/) (2023)
- [Exploring & Exploiting High-Order Graph Structure for Sparse Knowledge Graph Completion](https://mlsanity.com/paper/2306.17034/) (2023)
- [Towards Enhancing Relational Rules for Knowledge Graph Link Prediction](https://mlsanity.com/paper/2310.13411/) (2023)
- [Retrieval-Augmented Feature Generation for Domain-Specific Classification](https://mlsanity.com/paper/2406.11177/) (2024)
- [Multi-hop Reasoning and Retrieval in Embedding Space: Leveraging Large Language Models with Knowledge](https://mlsanity.com/paper/2603.13266/) (2026)
- [VEM2L: A Plug-and-play Framework for Fusing Text and Structure Knowledge on Sparse Knowledge Graph Completion](https://mlsanity.com/paper/2207.01528/) (2022)
- [Emulating the Human Mind: A Neural-symbolic Link Prediction Model with Fast and Slow Reasoning and Filtered Rules](https://mlsanity.com/paper/2310.13996/) (2023)
- [Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies](https://mlsanity.com/paper/2409.07932/) (2024)
- [MPRM: A Markov Path-based Rule Miner for Efficient and Interpretable Knowledge Graph Reasoning](https://mlsanity.com/paper/2505.12329/) (2025)
- [Q-GNN: Query-Conditioned Graph Neural Networks with Type Awareness for Knowledge Graph Completion](https://mlsanity.com/paper/2606.05639/) (2026)

## Abstract (arXiv)

Graph walking based on reinforcement learning (RL) has shown great success in navigating an agent to automatically complete various reasoning tasks over an incomplete knowledge graph (KG) by exploring multi-hop relational paths. However, existing multi-hop reasoning approaches only work well on short reasoning paths and tend to miss the target entity with the increasing path length. This is undesirable for many reason-ing tasks in real-world scenarios, where short paths connecting the source and target entities are not available in incomplete KGs, and thus the reasoning performances drop drastically unless the agent is able to seek out more clues from longer paths. To address the above challenge, in this paper, we propose a dual-agent reinforcement learning framework, which trains two agents (GIANT and DWARF) to walk over a KG jointly and search for the answer collaboratively. Our approach tackles the reasoning challenge in long paths by assigning one of the agents (GIANT) searching on cluster-level paths quickly and providing stage-wise hints for another agent (DWARF). Finally, experimental results on several KG reasoning benchmarks show that our approach can search answers more accurately and efficiently, and outperforms existing RL-based methods for long path queries by a large margin.