Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
This work addresses the need for robust benchmarking in the machine learning community to prevent overhyped claims about GNNs in optimization domains.
The authors tackled the problem of unsolid claims about graph neural networks (GNNs) outperforming classical heuristics in hard constraint satisfaction problems by proposing new hard benchmarks based on random problems, and their fair comparison showed that classical algorithms still outperform GNNs.
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.