Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecture

• URL: http://arxiv.org/abs/2511.19544v1
• Date: Mon, 24 Nov 2025 11:22:29 GMT
• Title: Learning to Solve Weighted Maximum Satisfiability with a Co-Training Architecture
• Authors: Kaidi Wan, Minghao Liu, Yong Lai,
• Abstract summary: SplitGNN is a graph neural network (GNN)-based approach that learns to solve maximum weighted satisfiabil ity (MaxSAT) problem.<n>We show that SplitGNN achieves 3* faster convergence and better predictions compared with other GNN-based artectures.
• Score: 3.6954955003852064
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• A Distributed Training Architecture For Combinatorial Optimization [0.0]
  We propose a distributed graph neural network (GNN)-based training framework for optimization.<n>Experiments are conducted on both real large-scale social network datasets and synthetically generated high-complexity graphs.<n>Our framework outperforms state-of-the-art approaches in both solution quality and computational efficiency.
  arXiv  Detail & Related papers  (2025-11-12T12:22:10Z)
• ScaleGNN: Towards Scalable Graph Neural Networks via Adaptive High-order Neighboring Feature Fusion [73.85920403511706]
  We propose ScaleGNN, a novel framework that adaptively fuses multi-hop node features for scalable and effective graph learning.<n>We show that ScaleGNN consistently outperforms state-of-the-art GNNs in both predictive accuracy and computational efficiency.
  arXiv  Detail & Related papers  (2025-04-22T14:05:11Z)
• GDSG: Graph Diffusion-based Solution Generator for Optimization Problems in MEC Networks [109.17835015018532]
  We present a Graph Diffusion-based Solution Generation (GDSG) method.<n>This approach is designed to work with suboptimal datasets while converging to the optimal solution large probably.<n>We build GDSG as a multi-task diffusion model utilizing a Graph Neural Network (GNN) to acquire the distribution of high-quality solutions.
  arXiv  Detail & Related papers  (2024-12-11T11:13:43Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  We introduce a novel algorithm, denoted hereafter as QRF-GNN, leveraging the power of GNNs to efficiently solve Combinatorial optimization (CO) problems. It relies on unsupervised learning by minimizing the loss function derived from QUBO relaxation. Results of experiments show that QRF-GNN drastically surpasses existing learning-based approaches and is comparable to the state-of-the-art conventionals.
  arXiv  Detail & Related papers  (2024-07-23T13:34:35Z)
• Towards a General Recipe for Combinatorial Optimization with Multi-Filter GNNs [13.871690454501389]
  We introduce GCON, a novel GNN architecture that leverages a complex filter bank and localized attention mechanisms to solve CO problems on graphs. GCON is competitive across all tasks and consistently outperforms other specialized GNN-based approaches.
  arXiv  Detail & Related papers  (2024-05-31T00:02:07Z)
• torchmSAT: A GPU-Accelerated Approximation To The Maximum Satisfiability Problem [1.5850859526672516]
  We derive a single differentiable function capable of approximating solutions for the Maximum Satisfiability Problem (MaxSAT) We present a novel neural network architecture to model our differentiable function, and progressively solve MaxSAT using backpropagation.
  arXiv  Detail & Related papers  (2024-02-06T02:33:00Z)
• T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
  T-GAE is a graph autoencoder framework that leverages transferability and stability of GNNs to achieve efficient network alignment without retraining. Our experiments demonstrate that T-GAE outperforms the state-of-the-art optimization method and the best GNN approach by up to 38.7% and 50.8%, respectively.
  arXiv  Detail & Related papers  (2023-10-05T02:58:29Z)
• Are Graph Neural Networks Optimal Approximation Algorithms? [26.5364112420121]
  We design graph neural network architectures that capture optimal approximation algorithms for a class of optimization problems. We take advantage of OptGNN's ability to capture convex relaxations to design an algorithm for producing bounds on the optimal solution from the learned embeddings of OptGNN.
  arXiv  Detail & Related papers  (2023-10-01T00:12:31Z)
• GNN at the Edge: Cost-Efficient Graph Neural Network Processing over Distributed Edge Servers [24.109721494781592]
  Graph Neural Networks (GNNs) are still under exploration, presenting a stark disparity to its broad edge adoptions. This paper studies the cost optimization for distributed GNN processing over a multi-tier heterogeneous edge network. We show that our approach achieves superior performance over de facto baselines with more than 95.8% cost eduction in a fast convergence speed.
  arXiv  Detail & Related papers  (2022-10-31T13:03:16Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  Large-scale graph training is a notoriously challenging problem for graph neural networks (GNNs) We present a new ensembling training manner, named EnGCN, to address the existing issues. Our proposed method has achieved new state-of-the-art (SOTA) performance on large-scale datasets.
  arXiv  Detail & Related papers  (2022-10-14T03:43:05Z)
• GNNRank: Learning Global Rankings from Pairwise Comparisons via Directed Graph Neural Networks [68.61934077627085]
  We introduce GNNRank, a modeling framework compatible with any GNN capable of learning digraph embeddings. We show that our methods attain competitive and often superior performance compared with existing approaches.
  arXiv  Detail & Related papers  (2022-02-01T04:19:50Z)
• Bag of Tricks for Training Deeper Graph Neural Networks: A Comprehensive Benchmark Study [100.27567794045045]
  Training deep graph neural networks (GNNs) is notoriously hard. We present the first fair and reproducible benchmark dedicated to assessing the "tricks" of training deep GNNs.
  arXiv  Detail & Related papers  (2021-08-24T05:00:37Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.