Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts

• URL: http://arxiv.org/abs/2601.05137v1
• Date: Thu, 08 Jan 2026 17:28:09 GMT
• Title: Neural Algorithmic Reasoning for Approximate $k$-Coloring with Recursive Warm Starts
• Authors: Knut Vanderbush, Melanie Weber,
• Abstract summary: We explore the use of graph neural networks (GNNs) for node coloring.<n>We introduce a lightweight greedy local search algorithm and show that it may be improved by using a $(k-1)-coloring to use as a warm start.<n> Numerical experiments show that while the local search algorithms perform best on small inputs, the GNN$ exhibits superior performance at scale.
• Score: 5.645823801022895
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: 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 and of central importance in 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, 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 vertices 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 graph neural networks (GNNs) for node coloring. We first present an optimized differentiable algorithm that improves a prior approach by Schuetz et al. 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 local search algorithms perform best on small inputs, the GNN exhibits superior performance at scale. The recursive warm start may be of independent interest beyond graph coloring for local search methods for combinatorial optimization.

Related papers

• Efficient hybrid variational quantum algorithm for solving graph coloring problem [4.4739537033766705]
  This paper proposes a hybrid variational quantum algorithm to solve the $k$-coloring problem of graph vertices.<n>We employ a hierarchical framework that integrates feedback correction and conflict resolution to achieve $k$-coloring.<n>We apply the proposed algorithm to optimize the scheduling of a subway transportation network, demonstrating a high degree of fairness.
  arXiv  Detail & Related papers  (2025-04-30T05:45:15Z)
• Node Classification and Search on the Rubik's Cube Graph with GNNs [55.2480439325792]
  This study focuses on the application of deep geometric models to solve the 3x3x3 Rubik's Rubik.<n>We begin by discussing the cube's graph representation and defining distance as the model's optimization objective.<n>The distance approximation task is reformulated as a node classification problem, effectively addressed using Graph Neural Networks (GNNs)
  arXiv  Detail & Related papers  (2025-01-30T18:52:43Z)
• Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs [0.0]
  We present a novel algorithm that leverages graph neural networks to tackle the problem efficiently, particularly for large graphs. We demonstrate the effectiveness of our method on a dataset of Erdos-Renyi graphs, showing its applicability also in hard-to-solve connectivity regions.
  arXiv  Detail & Related papers  (2024-08-02T18:02:51Z)
• Ensemble Quadratic Assignment Network for Graph Matching [52.20001802006391]
  Graph matching is a commonly used technique in computer vision and pattern recognition. Recent data-driven approaches have improved the graph matching accuracy remarkably. We propose a graph neural network (GNN) based approach to combine the advantages of data-driven and traditional methods.
  arXiv  Detail & Related papers  (2024-03-11T06:34:05Z)
• Gradual Weisfeiler-Leman: Slow and Steady Wins the Race [4.416484585765029]
  Weisfeiler-Leman algorithm aka color refinement is fundamental for graph learning and central for successful graph kernels and graph neural networks. We propose a framework for gradual neighborhood refinement, which allows a slower convergence to the stable coloring. Our approach is used to derive new variants of existing graph kernels and to approximate the graph edit distance via optimal assignments.
  arXiv  Detail & Related papers  (2022-09-19T14:37:35Z)
• Graph Neural Network Bandits [89.31889875864599]
  We consider the bandit optimization problem with the reward function defined over graph-structured data. Key challenges in this setting are scaling to large domains, and to graphs with many nodes. We show that graph neural networks (GNNs) can be used to estimate the reward function.
  arXiv  Detail & Related papers  (2022-07-13T18:12:36Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  We propose the Neighbor2Seq to transform the hierarchical neighborhood of each node into a sequence. We evaluate our method on a massive graph with more than 111 million nodes and 1.6 billion edges. Results show that our proposed method is scalable to massive graphs and achieves superior performance across massive and medium-scale graphs.
  arXiv  Detail & Related papers  (2022-02-07T16:38:36Z)
• A deep learning guided memetic framework for graph coloring problems [15.426481600285724]
  We present a new framework which combines a deep neural network with the best tools of "classical" metaheuristics for graph coloring. A study of the contribution of deep learning in the algorithm highlights that it is possible to learn relevant patterns useful to obtain better solutions to this problem.
  arXiv  Detail & Related papers  (2021-09-13T13:17:41Z)
• Time Complexity Analysis of Randomized Search Heuristics for the Dynamic Graph Coloring Problem [15.45783225341009]
  We study the dynamic setting where edges are added to the current graph. We then analyze the expected time for randomized searchs to recompute high quality solutions.
  arXiv  Detail & Related papers  (2021-05-26T13:00:31Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  Data association across frames is at the core of Multiple Object Tracking (MOT) task. Existing methods mostly ignore the context information among tracklets and intra-frame detections. We propose a novel learnable graph matching method to address these issues.
  arXiv  Detail & Related papers  (2021-03-30T08:58:45Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  We propose a novel pool-based Active Learning framework constructed on a sequential Graph Convolution Network (GCN) With a small number of randomly sampled images as seed labelled examples, we learn the parameters of the graph to distinguish labelled vs unlabelled nodes. We exploit these characteristics of GCN to select the unlabelled examples which are sufficiently different from labelled ones.
  arXiv  Detail & Related papers  (2020-06-18T00:55:10Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.