Graph Coloring with Physics-Inspired Graph Neural Networks
arXiv:2202.01606 · doi:10.1103/PhysRevResearch.4.043131
Abstract
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.
Manuscript: 8 pages, 5 figures, 2 tables. Supplemental Material: 1 page, 2 tables
References in corpus (2)
Cited by in corpus (11)
- Roadmap on machine learning glassy dynamics
- Machine-learning-assisted Monte Carlo fails at sampling computationally hard problems
- Qudit-inspired optimization for graph coloring
- Message Passing Variational Autoregressive Network for Solving Intractable Ising Models
- Scalable Parameter Design for Superconducting Quantum Circuits with Graph Neural Networks
- Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set
- Nearest-Neighbours Neural Network architecture for efficient sampling of statistical physics models
- Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks
- Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems
- Beyond Ground States: Physics-Inspired Optimization of Excited States of Classical Hamiltonians
- Eidolon: A Post-Quantum Signature Scheme Based on k-Colorability in the Age of Graph Neural Networks