Combinatorial optimization problems near algorithmic phase transitions represent a fundamental challenge for both classical algorithms and machine learning approaches. Among them, graph coloring is a prototypical constraint satisfaction problem characterized by phase transitions that fragment the solution space into distinct clusters, making the search for valid solutions challenging. Here we introduce a physics-inspired neural framework that learns to solve large-scale graph coloring instances by combining graph neural networks with statistical-mechanics principles. Our approach integrates a planting-based supervised signal, symmetry-breaking regularization, and iterative noise-annealed neural dynamics to navigate complex solution landscapes. When the number of iterations scales quadratically with graph size, the learned solver successfully tackles increasingly challenging instances, even in regimes where finding valid solutions becomes particularly difficult, demonstrating its ability to extract meaningful information from the graph structure. The model generalizes from small training graphs to instances up to 20 times larger, demonstrating that neural architectures can learn scalable algorithmic strategies that remain effective in hard connectivity regions. These results establish a general framework for learning neural solvers that operate near fundamental phase boundaries in combinatorial optimization and inference.
Figures & tables
Figure 1: Schematic illustration of the evolution of the solution-space landscape with increasing average connectivity c . The red cross represent the planted solution. At low connectivity, the planted solution belongs to a large connected region of solutions. Above the dynamical transition cd , the solution space fragments into an exponential number of clusters. At the condensation transition cc , the solution measure concentrates onto a subexponential number of dominant clusters, one of which contains the planted solution. The satisfiability threshold cs marks the transition beyond which typical random instances become unsatisfiable. The Kesten–Stigum threshold cKS marks the detectability of the planted structure. Blue regions denote solutions, whereas orange regions represent local minima.
Figure 2: (DTR Model) Extensive energy as a function of the number of iterations for four representative connectivity values, c=12.0,13.0,13.5,14.0 . Each data point is obtained by averaging results over 50 graphs with N= 10k nodes. Error bars indicate one standard deviation across graph instances. Circles indicate values for planted graphs, while crosses indicate values for random graphs. Error bars indicate standard error of the mean across graph instances.
Figure 3: (DTR Model) Main panel Mean intensive energy as a function of connectivity, for both random and planted graphs, and a number of nodes varying from N=2500 to N=50 k. Each data point is obtained by running the algorithm for Niter=200 k iterations and averaging the energy over 50 graphs. Inset The mean extensive energy grows with the size at each value of c and does not allow to determine the algorithmic threshold in the large N limit. Error bars indicate the standard error of the mean.
Figure 4: (DTR Model) Probability of finding a solution as a function of the graph connectivity c , for sizes N∈[1024,2048,4096,8192] and a number of iterations scaling as Niter=0.04N2 . Each point is the average over 400 graphs. Error bars indicate 95% Wilson binomial confidence intervals.
Figure 5: (DTR Model) Comparison of the probability of finding a solution as a function of the graph connectivity c for different solving algorithms. Values are obtained by averaging over 400 graphs of N=1024 nodes. The number of iterations Niter is chosen to ensure the same wall-clock execution time across all algorithms. The tested algorithms are a recurrent Physics-Inspired GNN (rPI) [ 35 ] , Belief Propagation (BP) [ 37 ] , Simulated Annealing (SA) [ 2 ] , our graph neural network (GNN), and Focused Metropolis Search (FMS) [ 36 ] . Error bars indicate 95% Wilson binomial confidence intervals.
Figure 6: (KSR Model) Main panel Probability of finding a solution as a function of the graph connectivity c , for sizes 1000≤N≤20000 and a number of iterations scaling as Niter=10−4N2 . Each point is the average over 2106/N graphs. Inset The mean overlap with the planted coloring of the configuration output by the algorithm. Error bars indicate 95% Wilson binomial confidence intervals.
Combinatorial optimization finds the best feasible choices among discrete alternatives in routing, scheduling, graph problems, and resource allocation.
Graph coloring seeks to assigns colors to a graph's nodes so that adjacent nodes receive different colors, using as few colors as possible. Here, we study approximate k-coloring, where the goal is to use at most k colors while minimizing the number of monochromatic edges. This problem is central to graph theory and has applications in areas such as scheduling and resource allocation. Recent unsupervised GNN approaches optimize each instance directly, precluding generalization across graph sizes and distributions. We instead propose a contrastive learning framework that learns transferable coloring geometry where the embeddings of same-color nodes align, while adjacent nodes' representations are pushed toward distinct directions. We analyze the resulting population objective over bounded-size graphs. For unit-norm embeddings, we show that its optima have a line-prototype structure: Representations of nodes of the same color collapse to a shared one-dimensional subspace, and edges connect orthogonal subspaces. This geometry yields stationarity conditions in the supervised setting and is preserved by projected subgradient dynamics under a balanced-coloring assumption. In an unnormalized variant, gradient descent has a max-margin bias governed by a quotient-graph hard-margin problem. Experiments on synthetic and real-world graphs show that contrastive GNN encoders generalize effectively and produce low-conflict colorings, matching and sometimes improving on greedy approaches.
Thien Le, Tianyu Zhao, Melanie Weber
Harvard University SEAS · Harvard University T.H. Chan School of Public Health
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 this paper, we propose an ONN-based solver for one well-known constrained combinatorial optimization problem, namely a Sudoku, by formulating the problem as a Graph Coloring problem. By modifying the already existing Graph Coloring solver to a computationally cheaper version and introducing an additional term ensuring the fulfillment of the Sudoku constraints, our solver is shown to significantly outperform the existing HNN- and ONN solvers in terms of accuracy. In particular, we are able to achieve nearly flawless accuracies on 4×4 as well as rather high accuracies on 9×9 Sudoku puzzles for different numbers of unknown digits.
Filip Sabo, Aida Todri-Sanial
NanoComputing Research Lab, Electrical Engineering Department Eindhoven University of Technology Eindhoven, the Netherlands
A key challenge in developing unified neural solvers for combinatorial optimization (CO) is the efficient generalization of models from a given set of tasks to new tasks unseen during initial training. To address this, we first establish a new GNN encoder, which uses a GCON module as a form of expressive message passing together with energy-based unsupervised loss functions. This model achieves highly competitive performance across multiple CO tasks when trained individually on each task. We then leverage knowledge from the computational reducibility literature to propose pretraining and fine-tuning strategies that transfer effectively (a) between MVC, MIS and MaxClique, and (b) in a multi-task learning setting that additionally incorporates MaxCut, MDS and graph coloring. Additionally, in a leave-one-out, multi-task learning setting, we observe that pretraining on all but one task almost always leads to faster convergence on the remaining task when fine-tuning, while avoiding negative transfer. Our findings indicate that learning common representations across multiple graph CO problems is viable through the use of expressive message passing coupled with pretraining strategies that are informed by the polynomial reducibility literature, thereby taking an important step towards enabling the development of foundational models for neural CO. We provide an open source implementation of our work at https://github.com/semihcanturk/COPT-MT.
Semih Cantürk, Thomas Sabourin, Frederik Wenkel +2
Dept. of Computer Science and Operations Research, Université de Montréal · Mila – Quebec AI Institute · Dept. of Mathematics & Statistics, Université de Montréal +2