Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems
Not on the map. Why?
Abstract (arXiv)
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.
Key facts. Cited by 1 paper in the map (data through 7 Oct 2026). Builds on 37 of its 82 references that are in the map. First posted on arXiv 20 Feb 2026.
Builds on
37 of 82 references.
References · 37
- 2015Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shiftcited by 6,979
- 2017Inductive Representation Learning on Large Graphscited by 6,284
- 2016Layer Normalizationcited by 5,579
- 2019Fast Graph Representation Learning with PyTorch Geometriccited by 2,414
- 2024Scaling LLM Test-Time Compute Optimally can be More Effective than Scaling Model Parameterscited by 1,928
- 2018Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizoncited by 612
- 2025Scaling up Test-Time Compute with Latent Reasoning: A Recurrent Depth Approachcited by 372
- 2019Exact Combinatorial Optimization with Graph Convolutional Neural Networkscited by 313
- 2020AdaBelief Optimizer: Adapting Stepsizes by the Belief in Observed Gradientscited by 282
- 2021Combinatorial optimization and reasoning with graph neural networkscited by 267
- 2023DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimizationcited by 216
- 2018Learning a SAT Solver from Single-Bit Supervisioncited by 198
25 more
- 2018Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Searchcited by 182
- 2021End-to-End Constrained Optimization Learning: A Surveycited by 154
- 2020Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphscited by 115
- 2021Combinatorial Optimization with Physics-Inspired Graph Neural Networkscited by 107
- 2020Learning the Travelling Salesperson Problem Requires Rethinking Generalizationcited by 96
- 2019Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problemscited by 40
- 2022Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 33
- 2022Graph Coloring with Physics-Inspired Graph Neural Networkscited by 29
- 2021Goal-Aware Neural SAT Solvercited by 27
- 2022Augment with Care: Contrastive Learning for Combinatorial Problemscited by 22
- 2021NeuroBack: Improving CDCL SAT Solving using Graph Neural Networkscited by 19
- 2022Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cutcited by 19
- 2022NSNet: A General Neural Probabilistic Framework for Satisfiability Problemscited by 18
- 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 17
- 2015The backtracking survey propagation algorithm for solving random K-SAT problemscited by 14
- 2022SATformer: Transformer-Based UNSAT Core Learningcited by 14
- 2020Learning from Survey Propagation: a Neural Network for MAX-E-3-SATcited by 11
- 2019Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphscited by 9
- 2023Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent setcited by 9
- 2022Hard Optimization Problems have Soft Edgescited by 8
- 2023Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problemscited by 5
- 2022Denoising Diffusion for Sampling SAT Solutionscited by 4
- 2024Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Updatecited by 4
- 2023Addressing Variable Dependency in GNN-based SAT Solvingcited by 3
- 2022Arbitrarily Large Labelled Random Satisfiability Formulas for Machine Learning Trainingcited by 1
Built on by
Citing papers per year: 2026: 1.
1 paper.