Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
Fuente:
arXiv
Saved in:
| Main Authors: | , , , , , , , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914386053955584 |
|---|---|
| author | Skenderi, Geri Buffoni, Lorenzo D'Amico, Francesco Machado, David Marino, Raffaele Negri, Matteo Ricci-Tersenghi, Federico Lucibello, Carlo Angelini, Maria Chiara |
| author_facet | Skenderi, Geri Buffoni, Lorenzo D'Amico, Francesco Machado, David Marino, Raffaele Negri, Matteo Ricci-Tersenghi, Federico Lucibello, Carlo Angelini, Maria Chiara |
| contents | Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid due to a lack of standard benchmarks on truly hard instances. From a statistical physics perspective, we propose new hard benchmarks based on random problems. We provide these benchmarks, along with performance results from both classical heuristics and GNNs. Our fair comparison shows that classical algorithms still outperform GNNs. We discuss the challenges for neural networks in this domain. Future claims of superiority can be made more robust using our benchmarks, available at https://github.com/ArtLabBocconi/RandCSPBench. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_18419 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems Skenderi, Geri Buffoni, Lorenzo D'Amico, Francesco Machado, David Marino, Raffaele Negri, Matteo Ricci-Tersenghi, Federico Lucibello, Carlo Angelini, Maria Chiara Disordered Systems and Neural Networks Machine Learning Graph neural networks (GNNs) are increasingly applied to hard optimization problems, often claiming superiority over classical heuristics. However, such claims risk being unsolid due to a lack of standard benchmarks on truly hard instances. From a statistical physics perspective, we propose new hard benchmarks based on random problems. We provide these benchmarks, along with performance results from both classical heuristics and GNNs. Our fair comparison shows that classical algorithms still outperform GNNs. We discuss the challenges for neural networks in this domain. Future claims of superiority can be made more robust using our benchmarks, available at https://github.com/ArtLabBocconi/RandCSPBench. |
| title | Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems |
| topic | Disordered Systems and Neural Networks Machine Learning |
| url | https://arxiv.org/abs/2602.18419 |