HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems
This addresses the problem of solving Weighted MaxSAT, a combinatorial optimization challenge in AI and computer science, with a novel neural approach that is incremental in applying hypergraph methods to this specific domain.
The paper tackled the underdeveloped area of using neural networks for Weighted MaxSAT problems by proposing HyperSAT, an unsupervised hypergraph neural network model, which achieved better performance than state-of-the-art competitors in experiments on various datasets.
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.