用图神经网络解决加权最大可满足性问题，速度更快且效果更优。
Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecture
- 设计双训练架构，结合监督消息传递与无监督解优化。
- 在复杂加权实例上比现有方法快3倍，且解的质量更高。
- 适合需要高效求解大规模可满足性问题的研究者和工程师。
我们提出SplitGNN，一种基于图神经网络（GNN）的加权最大可满足性（MaxSAT）求解方法。SplitGNN采用双训练架构，包含监督式消息传递机制与无监督解增强层。提出一种名为边分割因子图的新图表示，基于生成支撑树和边分类，提供更丰富的结构信息。为提升对困难加权实例的求解能力，引入基于GPU加速的层，实现高效的评分计算与松弛优化。实验表明，SplitGNN相较其他GNN方法实现3倍更快收敛，并取得更优预测结果。尤其在更大、更复杂的加权MaxSAT基准测试中，其解优于现代启发式求解器，且在多种结构实例上表现出卓越泛化能力。
原文摘要 · Abstract (English)
Wepropose SplitGNN, a graph neural network (GNN)-based approach that learns to solve weighted maximum satisfiabil ity (MaxSAT) problem. SplitGNN incorporates a co-training architecture consisting of supervised message passing mech anism and unsupervised solution boosting layer. A new graph representation called edge-splitting factor graph is proposed to provide more structural information for learning, which is based on spanning tree generation and edge classification. To improve the solutions on challenging and weighted instances, we implement a GPU-accelerated layer applying efficient score calculation and relaxation-based optimization. Exper iments show that SplitGNN achieves 3* faster convergence and better predictions compared with other GNN-based ar chitectures. More notably, SplitGNN successfully finds solu tions that outperform modern heuristic MaxSAT solvers on much larger and harder weighted MaxSAT benchmarks, and demonstrates exceptional generalization abilities on diverse structural instances.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。