# M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search

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

## Key facts

- Cited by 34 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2018.

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

- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [Knowledge Graph Reasoning with Relational Digraph](https://mlsanity.com/paper/2108.06040/) (2021)
- [TASKOGRAPHY: Evaluating robot task planning over large 3D scene graphs](https://mlsanity.com/paper/2207.05006/) (2022)
- [A*Net: A Scalable Path-based Reasoning Approach for Knowledge Graphs](https://mlsanity.com/paper/2206.04798/) (2022)
- [HAIChart: Human and AI Paired Visualization System](https://mlsanity.com/paper/2406.11033/) (2024)
- [A Survey of Trustworthy Graph Learning: Reliability, Explainability, and Privacy Protection](https://mlsanity.com/paper/2205.10014/) (2022)
- [Reinforcement Learning from Reformulations in Conversational Question Answering over Knowledge Graphs](https://mlsanity.com/paper/2105.04850/) (2021)
- [Learning to Walk with Dual Agents for Knowledge Graph Reasoning](https://mlsanity.com/paper/2112.12876/) (2021)
- [Beyond Games: A Systematic Review of Neural Monte Carlo Tree Search Applications](https://mlsanity.com/paper/2303.08060/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [MMKGR: Multi-hop Multi-modal Knowledge Graph Reasoning](https://mlsanity.com/paper/2209.01416/) (2022)
- [Is Multi-Hop Reasoning Really Explainable? Towards Benchmarking Reasoning Interpretability](https://mlsanity.com/paper/2104.06751/) (2021)
- [Logical Entity Representation in Knowledge-Graphs for Differentiable Rule Learning](https://mlsanity.com/paper/2305.12738/) (2023)
- [Explainable Biomedical Recommendations via Reinforcement Learning Reasoning on Knowledge Graphs](https://mlsanity.com/paper/2111.10625/) (2021)
- [R5: Rule Discovery with Reinforced and Recurrent Relational Reasoning](https://mlsanity.com/paper/2205.06454/) (2022)
- [Causal Question Answering with Reinforcement Learning](https://mlsanity.com/paper/2311.02760/) (2023)
- [Rule Induction in Knowledge Graphs Using Linear Programming](https://mlsanity.com/paper/2110.08245/) (2021)
- [Instance-based Learning for Knowledge Base Completion](https://mlsanity.com/paper/2211.06807/) (2022)
- [Inductive Meta-path Learning for Schema-complex Heterogeneous Information Networks](https://mlsanity.com/paper/2307.03937/) (2023)
- [Towards Enhancing Relational Rules for Knowledge Graph Link Prediction](https://mlsanity.com/paper/2310.13411/) (2023)
- [FLEX: Feature-Logic Embedding Framework for CompleX Knowledge Graph Reasoning](https://mlsanity.com/paper/2205.11039/) (2022)
- [Learning to Navigate Wikipedia by Taking Random Walks](https://mlsanity.com/paper/2211.00177/) (2022)
- [Knowledge Graph Reasoning with Self-supervised Reinforcement Learning](https://mlsanity.com/paper/2405.13640/) (2024)
- [Walk Wisely on Graph: Knowledge Graph Reasoning with Dual Agents via Efficient Guidance-Exploration](https://mlsanity.com/paper/2408.01880/) (2024)
- [Beyond Training: Optimizing Reinforcement Learning Based Job Shop Scheduling Through Adaptive Action Sampling](https://mlsanity.com/paper/2406.07325/) (2024)
- [Solving Graph-based Public Good Games with Tree Search and Imitation Learning](https://mlsanity.com/paper/2106.06762/) (2021)
- [APPTeK: Agent-Based Predicate Prediction in Temporal Knowledge Graphs](https://mlsanity.com/paper/2110.14284/) (2021)
- [Adaptive Pseudo-Siamese Policy Network for Temporal Knowledge Prediction](https://mlsanity.com/paper/2204.12036/) (2022)
- [Discover Important Paths in the Knowledge Graph Based on Dynamic Relation Confidence](https://mlsanity.com/paper/2211.00914/) (2022)
- [A Pre-training Framework for Knowledge Graph Completion](https://mlsanity.com/paper/2302.02614/) (2023)

## Abstract (arXiv)

Learning to walk over a graph towards a target node for a given query and a source node is an important problem in applications such as knowledge base completion (KBC). It can be formulated as a reinforcement learning (RL) problem with a known state transition model. To overcome the challenge of sparse rewards, we develop a graph-walking agent called M-Walk, which consists of a deep recurrent neural network (RNN) and Monte Carlo Tree Search (MCTS). The RNN encodes the state (i.e., history of the walked path) and maps it separately to a policy and Q-values. In order to effectively train the agent from sparse rewards, we combine MCTS with the neural policy to generate trajectories yielding more positive rewards. From these trajectories, the network is improved in an off-policy manner using Q-learning, which modifies the RNN policy via parameter sharing. Our proposed RL algorithm repeatedly applies this policy-improvement step to learn the model. At test time, MCTS is combined with the neural policy to predict the target node. Experimental results on several graph-walking benchmarks show that M-Walk is able to learn better policies than other RL-based methods, which are mainly based on policy gradients. M-Walk also outperforms traditional KBC baselines.