# Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 10 of its 43 references that are in the map.
- First posted on arXiv 2 Aug 2024.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Neural Networks: A Review of Methods and Applications](https://mlsanity.com/paper/1812.08434/) (2018)
- [Relational inductive biases, deep learning, and graph networks](https://mlsanity.com/paper/1806.01261/) (2018)
- [Spectral redemption: clustering sparse networks](https://mlsanity.com/paper/1306.5550/) (2013)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)
- [Rethinking Graph Neural Networks for the Graph Coloring Problem](https://mlsanity.com/paper/2208.06975/) (2022)
- [Graph Nets for Partial Charge Prediction](https://mlsanity.com/paper/1909.07903/) (2019)
- [A Graph Neural Network with Negative Message Passing for Graph Coloring](https://mlsanity.com/paper/2301.11164/) (2023)

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

- [Concept Learning in the Wild: Towards Algorithmic Understanding of Neural Networks](https://mlsanity.com/paper/2412.11205/) (2024)

## Abstract (arXiv)

Combinatorial optimization problems near algorithmic phase transitions represent a fundamental challenge for both classical algorithms and machine learning approaches. Among them, graph coloring stands as a prototypical constraint satisfaction problem exhibiting sharp dynamical and satisfiability thresholds. Here we introduce a physics-inspired neural framework that learns to solve large-scale graph coloring instances by combining graph neural networks with statistical-mechanics principles. Our approach integrates a planting-based supervised signal, symmetry-breaking regularization, and iterative noise-annealed neural dynamics to navigate clustered solution landscapes. When the number of iterations scales quadratically with graph size, the learned solver reaches algorithmic thresholds close to the theoretical dynamical transition in random graphs and achieves near-optimal detection performance in the planted inference regime. The model generalizes from small training graphs to instances orders of magnitude larger, demonstrating that neural architectures can learn scalable algorithmic strategies that remain effective in hard connectivity regions. These results establish a general paradigm for learning neural solvers that operate near fundamental phase boundaries in combinatorial optimization and inference.