Back to Search Start Over

Graph Neural Networks for Propositional Model Counting

Authors :
Saveri, Gaia
Bortolussi, Luca
Publication Year :
2022

Abstract

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.

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2205.04423
Document Type :
Working Paper