![[2602.18419] Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://arxiv.org/static/browse/0.3.4/images/arxiv-logo-fb.png){kind=logo}
[2602.18419] Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
Summary
This paper evaluates the performance of Graph Neural Networks (GNNs) in solving hard constraint satisfaction problems, comparing them against classical heuristics using newly proposed benchmarks.
Why It Matters
The study addresses the growing claims of GNN superiority in optimization tasks, providing a rigorous benchmarking framework that enhances the reliability of future comparisons. This is crucial for researchers and practitioners aiming to understand the true capabilities of GNNs in complex problem-solving scenarios.
Key Takeaways
- GNNs are increasingly used for hard optimization problems but lack standardized benchmarks.
- The paper introduces new benchmarks based on random problems for fair comparison.
- Classical heuristics still outperform GNNs in the studied scenarios.
- The findings highlight challenges faced by neural networks in optimization tasks.
- Future claims of GNN superiority need to be substantiated with robust benchmarks.
Condensed Matter > Disordered Systems and Neural Networks arXiv:2602.18419 (cond-mat) [Submitted on 20 Feb 2026] Title:Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems Authors:Geri Skenderi, Lorenzo Buffoni, Francesco D'Amico, David Machado, Raffaele Marino, Matteo Negri, Federico Ricci-Tersenghi, Carlo Lucibello, Maria Chiara Angelini View a PDF of the paper titled Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems, by Geri Skenderi and 8 other authors View PDF HTML (experimental) Abstract: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 this https URL. Subjects: Disordered Systems and Neural Networks (cond-mat.dis-nn); Machine Learning (cs.LG) Cite as: arXiv:2602.18419 [cond-mat.dis-nn] (or arXiv:2602.18419v1 [cond-mat.dis-nn] for this version) https://doi.org/10.48550/arXiv.2602.18419 Focus to le...
