mlsanityData to 13 Oct 2026

Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective

arXiv 2404.06492 ↗First posted 9 Apr 2024cs.LG cs.AIcited by 16

On the map: Deep reinforcement learning methods → RL for games and combinatorial optimization

Abstract (arXiv)

Graphs are a natural representation for systems based on relations between connected entities. Combinatorial optimization problems, which arise when considering an objective function related to a process of interest on discrete structures, are often challenging due to the rapid growth of the solution space. The trial-and-error paradigm of Reinforcement Learning has recently emerged as a promising alternative to traditional methods, such as exact algorithms and (meta)heuristics, for discovering better decision-making strategies in a variety of disciplines including chemistry, computer science, and statistics. Despite the fact that they arose in markedly different fields, these techniques share significant commonalities. Therefore, we set out to synthesize this work in a unifying perspective that we term Graph Reinforcement Learning, interpreting it as a constructive decision-making method for graph problems. After covering the relevant technical background, we review works along the dividing line of whether the goal is to optimize graph structure given a process of interest, or to optimize the outcome of the process itself under fixed graph structure. Finally, we discuss the common challenges facing the field and open research questions. In contrast with other surveys, the present work focuses on non-canonical graph problems for which performant algorithms are typically not known and Reinforcement Learning is able to provide efficient and effective solutions.

