Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems

Paper: 2602.18419 Authors: Geri Skenderi, Lorenzo Buffoni, Francesco D’Amico, David Machado, Raffaele Marino, Matteo Negri, Federico Ricci-Tersenghi, Carlo Lucibello, Maria Chiara Angelini Categories: cond-mat.dis-nn, cs.LG

Abstract

This paper addresses a critical gap in evaluating graph neural networks (GNNs) for hard optimization problems. While GNNs are increasingly applied to constraint satisfaction problems (CSPs) with claims of superiority over classical methods, these claims often lack rigorous validation on truly hard instances. The authors leverage statistical physics principles to create new benchmark datasets based on random CSP instances that exhibit genuine computational hardness. Through comprehensive experiments comparing state-of-the-art GNNs against classical heuristics, they demonstrate that classical algorithms still maintain superior performance. The work provides both the benchmark suite and detailed performance analysis, offering a foundation for more robust future comparisons in this domain.

Key Contributions

• Introduction of RandCSPBench, a standardized benchmark suite for hard constraint satisfaction problems grounded in statistical physics theory
• Rigorous comparison framework that ensures fair evaluation between GNNs and classical heuristics on genuinely hard problem instances
• Empirical demonstration that classical algorithms (including WalkSAT, Survey Propagation, and Belief Propagation) outperform current GNN approaches on hard CSP instances
• Analysis of fundamental challenges facing neural network methods in the hard optimization regime
• Open-source release of benchmarks and evaluation code to enable reproducible research

The Problem with Current Benchmarks

The optimization community has witnessed growing enthusiasm for applying GNNs to combinatorial problems, with numerous papers claiming neural approaches surpass classical methods. However, this research identifies a fundamental flaw in many such comparisons: the lack of truly hard benchmark instances.

From a computational complexity perspective, not all problem instances are created equal. Many CSP instances used in existing benchmarks fall into the “easy” regime where simple heuristics can find solutions quickly. The interesting computational challenge lies in the phase transition region—where problems shift from being under-constrained (many solutions exist) to over-constrained (no solutions exist). This critical region, characterized by the constraint density $\alpha$, represents where problems become genuinely hard.

The authors argue that without testing on instances from this hard regime, claims of GNN superiority lack solid foundation. Easy instances don’t reveal the true capabilities and limitations of different algorithmic approaches.

Methodology: Creating Truly Hard Benchmarks

The benchmark construction draws on deep insights from statistical physics of disordered systems. The authors focus on random $k$-SAT problems, a canonical CSP where each clause constrains $k$ Boolean variables. The hardness of these problems is well-understood theoretically through the lens of phase transitions.

For random $k$-SAT with $N$ variables and $M = \alpha N$ clauses, three distinct phases emerge:

1. SAT phase ($\alpha < \alpha_s$): Many solutions exist, problems are relatively easy
2. UNSAT phase ($\alpha > \alpha_c$): No solutions exist, unsatisfiability can often be proven efficiently
3. Hard phase ($\alpha_s < \alpha < \alpha_c$): The satisfiability threshold region where problems are computationally hardest

The benchmarks specifically target this hard phase, generating random instances with carefully controlled constraint densities. The suite includes:

• Random $k$-SAT instances for various $k$ values
• Random $k$-XORSAT problems (linear constraints over $\mathbb{F}_2$)
• Graph coloring problems on random graphs
• Instances spanning different size scales to test scalability

Each problem class is generated with multiple constraint densities around the critical threshold, ensuring comprehensive coverage of the hard regime.

Experimental Results and Analysis

The experimental evaluation compares several approaches:

Classical Methods:

• WalkSAT: A local search algorithm with random walk components
• Survey Propagation (SP): A message-passing algorithm from statistical physics
• Belief Propagation (BP): A standard inference algorithm
• Simulated Annealing: A probabilistic optimization technique

GNN Approaches:

• Graph Attention Networks (GAT)
• Message Passing Neural Networks (MPNN)
• Recurrent GNN architectures
• Various GNN variants specifically designed for combinatorial optimization

The results reveal a consistent pattern: classical algorithms, particularly Survey Propagation and WalkSAT, significantly outperform GNN methods on hard instances. The performance gap widens as problem size increases and as instances approach the critical threshold.

Key findings include:

• Solution quality: Classical methods find satisfying assignments more frequently on satisfiable instances
• Convergence speed: Traditional algorithms reach solutions faster in terms of computational steps
• Scalability: The performance advantage of classical methods grows with problem size
• Robustness: Classical approaches maintain consistent performance across different constraint densities, while GNN performance degrades sharply in the hard regime

Understanding GNN Limitations

The paper provides insightful analysis of why GNNs struggle on hard CSP instances:

Limited expressiveness: Standard GNN architectures have bounded expressive power related to the Weisfeiler-Leman graph isomorphism test. Hard CSP instances may require reasoning beyond this expressiveness level.

Training distribution mismatch: GNNs are typically trained on problem distributions that may not adequately represent the hard regime. The phase transition region has distinct statistical properties that are difficult to capture in training data.

Local vs. global reasoning: GNNs perform local message passing, which may be insufficient for problems requiring global constraint propagation. Classical algorithms like Survey Propagation explicitly model global statistical properties.

Optimization landscape: The loss landscape for training GNNs on hard instances is likely highly non-convex with many poor local minima, making effective training challenging.

Generalization challenges: Even when trained on hard instances of one size, GNNs struggle to generalize to larger problem sizes, suggesting they may be learning instance-specific patterns rather than general problem-solving strategies.

Implications for Future Research

This work has important implications for the field:

Benchmark standards: The community needs standardized, truly hard benchmarks to make meaningful comparisons. The RandCSPBench suite provides this foundation.

Honest evaluation: Claims of neural network superiority must be backed by rigorous testing on hard instances, not just easy cases where any reasonable algorithm succeeds.

Hybrid approaches: Rather than viewing GNNs as replacements for classical methods, future work might explore hybrid approaches that combine neural and classical techniques.

Theoretical understanding: More theoretical work is needed to understand the fundamental limitations of GNN architectures for hard optimization and what architectural innovations might overcome these limitations.

Problem-specific design: Different CSP classes may require specialized GNN architectures rather than generic designs. Understanding problem structure is crucial.

Takeaways

1. Classical algorithms still outperform state-of-the-art GNNs on truly hard constraint satisfaction problems, particularly in the phase transition region where computational complexity peaks.

2. Many existing benchmarks for evaluating neural approaches to combinatorial optimization use instances that are too easy, leading to misleading conclusions about relative performance.

3. The RandCSPBench suite provides a rigorous, physics-informed benchmark based on random CSP instances in the hard regime, enabling fair comparisons between neural and classical methods.

4. GNNs face fundamental challenges in the hard optimization regime, including limited expressiveness, training distribution mismatch, and difficulties with global reasoning that classical algorithms handle more effectively.

5. Future research should focus on understanding these limitations theoretically and developing hybrid approaches that combine the strengths of neural and classical methods rather than treating them as competing paradigms.

6. The statistical physics perspective offers valuable insights for designing hard benchmarks and understanding algorithmic behavior in different problem regimes.

7. Scalability remains a critical challenge—the performance gap between classical and neural methods widens as problem size increases, suggesting current GNN architectures may not capture the essential algorithmic principles needed for hard optimization.