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. Node coloring is the most widely studied instance of graph coloring and of central importance in structural graph theory; major results include the Four Color Theorem and work on the Hadwiger–Nelson problem. As an abstraction of classical combinatorial optimization tasks, such as scheduling and resource allocation, it is also rich in practical applications. Here, we focus on a relaxed version of node coloring, approximate k-coloring, which is the task of assigning at most k colors to the nodes of a graph such that the number of edges whose endpoints have the same color is approximately minimized. While classical approaches leverage mathematical programming or SAT solvers, recent studies have explored the use of machine learning. We follow this route and explore the use of neural algorithmic reasoning for node coloring, specifically the use of graph neural networks (GNNs). We first present an optimized differentiable algorithm that improves a prior approach by Schuetz et al (2022 Phys. Rev. Res. 4 043131) with orthogonal node feature initialization and a loss function that penalizes conflicting edges more heavily when their endpoints have higher degree; the latter inspired by the classical result that a graph is k-colorable if and only if its k-core is k-colorable. Next, we introduce a lightweight greedy local search algorithm and show that it may be improved by recursively computing a (k−1)-coloring to use as a warm start. We then show that applying such recursive warm starts to the GNN approach leads to further improvements. Numerical experiments on a range of different graph structures show that while the greedy algorithm performs best on inputs of order up to around 200, the GNN exhibits superior performance for larger orders up to around 2000. The recursive warm start may be of independent interest beyond graph coloring for local search methods for combinatorial optimization.