# Graph Neural Networks and Boolean Satisfiability

arXiv: https://arxiv.org/abs/1702.03592 · HTML: https://mlsanity.com/paper/1702.03592/

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 12 Feb 2017.

## Built on by (most cited first, 8 of 8)

- [Machine Learning Methods in Solving the Boolean Satisfiability Problem](https://mlsanity.com/paper/2203.04755/) (2022)
- [G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks](https://mlsanity.com/paper/2309.16941/) (2023)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [SATfeatPy -- A Python-based Feature Extraction System for Satisfiability](https://mlsanity.com/paper/2204.14116/) (2022)
- [Using deep learning to construct stochastic local search SAT solvers with performance bounds](https://mlsanity.com/paper/2309.11452/) (2023)
- [Neural Ising Machines via Unrolling and Zeroth-Order Training](https://mlsanity.com/paper/2602.00302/) (2026)
- [Hypergraph Neural Networks Accelerate MUS Enumeration](https://mlsanity.com/paper/2604.09001/) (2026)
- [Unsat Core Prediction through Polarity-Aware Representation Learning over Clause-Literal Hypergraphs](https://mlsanity.com/paper/2605.04819/) (2026)

## Abstract (arXiv)

In this paper we explore whether or not deep neural architectures can learn to classify Boolean satisfiability (SAT). We devote considerable time to discussing the theoretical properties of SAT. Then, we define a graph representation for Boolean formulas in conjunctive normal form, and train neural classifiers over general graph structures called Graph Neural Networks, or GNNs, to recognize features of satisfiability. To the best of our knowledge this has never been tried before. Our preliminary findings are potentially profound. In a weakly-supervised setting, that is, without problem specific feature engineering, Graph Neural Networks can learn features of satisfiability.