LEARNING A SAT SOLVER FROM SINGLE-BIT SUPER- VISION
We present NeuroSAT, a message passing neural network that learns to solve SAT problems after only being trained as a classifier to predict satisfiability. Although it is not competitive with state-of-the-art SAT solvers, NeuroSAT can solve problems that are substantially larger and more difficult than it ever saw during training by simply running for more iterations. Moreover, NeuroSAT generalizes to novel distributions; after training only on random SAT problems, at test time it can solve SAT problems encoding graph coloring, clique detection, dominating set, and vertex cover problems, all on a range of distributions over small random graphs.
This paper presents the NeuroSAT architecture, which uses a deep, message passing neural net for predicting the satisfiability of CNF instances. The architecture is also able to predict a satisfiable assignment in the SAT case, and the literals involved in some minimal conflicting set of clauses (i.e. core) in the UNSAT case. The NeuroSAT architecture is based on a vector space embedding of literals and clauses, which exploits (with message passing) some important symmetries of SAT instances (permutation invariance and negation invariance). This architecture is tested on various classes of random SAT instances, involving both unstructured (RS) problems, and structured ones (e.g. graph colorings, vertex covers, dominating sets, etc.).
Overall the paper is well-motivated, and the experimental results are quite convincing. Arguably, the salient characteristic of NeuroSAT is to iteratively refine the confidence of literals voting for the SAT - or UNSAT - output, using a voting scheme on the last iteration of the literal matrix. This is very interesting, and NeuroSAT might be used to help existing solvers in choosing variable orderings for tackling hard instances, or hard queries (e.g. find a core).
On the other hand, the technical description of the architecture (sec. 3) is perhaps a little vague for having a clear intuition of how the classification task - for SAT instances - is handled in the NeuroSAT architecture. Namely, a brief description of the initial matrices (which encode the literal en clause embeddings) would be nice. Some comments on the role played by the multilayer perceptron units and the normalization units would also be welcome. The two update rules in Page 3 could be explained in more detail. For the sake of clarity, I would suggest to provide a figure for depicting a transition (from iteration t-1 to iteration t) in the architecture. As a minor comment, it would be nice (in Section 2) to define the main parameters $n$, $m$, and $d$ used in the rest of the paper.
Concerning the experimental part of the paper, Sections 4 & 5 are well-explained but, in Section 6,  the solution decoding method, inspired from PCA is a bit confusing. Specifically, we don’t know how a satisfying assignment is extracted from the last layer, and this should be explained in detail. According to Figure 4 and the comments above, it seems that a clustering method (with two centroids) is advocated, but this is not clear. In Table 1, the correlation between the accuracy on SAT instances, and the percent of SAT instances solved is not clear. Is the ratio of 70% measured on the CNF instances which have been predicted to be satisfiable? Or, is this ratio measured on the whole set of test instances? Finally, for the results established in Table 1, how many training instances and test instances have been used?
In Section 7, some important aspects related to experiments, are missing. In Sec 7.1, for SR(200) tasks, was NeuroSAT tested on the same conditions as those for SR(40) tasks? Notably, what is the input dimension $d$ of the embedding space here? (I guess that $d = 128$ is too small for such large instances). Also, how many training and test instances have been used to plot the curves in Figure 5? For the 4,888 satisfiable instances generated in Sec. 7.2, which solver have been used to determine the satisfiability of those instances (I guess it is Minisat, but this should be mentioned somewhere). 
In Section 8, I found interesting the the ability of NeuroSAT in predicting the literals that participate in an UNSAT core. Indeed the problem of finding an UNSAT core in CNF instances is computationally harder than determining the satisfiability of this instance. So, NeuroSAT might be used here to help a solver in finding a core. But the notion of “confidence” should be explained in more detail in this section, and more generally, in the whole paper. Namely, it seems that in the last layer of each iteration, literals are voting for SAT (red colors) with some confidence (say $\delta$)  and voting for UNSAT (blue colors) with some confidence (say $\delta’$). Are $\delta$ and $\delta’$ correlated in the neural architecture? And, how confidences for UNSAT votes are updated?
Finally, I found that the different benchmarks where relevant, but I would also suggest (for future work, or in the appendix) to additionally perform experiments on the well-known random 3-SAT instances ($k$ is fixed to 3). Here, it is well-known that a phase transition (on the instances, not the solver/learner) occurs at 4.26 for the clause/variable ratio. A plot displaying the performance of NeuroSAT (accuracy in predicting the label of the instance) versus the clause/variable ratio would be very helpful in assessing the robustness of NeuroSAT on the so-called “hard” instances (which are close to 4.26). By extension, there have been a lot of recent work in generating “pseudo-industrial” random SAT instances, which incorporate some structure (e.g. communities) in order to mimic real-world structured SAT instances. To this point, it would be interesting to analyze the performance of NeuroSAT on such pseudo-industrial instances.