# Coloring Big Graphs with AlphaGoZero

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

## Key facts

- Cited by 13 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 26 Feb 2019.

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

- [Beyond Games: A Systematic Review of Neural Monte Carlo Tree Search Applications](https://mlsanity.com/paper/2303.08060/) (2023)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Multi-Robot Active Mapping via Neural Bipartite Graph Matching](https://mlsanity.com/paper/2203.16319/) (2022)
- [Deep learning-driven scheduling algorithm for a single machine problem minimizing the total tardiness](https://mlsanity.com/paper/2402.14847/) (2024)
- [Costly Features Classification using Monte Carlo Tree Search](https://mlsanity.com/paper/2102.07073/) (2021)
- [RL4ReAl: Reinforcement Learning for Register Allocation](https://mlsanity.com/paper/2204.02013/) (2022)
- [A deep learning guided memetic framework for graph coloring problems](https://mlsanity.com/paper/2109.05948/) (2021)
- [Deployment Optimization for Shared e-Mobility Systems with Multi-agent Deep Neural Search](https://mlsanity.com/paper/2111.02149/) (2021)
- [Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks](https://mlsanity.com/paper/2304.04051/) (2023)
- [Reinforcement Learning for Graph Coloring: Understanding the Power and Limits of Non-Label Invariant Representations](https://mlsanity.com/paper/2401.12470/) (2024)
- [Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs](https://mlsanity.com/paper/2408.01503/) (2024)
- [Deep Learning Chromatic and Clique Numbers of Graphs](https://mlsanity.com/paper/2108.01810/) (2021)
- [Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloring](https://mlsanity.com/paper/2408.05054/) (2024)

## Abstract (arXiv)

We show that recent innovations in deep reinforcement learning can effectively color very large graphs -- a well-known NP-hard problem with clear commercial applications. Because the Monte Carlo Tree Search with Upper Confidence Bound algorithm used in AlphaGoZero can improve the performance of a given heuristic, our approach allows deep neural networks trained using high performance computing (HPC) technologies to transform computation into improved heuristics with zero prior knowledge. Key to our approach is the introduction of a novel deep neural network architecture (FastColorNet) that has access to the full graph context and requires O(V) time and space to color a graph with V vertices, which enables scaling to very large graphs that arise in real applications like parallel computing, compilers, numerical solvers, and design automation, among others. As a result, we are able to learn new state of the art heuristics for graph coloring.