mlsanityData to 14 Oct 2026

Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations

arXiv 2401.12470 ↗First posted 23 Jan 2024cs.LG cs.AIcited by 1

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

Abstract (arXiv)

Register allocation is one of the most important problems for modern compilers. With a practically unlimited number of user variables and a small number of CPU registers, assigning variables to registers without conflicts is a complex task. This work demonstrates the use of casting the register allocation problem as a graph coloring problem. Using technologies such as PyTorch and OpenAI Gymnasium Environments we will show that a Proximal Policy Optimization model can learn to solve the graph coloring problem. We will also show that the labeling of a graph is critical to the performance of the model by taking the matrix representation of a graph and permuting it. We then test the model's effectiveness on each of these permutations and show that it is not effective when given a relabeling of the same graph. Our main contribution lies in showing the need for label reordering invariant representations of graphs for machine learning models to achieve consistent performance.

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 5 of its 12 references that are in the map. First posted on arXiv 23 Jan 2024.

Builds on

5 of 12 references.

References · 5

  1. 2017Proximal Policy Optimization Algorithmscited by 15,215
  2. 2013Playing Atari with Deep Reinforcement Learningcited by 3,274
  3. 2020Reinforcement Learning for Combinatorial Optimization: A Surveycited by 236
  4. 2019Coloring Big Graphs with AlphaGoZerocited by 13
  5. 2019Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocationcited by 2

Built on by

Cited by year

Citing papers per year: 2025: 1.

1 paper.

  1. 2025Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layoutscited by 0

Similar, not cited

Close in wording, no citation either way

  1. 2024Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective
  2. 2026RLGT: A reinforcement learning framework for extremal graph theory
  3. 2025Reinforcement learning for graph theory, Parallelizing Wagner's approach
  4. 2026Reinforcement Learning for Graph Generation under a Hard Assortativity Constraint
  5. 2024Refutation of Spectral Graph Theory Conjectures with Search Algorithms)
  6. 2026Deep Reinforcement Learning for Minimum Zero-Forcing Sets
  7. 2024A Structure-Aware Framework for Learning Device Placements on Computation Graphs
  8. 2025G1: Teaching LLMs to Reason on Graphs with Reinforcement Learning