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

arXiv: https://arxiv.org/abs/2401.12470 · HTML: https://mlsanity.com/paper/2401.12470/

## Key facts

- Cited by 1 papers 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.

## Placed in

- Deep reinforcement learning methods / [RL for games and combinatorial optimization](https://mlsanity.com/deeprl/rl-for-games-and-combinatorial-optimization/)

## Builds on (most cited first, 5 of 5)

- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)
- [Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation](https://mlsanity.com/paper/1912.03700/) (2019)

## Built on by (most cited first, 1 of 1)

- [Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layouts](https://mlsanity.com/paper/2511.16374/) (2025)

## 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.