# Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 14 of its 42 references that are in the map.
- First posted on arXiv 8 Apr 2023.

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

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Playing Atari with Deep Reinforcement Learning](https://mlsanity.com/paper/1312.5602/) (2013)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Principal Neighbourhood Aggregation for Graph Nets](https://mlsanity.com/paper/2004.05718/) (2020)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation](https://mlsanity.com/paper/2205.10106/) (2022)
- [Reinforcement learning based local search for grouping problems: A case study on graph coloring](https://mlsanity.com/paper/1604.00377/) (2016)
- [Variations on Memetic Algorithms for Graph Coloring Problems](https://mlsanity.com/paper/1401.2184/) (2014)

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

The graph colouring problem consists of assigning labels, or colours, to the vertices of a graph such that no two adjacent vertices share the same colour. In this work we investigate whether deep reinforcement learning can be used to discover a competitive construction heuristic for graph colouring. Our proposed approach, ReLCol, uses deep Q-learning together with a graph neural network for feature extraction, and employs a novel way of parameterising the graph that results in improved performance. Using standard benchmark graphs with varied topologies, we empirically evaluate the benefits and limitations of the heuristic learned by ReLCol relative to existing construction algorithms, and demonstrate that reinforcement learning is a promising direction for further research on the graph colouring problem.