Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
This addresses a fundamental problem in combinatorial optimization for researchers and practitioners, offering a scalable neural solver that operates near phase boundaries, though it builds on existing methods with incremental innovations.
The paper tackles the challenge of solving large-scale graph coloring problems near algorithmic phase transitions by introducing a physics-inspired neural framework, achieving near-optimal detection performance and reaching thresholds close to theoretical dynamical transitions in random graphs.
Combinatorial optimization problems near algorithmic phase transitions represent a fundamental challenge for both classical algorithms and machine learning approaches. Among them, graph coloring stands as a prototypical constraint satisfaction problem exhibiting sharp dynamical and satisfiability thresholds. 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 clustered solution landscapes. When the number of iterations scales quadratically with graph size, the learned solver reaches algorithmic thresholds close to the theoretical dynamical transition in random graphs and achieves near-optimal detection performance in the planted inference regime. The model generalizes from small training graphs to instances orders of magnitude larger, demonstrating that neural architectures can learn scalable algorithmic strategies that remain effective in hard connectivity regions. These results establish a general paradigm for learning neural solvers that operate near fundamental phase boundaries in combinatorial optimization and inference.