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.

本研究解决了现有强化学习方法在大规模、动态和隐私敏感环境下图路径搜索的局限性。我们提出了一种多智能体方法，能够有效利用社会网络中的同质性和结构异质性，实现分散且高效的搜索。实验结果表明，该方法在合成和真实社交网络上显著优于已有的基线方法，并能够构建适用于图导航的有意义嵌入。 

强化学习发现高效的分散图路径搜索策略