Graph Neural Networks for Propositional Model Counting
This work addresses the #SAT problem for AI and logic communities, offering a novel machine learning-based approach that is incremental in applying GNNs to a specific counting task.
The authors tackled the propositional model counting (#SAT) problem by developing a Graph Neural Network (GNN) architecture based on belief propagation and self-attention, trained on random Boolean formulae. Their model scales effectively to larger problem sizes, achieving comparable or better performance than state-of-the-art approximate solvers, with efficient fine-tuning for generalization across different formula distributions.
Graph Neural Networks (GNNs) have been recently leveraged to solve several logical reasoning tasks. Nevertheless, counting problems such as propositional model counting (#SAT) are still mostly approached with traditional solvers. Here we tackle this gap by presenting an architecture based on the GNN framework for belief propagation (BP) of Kuch et al., extended with self-attentive GNN and trained to approximately solve the #SAT problem. We ran a thorough experimental investigation, showing that our model, trained on a small set of random Boolean formulae, is able to scale effectively to much larger problem sizes, with comparable or better performances of state of the art approximate solvers. Moreover, we show that it can be efficiently fine-tuned to provide good generalization results on different formulae distributions, such as those coming from SAT-encoded combinatorial problems.