G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks
Authors: Zhaoyu Li
Jinpei Guo
Xujie Si
Venue: Accepted by TMLR ()

Abstract: Graph neural networks (GNNs) have recently emerged as a promising approach for solving the Boolean Satisfiability Problem (SAT), offering potential alternatives to traditional backtracking or local search SAT solvers. However, despite the growing volume of literature in this field, there remains a notable absence of a unified dataset and a fair benchmark to evaluate and compare existing approaches. To address this crucial gap, we present G4SATBench, the first benchmark study that establishes a comprehensive evaluation framework for GNN-based SAT solvers. In G4SATBench, we meticulously curate a large and diverse set of SAT datasets comprising 7 problems with 3 difficulty levels and benchmark a broad range of GNN models across various prediction tasks, training objectives, and inference algorithms. To explore the learning abilities and comprehend the strengths and limitations of GNN-based SAT solvers, we also compare their solving processes with the heuristics in search-based SAT solvers. Our empirical results provide valuable insights into the performance of GNN-based SAT solvers and further suggest that existing GNN models can effectively learn a solving strategy akin to greedy local search but struggle to learn backtracking search in the latent space. Our codebase is available at https://github.com/zhaoyu-li/G4SATBench.

Published in Transactions on Machine Learning Research (05/2024)
G4SATBench: Benchmarking and Advancing SAT Solving with Graph Neural Networks
Zhaoyu Li University of Toronto
shaomu@@s..oronto..de edu
Jinpei Guo
mike072880situ.ccuuc
Shanghai Jiao Tong Universiby
Xujie Si University of Toronto
sin@cs.toronto. edu
Reviewed OpenReview:
https: oppnreeveee.. net/ forum? id= 7V1r
Abstract
Graph neural networks (GNNs) have recently emerged as a promising approach for solving the Boolean Satisfiability Problem (SAT), offering potential alternatives to traditional back- tracking or local search SAT solvers. However, despite the growing volume of literature in this field, there remains notable absence of unified dataset and fair benchmark to evalu- and compare existing approaches. To address this crucial gap, we present G4SATBench, the first benchmark study that establishes a comprehensive evaluation framework for GNN- based SAT solvers. In G4SATBench, we meticulously curate a large and diverse set of SAT datasets comprising problems with difficulty levels and benchmark a broad range of GNN models across various prediction tasks, training objectives, and inference algorithms. plore the learning abilities and comprehend the rengths and limitations GNN-based SAT solvers, we also compare their solving processes with the heuristics in tearch-based SAT solvers. Our empirical results provide valuable insights into the performance of GNN- based SAT solvers and further suggest that existing GNN models can effectively learn solving strategy akin to greedy local search but struggle to learn backtracking search in the latent space. Our codebase is available at httpp:///tthabb.oo///oooo/o/////
ex-
1 Introduction
The Boolean Satisfiability Problem (SAT) is crucial problem at the nexus of computer science, logic, and operations research, which has garnered significant attention over the past five decades. To solve SAT in- stances efficiently, modern SAT solvers have been developed with backtracking (especially with conflict-driven clause learning, a.k.a. CDCL) or local search (LS) heuristics that effectively exploit the instance's structure and traverse its vast search space (Biere et al. 2009). However, designing such heuristics remains a highly non-trivial and time-consuming lask, with a lack of significant improvement recent years. Conversely, the recent rapid advances in graph neural networks (GNNs) (Li ct al., 2016: Kipf Welling 2017 Xu et al., 2019) have shown impressive performances in analyzing structured data, offering a promising opportunity to enhance even replace modern SAT solvers. As such, there have been massive efforts to leverage GNNs
to solve SAT over the last few years (Holden et al. 2021 Guo et al. 2022)
Despile the recent. progress, the question of how (well) GNNs can solve SAT remains unanswered. One of the main reasons for this is the variety of learning objectives and usage scenarios employed existing work, making difficult to evaluate different methods in a fair and comprchensive manner. For example, NeuroSAT (Selsam et al. 2019) predicts satisfiability, NeuroCore (Selsam & Bjorner 2019) classifies unsat-
variables, QuerySAT Ozolins et al. 2022 constructs satisfying assignment, and NSNet (T. & Si 2022)

---

Published in Transactions on Machine Learning Research (05/2024)
predicts marginal distributions of all satistying solutions to solve the SAT problem. Moreover, most previous research has experimented on different datasets that vary in range of settings (e.g., data distribution, instance size, and dataset size), which leads to a lack of unified and standardized datasets for training and evaluation. Additionally, some work (Amizadeh et al. 2019b; Shi et al.) 2023 Yan et al. 2023) has noted the difficulty of re-implementing prior approaches as baselines, rendering it arduous to draw consistent conclusions about the performance of peer methods. All of these issues impode the development of GNN- based solvers for SAT solving.
To systematically quantify the progress in this field and facilitate rapid, reproducible, and generalizable rescarch, we propose G4SATBench, the first comprchensive benchmark study for SAT solving with GNNs. G4SATBench is characterized as follows:
First, we construct a large and diverse collection of SAT datasets that includes instances from distinct sources and difficulty levels. Specifically, our benchmark consists of 7 different datasets from 3 benchmark families, including random instances, pscudo-industrial instances, and combinatorial problems. It not only covers wide range of prior datasets but also introduces 3 levels of difficulty for each dataset to enable fine-grained analyses.
Second, we re-implement various GNN-based SAT solvers with unified interfaces and configuration set- tings, establishing a general evaluation protocol for fair and comprehensive comparisons. Our framework allows for evaluating different GNN models in SAT solving with various prediction tasks, training objec- tives, and inference algorithms, encompassing the diverse learning frameworks employed in the existing literature.
Third, we present baseline results and conduct thorough analyses of GNN-based SAT solvers, providing detailed reference of prior work and laying solid foundation for future rescarch. Our evaluations assess the performances of different choices of GNN models (e.g., graph constructions, message-passing schemes) with particular attention to some crilical parameters (e.g., message-passing iteralions), as well as their generalization ability across different distributions.
Lastly, we conduct series of in-depth experiments to explore the learning abilities of GNN-based SAT solvers. Specifically, we compare the training and solving processes of GNNs with the heuristics employed in both CDCL and LS-based SAT solvers. Our experimental results reveal that GNNs lend to develop a solving heuristic similar to greedy local search to find a satisfying assignment but fail to effectively learn the CDCL heuristic in the latent space.
We believe that G4SATBench will help the research community to make significant strides in understanding the capabilities and limitations of GNNs for solving SAT and facilitate further endeavors in this domain.
2 Related Work
SAT solving with GNNs.
Existing GNN-based SAT solvers can be broadly categorized into two
branches (Holden et al.]
2021 Guo et al. 2022 ; standalone neural solvers and newral-guided solvers. Stan-
dalone neural sol vers utilize GNNs to solve SAT instances directly. For example, a stream of research BBnz
& Lamm
2017 Selsam et al. 2019
Jaszczur et al.) 2020 Cameron et al. 2020 Shi et al. 2023) focuses
on predicting the satisfiability of a given formula, while several alternative approaches (Amizadeh et al.
2019a by Ozolins et al.) 2022 Li et al. 2023; Yan et al.) 2023) aim to construct a satistying assignment. Neural-guided solvers, the other hand, integrate GNNs with modern SAT solvers, trying to improve their search heuristics with the prediction of GNNs. These methods typically train GNN models using supervised learning on some tasks such as unsat-core variable prediction (Selsam & Bjørner 2019 Wang et al. 2021) satisfying assignment prediction [Zhang et al. 2020), glue variable prediction (Han 2020), and assignment marginal prediction [Li & Si 2022), or through reinforcement learning (Yolcu & Póczos 2019 Kurin et al,
2020) by modeling the entire search procedure as a Markov decision process. Despite the rich literature on SAT solving with GNNs, there is no benchmark study evaluate and compare the performance of these GNN models. We hope the proposed Genc would address this gap.
2

---

