mlsanityData to 14 Oct 2026

On the Expressive Power of GNNs for Boolean Satisfiability

arXiv 2602.08745 ↗First posted 9 Feb 2026cs.LG cs.AIcited by 1

Not on the map. Why?

Abstract (arXiv)

Machine learning approaches to solving Boolean Satisfiability (SAT) aim to replace handcrafted heuristics with learning-based models. Graph Neural Networks have emerged as the main architecture for SAT solving, due to the natural graph representation of Boolean formulas. We analyze the expressive power of GNNs for SAT solving through the lens of the Weisfeiler-Leman (WL) test. As our main result, we prove that the full WL hierarchy cannot, in general, distinguish between satisfiable and unsatisfiable instances. We show that indistinguishability under higher-order WL carries over to practical limitations for WL-bounded solvers that set variables sequentially. We further study the expressivity required for several important families of SAT instances, including regular, random and planar instances. To quantify expressivity needs in practice, we conduct experiments on random instances from the G4SAT benchmark and industrial instances from the International SAT Competition. Our results suggest that while random instances are largely distinguishable, industrial instances often require more expressivity to predict a satisfying assignment.

Key facts. Cited by 1 paper in the map (data through 14 Oct 2026). Builds on 19 of its 52 references that are in the map. First posted on arXiv 9 Feb 2026.

Builds on

19 of 52 references.

References · 19

  1. 2016Semi-Supervised Classification with Graph Convolutional Networkscited by 11,361
  2. 2018How Powerful are Graph Neural Networks?cited by 4,393
  3. 2018Weisfeiler and Leman Go Neural: Higher-order Graph Neural Networkscited by 881
  4. 2019Provably Powerful Graph Networkscited by 389
  5. 2018Learning a SAT Solver from Single-Bit Supervisioncited by 200
  6. 2021Identity-aware Graph Neural Networkscited by 198
  7. 2019Universal Invariant and Equivariant Graph Neural Networkscited by 183
  8. 2019Guiding High-Performance SAT Solvers with Unsat-Core Predictionscited by 62
  9. 2022A Short Tutorial on The Weisfeiler-Lehman Test And Its Variantscited by 52
  10. 2022A Theoretical Comparison of Graph Neural Network Extensionscited by 48
  11. 2021Goal-Aware Neural SAT Solvercited by 28
  12. 2023The Descriptive Complexity of Graph Neural Networkscited by 26
7 more
  1. 2022Machine Learning Methods in Solving the Boolean Satisfiability Problemcited by 22
  2. 2019G2SAT: Learning to Generate SAT Formulascited by 20
  3. 2021NeuroBack: Improving CDCL SAT Solving using Graph Neural Networkscited by 19
  4. 2023G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networkscited by 18
  5. 2022SATformer: Transformer-Based UNSAT Core Learningcited by 14
  6. 2017The Weisfeiler-Leman Dimension of Planar Graphs is at most 3cited by 10
  7. 2017Improve SAT-solving with Machine Learningcited by 6

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2026: 1.

1 paper.

  1. 2026Target-Aware Data Augmentation for SAT Predictioncited by 0