Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , , , , |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918357659287552 |
|---|---|
| author | Colantonio, Lorenzo Cacioppo, Andrea Scarpati, Federico Angelini, Maria Chiara Ricci-Tersenghi, Federico Giagu, Stefano |
| author_facet | Colantonio, Lorenzo Cacioppo, Andrea Scarpati, Federico Angelini, Maria Chiara Ricci-Tersenghi, Federico Giagu, Stefano |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_01503 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs Colantonio, Lorenzo Cacioppo, Andrea Scarpati, Federico Angelini, Maria Chiara Ricci-Tersenghi, Federico Giagu, Stefano Machine Learning 68T20 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. |
| title | Efficient Graph Coloring with Neural Networks: A Physics-Inspired Approach for Large Graphs |
| topic | Machine Learning 68T20 |
| url | https://arxiv.org/abs/2408.01503 |