论文标题
用于命题模型计数的图形神经网络
Graph Neural Networks for Propositional Model Counting
论文作者
论文摘要
最近已经利用图形神经网络（GNN）来解决几个逻辑推理任务。然而，计算诸如命题模型计数（#sat）之类的问题仍然主要与传统求解器联系在一起。在这里，我们通过基于Kuch等人的信念传播框架（BP）的架构来解决这一差距，该架构以自我牵手的GNN扩大，并经过训练以大致解决#Sat问题。我们进行了一项彻底的实验研究，表明我们的模型在一小部分随机布尔公式上进行了训练，能够有效地扩展到更大的问题大小，具有可比或更好的最新状态性能。此外，我们表明它可以有效地进行微调，以便在不同公式分布（例如来自SAT编码的组合问题的公式分布）上提供良好的概括结果。
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.
