Graph Coloring with Physics-Inspired Graph Neural Networks

Author name not available (Why is that?)

Publication date: 3 February 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.

Has companion code repository: https://github.com/amazon-research/gcp-with-gnns-example

This page was built for publication: Graph Coloring with Physics-Inspired Graph Neural Networks

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6390038)