# Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems

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

## Key facts

- Cited by 40 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 11 Mar 2019.

## Built on by (most cited first, 30 of 40)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Generative Recursive Reasoning](https://mlsanity.com/paper/2605.19376/) (2026)
- [Annealed Training for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2207.11542/) (2022)
- [A Survey on Influence Maximization: From an ML-Based Combinatorial Optimization](https://mlsanity.com/paper/2211.03074/) (2022)
- [Rethinking Graph Neural Networks for the Graph Coloring Problem](https://mlsanity.com/paper/2208.06975/) (2022)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Can Graph Neural Networks Learn to Solve MaxSAT Problem?](https://mlsanity.com/paper/2111.07568/) (2021)
- [A Graph Neural Network with Negative Message Passing for Graph Coloring](https://mlsanity.com/paper/2301.11164/) (2023)
- [Monte Carlo Policy Gradient Method for Binary Optimization](https://mlsanity.com/paper/2307.00783/) (2023)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [Towards a Generic Representation of Combinatorial Problems for Learning-Based Approaches](https://mlsanity.com/paper/2403.06026/) (2024)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Computing Steiner Trees using Graph Neural Networks](https://mlsanity.com/paper/2108.08368/) (2021)
- [RL4ReAl: Reinforcement Learning for Register Allocation](https://mlsanity.com/paper/2204.02013/) (2022)
- [Towards graph neural networks for provably solving convex optimization problems](https://mlsanity.com/paper/2502.02446/) (2025)
- [Optimal Solving of Constrained Path-Planning Problems with Graph Convolutional Networks and Optimized Tree Search](https://mlsanity.com/paper/2108.01036/) (2021)
- [A deep learning guided memetic framework for graph coloring problems](https://mlsanity.com/paper/2109.05948/) (2021)
- [Neural Lattice Reduction: A Self-Supervised Geometric Deep Learning Approach](https://mlsanity.com/paper/2311.08170/) (2023)
- [Graph Coloring via Neural Networks for Haplotype Assembly and Viral Quasispecies Reconstruction](https://mlsanity.com/paper/2210.12158/) (2022)
- [Generalizable Reasoning through Compositional Energy Minimization](https://mlsanity.com/paper/2510.20607/) (2025)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Solving Disjunctive Temporal Networks with Uncertainty under Restricted Time-Based Controllability using Tree Search and Graph Neural Networks](https://mlsanity.com/paper/2203.15030/) (2022)
- [Lightsolver challenges a leading deep learning solver for Max-2-SAT problems](https://mlsanity.com/paper/2302.06926/) (2023)
- [Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks](https://mlsanity.com/paper/2304.04051/) (2023)
- [A Unified Pre-training and Adaptation Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2312.11547/) (2023)
- [Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs](https://mlsanity.com/paper/2408.01503/) (2024)
- [Scalable Parameter Design for Superconducting Quantum Circuits with Graph Neural Networks](https://mlsanity.com/paper/2411.16354/) (2024)
- [Deep Learning Chromatic and Clique Numbers of Graphs](https://mlsanity.com/paper/2108.01810/) (2021)

## Abstract (arXiv)

Deep learning has consistently defied state-of-the-art techniques in many fields over the last decade. However, we are just beginning to understand the capabilities of neural learning in symbolic domains. Deep learning architectures that employ parameter sharing over graphs can produce models which can be trained on complex properties of relational data. These include highly relevant NP-Complete problems, such as SAT and TSP. In this work, we showcase how Graph Neural Networks (GNN) can be engineered -- with a very simple architecture -- to solve the fundamental combinatorial problem of graph colouring. Our results show that the model, which achieves high accuracy upon training on random instances, is able to generalise to graph distributions different from those seen at training time. Further, it performs better than the Neurosat, Tabucol and greedy baselines for some distributions. In addition, we show how vertex embeddings can be clustered in multidimensional spaces to yield constructive solutions even though our model is only trained as a binary classifier. In summary, our results contribute to shorten the gap in our understanding of the algorithms learned by GNNs, as well as hoarding empirical evidence for their capability on hard combinatorial problems. Our results thus contribute to the standing challenge of integrating robust learning and symbolic reasoning in Deep Learning systems.