# Graph Coloring with Physics-Inspired Graph Neural Networks

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

## Key facts

- Cited by 29 papers in the map (data through 14 Oct 2026).
- Builds on 13 of its 51 references that are in the map.
- First posted on arXiv 3 Feb 2022.

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

- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Graph Convolutional Neural Networks for Web-Scale Recommender Systems](https://mlsanity.com/paper/1806.01973/) (2018)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Ising formulations of many NP problems](https://mlsanity.com/paper/1302.5843/) (2013)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Community detection in networks: A user guide](https://mlsanity.com/paper/1608.00163/) (2016)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Utilising Graph Machine Learning within Drug Discovery and Development](https://mlsanity.com/paper/2012.05716/) (2020)
- [Solving Multi-Coloring Combinatorial Optimization Problems Using Hybrid Quantum Algorithms](https://mlsanity.com/paper/1911.00595/) (2019)

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

- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2302.03602/) (2023)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)
- [A Graph Neural Network with Negative Message Passing for Graph Coloring](https://mlsanity.com/paper/2301.11164/) (2023)
- [Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems](https://mlsanity.com/paper/2303.12096/) (2023)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Geometric Algorithms for Neural Combinatorial Optimization with Constraints](https://mlsanity.com/paper/2510.24039/) (2025)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply](https://mlsanity.com/paper/2306.02555/) (2023)
- [Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs](https://mlsanity.com/paper/2408.01503/) (2024)
- [Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems](https://mlsanity.com/paper/2411.05834/) (2024)
- [Scalable Parameter Design for Superconducting Quantum Circuits with Graph Neural Networks](https://mlsanity.com/paper/2411.16354/) (2024)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Unsupervised Graph-based Learning Method for Sub-band Allocation in 6G Subnetworks](https://mlsanity.com/paper/2401.00950/) (2023)
- [Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloring](https://mlsanity.com/paper/2408.05054/) (2024)
- [Efficient Optimization Accelerator Framework for Multistate Ising Problems](https://mlsanity.com/paper/2505.20250/) (2025)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [Unsupervised Graph Neural Network Framework for Balanced Multipatterning in Advanced Electronic Design Automation Layouts](https://mlsanity.com/paper/2511.16374/) (2025)
- [Neural Algorithmic Reasoning for Approximate k-Coloring with Recursive Warm Starts](https://mlsanity.com/paper/2601.05137/) (2026)
- [Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks](https://mlsanity.com/paper/2602.02689/) (2026)
- [Can Computational Reducibility Lead to Transferable Models for Graph Combinatorial Optimization?](https://mlsanity.com/paper/2603.02462/) (2026)
- [Crystal structure prediction using graph neural combinatorial optimization](https://mlsanity.com/paper/2604.23921/) (2026)
- [Distribution-Aware Algorithm Design with LLM Agents](https://mlsanity.com/paper/2605.14141/) (2026)

## Abstract (arXiv)

We show how graph neural networks can be used to solve the canonical graph coloring problem. We frame graph coloring as a multi-class node classification problem and utilize an unsupervised training strategy based on the statistical physics Potts model. Generalizations to other multi-class problems such as community detection, data clustering, and the minimum clique cover problem are straightforward. We provide numerical benchmark results and illustrate our approach with an end-to-end application for a real-world scheduling use case within a comprehensive encode-process-decode framework. Our optimization approach performs on par or outperforms existing solvers, with the ability to scale to problems with millions of variables.