mlsanityData to 14 Oct 2026

Graph Q-Learning for Combinatorial Optimization

arXiv 2401.05610 ↗First posted 11 Jan 2024cs.LG cs.AIcited by 1

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

Abstract (arXiv)

Graph-structured data is ubiquitous throughout natural and social sciences, and Graph Neural Networks (GNNs) have recently been shown to be effective at solving prediction and inference problems on graph data. In this paper, we propose and demonstrate that GNNs can be applied to solve Combinatorial Optimization (CO) problems. CO concerns optimizing a function over a discrete solution space that is often intractably large. To learn to solve CO problems, we formulate the optimization process as a sequential decision making problem, where the return is related to how close the candidate solution is to optimality. We use a GNN to learn a policy to iteratively build increasingly promising candidate solutions. We present preliminary evidence that GNNs trained through Q-Learning can solve CO problems with performance approaching state-of-the-art heuristic-based solvers, using only a fraction of the parameters and training time.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Placed in RL for games and combinatorial optimization, one of 15 directions in Deep reinforcement learning methods. Builds on 15 of its 26 references that are in the map. First posted on arXiv 11 Jan 2024.

Builds on

15 of 26 references.

References · 15

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2017Graph Attention Networkscited by 8,923
  3. 2017Inductive Representation Learning on Large Graphscited by 6,320
  4. 2017Neural Message Passing for Quantum Chemistrycited by 3,487
  5. 2018Graph Convolutional Neural Networks for Web-Scale Recommender Systemscited by 1,138
  6. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  7. 2018Representation Learning on Graphs with Jumping Knowledge Networkscited by 877
  8. 2021How Attentive are Graph Attention Networks?cited by 835
  9. 2020On the Bottleneck of Graph Neural Networks and its Practical Implicationscited by 631
  10. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  11. 2019Multi-Agent Game Abstraction via Graph Attention Neural Networkcited by 82
  12. 2020Deep Implicit Coordination Graphs for Multi-agent Reinforcement Learningcited by 60
3 more
  1. 2021ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learningcited by 31
  2. 2022Agent-Temporal Attention for Reward Redistribution in Episodic Multi-Agent Reinforcement Learningcited by 9
  3. 2022Recursive Reasoning Graph for Multi-Agent Reinforcement Learningcited by 2

Built on by

Cited by year

Citing papers per year: 2024: 1.

1 paper.

  1. 2024Graph Neural Networks for Job Shop Scheduling Problems: A Surveycited by 15

Similar, not cited

Close in wording, no citation either way

  1. 2025A Distributed Training Architecture For Combinatorial Optimization
  2. 2023COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems
  3. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  4. 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networks
  5. 2025Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization
  6. 2025Binarizing Physics-Inspired GNNs for Combinatorial Optimization
  7. 2024Solving the QAP by Two-Stage Graph Pointer Networks and Reinforcement Learning
  8. 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization