Back to Search
Start Over
Graph Coloring with Physics-Inspired Graph Neural Networks
- Source :
- Phys. Rev. Research 4, 043131 (2022)
- Publication Year :
- 2022
-
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.<br />Comment: Manuscript: 8 pages, 5 figures, 2 tables. Supplemental Material: 1 page, 2 tables
Details
- Database :
- arXiv
- Journal :
- Phys. Rev. Research 4, 043131 (2022)
- Publication Type :
- Report
- Accession number :
- edsarx.2202.01606
- Document Type :
- Working Paper
- Full Text :
- https://doi.org/10.1103/PhysRevResearch.4.043131