HyperSAT: Unsupervised Hypergraph Neural Networks for Weighted MaxSAT Problems
By: Qiyue Chen , Shaolin Tan , Suixiang Gao and more
Potential Business Impact:
Solves hard logic puzzles better than before.
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.
Similar Papers
Neural Approaches to SAT Solving: Design Choices and Interpretability
Machine Learning (CS)
Helps computers solve hard puzzles faster.
Attn-JGNN: Attention Enhanced Join-Graph Neural Networks
Machine Learning (CS)
Solves hard math puzzles faster with smart computer learning.
Wasserstein Hypergraph Neural Network
Machine Learning (CS)
Helps computers understand complex connections better.