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
Organizations: Department of Computing Sciences, Bocconi University, Milan, Italy · Bocconi Institute for Data Science and Analytics (BIDSA) · Department of Physics and Astronomy and INFN, University of Florence · Dipartimento di Fisica, Sapienza Universit`a di Roma · CNR - Nanotec, unit`a di Roma, P.le Aldo Moro 5, 00185 Rome, Italy · Department of Theoretical Physics, Physics Faculty, University of Havana. CP10400, La Habana, Cuba · INFN, sezione di Roma1, P.le Aldo Moro 5, 00185 Rome, Italy
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.
Figures & tables
Figure 1: Probability of finding a satisfying assignment to 3-SAT problems as a function of α=M/N with the supervised (top row) and unsupervised (bottom row) NeuroSAT GNN model. To validate claims regarding the importance of scaling the inference time message-passing iterations of GNNs with the problem size ( N ), we test the model in three different scenarios by performing a small number of fixed iterations (left), a large number of fixed iterations (center), and linearly scaling the number of iterations with the problem size (right). The figure shows that the linear scaling procedure produces excellent results. It is worth noting that with the scaling, inference time is handled more consistently (by definition). For instance, using 512 iterations takes significantly longer for smaller sizes compared to employing linear scaling. Finally, it is clear to see that training an unsupervised model produces much better results compared to the supervised case.
Figure 2: Probability of finding a satisfiable assignment using different algorithms at fixed size ( N=256 on the left and N=1024 on the right) for the K -SAT ( K=3,4 ) and q -col ( q=3,5 ) problems. We focus on two sizes: N=256 is the largest size in the training set, and N=1024 , which is out-of-distribution, to check the generalization power.
SAT
K=3 ; S ↑
K=4 ; S ↑
K=3 ; RE ↓
K=4 ; RE ↓
NeuroSAT
84.48
47.52
0.0072
0.0028
QuerySAT
92.38
66.57
0.0068
0.0027
FMS
99.98
95.15
0.0061
0.0032
SA
98.75
82.61
0.0063
0.0027
SP + dec.
82.28
60.02
-
-
Table 1: Score (S) and Residual Energy (RE) reached by each algorithm . The Score is the ratio of solved instances over the satisfiable ones in the test dataset ( N≤256 and any α or c values). An instance is considered satisfiable if at least one of the analyzed algorithms found a solution (see Sec. 4.5 ). The ratio of sat instances nsat/ntot are 28656/42000 (3-SAT), 19806/21000 (4-SAT), 11750/20000 (3-col), and 9184/20000 (5-col). RE is the average of the intensive energy computed on instances for which the algorithm is not finding a solution. The running steps are 1000N for SA, 100N for FMS in the K -SAT problem, and 1000N for SA, 625N for FMS in the q -col problem, with each step involving N attempted single-variable updates. The number of recurrent iterations is 2N for NeuroSAT and QuerySAT. Best results are in bold. RE values for the SP algorithm are missing because SP sometimes does not converge on hard instances, and in this case it does not output a configuration of the variables (see Sec. 4.3.3 for details).
Figure 3: Estimation of the algorithmic threshold in the large size limit for different algorithms and problems, indicated in the label under the panel. The left panel shows the easy situation, when crossings of curves for different sizes take place at the same point (apart from small finite-size corrections), and the crossing point corresponds to the algorithmic threshold in the large N limit. Instead, in the central and the right panels, we report more difficult situations, where the crossings are not present or happen very close to boundaries ( P=0 or P=1 ). In the latter cases, the curves measured at finite N provide a bound to the algorithmic threshold in the large N limit. Data in the central panel provide a lower bound, while those in the right panel provide an upper bound.
SAT
K=3
K=4
NeuroSAT
3.8
≲ 8.1
QuerySAT
4.1
9.1
FMS
4.2
9.8
SA
4.1
9.5
SP + dec.
4.2
9.7
Table 2: Algorithmic threshold for different algorithms By definition, the algorithmic threshold is computed taking the limit of large N . In this limit, Neural Solvers behave much worse than classical algorithms, especially in the hard 1RSB problems ( 4 -SAT and 5 -col). FMS is the algorithm that has the best algorithmic thresholds.
SAT
K=3
K=4
NeuroSAT
14.57
24.91
QuerySAT
134.43
322.53
FMS
1.83
3.80
SA
1.82
13.04
SP + dec.
2.61
3.06
Table 3: Average running times (in seconds) for different algorithms over 400 instances with N=1024 variables. For neural solvers, we report the testing time. We fix α=4.1 for 3-SAT, α=9.4 for 4-SAT, c=3.68 for 3-col and c=11.1 5-col. For K -SAT, we ran the algorithms using Lenovo Hardware AMD Ryzen Threadripper PRO 5975WX 32-Cores with 251 GB of RAM. For q -col, we ran the rPI-GNN using the NVIDIA Tesla V100 SXM2 32G GPU and QuerySAT on NVIDIA TITAN RTX GPU, while all other algorithms were run on a single CPU Intel Xeon Gold 6248 2.5G.
ntot
nsat
3-SAT
42000
28656
4-SAT
21000
19806
3-col
20000
11750
5-col
20000
9184
Table 4: The total number of instances and the number of satisfiable ones for each (in-distribution, N≤256 ) test dataset.
Graph neural networks are usually treated as auxiliaries for combinatorial optimization: they imitate algorithms, guide search, or supply scores to classical procedures. We show that this auxiliary role is not intrinsic. A GNN can itself be a heuristic. For the Euclidean Travelling Salesman Problem, we train a non-autoregressive GNN with no labels, rewards, sequential decoding, search, or local improvement. A differentiable Hamiltonian-cycle objective is the only supervision. The trained model produces a complete tour in one forward pass, while dropout and snapshots from a single training trajectory provide solution diversity without engineered moves. The heuristic is therefore learned, not programmed. It is also fast: batched inference remains in the millisecond regime on GPUs. Experiments on TSP100, TSP200, and TSP500 show that the model consistently improves over nearest-neighbor greedy baselines. These results identify unsupervised GNNs as a class of fast learned heuristics for combinatorial optimization.
Yimeng Min, Carla P. Gomes
Department of Computer Science Cornell University Ithaca, NY, USA
The Winner Determination Problem (WDP) in combinatorial auctions is NP-hard, and no existing method reliably predicts which instances will defeat fast greedy heuristics. The ML-for-combinatorial-optimization community has focused on learning to replace solvers, yet recent evidence shows that graph neural networks (GNNs) rarely outperform well-tuned classical methods on standard benchmarks. We pursue a different objective: learning to predict when a given instance is hard for greedy allocation, enabling instance-dependent algorithm selection. We design a 20-dimensional structural feature vector and train a lightweight MLP hardness classifier that predicts the greedy optimality gap with mean absolute error 0.033, Pearson correlation 0.937, and binary classification accuracy 94.7% across three random seeds. For instances identified as hard -- those exhibiting ``whale-fish'' trap structure where greedy provably fails -- we deploy a heterogeneous GNN specialist that achieves ≈0% optimality gap on all six adversarial configurations tested (vs.\ 3.75--59.24% for greedy). A hybrid allocator combining the hardness classifier with GNN and greedy solvers achieves 0.51% overall gap on mixed distributions. Our honest evaluation on CATS benchmarks confirms that GNNs do not outperform Gurobi (0.45--0.71 vs.\ 0.20 gap), motivating the algorithm selection framing. Learning when to deploy expensive solvers is more tractable than learning to replace them.
Sungwoo Kang
Department of Electrical and Computer Engineering Korea University Seoul 02841, Republic of Korea
The conclusions of an experimental study of algorithms are only as good as the instances they are run on. Benchmark libraries for well-studied problems took decades to curate, while evaluations of new problems often fall back on random instances, which are known to be misleading: they may say more about the random generator than about the algorithmic question at hand. We treat instance generation as an optimization problem: parameterize the instance space, take the solver's running time as the objective, and let a black-box optimizer search for hard instances. We develop a widely applicable workflow built on the Nevergrad optimization platform and demonstrate it on four NP-hard problems: satisfiability, traveling salesperson, Hamiltonian cycle, and non-permutation flow-shop scheduling. The search needs only the solver, an instance encoder, and a compute budget. Our evolved instances beat the hardest instance of a budget-matched random draw in all four case studies, by an order of magnitude or more in three. They are often competitive with long-curated benchmark sets: our SAT champion is harder (for a three-solver portfolio) than 78% of the 498 SAT Competition formulas in its size class; our 20-city TSP champions take several times longer than the hardest measured classical TSPLIB instance (229 cities); and our flow-shop champion takes 238.6 seconds of CP Optimizer time to solve to proven optimality (versus 4.5 seconds for the hardest of 100,000 random draws) while denying CP-SAT an optimality proof. The optimizer even recovers known structure from running time alone: it locates a SAT clause/variable ratio near the phase transition and finds structurally different champions for the two scheduling engines.
Jamie Fravel, Martin Koutecký, Pavlo Tsitsei
Computer Science Institute, Faculty of Mathematics and Physics, Charles University, Prague, Czech Republic.