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

AAAI 2023 pp. 16264-16265

doi:10.1609/AAAI.V37I13.26992 /aaai/2023/liu2023aaai-graph/

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.

PDF AAAI Semantic Scholar

Cite

Text

Liu et al. "Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)." AAAI Conference on Artificial Intelligence, 2023. doi:10.1609/AAAI.V37I13.26992

Markdown

[Liu et al. "Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)." AAAI Conference on Artificial Intelligence, 2023.](https://mlanthology.org/aaai/2023/liu2023aaai-graph/) doi:10.1609/AAAI.V37I13.26992

BibTeX

@inproceedings{liu2023aaai-graph,
  title     = {{Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)}},
  author    = {Liu, Minghao and Huang, Pei and Jia, Fuqi and Zhang, Fan and Sun, Yuchen and Cai, Shaowei and Ma, Feifei and Zhang, Jian},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year      = {2023},
  pages     = {16264-16265},
  doi       = {10.1609/AAAI.V37I13.26992},
  url       = {https://mlanthology.org/aaai/2023/liu2023aaai-graph/}
}