![[2408.01503] Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2408.01503] Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
Summary
This article presents a novel physics-inspired neural network approach for efficiently solving large-scale graph coloring problems, a key challenge in combinatorial optimization.
Why It Matters
Graph coloring is a fundamental problem in computer science and optimization. This research demonstrates how neural networks can leverage principles from physics to improve performance in solving complex graph problems, potentially influencing future AI applications in optimization and inference.
Key Takeaways
- Introduces a physics-inspired neural framework for graph coloring.
- Achieves near-optimal performance in large-scale graph instances.
- Combines graph neural networks with statistical mechanics principles.
- Demonstrates scalability from small to large graph instances.
- Establishes a paradigm for learning neural solvers in combinatorial optimization.
Computer Science > Machine Learning arXiv:2408.01503 (cs) [Submitted on 2 Aug 2024 (v1), last revised 26 Feb 2026 (this version, v2)] Title:Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs Authors:Lorenzo Colantonio (1), Andrea Cacioppo (1), Federico Scarpati (1), Maria Chiara Angelini (1), Federico Ricci-Tersenghi (1), Stefano Giagu (1) ((1) Department of Physics, Sapienza University of Rome) View a PDF of the paper titled Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs, by Lorenzo Colantonio (1) and 6 other authors View PDF HTML (experimental) Abstract: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 rand...
