Graph Coloring with Physics-Inspired Graph Neural Networks
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.
Code (1)
Tasks
ClusteringCommunity DetectionNode ClassificationSchedulingSimilar Papers 제목 키워드 기반
Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
The graph coloring problem is an optimization problem involving the assignment of one of q colors to each vertex of a graph such that no two adjacent vertices share the same color. This problem is NP-hard and arises in v…
Structure Learning of $H$-colorings
We study the structure learning problem for $H$-colorings, an important class of Markov random fields that capture key combinatorial structures on graphs, including proper colorings and independent sets, as well as spin …
Graph Coloring Approach to Solving Sudoku with Oscillatory Neural Networks
Oscillatory Neural Networks (ONNs) present an attractive physics-based computing paradigm rooted in the dynamics of a network of typically fully coupled oscillators aiming to minimize an underlying energy function. In th…
Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts
Node coloring is the task of assigning colors to the nodes of a graph such that no two adjacent nodes have the same color, while using as few colors as possible. It is the most widely studied instance of graph coloring a…
A deep learning guided memetic framework for graph coloring problems
Given an undirected graph $G=(V,E)$ with a set of vertices $V$ and a set of edges $E$, a graph coloring problem involves finding a partition of the vertices into different independent sets. In this paper we present a new…
Deep Learning