论文标题
NSNET：一个通用的神经概率框架，解决令人满意的问题
NSNet: A General Neural Probabilistic Framework for Satisfiability Problems
论文作者
论文摘要
我们提出了神经满意度网络（NSNET），这是一种将令人满意的问题建模为概率推断的一般神经框架，同时表现出适当的解释性。受信仰传播（BP）的启发，NSNET使用新颖的图神经网络（GNN）在潜在空间中参数化BP，在该空间中，其隐藏的表示与BP保持相同的概率解释。可以通过应用不同的学习目标来灵活地配置NSNET来解决SAT和#SAT问题。对于SAT而言，NSNet并没有直接预测令人满意的作业，而是在所有令人满意的解决方案之间执行边际推断，我们发现，对于神经网络而言，这是更可行的。通过估计的边际，可以通过舍入和执行随机的本地搜索来有效地产生令人满意的分配。对于#SAT，NSNET通过学习分区函数的近似值来执行近似模型计数。我们的评估表明，NSNET在多个SAT和#SAT数据集上的推理准确性和时间效率方面取得了竞争成果。
We present the Neural Satisfiability Network (NSNet), a general neural framework that models satisfiability problems as probabilistic inference and meanwhile exhibits proper explainability. Inspired by the Belief Propagation (BP), NSNet uses a novel graph neural network (GNN) to parameterize BP in the latent space, where its hidden representations maintain the same probabilistic interpretation as BP. NSNet can be flexibly configured to solve both SAT and #SAT problems by applying different learning objectives. For SAT, instead of directly predicting a satisfying assignment, NSNet performs marginal inference among all satisfying solutions, which we empirically find is more feasible for neural networks to learn. With the estimated marginals, a satisfying assignment can be efficiently generated by rounding and executing a stochastic local search. For #SAT, NSNet performs approximate model counting by learning the Bethe approximation of the partition function. Our evaluations show that NSNet achieves competitive results in terms of inference accuracy and time efficiency on multiple SAT and #SAT datasets.
