# Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods.
- Builds on 16 of its 52 references that are in the map.
- First posted on arXiv 12 Sep 2024.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

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

- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Asynchronous Methods for Deep Reinforcement Learning](https://mlsanity.com/paper/1602.01783/) (2016)
- [Multi-Agent Actor-Critic for Mixed Cooperative-Competitive Environments](https://mlsanity.com/paper/1706.02275/) (2017)
- [Counterfactual Multi-Agent Policy Gradients](https://mlsanity.com/paper/1705.08926/) (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)
- [Deep Reinforcement Learning meets Graph Neural Networks: exploring a routing optimization use case](https://mlsanity.com/paper/1910.07421/) (2019)
- [Traversing Knowledge Graphs in Vector Space](https://mlsanity.com/paper/1506.01094/) (2015)
- [Experience-driven Networking: A Deep Reinforcement Learning based Approach](https://mlsanity.com/paper/1801.05757/) (2018)
- [Learning Heuristic Search via Imitation](https://mlsanity.com/paper/1707.03034/) (2017)
- [M-Walk: Learning to Walk over Graphs using Monte Carlo Tree Search](https://mlsanity.com/paper/1802.04394/) (2018)
- [Learning to Walk with Dual Agents for Knowledge Graph Reasoning](https://mlsanity.com/paper/2112.12876/) (2021)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [CFR-RL: Traffic Engineering with Reinforcement Learning in SDN](https://mlsanity.com/paper/2004.11986/) (2020)
- [GDDR: GNN-based Data-Driven Routing](https://mlsanity.com/paper/2104.09919/) (2021)
- [Learning Graph Search Heuristics](https://mlsanity.com/paper/2212.03978/) (2022)
- [Intrinsically motivated graph exploration using network theories of human curiosity](https://mlsanity.com/paper/2307.04962/) (2023)

## Abstract (arXiv)

Graph path search is a classic computer science problem that has been recently approached with Reinforcement Learning (RL) due to its potential to outperform prior methods. Existing RL techniques typically assume a global view of the network, which is not suitable for large-scale, dynamic, and privacy-sensitive settings. An area of particular interest is search in social networks due to its numerous applications. Inspired by seminal work in experimental sociology, which showed that decentralized yet efficient search is possible in social networks, we frame the problem as a collaborative task between multiple agents equipped with a limited local view of the network. We propose a multi-agent approach for graph path search that successfully leverages both homophily and structural heterogeneity. Our experiments, carried out over synthetic and real-world social networks, demonstrate that our model significantly outperforms learned and heuristic baselines. Furthermore, our results show that meaningful embeddings for graph navigation can be constructed using reward-driven learning.