Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2511.19544 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866914169842827264 |
|---|---|
| author | Wan, Kaidi Liu, Minghao Lai, Yong |
| author_facet | Wan, Kaidi Liu, Minghao Lai, Yong |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_19544 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecture Wan, Kaidi Liu, Minghao Lai, Yong Machine Learning 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. |
| title | Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecture |
| topic | Machine Learning |
| url | https://arxiv.org/abs/2511.19544 |