Key facts. Cited by 16 papers in the map (data through 13 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 107 of its 238 references that are in the map. First posted on arXiv 9 Apr 2024.

Builds on

107 of 238 references.

References · 107

  1. 2017Proximal Policy Optimization Algorithmscited by 14,592
  2. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,318
  3. 2017Graph Attention Networkscited by 8,888
  4. 2017Inductive Representation Learning on Large Graphscited by 6,303
  5. 2013Intriguing properties of neural networkscited by 5,137
  6. 2018Soft Actor-Critic: Off-Policy Maximum Entropy Deep Reinforcement Learning with a Stochastic Actorcited by 4,656
  7. 2014Neural Machine Translation by Jointly Learning to Align and Translatecited by 4,539
  8. 2018How Powerful are Graph Neural Networks?cited by 4,373
  9. 2017Neural Message Passing for Quantum Chemistrycited by 3,471
  10. 2015Continuous control with deep reinforcement learningcited by 3,290
  11. 2015Trust Region Policy Optimizationcited by 2,513
  12. 2018Addressing Function Approximation Error in Actor-Critic Methodscited by 2,310
38 more
  1. 2016Asynchronous Methods for Deep Reinforcement Learningcited by 2,223
  2. 2016Convolutional Neural Networks on Graphs with Fast Localized Spectral Filteringcited by 2,086
  3. 2016node2vec: Scalable Feature Learning for Networkscited by 1,915
  4. 2015Deep Reinforcement Learning with Double Q-learningcited by 1,710
  5. 2016Generative Adversarial Imitation Learningcited by 1,577
  6. 2014DeepWalk: Online Learning of Social Representationscited by 1,544
  7. 2018Relational inductive biases, deep learning, and graph networkscited by 1,353
  8. 2019Mastering Atari, Go, Chess and Shogi by Planning with a Learned Modelcited by 1,334
  9. 2013Spectral Networks and Locally Connected Networks on Graphscited by 1,101
  10. 2015Prioritized Experience Replaycited by 1,078
  11. 2016Geometric deep learning: going beyond Euclidean datacited by 1,045
  12. 2015Gated Graph Sequence Neural Networkscited by 794
  13. 2018Hierarchical Graph Representation Learning with Differentiable Poolingcited by 787
  14. 2017Rainbow: Combining Improvements in Deep Reinforcement Learningcited by 777
  15. 2015Convolutional Networks on Graphs for Learning Molecular Fingerprintscited by 753
  16. 2018DAGs with NO TEARS: Continuous Optimization for Structure Learningcited by 748
  17. 2017A Distributional Perspective on Reinforcement Learningcited by 745
  18. 2019GNNExplainer: Generating Explanations for Graph Neural Networkscited by 736
  19. 2017Evasion Attacks against Machine Learning at Test Timecited by 689
  20. 2018Junction Tree Variational Autoencoder for Molecular Graph Generationcited by 648
  21. 2018Attention, Learn to Solve Routing Problems!cited by 648
  22. 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 613
  23. 2017One pixel attack for fooling deep neural networkscited by 581
  24. 2017Evolution Strategies as a Scalable Alternative to Reinforcement Learningcited by 562
  25. 2017Learning Combinatorial Optimization Algorithms over Graphscited by 557
  26. 2017End-to-end Driving via Conditional Imitation Learningcited by 480
  27. 2017Representation Learning on Graphs: Methods and Applicationscited by 456
  28. 2018GraphRNN: Generating Realistic Graphs with Deep Auto-regressive Modelscited by 410
  29. 2018MolGAN: An implicit generative model for small molecular graphscited by 392
  30. 2018Graph Convolutional Policy Network for Goal-Directed Molecular Graph Generationcited by 363
  31. 2020POMO: Policy Optimization with Multiple Optima for Reinforcement Learningcited by 344
  32. 2018Adversarial Attack on Graph Structured Datacited by 301
  33. 2017Grammar Variational Autoencodercited by 284
  34. 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
  35. 2015Deep Convolutional Networks on Graph-Structured Datacited by 246
  36. 2017Thinking Fast and Slow with Deep Learning and Tree Searchcited by 246
  37. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 235
  38. 2019Efficient Graph Generation with Graph Recurrent Attention Networkscited by 233

50 most cited of 107 All 107 (JSON)

Built on by

Cited by year (2026 to 13 Oct)

Citing papers per year: 2024: 3; 2025: 7; 2026: 6.

16 papers.

Sort:

By area:

  1. 2025ALE-Bench: A Benchmark for Long-Horizon Objective-Driven Algorithm Engineeringcited by 34
  2. 2024Neural Combinatorial Optimization Algorithms for Solving Vehicle Routing Problems: A Comprehensive Survey with Perspectivescited by 23
  3. 2025Graph-Enhanced Policy Optimization in LLM Agent Trainingcited by 4
  4. 2024NetDiff: Graph Diffusion with Improved Global Capabilities to Generate and Update Mobile Network Topologiescited by 2
  5. 2025ReFill: Reinforcement Learning for Fill-In Minimizationcited by 1
  6. 2025INSPIRE-GNN: Intelligent Sensor Placement to Improve Sparse Bicycling Network Prediction via Reinforcement Learning Boosted Graph Neural Networkscited by 1
  7. 2024Reinforcement Learning Discovers Efficient Decentralized Graph Path Search Strategiescited by 0
  8. 2025Hybridising Reinforcement Learning and Heuristics for Hierarchical Directed Arc Routing Problemscited by 0
  9. 2025Accelerating Atomic Fine Structure Determination with Graph Reinforcement Learningcited by 0
  10. 2025Tackling GNARLy Problems: Graph Neural Algorithmic Reasoning Reimagined through Reinforcement Learningcited by 0
  11. 2026Critic-Free Deep Reinforcement Learning for Maritime Coverage Path Planning on Irregular Hexagonal Gridscited by 0
  12. 2026Teacher-Aware Evolution of Heuristic Programs from Learned Optimization Policiescited by 0
4 more
  1. 2026Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimizationcited by 0
  2. 2026Smart Transportation Without Neurons -- Fair Metro Network Expansion with Tabular Reinforcement Learningcited by 0
  3. 2026Maximising the Set-Piece Return: Optimising Football Corner Tactics with Graph Reinforcement Learningcited by 0
  4. 2026Baseline-Free Policy Optimization for Neural Combinatorial Optimizationcited by 0