用注意力机制提升图神经网络求解SAT问题的精度
Attn-JGNN: Attention Enhanced Join-Graph Neural Networks
- 基于树分解构建联合图，通过迭代消息传递编码约束
- 引入注意力机制聚焦关键变量与簇，减少冗余计算
- 在SAT求解上优于现有神经网络方法，适合逻辑推理研究者
我们提出一种注意力增强的联合图神经网络（Attn-JGNN）模型，用于求解#SAT问题，显著提升求解精度。受迭代联合图传播（IJGP）算法启发，Attn-JGNN利用树分解将布尔可满足性公式（CNF）编码为联合图，在其上进行迭代消息传递，并通过学习划分函数来近似模型数量。为进一步提高求解精度，我们在联合图的簇内与簇间引入注意力机制，使模型在概率推断中更关注关键变量与簇，减少冗余计算。实验表明，该模型在求解性能上优于其他神经网络方法。
原文摘要 · Abstract (English)
We propose an Attention Enhanced Join-Graph Neural Networks(Attn-JGNN) model for solving #SAT problems, which significantly improves the solving accuracy. Inspired by the Iterative Join Graph Propagation (IJGP) algorithm, Attn-JGNN uses tree decomposition to encode the CNF formula into a join-graph, then performs iterative message passing on the join-graph, and finally approximates the model number by learning partition functions. In order to further improve the accuracy of the solution, we apply the attention mechanism in and between clusters of the join-graphs, which makes Attn-JGNN pay more attention to the key variables and clusters in probabilistic inference, and reduces the redundant calculation. Finally, our experiments show that our Attn-JGNN model achieves better results than other neural network methods.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。