AAAI 2023technical10 citations
Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)
Minghao Liu, Pei Huang, Fuqi Jia, Fan Zhang, Yuchen Sun, Shaowei Cai, Feifei Ma, Jian Zhang
Abstract
The paper presents an attempt to bridge the gap between machine learning and symbolic reasoning. We build graph neural networks (GNNs) to predict the solution of the Maximum Satisfiability (MaxSAT) problem, an optimization variant of SAT. Two closely related graph representations are adopted, and we prove their theoretical equivalence. We also show that GNNs can achieve attractive performance to solve hard MaxSAT problems in certain distributions even compared with state-of-the-art solvers through experimental evaluation.
BibTeX
@article{Liu_Huang_Jia_Zhang_Sun_Cai_Ma_Zhang_2024, title={Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)}, volume={37}, url={https://ojs.aaai.org/index.php/AAAI/article/view/26992}, DOI={10.1609/aaai.v37i13.26992}, abstractNote={The paper presents an attempt to bridge the gap between machine learning and symbolic reasoning. We build graph neural networks (GNNs) to predict the solution of the Maximum Satisfiability (MaxSAT) problem, an optimization variant of SAT. Two closely related graph representations are adopted, and we prove their theoretical equivalence. We also show that GNNs can achieve attractive performance to solve hard MaxSAT problems in certain distributions even compared with state-of-the-art solvers through experimental evaluation.}, number={13}, journal={Proceedings of the AAAI Conference on Artificial Intelligence}, author={Liu, Minghao and Huang, Pei and Jia, Fuqi and Zhang, Fan and Sun, Yuchen and Cai, Shaowei and Ma, Feifei and Zhang, Jian}, year={2024}, month={Jul.}, pages={16264-16265} }