SAT-GNN: An Innovative Framework for Solving Boolean Satisfiability Problems Using Graph Neural Networks

SAT-GNN is a deep learning framework that uses Graph Neural Networks (GNNs) to solve the Boolean Satisfiability (SAT) problem. Its core idea is to convert CNF formulas into bipartite graph structures and use GNNs to learn structural patterns to predict whether a formula is satisfiable. This article will discuss the framework's principles and practical significance from aspects such as background, technical innovations, implementation process, training and evaluation, and application prospects.

The Boolean Satisfiability Problem (SAT) is the first proven NP-complete problem, with solution time growing exponentially with the number of variables. It is widely used in fields such as chip design verification, software testing, and scheduling optimization. Traditional solvers like DPLL and CDCL, although optimized, still struggle with large-scale complex formulas, so researchers are exploring machine learning methods to accelerate solving.

The core innovation of SAT-GNN lies in converting CNF formulas into bipartite graphs: variable nodes and clause nodes are connected by edges (edges indicate whether a variable appears in a clause in positive or negative form). This representation retains all structural information, adapts to the message-passing mechanism of GNNs, can learn constraint propagation patterns between variables and clauses, and aligns with the characteristics of the SAT problem.

SAT-GNN implementation consists of three steps: 1. Graph Construction: Parse CNF formulas into bipartite graphs, assign initial features to nodes and encode edge types; 2. GNN Computation: Use multi-layer GCN/GAT, aggregate neighborhood information through iterative message passing to generate context-aware node representations; 3. Classification Decision: Aggregate node representations into graph embeddings, output SAT/UNSAT binary classification results through fully connected layers, with end-to-end learning requiring no manual heuristic rules.

The project uses SATLIB's 3-SAT benchmark datasets (including instances of varying difficulty) for training and evaluation. The model learns to identify structural patterns related to satisfiability. Evaluation results show that it has high prediction accuracy, and after training, predictions for new instances are almost instantaneous, saving a lot of computational resources compared to traditional solvers.

SAT-GNN not only provides a new SAT solving tool but also demonstrates the idea of converting combinatorial optimization problems into graph learning, which can be extended to NP-hard problems such as graph coloring and constraint satisfaction. In practice, it can be used as a pre-filter for traditional solvers (quickly handling obvious instances) to improve efficiency with hybrid strategies; its lightweight design makes it easy to deploy and expand, and adapting to new problems only requires retraining.

SAT-GNN is a model of integration between AI and traditional algorithms. It does not replace traditional solving techniques but provides a new perspective. Its structure-aware capability is beyond the reach of traditional methods, showing developers a case of combining domain knowledge with deep learning. With the progress of neural networks in the future, more such innovations are expected to emerge, opening up a new paradigm of human-machine collaborative solving.