用超图神经网络无监督求解加权最大满足问题，效果优于现有方法。
HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems
- 构建加权最大满足问题的超图表示，捕捉文字间逻辑关系。
- 在多个数据集上超越当前最优方法，提升求解精度。
- 适合需要高效求解复杂约束问题的研究者和工程师。
图神经网络（GNN）因其能有效建模文字与子句间的结构依赖，在布尔满足性（SAT）和最大满足性（MaxSAT）问题求解中表现优异。然而，针对加权最大满足性（Weighted MaxSAT）问题的GNN方法仍不成熟。挑战源于子句权重分布不均导致的非线性依赖关系和敏感的目标函数。本文提出HyperSAT，一种新颖的无监督超图神经网络模型，用于求解加权最大满足性问题。我们设计了加权最大满足性实例的超图表示，并引入交叉注意力机制与共享表示约束损失函数，以捕捉超图中正负文字节点间的逻辑交互。在多个加权最大满足性数据集上的大量实验表明，HyperSAT性能优于当前最先进的方法。
原文摘要 · Abstract (English)
Graph neural networks (GNNs) have shown promising performance in solving both Boolean satisfiability (SAT) and Maximum Satisfiability (MaxSAT) problems due to their ability to efficiently model and capture the structural dependencies between literals and clauses. However, GNN methods for solving Weighted MaxSAT problems remain underdeveloped. The challenges arise from the non-linear dependency and sensitive objective function, which are caused by the non-uniform distribution of weights across clauses. In this paper, we present HyperSAT, a novel neural approach that employs an unsupervised hypergraph neural network model to solve Weighted MaxSAT problems. We propose a hypergraph representation for Weighted MaxSAT instances and design a cross-attention mechanism along with a shared representation constraint loss function to capture the logical interactions between positive and negative literal nodes in the hypergraph. Extensive experiments on various Weighted MaxSAT datasets demonstrate that HyperSAT achieves better performance than state-of-the-art competitors.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。