mlsanityData to 7 Oct 2026

Planning Spatial Networks with Monte Carlo Tree Search

arXiv 2106.06768 ↗First posted 12 Jun 2021cs.AIcited by 5

Not on the map. Why?

Abstract (arXiv)

We tackle the problem of goal-directed graph construction: given a starting graph, a budget of modifications, and a global objective function, the aim is to find a set of edges whose addition to the graph achieves the maximum improvement in the objective (e.g., communication efficiency). This problem emerges in many networks of great importance for society such as transportation and critical infrastructure networks. We identify two significant shortcomings with present methods. Firstly, they focus exclusively on network topology while ignoring spatial information; however, in many real-world networks, nodes are embedded in space, which yields different global objectives and governs the range and density of realizable connections. Secondly, existing RL methods scale poorly to large networks due to the high cost of training a model and the scaling factors of the action space and global objectives. In this work, we formulate this problem as a deterministic MDP. We adopt the Monte Carlo Tree Search framework for planning in this domain, prioritizing the optimality of final solutions over the speed of policy evaluation. We propose several improvements over the standard UCT algorithm for this family of problems, addressing their single-agent nature, the trade-off between the costs of edges and their contribution to the objective, and an action space linear in the number of nodes. We demonstrate the suitability of this approach for improving the global efficiency and attack resilience of a variety of synthetic and real-world networks, including Internet backbone networks and metro systems. Our approach obtains a 24% improvement in these metrics compared to UCT on the largest networks tested and scalability superior to previous methods.

Key facts. Cited by 5 papers in the map (data through 7 Oct 2026). Builds on 18 of its 71 references that are in the map. First posted on arXiv 12 Jun 2021.

Builds on

18 of 71 references.

References · 18

  1. 2019PyTorch: An Imperative Style, High-Performance Deep Learning Librarycited by 20,160
  2. 2017Neural Message Passing for Quantum Chemistrycited by 3,460
  3. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,133
  4. 2016Geometric deep learning: going beyond Euclidean datacited by 1,042
  5. 2015Pointer Networkscited by 882
  6. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 647
  7. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
  8. 2016Neural Combinatorial Optimization with Reinforcement Learningcited by 600
  9. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  10. 2018Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generationcited by 363
  11. 2018Adversarial Attack on Graph Structured Datacited by 300
  12. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 245
6 more
  1. 2015Deep Reinforcement Learning in Large Discrete Action Spacescited by 158
  2. 2017Geometric Matrix Completion with Recurrent Multi-Graph Neural Networkscited by 88
  3. 2018Learn What Not to Learn: Action Elimination with Deep Reinforcement Learningcited by 77
  4. 2019A Model to Search for Synthesizable Moleculescited by 37
  5. 2018Ranked Reward: Enabling Self-Play Reinforcement Learning for Combinatorial Optimizationcited by 25
  6. 2020Goal-directed graph construction using reinforcement learningcited by 13

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 1; 2024: 2; 2025: 0; 2026: 2.

5 papers.

  1. 2024Large Language Models are Effective Priors for Causal Graph Discoverycited by 23
  2. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspectivecited by 16
  3. 2023Tree Search in DAG Space with Model-based Reinforcement Learning for Causal Discoverycited by 3
  4. 2026AlphaTransit: Learning to Design City-scale Transit Routescited by 0
  5. 2026Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learningcited by 0