Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2024
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866917848463441920 |
|---|---|
| author | Pisacane, Alexei Darvariu, Victor-Alexandru Musolesi, Mirco |
| author_facet | Pisacane, Alexei Darvariu, Victor-Alexandru Musolesi, Mirco |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2409_07932 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies Pisacane, Alexei Darvariu, Victor-Alexandru Musolesi, Mirco Machine Learning Artificial Intelligence Multiagent Systems Social and Information Networks 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. |
| title | Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategies |
| topic | Machine Learning Artificial Intelligence Multiagent Systems Social and Information Networks |
| url | https://arxiv.org/abs/2409.07932 |