Research map / Graph learning / Graph algorithms and clustering
Can Graph Neural Networks Learn to Solve the MaxSAT Problem? (Student Abstract)
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's title only (no summary yet). Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Train GMS-N on synthetic instances from the matching distribution | GMS-N · UF(2,60,600), UF(3,60,600), PL(2,60,600), and PL(3,60,600) validation sets | approximation ratio: >0.99 | Helped |
| Train GMS-E on synthetic instances from the matching distribution | GMS-E · UF(2,60,600), UF(3,60,600), PL(2,60,600), and PL(3,60,600) validation sets | approximation ratio: >0.99 | Helped |
| Train on smaller instances from the same distribution and apply to larger instances | GMS-N and GMS-E · UF and PL testing problems with n ∈ [100, 1600] | % of satisfied clauses | Helped |
| Use GMS-N or GMS-E instead of MaxHS, Loandra, or SATLike | GMS-N and GMS-E · UF and PL testing problems with up to 1,600 variables | % of satisfied clauses | Mixed |
Closest papers by meaning
- Learning a SAT Solver from Single-Bit Supervision (ICLR 2019 · similarity 0.91)
- On the Expressive Power of GNNs for Boolean Satisfiability (ICLR 2026 · similarity 0.91)
- Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver? (NeurIPS 2020 · similarity 0.90)
- Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs (ICLR 2026 · similarity 0.90)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.87)
- NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (ICLR 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.