Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)

Authors

  • Minghao Liu State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Pei Huang State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Fuqi Jia State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Fan Zhang Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Yuchen Sun Inspir.ai
  • Shaowei Cai State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Feifei Ma State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences Laboratory of Parallel Software and Computational Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences
  • Jian Zhang State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences University of Chinese Academy of Sciences

DOI:

https://doi.org/10.1609/aaai.v37i13.26992

Keywords:

Graph Neural Networks, MaxSAT Problem, Neuro-symbolic Methods

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.
AAAI-23 Proceedings Cover

Downloads

Published

2024-07-15

How to Cite

Liu, M., Huang, P., Jia, F., Zhang, F., Sun, Y., Cai, S., Ma, F., & Zhang, J. (2024). Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract). Proceedings of the AAAI Conference on Artificial Intelligence, 37(13), 16264-16265. https://doi.org/10.1609/aaai.v37i13.26992

Issue

Vol. 37 No. 13: AAAI-23 Special Programs, IAAI-23, EAAI-23, Student Papers and Demonstrations

Section

AAAI Student Abstract and Poster Program