Published in Transactions on Machine Learning Research (05/2024)
SAT datasets. Several established SAT benchmarks, including the prestigions SATLIB (Hoos & Stützle 2000) and the SAT Competitions over the years, have provided variety of practical instances to assess the performance of modern SAT solvers. Regrettably, these datasets are not particularly amenable for GNNs to learn from, given their relatively modest scale (less than 100 instances for a specific domain) or overly exlensive instances (exceeding 10 million variables and clauses). To address this issue, researchers have turned to synthetic SAT instance generators @Giráldez-Cru Levy, 2015 2017 Lauria et al., 2017 Sclsam iet al. 2019), which allow for the creation of flexible number of instances with eustomizable settings. However, most of the existing datasets generated from these sources limited to few domains (less than 3 generators), small in size (less than 10k instances), or easy in difficulty (less than 40 variables within an instance), and there is no standardized dataset for evaluation. In G4SATBench, we include a variety of synthetic generators with carefully selected configurations, aiming to construct a broad collection of SAT datasets that are highly conducive for training and evaluating GNNs.
3 Preliminaries
The SAT problem. In propositional logic, a Boolean formula is constructed from Boolean variables and logical operators such conjunctions (A), disjunctions (V), and negations (-). It is typical represent Boolean formulas in conjunctive normal form (CNF), expressed as conjunction of clauses, where each clause is a disjunction of literals, which can be either a variable or its negation. Given a CNF formula, the SAT problem is to determine if there exists an assignment of boolean values to its variables such that the formula evaluates to true. If this is the case, the formula. is called satisfiable; otherwise, it is issalilfi For a satisfiable instance, one expected to construct a satisfying assignment to prove its satisfiability. On the other hand, for an unsatisfiable formula, one can find a minimal subsot of clauses whose conjunction still unsatisfiable. Such set of clauses is termed the unsat core, and variables in the unsat core are referred to unsat-core variables.
Graph representations of CNF formulas. Traditionally, CNF formula can be represented using 4 types of graphs (Biere et al. 2009): Literal-Clause Graph (LCG), Variable-Clan Clause Graph (VCG), Literal- Incidence Graph (LIG), and Variable-Incident clause nodes connected by edges indicating the presence of a literal in a clause. The VCG is formed by merging the positive and negative literals of the same variables LCG. The LIG, on the other hand, only consists of literal nodes, with edges indicating co-occurrence in clause. Lastly, the VIG is derived from LIG using the same merging operation as VCG.
Graph (VIG), The LCG is bipartite graph with literal and
4 G4SATBench: A Benchmark Study on GNNs for SAT Solving
The goal of G4SATBench is to establish general framework that enables comprehensive comparisons and evaluations of various GNN-based SAT solvers. In this section, we will delve into the details of G4SATBench, including its datasets, GNN models, prediction tasks, as well as training and testing methodologies. The overview of the G-SSABBench framework is shown in Figure
4.1 Datasets
G4SATBench is built on a diverse set of synthetic CNF generators. It currently consists of 7 datasets sourced from 3 distinct domain areas: random problems, psendo-induutriall problems, and combinatorial problems. Specifically, in CNFGen [Lauria et al., 2017) to produce random CNF formulas. For pscudo-industrial problems, we employ the Community Attachment (CA) model (Girâldez-Cru & Levy 2015 and the Popularity-Similann (PS) model (Giráldez-Cre & Levy, 2017), which generate synthetic instances that exhibit similar statistical features, such as the community and the locality, to those observed in real-world industrial SAT instances. For combinatorics, we resort 3 synthetic generators in CNFGGn (Lauria et al. 2017) to create SAT instances derived from the translation of k-Clique, k- k-Dominating Set, and k- Verete Cover problems.
utilize the SR generator in NeuroSAT (Selsam et al. 2019) and the 3-SAT generator
3

---

Published in Transactions on Machine Learning Research (05/2024)
Datasets
Graphs
Models
Tasks
Training Objectives
Inference Algorithms
Random Problems
Preudo- industrial Problems
Combinatrnal Problems
NeurošAT
Satifiabilitt
Standand Reacout
Supersised
SA
CA
k-clque
GCN
Satisfing Assigmment
Clustering Decading
A D-Domset
VCG*
6GNN
Unsuperxised
Unsat-core Variable
Multple Precictions
GIN
Figure 1: Framework overview of G4SATBench.
In addition to the diversity of datasets, G4SATBench offers distinct difficulty levels for all datasets to enable fine-grained analyses. These levels include easy, medium, and hard, with the latter representing more complex problems with increased instance sizes. For example, the easy SR dataset contains instances with 40 variables, the medium SR dataset contains formulas with 40 200 variables, and the hard SR dataset consists of formulas with variables ranging from 200 to 400. For each casy and medium dataset, generate 80k pairs of satisfiable and unsatisfiable instances for training, 10k pairs for validation, and 10k pairs for testing. For each hard dataset, we produce 10k testing pairs. It is also worth noting that the parameters for our synthetic generators are meticulously selected to avoid generating trivial cases. For instance, we produce random 3-SAT formulas at the phase-transitee transition region where the relationship between the number of clauses (m) and variables (n) is m 4.258n + 58.26n 2/3 Crawford Auton 1996), and utilize the vertex Erdös-
Rényi graph with an edge probability of = ( -1/(2) to generate k- d-Clique problems, making the expected number of k-Cliques in a graph equals [Bollobás & Erdös 1976). To provide a detailed characterization of our generated datasets, we compute several statistics the SAT instances across difficulty levels G4SATBench. Please refer to Appendix for more information about the datasets.
4.2 GNN Baselines
Graph constructions. It is important to note that traditional graph representations of CNF formula of- ten lack the requisite details for optimally constructing GNNs. Specifically, the LIG and VIG exclude clause- specific information, while the LCG and VCG fail to dif- ferentiate between positive and negative literals of the same variable. To address these limitations, existing ap- proaches typically build GNN models on the refined ver- sions of the T.CG and VCG encodings. In the LCG, new type of edge is added between each literal and its nega- tion, while the VCG is modified by using two types of edges to indicate the polarities of variables within clause. These modified encodings are termed the LCG and VCG* respectively, and example of them is shown in Figure 2 It is also worth noting alternative graph encodings like the Lond-Inverter-rran can be applied for SAT instances that are not in CNF. However, such representations are specialized to specific applications (like CircuitSAT) and are not designed for general purposes. Given this specialization, we choose to keep them outside the scope of the current G4SATBench.
LOG*
VCG*
Figure 2: LCG* and VCG* of the CNF formula
(x1 -r2) (#1 V Is) A (-r1 V V Vz).
(AIG),
Message-passing schemes. G4SATBench enables performing various helergeneous message-passage al- gorithms between neighboring nodes on the LCG* or VCG* encodings of a CNF formula. For the sake of illutration, we will take GNN models on the LCG* as an example. We first define d-dimensional embed- ding for every literal node and clause node, denoted by b and he respectively. Initially, all these embeddings are assigned to two learnable vectors hy and bo, depending their node types. At the k-th iteration of
4

---

Published in Transactions on Machine Learning Research (05/2024)
message passing, these hidden representations updated as:
A.(k) = UPD
AGG (EN(c)
(( {MLP (ng (n(--11)3 1 (k-1) mi mf6-1)
}) h )
(1)
/ = UPD
AGG (EN())
(MLP [ (n(--1)3
where NV) denotes the set neighbor nodes, MLP the multi-layer perception, UPD(-) is the update func- tion, and -. is the aggregation function. Most GNN models on LCG* use Equation | with different choices of the update function and aggregation function. For instance, NeuroSAT employs LayerNormL- STM (Ba et al.) 2016) as the update function and summation the aggregation function. In G4SATBench, provide diverse range of GNN models, including NeuroSAT (Selsam et al. 2019), Graph Convolutional Network (GCN) (Kipf & Welling, 2017), Gated Graph Neural Network (GGNN) (Li et al., (016), and Graph Isomorphism Network (GIN) (Xu et al. 2019), on the both LCG* and VCG*. More details of these GNN modols are included in Appendix
4.3 Supported Tasks, Training and Testing Settings
Prediction tasks. In G4SATBench, we support three essential prediction tasks for SAT solving: satis- liability prediction, satisfying assignment prediction, and unsal-core variable prediction. These lasks are widely used in both standalone neural solvers and neural-guided solvers. Technically, we model satisfiability prediction as binary graph classification task, where 1/0 denotes the given SAT instance is satisfi- bole/uunstissiablee Here, we take GNN models the LCG* as example. After T message passing iterations, we obtaín the graph embedding by applying mean pooling on all literal embeddings, and then predict the satisfiability using an MLP followed by the sigmoid function a:
yo = a MMPP (MEAN (1nF))
(2)
For satisfying assignment prediction and unsat-core variable prediction, we formulate them binary node classification tasks, predicting the label for each variable in the given CNF formula 6. In the case of GNNs on the I.CG*, we concatenate the embeddings of each pair of literals hy and h to construct the variable embedding, and then readout using an MLP and the sigmoid function σ:
yo = (MIP (Tfm,.9)
(3)
Training objectives. To train GNN models on the aforementioned tasks, one common approach is to minimize the binary cross-entropy loss between the predictions and the ground truth labels. In addition to supervised learning, GencTBench supports two unsupervised training paradigms for satisfying assignment prediction (Amizadch al., 2019a] Ozolins et al.) (202)). The first approach aims to differentiate and maximize the satisfiability value of a CNF formula (Amizadeh el al.) 2019a). It replaces the operator with the function (x;)) 1 I, and uses smooth max and min functions to replace the V and A operators, The smooth max and min functions are defined follows:
Smaz (11 x2 .2a) Σi=1 Ii eF//t
(21 U2, T2,.... .......)) Di 8i : -2/7
(4)
Σi e0i/T
Σ E-i/T
where 7 2 0 is the temperature parameter. Given predicted assignment 2, apply the smoothing logical operators and substitute variables in formula & with the corresponding values from x to calculate its satisfiability value S(x). Then we can minimize the following loss function:
(1 (1- S(x)) (x(x) = - (1=S(x))) + 8(x)** (n 2 1 is a predefined constant)
(5)
The second unsupervised loss is defined as follows Ozolins et al.
2022):
Ve(x) 1 II (1 xx) II Di,
Lo(x) log |[
Ve(xr)
Σ
Elog log (V.(x)),
(6)
rEct
iEc
oE
5

---

Published in Transactions on Machine Learning Research (05/2024)
where et and cT are the sets of variables that occur in the clause c in positive and negative form respectively. Note that these two losses reach the minimum only when the prediction is a satisfying assignment, thus minimizing such losses could help to construct a possible satisfying assignment.
Inference algorithms. Beyond the standard readout process like training, G4SATBench offers two alter- native inference algorithms for satisfying assignment prediction (Selsam et al. 2019 Amizadeh et al. 2019b). The first method performs 2-clustering on the literal embeddings to obtain two centers A and A₂ and then partitions the positive and negative literals of each variable into distinct groups based on the predicate | -111 + I1 A2ll² < ||=; A2ll +
A1ll2 (Selsam et al. 2019 This allows the construction of two possible assiguments by mapping one group of literals to true. The second approach is to employ the readout function at each iteration of message passing, resulting in multiple assignment predictions for a given instance [Amizadeh et al. 2019bb.
Evaluation metrics. For satisfiability prediction and unsal-core variable prediction, we report the classi- fication accuracy of each GNN model in G4SATBench. For satisfying assignment prediction, we report the solving accuracy of the predicted assignments. If multiple assignments are predicted for SAT instance, the instance is considered solved if any of the predictions satisfy the formula.
5 Benchmarking Evaluation G4SATBench
In this section, present the benchmarking results of G4SATBench. To ensure a fair comparison, conduct grid search to tune the hyperparameters of each GNN baseline. The best checkpoint for each GNN model is selected based on its performance on the validation set. To mitigate the impact of randomness, we use 3 different random seeds to repeat the experiment in each setting and report the average performance. Each experiment performed on a single RTXS000 GPU and 16 AMD EPYC 7502 CPU cores, and the total time cost approximately 8,000 GPU hours. For detailed experimental setup and hyperparameters, please refer to Appendix C.1.
5.1 Satisfiability Prediction
Evaluation on the same distribution. Table shows the benchmarking results of each GNN baseline when trained and evaluated on datasets possessing identical distributions. All GNN models exhibit strong performance across most easy and medium datasets, except for the medium SR dataset. This difficulty can be attributed to the inherent characteristic of this dataset, which includes satisfiable and unsatisfiable pairs of medium-sized instances distinguished by just single differing literal. Such a subtle difference presents a substantial challenge for GNN models in satisfiability classification. Among all GNN models, the different graph constructions do not seem to have a significant impact on the results, and NeuroSAT (on LCG*) and GGNN (on VCG*) achieve the best overall performance.
Table 1: Classification accuracy of satisfiability on identical distribution.
Graph
Method
Easy Datasets
Medium Datasets
A-Clique
L-Dontet
J-Vercuv
PS
k-Clique
A-Domset
(-Vercov
NeuroSAT
96.00
96.33
98.88
56.20
97.99
99.77
90.99
78.02
84.90
99.55
96.81
89.39
99.67
99.90
LOG*
GCN
94.43
94.47
98.79
97.53
08.24
00.50
99.98
60.30
82.67
09.53
96.16
85.72
98.16
00.74
GIN
96.78
95.37
98.14
96.98
07.60
99.71
99.97
70.54
82.80
90:49
95.90
83.87
09.61
00.62
GCN
90.19
97.82
95.75
98.72
99.99
06:35
$3.75
95.08
$2.99
99.89
96.25
98.77
96.44
50.98
77.12
85.11
99.57
96.48
83.63
GIN
96.04
95.71
08.47
96.99
97.33
99.50
59.98
73.56
85.26
59.89
96.65
89.41
09.38
99.90
Evaluation across differentt distributions. To assess the generalization ability of GNN models, we evaluate the performance of NeuroSAT (on LCG*) and GGNN (on VCG*) across different datasets and difficulty levels. As shown Figure and Figure NeuroSAT and GGNN struggle to generalize effectively datasets distinct from their training data in most cases. However, when trained on the SR dataset, they exhibit. better generalization performance across different datasets. Furthermore, while both GNN models

---

Published in Transactions on Machine Learning Research (05/2024)
demonstrate limited generalization to larger formulas beyond their training data, they perform relatively better on smaller instances. These observations suggest that the generalization performance of GNN models for satisfiability prediction is influenced by the distinct nature and complexity of its training data. Training on more challenging instances could potentially enhance their generalization ability.
61:34
(6667
$4.55
50.10
3547
00.89
06.0
50.03
65:75
50.30
53.00
3-5AT
51.35
20
56.00
366
52.33
56.3
$0.30
45.44
$2.04
2-547
5661
05.78
51.00
51
52:46
$0.0
56.32
46.93
47.38
50.30
53.30
$2.00
50
50
56.00
5o
56.15
5001
16:35
6604
52.00
01.00
50.00
59.33
06.42
02.33
56.32
20.52
50.00
31.00
P5
52.02
02:00
20.00
0340
50.32
13.23
56.32
50.30
5000
37.00
50.02
22
21.00
50.00
A-llau 50.65
56.36
49.23
56.02
$133
$2.00
$1.00
42.10
50.00
71.18
50.36
46.22
$290
16.38
5000
Aclquu
$2.00
50.00
4122
72.60
50.00
k.Donsee 50.1
50:00
55.33
20.14
D.Desss
52.02
55.00
30:33
57
56.79
6.20m601
48:32
50.00
4002
15.72
12.02
3003
35.02
38.00
0050
51.00
20:3
A-Vorcy 50.60 46.33
13.80
50.02
53.57
$4.0
AMMrayy
$2.00
32.00
06:36
50.30
50.00
4982 50.00
52.3
5001 $2.03 52.00 50.72 42.77
20.99
00.52
NeuroSAT on easy datasets
NeuroSAT on medium datasets
GGNN on easy datasets
GGNN on medium datasets
Figure 3: Classification accuracy of satisfiability across different datasets. The x-axis denotes testing datasets and the y-axis denotes training datasets.
easy 94.19 65.56
54.82
easy
96.16
74,98
66.08
easy 96.62
65.23
53.90
easy
96.38
80.20 76.76
medium
78.40
medium
93.27
medium
95.48
medium
94.99
85.
easy medium hard
medium hard
easy medium hard
mecium hard
NeuroSAT on the SR dataset
NeuroSAT on the 3-SAT dataset
GGNN on the SR dataset
GGNN the 3-SAT dataset
Classification accuracy of satisfiability across different difficulty levels. The x-axis denotes testing datasets and the y-axis denotes training datasets.
Figure 4:
Due to the limited space, Figure exclusively displays the performance of NeuroSAT and GGNN on the SR and 3-SAT datasets. Comprehensive results on the other five datasets, as well as the experimental results different massage passing iterations, are provided in Appendix C.2
5.2 Satisfying Assignment Prediction
Evaluation with different training losses. Table 2 presents the results of NeuroSAT (on LCG*) and GGNN (on VCG*) across three different training objectives. The results of other GNN models are listed in Table 10 in Appendix C.3 Interestingly, the unsupervised training methods outperform the supervised learning approach across the majority of datasets. We hypothesize that this is due to the presence of multiple satisfying assignments in most satisfiable instances. Supervised training tends to bias GNN models towards learning a specific satisfying solution, thereby neglecting the exploration of other feasible ones. This bias may compromise the models' ability to generalize effectively. Such limitations become increasingly apparent when the space of satisfying solutions is much larger, as scen the medium CA and PS datascts. Additionally, the loss function can result. in instability during the training of
it is noteworthy that employing UNS, some GNN models, leading to failure to converge in some cases. Conversely, using UNS, loss demonstrates strong and stable performance across all datascts.
In addition to evaluating the performance of GNN models under various training loss functions, we exlend our analysis to explore how these models perform across different data distributions and under various inference algorithms. Furthermore, we assess the robustness of these GNN models when trained on noisy datasets that inchude unsatisfiable instances in an unsupervised fashion. For detailed results of these evaluations across different GNN baselines, please refer to Appendix C.3

---

Published in Transactions on Machine Learning Research (05/2024)
Table 2: Solving accuracy on identical distribution with different training losses. SUP denotes the super- vised loss, UNS, and U correspond the unsupervised losses defined in Equation S and Equation [ respectively. The symbol 5_" indicates that some seeds failed during training. Note that only satisfiable instances are evaluated in this experiment.
Graph
Method
Easy Datasets
Medium Datasets
C-Clique
k-Domset
V-Vercov
3-SAT
K-CBque
>-Domset
SUP
88.47
78.
0.27
39:18
66.30
68.01
85.16
34.97
20.07
0.00
3.64
52.08
74.77
LOG'
NeuroSAT
UNS;
82.30
90.21
52.17
89.23
68.34
96.74
00.36
25.00
30.30
35.45
60.28
41.45
96.06
67.41
UNS
70.79
80.59
89.34
58.70
63.45
98.85
90.73
37.25
41.61
70.83
71.03
96.18
95.90
72.57
$8.62
7.06
2.55
VOG
GGNN
UNS;
76.30
70.65
78.13
$1.44
84.60
97.40
16.55
44.89
66.37
UNS
78.75
76.42
$4.08
86.29
87.12
98.06
99:34
21:18
25.68
50.66
$7.06
68.91
92.26
94.30
5.3 Unsat-core Variable Prediction
Evaluation on the same distribution. The benchmarking results presented in Table 3 exhibit the superior performance all GNN models on both easy and medium datasets, with NeuroSAT consistently achieving the best results across most datasets. It is important note that the primary objective of predicting unsat-core variables not to solve SAT problems directly but to provide valuable guidance for enhancing the backtracking search process. As such, even imperfect predictions for instance, those with classification accuracy of 90% have been demonstrated to be sufficiently effective in improving the search heuristics employed by modern CDCL-based SAT solvers, as indicated by previous studies (Selsam & Bjørner
2019
Wang et al. 2021
Table 3: Classification accuracy of unsat-core variables on identical distribution. Only unsatisfiable instances are evaluated.
Graph
Easy Datasets
Mediuu
SR
3-SAT
CA
PS
J-Clique
L-Domset
V-Vereov
SR
3-SAT'
CA
PS
X-Cllquue
J-Domset
(- L-Vercov
NeurSAT
90.76
91.43
83.69
86.20
99.93
95.80
94.47
90.07
99.65
85.75
88.53
99.97
97.90
99.10
LOG'
GCN
82.89
GGNN
90.02
94.38
63.59
66.03
99.93
95.79
91.46
89.05
00.65
85.69
87.95
98.96
07.88
99.00
GIN
89:29
94.33
60.71
85.97
94.47
88.85
99.65
85.71
87.92
99.96
97.80
99.09
GUN
88.67
94.34
83.17
65.27
00.05
95.79
88.
00.65
70
87.37
99.96
97.90
VOG
GGNN
89.57
94.37
83,50
85.84
99.93
95,81
94.49
$8.81
99.65
85 85.68
88.03
99.98
97.90
99.10
91.47
89.51
88.13
We also conduct experiments to evaluate the generalization ability of GNN models on unsal-core variable prediction. Please see appendix C.4 for details.
6 Advancing Evaluation on G4SATBench
To gain deeper insights into how GNNs tackle the SAT problem, we conduct comprehensive comparative analyses between GNN-based SAT solvers and the CDCL and LS heuristies in this section. Since these search heuristics aim to solve a SAT instance directly, our focus only lies on the tasks of (T1) satisfiability prediction and (T2) satisfying assignment prediction (with UNS₂ as the training loss). We employ NeuroSAT (on LCG*) and GGNN (on VCG*) as our GNN models and experiment on the SR and 3-SAT datasets. Detailed experimental settings are included in Appendix D.1
6.1 Comparison with the CDCL Heuristic
Evaluation on the clauso-learning augmented instances. CDCL-based SAT solvers enhance back- tracking search with conflict analysis and clause learning, enabling efficient exploration of the search space by iteratively adding "learned clauses" to avoid similar conflicts in future searches (Sivaa & Sakallah 1999). To assoss whether GNN-basod SAT solvers can learn and benefit from the backtracking search (with CDCL) heuristic, we augment the original formulas in the datasets with learned clauses and evaluate GNN models these clause-augmented instances.
8

---

Published in Transactions on Machine Learning Research (05/2024)
Table 4 shows the testing results on augmented SAT datasets. Notably, training on the augmented instances leads to significant improvements in both satisfiability prediction and satislying assignment, prediction. These improvements can be attributed to the presence of "learned clauses" that effectively modify the structure of the original formulas, thereby facilitating GNNs to solve with relative case. However, despite the augmented instances being easily solvable using the backtracking search within a few search steps, GNN models fail to effectively handle these instances when trained on the original instances. These findings suggest that GNNs may not implicitly learn the CDCL heuristic when trained for satisfiability prediction or satisfying assignment prediction.
Table 4: Results on augmented datasets. Values in- side side/outsen outside parentheses denote the results of models trained on augmented/ / instances.
Table 5: Results using contrastive pretraining. Val- ues in parenthescs denote the difference between the results without pretraining.
Task Method
Easy Datawets
Mediam Datawets
Task
Method
Easy Datasets
Medium Datasnts
SR
3-SAT
SR
3-SAT
3-SAT
T1
GGNN
NemoSAT
100.00 (97.96)
100.00 (36.7%
100.00 (96.46)
100.00 (96.00
100.00 (84.01)
100.00 (84.57)
96.29 (85.80)
96.78 (S1.85)
T1
GGNN
NearoAAT
96368 (+0.68)
96.46 (-0.29)
96.45 (40.20)
96.28 (-1.10)
78.31 (+0.29
76.34 (-0.78)
85.17 (40.05
85.02 (+0.12)
12
NemoSAT
GGNN
85.35 (83.42)
06 (83.28)
81.56 (79.90)
83.00 (81.04)
44.18 (40.00)
51.96 (46.01)
54.67 (14.75)
39.00 (36.62)
T2
GGNN
NeuröAT
80.54 (+0.75)
80.66 (-0.34)
70.23 (-0.00)
79.71 (-0.88)
53.44 (+0.77)
36,42 (-0.83)
36.39 (+0.4)
41.23 (-0.38)
Evaluation with contrastive pretraining. Observing that GNN models exhibit superior performance on clauso-learning augmented SAT instances, there is potential to improve the performance of GNNs by
learning a latent, representation of the original formula similar to its augmented counterpart. Motivated by this, we also experiment with a contrastive learning approach (i.e., SimCLR (Chen et al. 2020 to
pretrain the representation of CNF formulas to be close to their augmented ones (Duan et al. 2022 trying to explicitly embed the CDCL heuristic in the latent space through representation learning.
The results of contrastive pretraining are presented in Table 5 In contrast to the findings in Duan et al. (0022), our results show limited performance improvement through contrastive pretraining, indicating that GNN models still encounter difficulties in effectively learning the CDCL heuristic in the latent space. This observation aligns with the conclusions drawn in Chen & Yang (2019), which highlight that static GNNs may fail to exactly replicate the same scarch operations due to the dynamic changes in the graph structure introduced by the clause learning technique.
6.2 Comparison with the LS Heuristic
Evaluation with random initialization. T.S-based SAT solvers typically begin by randomly initializing an assignment and then iteratively flip variables guided by specific heuristics until reaching satisfying assignment. To compare the behaviors of GNNs with this solving procedure, first conduct an evaluation of GNN models with randomized initial embeddings in both training and lesting, emulating the initialization of LS SAT solvers.
The results presented in Table 6 demonstrate that us- ing random initialization has a limited impact on the overall performances of GNN-basod SAT solvers. This suggests that GNN models do not aim to learn a fixed latent representation of each formula for satisfiability prediction and satisfying assignment prediction. In- stead, they have developed solving strategy that ef- fectively exploits the inherent graph structure of each SAT instance.
Table 6: Results using random initialization. Values in parentheses denote the difference between the re- sults with learned initialization.
Easy Datasets
Medium Datasets
Taok
Method
3-SAT
3-SAT
NeuuSAT
87.24 (+1:24)
06:44 (#0.11)
77.28 (-0.9))
84.85 (-005)
11
GGNN
96.78 (+0.00)
06.58
(40.13)
76.97 (.015)
$5,80 (+0.89)
T2
GGNN
NemuSAAT
79.00 (41.70)
80.10 (-0.90)
80.77
70.83
(40200)
(4051)
87
39.85 (-0.2)
(4002)
36.59 (+0.64)
40.75 (-088)
Evaluation on the predicted assignments. Under random initialization, we further analyze the solving strategics of GNNs by evaluating their predicted assignments decodod from the latent space. For the task of satisfiability prediction, we employ the 2-clustering decoding algorithm extract the predicted assignments from the literal embeddings of NeuroSAT at each iteration of message passing. For satisfying assignment
9

---

Published in Transactions on Machine Learning Research (05/2024)
prediction, evaluate both NeuroSAT and GGNN using multiple-prediction decoding. Our evaluation focuses on three key aspects: (a) the number of distinct predicted assignments, (b) the number of flipped variables between two consecutive iterations, and (c) the number of unsatisfiable clauses associated with the predicted assignments.
175
NeursAK
Nounsal
NeurosAl
CCNN
Num of unsattisiaaae iabbllttiiiiieeeeeeeaa clauses
GGAN
Number distnet aesigeaaiigmene
130
Neurosat>
Meuredam
cup datset
eacy dabrett
evry desser
shop
casy datesei
eay 3-5Al desradt
of flippd
med
20
25
90
100
120
60
00
103
120
20
60
100
120
Message passing Iteration T
Message passing Reration
Message passing Itoration
(a) # #Distinct assignments
(b) # #'lipped variables
(c) # Unsatisfible clauses
Figure 5: Results on the predicted assignments with the increased message passing iteration T. NeuroSAT* refers to the model trained for satisfiability prediction.
As shown in Figure 5 all three GNN models initially generate a wide array of assignment predictions by flipping considerable number of variables, resulting in a notable reduction in the number of unsatisfiable clauses. However, as the iterations progress, the number of flipped variables diminishes substantially, and most GNN models eventually converge towards predicting a specific assignment or making minimal changes to their predictions when there are very few unsatisfiable clauses remaining. This trend is reminiscent of the greedy solving strategy adopted by the LS solver GSAT (Selman et al. 1992) where changes are made to minimize the number of unsatisfied clauses in the new assignment. However, unlike GSAT's approach of flipping one variable at a time and incorporating random selection to break tics, GNN models simulta- neously modify multiple variables and potentially converge to particular unsatisfied assigument and find it challenging to deviate from such a prediction. It is also noteworthy that despite being trained for satis- fiability prediction, NcuroSAT* demonstrates similar behavior to the GNN models trained for assignment prediction. This observation indicates that GNNs also learn to search for satisfying assigument implicitly in the latent space while performing satisfiability prediction. To provide more insights into the strengths and limitations of GNN-based heuristics, we further conduct experiments to compare GNN-based SAT solvers against statc-of- tht-rrr-ttt-ttttt CDCL and LS-based SAT solvers in Appendix D.2
7 Discussions
7.1
Limitations and Future Work
While G4SATBench represents significant step in evaluating GNNs for SAT solving, there are still some limitations and potential future directions to consider. Firstly, G4SATBench primarily focuses on evaluating standalone neural SAT solvers, excluding the exploration of neural-guided SAT solvers that integrate GNNs with search-based SAT solvers. It also should be emphasized that the instances included in G4SATBench are considerably smaller compared to most practical instances found in real-world applications, where GNN models alone are not sufficient for solving such large-scale instances. The efficacy of GNN models in unsat- core prediction shows a promising avenue for combining GNNs with modern SAT solvers, and future research could explore more techniques to effectively leverage these neural-guider SAT solvers to scale up to real- world instances. Secondly, G4SATBench benchmarks general GNN models the LCG* and VCG* graph representations for SAT solving, but does not consider sophisticated GNN models designed for specific graph constructions in certain domains, such as Circuit SAT problems. Investigating domain-specific GNN models tailored to the characteristics of specific problems could lead to improved performance in specialized instances. Lastly, all existing GNN-based SAT solvers in the literature are static GNNs, which have limited learning ability to capture the CDCL heuristic. Exploring dynamic GNN models that can effectively learn the CDCL heuristic is also potential direction for future research.
10

---

Published in Transactions on Machine Learning Research (05/2024)
7.2 Conclusion
In this work, we present G4SATBench, benchmark study that comprehensively evaluates GNN models in SAT solving, G4SATBench offers curated synthetic SAT datasets sourced from various domains and difficulty levels and benchmarks wide range of GNN-based SAT solvers under diverse settings. Our empirical analysis yields valuable insights into the performances of GNN-based SAT solvers and further provides a deeper understanding of their capabilities and limitations. We hope the proposed G4SATBench will serve as a solid foundation for GNN-based SAT solving and inspire future research in this exciting field.
Acknowledgments
This work was supported, in part, by Individual Discovery Grants from the Natural Sciences and Engineering Research Council of Canada, and the Canada CIFAR Al Chair Program.
References
Saeed Amizadeh, Sergiy Matusevych, and Markus Weimer, Learning to solve Circuit-SAT: An unsupervised differentiable approach. In International Conference on Learning Representations (ICLR), 2019a.
Saced Amizadeh, Sergiy Matusevych, and Markus Weimer. PDP: A general neural framework for learning constraint satisfaction solvers. arXiv preprinl ar Xiv: Nki:1100. 100300166, 2019b.
Jimuny Lei Ba, Jamie Ryan Kiros, and GeofTrey 16070060 2016.
Hinton.
Layer normalization. arv preprinl
Adrian Balint and Andreas Fröhlich. Improving stochastic local search for sat with new probability dis- tribution. In Theory and Applications of Satisfiability Testing SAT 2010: 13th International Conference, SAT 2010, Edinburgh, UK, July 11-14, 2010. Proceedings 18, pp. 10-15. Springer, 2010.
Armin Bicre, Marijn Heule, and Hans Maaren. Handbook of Satisfiability, volume 185. IOS press, 2009.
Béla Bollobás and Paul Erdös. Cliques in random graphs. In Mathematical Proceedings of the Cambridge Philosophical Sociely, 1976.
Benedikt Bünz and Matthew Lamm. Graph neural networks and boolean satisfiability. ar preprint arXiv:1702. 03599, 2017.
Chris Cameron, Rex Chen, Jason Hartford, and Kevin Leyton-Brown. Predicting propositional satisfiability via end-to-end learning. Tn AAAT Conference on Artificial Intelligence (AAAT), 2020.
Ting Chen, Simon Kornblith, Mohammad Norouzi, and Geoffrey F. Hinton. simple framework for con- trastive learning of visual reprosentations. In International Conference on Machine Learning (ICML), 2020.
Ziliang Chen and Zhanfu Yang. Graph neural reasoning may fail in certifying boolean unsatisfiability. arXiv preprint Xr::::1999. 1188, 2019.
James M. Crawford and Larry D. Auton. Experimental results on the crossover point in random 3-SAT, Artificial Intelligence, 1996.
Haonan Duan, Pashootan Vaezipoor, Max B. Paulus, Yangjun Ruan, and Chris J. Maddison. Augment with care: Contrastive learning for combinatorial problems. In International Conference on Machine Learning (ICML), 2022.
Matthias Fey and Jan Eric Lenssen. Fast graph representation learning with pytorch geometric. ar preprint arXio:1903.00/22 2019.
ABKFM Fleury and Maximilian Heisinger. Cadical, kissat, paracooba, plingeling and treengeling entering the sat competition 2020. SAT COMPETITION, 2020.
11

---

Published in Transactions on Machine Learning Research (05/2024)
Jesús Giráldez-Cri Cru and Jordi Levy. A modularity- random SAT instances generator. In International Joint. Conference on Arlificial Intelligence (IJCAT), 2015.
Jesús Giräldez-Cru and Jordi Levy. Locality in random SAT instances. In International Joinl Conference on Artificial Intelligence (IJCAI), 2017.
Wenxuan Guo, Junchi Yan, Hui- Luii Zhen, Xijun Li, Mingxuan Yuan, and Yaohui Jin. Machine learning methods in solving the boolean satisfiability problem. arXiv preprint arXi::2303.04755 2022.
Jesse Michael Han. Enhancing SAT solvers with glue variable predictions. arXiv preprint orXiv:2007.02550 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Delving deep into rectifiers: Surpassing human- level performance on imagenet classification. In IEEE International Conference on Computer Vision (ICCV), 2015.
Sean B Holden et al. Machine learning for automated theorem proving: Learning to solve SAT and QSAT. Foundations and Trends@ in Machine Learning, 14(6):807-989, 2021.
Holger H Hoos and Thomas Stützle. SATLIB: An online resource for rescarch on SAT. Workshop on Sulisfabilily (SAT), 2000.
Scbastian Jaszezur, Michal Luszezyk, and Henryk Michalewski. Neural heuristies for SAT solving. arXiv preprinl ar Xiv:2000. 13406, 2020.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Confer- ence on Learning Representations (ICLR), 2015.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional networks. In International Conference on Learning Representations (ICLR), 2017.
Vitaly Kurin, Saad Godil, Shimon Whiteson, and Bryan Catanzaro. Can q-learning with graph networks
learn a generalizable branching heuristic for a SAT solver? In Advances in Neural Information Processing Systems (NeurIPS), 2020.
Massimo Lauria, Jan Elffers, Jakob Nordström, and Mare Vinyals. Cufgen: A generator of crafted bench- marks. In Theory and Applications of Satisfiability Testing (SAT), 2017.
Min Li, Zhengyuan Shi, Qiuxia Lai, Sadaf Khan, Shaowei Cai, and Qiang Xu. On eda-driven learning for sat solving. In Design Automation Conference (DAC), 2023.
Yujia Li, Danicl Tarlow, Mare Brockschmidt, and Richard S. Zemel. Gated graph sequence neural networks. In International Conference on Learning Representations (ICLR), 2016.
Zhaoyu Li and Xujie Si. NSNet: A general neural probabilistic framework for satisfiability problems. In Advances in Neural Information Processing Systems (NewrIPS), 2022.
Vinod Nair and Geoffrey E. Hinton. Rectified linear units improve restricted boltzmann machines. In International Conference on Machine Learning (ICML), 2010.
Emils Ozolins, Karlis Freivalds, Andis Draguns, Eliza Gaile, Ronalds Zakovskis, and Sergejs Kozlovics. Goal-aware neural SAT solver. In International Joinl Conference on Neural Networks (IJCNN), 2022.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, Alban Desmaison, Andreas Köpf, Edward 7. Yang, Zachary DeVito, Martin Raison, Alykhan Tejani, Sasank Chilamkurthy, Benoit Steiner, Lu Fang, Junjie Bai, and Soumith Chintala. Pytorch: An imperative style, high- high-performance deep learning library. In Advances in Newral Information Processing Systems (NewrIPS), 2019.
Bart Selman, Hector Levesque, and David G. Mitchell. A new method for solving hard satisfiability problems. In National Conference on Artificial Intelligence (AAAT), 1992.
12

---

Published in Transactions on Machine Learning Research (05/2024)
Daniel Selsam and Nikolaj S. Bjorner. Guiding high-performance SAT solvers with unsat-core predictions. In Theory and Applications of Salisfabilityy Testing (SAT), 2019.
Daniel Selsam, Matthew Lamm, Benedikt Bünz, Percy Liang, Leonardo de Moura, and David L. Dill. Learn- ing SAT solver from single-bit supervision. In International Conference Learning Representations (ICLR), 2019.
Zhengyuan Shi, Min Li, Yi Liu, Sadaf Khan, Junhua Huang, Hui-Ling Zhen, Mingxuan Yuan, and Qiang Xu. Satformer: Transformer- based unsat core learning. In International Conference on Computer Aided Design (ICCAD), 2023.
João P. Marques Silva and Karem A. Sakallah. GRASP: A search algorithm for propositional satisfiability.
IEEE Transactions on Computers, 1999.
Wenxi Wang, Yang Hu, Mohit Tiwari, Sarfraz Khurshid, Kenneth McMillan, and Risto Miikkulainen. Neu- rocomb: Improving SAT solving with graph neural networks. arXiv preprint 1XXi:2210014055. 2021.
Nathan Wetzler, Marijn Heule, and Warren A. Hunt Jr. Drat-trim: Efficient checking and trimming using expressive clausal proofs. In Theory and Applications of Satisfiability Testing (SAT), 2014.
Ben Wieland and Anant P. Godbole. On the domination number random graph. The Electronic Journal of Combinatorics, 2001.
Keyulu Xu, Weihua Hu, Jure Leskovec, and Stefanic Jegelka. How powerful are graph neural networks? In Internaiional Conference on Learning Representations (ICLR), 2019.
Zhiyuan Yan, Min Li, Zhengyuan Shi, Wenjie Zhang, Yingcong Chen, and Hongee Zhang. Addressing variable dependency in gun-based SAT solving, arXiv preprint XrX::220040088 08738, 2023.
Emre Yolcu and Barnabés Póezos. Learning local search heuristics for boolean satisfiability. In Advances in Neurul Information Processing Systems (NeurIPS), 2019.
Wenjie Zhang, Zeyu Sun, Qihao Zhu, Ge Li, Shaowei Cai, Yingfei Xiong, and Lu Zhang, Nlocalsat: Boosting local search with solution prediction. In International Joint Conference on Artificial Intelligence (IJCAT), 2020.
13

---

Published in Transactions on Machine Learning Research (05/2024)
A Datasets
Generators. To generate high-quality SAT datasets that do not contain trivial instances, we have em- ployed a rigorous process of selecting appropriate parameters for each CNF generator in G4SATBench. Table provides detailed information about the generators we have used.
Table 7: Details of the synthetic generators employed in G4SATBench.
Dataset
Description
Parameters
Notes
The SR dataset is compoeed of pains of satisfibbe and insatisfibble formudss, with the only difference between each pair being the polar- ity of single literal. Given the mumber of variables n, the syuthetic generator iteratively samples k = 1+ Berneull(()- + Geometzic g) vari- ahles mniformly random without replacement and negutes each with independent probability 50% to build clause. This procedure continues until the generated formula is unsatiafable. The satisfiable instance then coustructed by negating the first literal in the last clause of the unsatisflable one.
General: 0.3.g - 0.4,
The sumpling porsametens the sumne the orig. inal paper Selsam et al. 2019
Easy dataset: Unikorm([0 40);
Medium dataset; < Uniformi 10, 200).
Hard dataset: Uniform (200, 100)
The 3-SAT dataset comprises CNF formalas at the phase transition, where the proportion of generated satisfiable and unsatisflable formu- las is roughly equal. Given the mumber of variahles and clanses in, the syuthetic generator iteratively samples three variables (and their polarities) uniforalyy random until clanses obtained.
General: 4.258n 58.26n 2/3
The parameter m is the same as the paper Crnw. ford & Auton 1996
Easy datasot: a Uniform[10 40),
3-SAT
Medium dataset; Uniformi 10, 200).
Hard dataset: a Uniform (200, 200)
The parametens are se-
The CA dataset contains SAT instances that are designed mimic the community structures and modularity features found in real-world
General: in ~. Unilorm([Srr 1551)
lected based on the exper- iments in the original pa- per Gireldez- & Levy 2015 and our study to ensure that the generated
Uniformi4,
industrial instances. Given variable number n, clause number m,
e Uniffrm(33 10).
clause sine k. communiiy number e, and modularity Q. the syuthetie
CA
generator iteratively selects k literals in the same community uni-
Q Unfform(0.77 0.9)
Easy dataset: (1ilorm 10),
formly at random with probshility P P-0 Q 1/fe seleets literals
in the distinet community uniformly at random with probebiity 1- P to build a clause and repear for m times to construct a CNP formula.
Medium datasot: a ~ Uniform( 400 200).
SAT instances have a bal- ance sutisfiability and
Hard datuset: a Uniform (200, 400)
unsaticfubilitt.
PS dataset eacompases SAT instances with power-luw distribution good clus-
the number of variable occureecces (popularity), tering between them (similarity). Given variable number clause mumber m. and average clause size R the synthetic generator first as- signs random angles 8, [0, 2x] to each variable and each clause J. and then randomly samples variable i in clanse j with the proba-
General: in Uniform(Gr, 8n),
The perameters are
k~ Uniform(4,55
lected based on the exper- iments in the original pa-
0 Uniform(O.))
8'
per GGrsäldez.Cr & Levy 2017 and our study to that the generated
PS
bility P= 1/(1- - ( R)/R)"; Here, fy = x - |st - 10. - Byll angle between variable and clause j. The expeuent panumeters and S control the power-llw distribation of variable oecurrences and clanse size respocsively. The temperature parameter T' controls sharpuess of the probability distribution, while Rt approximate normalization ccastann that ensures the average mumber of selected edges kn..
e~ Uniform(3, 10),
T Uniform(0.75, 1.5)
Easy datasot: a Uniform (10, 40),
SAT instances have a bal- ance satisfabillity and unstiisiabiiitty
Medium datasot: a- Uniformn 200),
Hard dataset: n~ Uniform (200, 300)
The A-Clique dataset includes SAT instances that encode the k-Clique problem, which involves desermining whether there existt clique (le, a subset of vertices that are all adjacmnt to each other) with o vertices in a given graph. Given number of cliques generator produces an Erdie-Réuyi Réuyi graph with vertices and a given edge probubility and then transforms the corresoondngg k-Clique problem into SAT instance.
General: (v) (0/1/3
The parameter P bosed
Easy datasot: 8 ~ Uniform(5, 15),
selected
the (Rollobis &
<- Uniform(3.4)
paper Erdid
A-Clique
syuthotic
Medium dataset; - Uniformm(15 20),
1976 making
3niforma3,5) 5).
the expected mumber of
Hard dataset; e Uni 25),
& C-Cliques in the generated graph equals
k ~ Uniformí1,6) 6)
The D-Domttt dataset contains SAT instanoes that encode A- Dominating Set problem. This problem determine whether there exists a dominating set (Le,, a subsot of vert such that every vertex gmah either in the subset or adjucent to a vertex in the sub- sos) with at most è vertires in a given graph. Given the domination ramber k the synthetic geserator produces an Erdös= with v vertices and given edge probability p and then transforms the vorresponddngg & t-Deminating Set peoblem into SAT instancr.
General: p= 1- 10 (2) 4/ 3/k
The parameter p is se- based on the pa- Wiellnd Godbole 2001 making the ex- pected number domina-
Easy dataset: Uniiform(S 15).
k Uniform(2.3)
A-Domset
Medium datasot:: e Uniformi 15, 20).
graph
Uniform(3,5)
Hard datasnt: a Uniform(20 25),
tion set with size & in the generated graph equals 1.
Uniform(4, 6)
The generation process aud the parameter are lested based on the rela- tionsbip between V-Vertex Cover and K-Clique prob- lems, making the size of mitimum vertex in the generated graph around A.
The i- Vercov datases consista of SAT instances that encode the k- Vertex Cover problem, in., chock whether there exists set of & ver- tiore in a graph such that every edge has least, one endpoint in this set. Given the verter duoes a complemaeut gnaph of an Redii gmph with vertãoes and given edge probubility p and then converts the corresponding & Vertex Cover problem into SAT instance.
General: p= (0) -VG)
Easy datasot: Uniformm(, 15), & F~ Uniform(3.
A- V-Vero
mumber &. the synthetic generator pro-
Medium datasot: > Uniform([0 20), k Uniform16,8)
Hard dataset; - Uniform(15, 25), n Uniform(9,10))
14

---

Published in Transactions on Machine Learning Research (05/2024)
Statistics. To provide comprehensive understanding of our generated datasets, compute several characteristics across three difficulty levels. These statistios include the average number of variables and clauses, as well as graph measures such as average clustering coefficient (in VIG) and modularity (in VIG, VCG, and LCG). The dataset statistics are summarized in Table
Table 8: Dataset statistics across difficulty levels in G4SATBench.
Perrect
B GNN Models
Message-passing schemes on VCG*. Recall that VCG* incorporates two distinct edge types, G4SATBench employs different functions to execute heterogeneous message-passing in each direction of each edge type. Formally, we define a d-dimensional embedding for each variable and clause node, denoted by hy and he, respectively. These embeddings are initialized to two Icarnable vectors hς and No, depending on the node type. At the k-th iteration of message passing, these hidden representations are updated follows:
h(4) UPD
([MLPt (n) AGG ((NLP; (n!+-1))3) h((-1)) AGG
vEct
wEc
(7)
h00 UPD
AGG cENt
(MIP.. (n!- })
AGG CEP
((MIP) (no- ((
where et and ct denote the sets of variable nodes that occur in the clause e with positive and negative polarity, respectively. Similarly, o+ and e- denote the sets of clause nodes where variable occurs in positive and negative form. MLP MLP,, MLP* and MLP. are four MLPs. UPD(-) is the update function, and AGG(.) is the aggregation function.
GNN basclines. Table g summarizes the messago- messago-passing passing algorithms of the GNN models used in G4SATBench. We adopt heterogeneous versions of GCN (Kipf & Welling, 2017), GGNN (Li et al. 2016). and GIN Xu ct al., 2019) on both LCG* and VCG*, while maintaining the original NeuroSAT (eelsa
et al. 2019 only on LCG
C Benchmarking Evaluation
C.1 Implementation Details
In G4SATBench, we provide the ground truth of satisfiability and satislying assignments by calling the state- of-the-art modern SAT solver CaDiCaL (Fleury & Heisinger 2020) and generate the truth labels for unsat-
core variables by invoking the proof checker DRAT-trim [Wetzler et al. 2014h. All neural networks in our
study are implemented using PyToorch (Paszke et al. 2019 and PyTorch Geometric (Fey & Lenssen 2019
For all GNN models, we set the feature dimension d 128 and the number of message passing iterations T to 32. The MLPs in the models consist of two hidden layers with the ReLU (Nair & Hinton 2010) activation function. To select the optimal hyperparameters for each GNN baseline, we conduct grid search over several settings. Specifically, training epochs from (50, 100, 200), weight decay values from {10-6 10-7, 10.8 --0-- 10-
explore different learning rates from {10-3, x 10 10-4. 4.5 10-5 10-5,10-5) 10-05,, 5),
1100-.10-100001111111111011 10-10), and gradient clipping norms from 10.1, 0.5, 1}. We employ Adam (Kingma & Ba 2015 as the optimizer and set the batch size to 128, 64, or 32 to fit within the maximum GPU memory (48G). For the parameters 7 and x of the unsupervised loss in Equation 4 and Equation 5 we try the default scttings (r= t-04 and к 10, where is the global step during training) as the original paper (Amizadeh et al. 2019a) as well as other values (r E (0.05, 0.1, 0.5), & E (1,2,5) and empirically find 0.1, K = yield the best results. Furthermore,
15

---

Published in Transactions on Machine Learning Research (05/2024)
Table 9: Supported GNN models in G4SATBench.
Graph Method
Message-passee Algorithm
Notes
LayerNormLSTM,
MLP: (4 (44-1)) (n( (.6t-1)))
NTT
NEMO
Res dj are the hidden states which are initialized vectors. de di ure the degrees of clause mode and Nitoral in L.G respcctivlly
N :4
Nore-NoMM..SMMM
MIP.P (a! ").a% 00(00 9. 1)
MLP. (4f-1)) 1
Lineary
Σ
GCN
(eM(cs)
Vaia.
6/49 Tanrarg
MLP. (MPP
LOG**
ct.(1))
Vidah
6 GRU,
((MLP) (Ni* ")}}) 110
GGNN
(EN())
A/ GRU,
Σ MLPa
(n!f-"1) 13--11 11 11
619 MLP,
((MLR) (aff (n)+-))) 11
GIN
4/4 MLP
Σ MLP,
(A 1i 11---1
R1 Linear;
(M0-1)
A
Visad
der dy are the degross of clanse node e and sariable VCG respertivdy.
GCN
14 Lineara
Σ (1)
(1f--1)
A GRU,
Σ MLP (M
Σ MLP, (M
VOG
GGNN
R GRU2
Σ MLP! (NL 11-
Σ MLP? 1)
MLP! (1))
Σ MLP. (1.--1)) )
MLP
GIN
MLP
Σ MLP (M
Σ MLP
(o!- (0-1)
it is important to note that we use three different random seeds to benchmark the performance of different GNN models and assess the generalization ability of NeuroSAT and GGNN using one seed for simplicity.
C.2 Satiafiability Prediction
Evaluation across different difficulty levels. The complete results of NeuroSAT and GGNN across different difficulty levels are presented in Figure C Consistent with the findings on the SR and 3-SAT datasets, both GNN models exhibit limited generalization ability to larger instances beyond their training data, while displaying relatively better performance smaller instances. This observation suggests that training these models on more challenging instances could potentially enhance their generalization ability and improve their performance on larger instances.
$2.19
$482
96.11 16
$4.00
331 EC
31.11
51
99.74
64.74
5020
$9.99
55
50:33
35.20
12.40
52:1
redim
$3.27
04.67
$3.00
redium
$6.17
50.00
230
17.04
mstam 72.36
59.67
65.40
60:37
2333
56.32
1000
1008T7
320
720
1000
Hearder the oninet
MaurOAA an the 3-54 cruset
RRa- an the CA siasee
HeaedAT ce the Miieet
TourSSAT on the :iroe Staat Rour USAT on the Domoot diteet
Neerdoo the k-/ert siase:
099
091
medum
11:46
17.70
4160
redim
$1.00
61.24
$3.00
reciun
86.17
302.0
nadur
26.22
63.28
12.62
12
madim
$5.10
V132
16
redlan
$0.22
Figure 6: Classification accuracy of satisfiability across different difficulty levels. The x-axis denotes testing datasets and the y-axis denotes training datasets.
16

---

Published in Transactions on Machine Learning Research (05/2024)
Evaluation with different message passing iterations. To investigate the impact of musssag-passiing iterations on the performance of GNN models during training and testing, we conducted experiments with varying iteration values. Figure 0 presents the results of NeuroSAT and GGNN trained and evaluated with different message passing iterations. Remarkably, using a training iteration value of 32 consistently yielded the best performance for both models. Conversely, employing loo small or too large iteralion values during training resulted in decreased performance. Furthermore, the models trained with 32 iterations also demonstrated good generalization ability to testing iterations 16 and 64. These findings emphasize the critical importance of selecting appropriate meessage-assingg iteration to ensure optimal learning and reasoning within GNN models.
61:23
12.34
01:2
1E.3
11.27
$3.21
19.23
1442
12:4
17:00
12:1
10.0
74.01
34-23
10.00
13.33
27:21
X6:11
18.22
11:00
2012
30.4
22:00
C1.0
11.25
13:09
13-12
19.00
12:30
30.1
10.00
1228
11:00
7942
1921
7730
11.08
$1.15
PLL3
15.13
19:11
2012
0L-11
10.00
2012
12:2
10
90.0
3001
11.01
14.10
50.04
1778
1237
1941
RCW
10.0
M121
10
80.11
14
0.50
14.0
1114
11:00
57.0
14:1
51.00
60.0
10.15
00.1
milect
Figure 7: Classification accuracy of salisfiability across different message passing iterations T. The x-axis denotes testing iterations and the y-axis denotes training iterations.
C.3 Satisfying Assignment Prediction
Evaluation with different training losses. Table I0 presents the complete results of each GNN baseline across three different training objectives. Like the results of NeuroSAT and GGNN, all other GNN models with unsupervised training oulperform their supervised training counterparts.
Solving accuracy on identical distribution with different training losses. The top and bottom 7 rows represent the results for easy and medium datasets, respectively. SUP denotes the supervised loss, UNS; and U correspond to the unsupervised losses defined in Equation 5 and Equation D respectively. The symbol *_" indicates that some seeds failed during training. Note that only satisfiable instances are evaluated this experiment.
Table 10:
Graph
Method
Si
3-SAT
CAA
PS
I-Clligan
b- Donment
b- Viereaee
SUP
UNS
LNS
SUP
UNSS
UNS
SUP
UNSS
UNS
SUP
UNS
UNS
SUP
UNS
UNS
SUP
UNS,
UNS
SUP
UNS
UNS
NeurSAll
68:47
50.00
75.70
78.30
50.23
80.20
0.57
52.17
50.34
21.15
89.23
85,73
10:30
58.34
63.42
(2.61
56.24
96.86
85.15
10:35
09.78
100*
GCDN
OUN
84.15
63.74
T3.05
19.21
18.15
77.00
12.53
70.34
19.35
76.79
71.31
16:42
0.29
0.17
18.13
75.30
84.06
25.41
35.86
50.75
56.29
81.50
01.85
00.80
$0.00
$2.00
87.12
81:17
68.36
09.20
$1.29
15.50
98.06
97.55
70.33
19.10
99.54
19. 25
CIN
83.51
51.45
80.50
73.39
76.34
0.20
78.44
85.15
85.43
$0.85
$6.45
85.11
08.35
97.45
99.58
83:36
43.51
VOG
GCNX
GIN
NemnSWT
LOG*
GCNN
GIN
GCN
20.50
0.21
22.44
12.45
17.00
26.58
0.44
20.14
45.59
2.29
55.99
55.46
69.09
25.99
05.62
05.96
92.58
09.15
96.46
VDG*
OCXX
28.04
02
33.57
16.46
20.65
35.56
0.50
48.13
43.00
3.12
51.78
65.11
64.26
60.92
56.48
61.01
71.97
05.55
CIN
26.75
26.48
33.97
14.84
20.85
35.51
0.64
45.05
03.54
3.88
78.00
64.66
03.47
20.97
67.75
05.95
05.28
00.40
06.00
Evaluation across different difficulty levels. The performance of NeuroSAT across different difficulty levels is shown in Figure [] Notably, training on medium datasets yields superior generalization performance compared to training on easy datasets. This suggests that training more challenging SAT instances with larger sizes can enhance the model's ability to generalize to wider range of problem complexities.
13.08
20.50
2:25
$7.00
35.22
2.25
BOL35
25
32
33.57
13:25
$3.06
63.72
50.21
25
3.00
$1.00
21.25
5.9
$2.52
4L4i
1126
$5.12
32.55
24.28
12 02
47
65.55
22.58
1468
$6.00
94.2
96.12
SALSS
21.22
1110
NeutrMaT in the 1:577 arroot
Ni avRo MlASss
TINEVAAT an the clige Saaut
Nearroot the Sevees AMAA
Figure 8: Solving accuracy of NeuroSAT across different difficulty levels (with UNS₂ as the training loss). The x-axis denotes testing datasets and the y-axis denotes training datasots.
17

---

Published in Transactions on Machine Learning Research (05/2024)
Evaluation with different datasets. Figure 9 il- lustrates the performance of NeuroSAT across differ- ent datasets. For easy datasets, we observe that Neu- roSAT demonstrates a strong gencralization ability to other datasets when trained on the SR, 3-SAT, CA, and PS datasots. However, when trained on the k- Clique, k-Domset, and V-Vereov datasets, which in- volve specific graph structures inherent to their com- binatorial problems, NeuroSAT struggles to generalize effectively. This observation indicates that the GNN model may overfit. to leverage specific graph feal associated with these combinatorial datasets, without developing a generalized solving stratogy that can be applied to other problem domains for satislying as- signment prediction. For medium datasets, NeuroSAT also faces challenges in generalization, its performance is relatively limited. This can be attributed to the difficulty of these datasets, where finding satisfying assignments is much harder than easy datasets.
23:4
20-1
X30
020
20
CM
NeuroSAT on easy datasets
NeuroSAt on medium datasets
Figure 9: Solving accuracy of NeuroSAT across dif- ferent datasets (with UNS₂ the training loss). The x-axis denotes testing datasets and the y-axis denotes training datasets.
Evaluation with different inference algorithms. Figure [0 illustrates the results of NeuroSAT using various decoding algorithms (with UNS2 as the train- ing loss). Notably, all three decoding algorithms demonstrate similar performances across all datasets. This observation indicates that utilizing the standard readout after message passing is sufficient for predict- ing a satisfying assignment. Also, the GNN model has successfully learned to identify potential satisfy- ing assignments within the latent space, which can be extracted by clustering the literal embeddings.
5.6
MaurdATT K0 100 40007
127 FOoe Kowr antwwor
NearsA midian
Figure 10: Solving accuracy of NeuroSAT with dif- ferent inference algorithms.
Evaluation with unsatisfiable training in- stances. Following previous works (Amizadeh et al. 2019a by Ozolins et al. 2022), our evaluation of GNN models focuses solely on satisfiable instances. However, in practical scenarios, the satisfiability of instances may not be known before training. To address this gap, we explore the effectiveness of training NeuroSAT using the unsupervised loss UNS2 on noisy datasets that contain unsatisfialle instances. Table 11 presents the results of NeuroSAT when trained on such datasets, where 50% of the instances are unsatisfiable. In- terestingly, incorporating unsatisfialle instances for training does not significantly affect the performance of the GNN model. This finding highlights the potential utility of training GNN models using UNS, loss on new datasets, irrespective of any prior knowledge regarding their satisfiability.
Table 11: Solving accuracy of NcuroSAT when trained on noisy datasets. Values in parentheses indicate the performance difference compared to the model trained without unsatisfiable instances. The k-Clique dataset is excluded as NeuroSAT fails during training.
Easy Datasets
Medium Datasets
SR
3-SAT
CA
PS
D-Domset
Vercov
3-SAT
CA
PS
<-Domset
Veeroov
78.84
80.48
87.01
88.66
98.00 (-0.85)
95.24
37.21
41.75
76.49
72.52
94.93
96.18
(-0.95)
(-0.11)
(-2,33)
(-0.13)
(-4.49)
(-0.04)
(+0.14)
(+5.64)
(+1.46)
(-1.25)
(+0.19)
C.4
Unsat-core Variable Prediction
Evaluation across different difficulty levels. The results across different difficulty levels are presented in Figure 11 Remarkably, both NeuroSAT and GGNN exhibit a strong generalization ability when trained easy or medium datasets. This suggests that GNN models can effectively learn and generalize from the
18

---

Published in Transactions on Machine Learning Research (05/2024)
characteristics and patterns present in these datasets, enabling them to perform well wide range of problem complexities.
23.05
67.50
30.06
$4.43
03.22
2852
83.33
8:35
00:35
35.08
06.3 37
30.03
55.35
33.39
$5.05
92.79
54.63
$4,47
33.00
25.85
medum
reden
mecium
$5.70
medurm
medin
Tate
120
2213
Nevrrarr the 166 syrio
Seveskat
dligen Waaaet
RourAAST the
the lenrr Aoose
0030
Ea3
640
waay
603
$1.57
06.34
2250
$4.15
9X55
20000
$3.25
$5.70
06.3
34.33
08 04
33.03
55.35
9339
$5.00
92.39
50.02
$0.00
53
25.05
CONNon the adicet
OINI
CONS
S01W
colave
Figure 11: Classification accuracy of unsat-core variables across different difficulty levels. The x-axis denotes lesting datasets and the y-axis denotes training datasets.
Evaluation across different datasets. Figure 12 shows the generalization results across different datasets. Both NeuroSAT and GGNN demonstrate good generalization performance to datasets that are different from their training data, except for the CA dataset. This discrepancy can be attributed to the specific characteristics of the CA dataset, where the number of unsat-core variables is significantly smaller compared to the number of variables not in the unsat core. In contrast, other datasets have different distribution, where the number of unsat-core variables is much larger. This variation in distribution presents a challenge for the models' generalization ability on the CA dataset.
XX0
3:00
0.01
FPC
14
11.41
1830
1111
NeuroSAT on easy datasets
Neuro5AT medium datasets
GGMN on easy datasets
GGNN on medium datasets
Figure 12: Classification accuracy of unsat-core variables across different datascts. The x-axis denotes testing datasets and the y-axis denotes training datasets.
D Advancing Evaluation
D.1 Implementation details
To create the augmented datasets, we leverage CaDiCaL (Fleury & Heisinger 2020 to generate DART proof Wetzler et al. 2014) for each SAT instance, which tracks the clause learning procedure and records all the learned clauses during the solving process. These learned clauses are then added to each instance, with a maximum limit of 1,000 clauses. For experiments on augmented datasets, we keep all training settings identical to those used for the original datasets.
For contrastive pretraining experiments, we treat each original formula and its augmented counterpart as a positive pair and all other instances in mini-batch negative pairs. We use an MLP projection to map the graph embedding of each formula to m; and employ the SimCLR's contrastive loss (Chen et al. 2020 where the loss function for positive pair of examples (i.j) in mini-batch of size 2N is defined as:
exp(sim(m,, m₃)/T)
Li = - log
(8)
Σ 1 [ exp(sim exp
19

---

Published in Transactions on Machine Learning Research (05/2024)
Here, [[y is an indicator function that evaluates to 1 if A * i, is temperature parameter, and sim(:,) is the similarity function defined as sim(m; my) = m, my/l| (mm/llmmm)l The final loss is the average over all positive pairs. In our experiments, 10-1 with weight decay of 10- The pretraining process is performed for total of 100 epochs. Once the pretraining is completed, we keep the GNN model and remove the projection head for downstream tasks.
set the temperature parameter to 0.5 and utilize learning rate of
For experiments involving random initialization, we utilize Kaiming Initialization (He ct al. 2015 to initialize all Aieeral/arribbl and clause embeddings during both training and lesting. For the predicted assignments, we utilize 2-clustering decoding to construct two possible assignment predictions for NeuroSAT* at each iteration. When calculating the number of flipped variables and unsatisfiable clauses for NeuroSAT", we only consider the better assignment prediction of the two at each iteration, which is the one that satisfies more clauses. All other experimental settings remain the same as in the benchmarking evaluation.
D.2 Comparisons with State-of-the-ae SAT Solvers
We compare NeuroSAT with two advanced CDCL and LS solvers, CaDiCaL Fleury & Heisinger 2020) and Sparrow (Balint & Fröhlich 2010). To enable a fair comparison, we first configure Sparrow to generate the same number of assignments as NeuroSAT by setting its maximum flip number to 32, allowing for an apples-to-apples comparison of both solvers' accuracy and execution time. Subsequently, we allow Sparrow and CaDiCaL to run without constraints to solve the satisfiable instances in G4SATBench. Considering that NeuroSAT processes a batch of problems parallel on GPUs, we calculate its per-instance runtime by dividing the total execution time by the number of testing instances.
The results, summarized in Table 12 indicate that GNN-based heuristics could outperform modern local search solvers like Sparrow, generating more satisfying assignments extremely fast when constrained to output a limited number of solutions. However, once such constraint is lifted, both Sparrow and CaDiCaL can traverse the solution space efficiently and solve all satisfiable instances in G4SATBench, while GNN models like NeuroSAT may find it challenging due to their limited exploration capacity as evidenced in Figure 5a Nevertheless, it's crucial recognize that while GNN models are hard to compete with CaDiCal, and Sparrow, their assignment predictions could still serve as good initializations in these solvers, potentially leading to better performance (Zhang et al. 2020 Li & Si 2022).
Table 12: Results of NeuroSAT, Sparrow, and CaDiCaL. The top 2 rows represent the solving accuracy (%), and the bottom rows represent the running time (sccond) per instance. Sparrow" refers Sparrow limited to maximum of 32 flips.
Fasy Datasets
Medhum Datasets
Method
SR.
3-SAT
CA
PS
X-Clique
k-Domsct
k- Vereow
SR
3-SAT
CA
PS
J- S-Clique
i-Domset
L-Vercov
NeuuSAT
79.79
80.59
89.31
88.79
63.43
98.85
99.73
37.25
11.461
70.83
71.03
32.18
96.18
95.99
Sparrow"
56.03
52.09
85.48
77.25
63.08
37.15
31.61
1.85
12.08
10.72
12:99
1.27
0.53
NeHoSAT
0.002
0.002
0.002
0.002
0.003
0.002
0.003
0.008
0.008
0.009
0.010
0.009
0.006
0.007
Sparrow"
0.005
0.005
0.006
0.006
0.005
0.005
0.005
0.008
0.007
0.006
0.006
0.006
0.007
0.006
Sperrow
0.007
0.007
0.008
0.008
0.007
0.009
0.009
0.013
0.013
0.010
0.013
0.013
0.012
0.011
CaDICaL
0.013
0.013
0.012
0.011
0.014
0.012
0.011
0.014
0.043
0.016
0.018
0.015
0.013
0.012
20


Reviews:
[{"review_id": "ZFCumhh4kK", "reviewer": "Reviewer_1Lz5", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The main strength of the paper is that it is very well written, contains a wide and updated literature review, and all the software and data are available online.\n\nWe also particularly like the evaluation of the existing GNN-based SAT solvers on the proposed benchmarks. We particularly appreciate Figure 3, where the authors compare how different solvers perform in terms of accuracy across different SAT instances domains: it is quite clear that current GNN-based SAT solvers are able to generalize on a specific class of instances, but they still struggle to generalize across different domain.\n\nThe only small weakness of this paper is that it gives less emphasis to real industrial applications. The proposed benchmark includes a class of pseudo-industrial problems, but we would have preferred to see real industrial problems (in the worst case, some industrial problems of the ’90, which were not as large as today’s instances). We understand that real industrial applications are still very challenging for GNN-based SAT solvers, but for these solvers to ever become useful, they shall be able to tackle real-world instances.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper presents a unified benchmark dataset for evaluating SAT solvers based on Graphical Neural Networks. The authors review several datasets used in the literature and present a unified review of the main GNN-based SAT solvers. In addition, they compare the main solvers of the proposed dataset, called G4SATBench.\n\nIn this case, one contribution is a nice and synthetic review of GNN-based SAT solvers: we appreciate that the review is almost a small tutorial, readable also for people not working on SAT solvers.\n\nA second contribution is indeed the presentation and sharing of a common dataset that is fundamental for comparing and improving new GNN-based SAT solvers.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "We have no specific request, only a pair of marginal comments.\n\nMinor comments:\n- Sections 2 and 3 are very short; maybe they can be merged into a single unified section.\n\n- The tables have a font size that is too small. Please consider splitting the tables in order to favour the font size (older people do not read that small!) (See for instances Table 1 and Figure 3)\n\n- In the conclusion (Section 7.2), I would not say a “groundbreaking benchmark”: please remove “groundbreaking”.\n\n- The repository https://anonymous.4open.science/r/G4SATBench was expired, so I was unable to check the content", "broader_impact_concerns": "No concern.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "eCjhLgL41g", "reviewer": "Reviewer_LgLz", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "## Strengths\n\n* I can't verify whether or not (the tested) GNNs are struggling to learn certain useful heuristics but the paper suggests there is an evidence of that and it may well be a useful knowledge or an inspiration for the interested research community.\n* There is value in systematizing benchmarks and providing a unified way of evaluation.\n* The paper also introduces a few more novel problem generators.\n\n## Weaknesses\n\n* I'm not an expert in SAT solving but my experience in MIP solving using GNNs strongly suggests that synthetic datasets are of limited value in terms of both training and evaluation. It is very difficult to construct synthetic datasets that truly follow real-world data because we don't always understand the underlying generative process of real data, its properties and what makes it easy or challenging for learning. Therefore, I personally would not expect most of the findings to transfer to real-world datasets. Why can't we use, for example, real-world graph datasets for k-clique benchmark? Can we use data from e.g. (Jiang et al, ICLR, 2024) for testing SAT solvers, including those based on GNNs? To me it would be a more preferable and convincing study than a synthetic benchmark.\n\nErdos-Renyi model is one of the most basic graph models, I'm, again, not convinced by this choice, unless simplicity is somehow desirable for constructing benchmarks which I don't see a strong argument for.\n\n* I'm not sure why authors settled for quite modest problem sizes even for hard instances and whether this is reflective of any real-world applications.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper introduces a benchmark for evaluating GNN-based solvers for SAT problems. The benchmark consists of 7 synthetic datasets, each available in 3 modes (easy/medium/hard). Authors evaluate some established models on the datasets and come to the conclusion that the tested methods do not learn backtracking strategies.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Wouldn't it be cleaner if problem sizes for the three difficulty levels always matched across datasets?\n\n2. If that's possible, I'd like to see some evidence of results transfer from the proposed synthetic datasets to any real-world problems.", "broader_impact_concerns": "No concerns", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cMs1m0KSm0", "reviewer": "Reviewer_PK1Q", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "STRENGTH\nA unified implementation and benchmark will clearly help the community design and compare other GNN-based SAT solvers.\n\nWEAKNESS\nSection 7.1 gives, in my opinion, a fair account of this paper’s weaknesses. To me, the most noteworthy weakness is the fact that the instances of G4SATBench are tailored for ML approaches. Instead, I think it would have been interesting if G4SATBench could have been designed to challenge ML approaches with datasets for which they were not well suited, and instead were closer to more realistic instances, e.g. with small training sets and/or extreme sizes.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper implements multiple GNN-based SAT solving approaches from the literature and benchmarks them on a new set of instances designed for this purpose.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I am not requesting any change.", "broader_impact_concerns": "None.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: In their initial reviews, the reviewers all seemed convinced that this paper should be accepted by TMLR. Following a brief round of author discussion, they are unanimous in their recommendation for acceptance. 

The paper is likely acceptable as is. Nonetheless, I suggest minor revisions to fix the small table fonts (comment from reviewer 1Lz5). 

Given that all reviewers commented, in one way or another, on the "sim2real" gap, I wonder if it might be helpful to emphasize further how the paper might help close that gap. You already discussed these in the limitation section (7.1), and I only suggest this as a potential opportunity (in other words, I will not "enforce" it).
Decision: Accept (poster)