Research map / Graph learning / Graph algorithms and clustering
Can Q-Learning with Graph Networks Learn a Generalizable Branching Heuristic for a SAT Solver?
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 on graph coloring (flat-75-180) instead of zero-shot transfer from SAT-50-218 | Graph-Q-SAT · SATLIB flat graph coloring 100-239 | MRIR: 1.44 -> 2.89 | Helped |
| use Graph-Q-SAT for only the first 10 decisions before handing control to VSIDS (ablation) | MiniSat · SAT-50-218 | MRIR | Helped |
| train on a single SAT problem instead of 800 (ablation) | Graph-Q-SAT · SAT-50-218 generalization | MRIR | Mixed |
| train on SAT-50-218 and transfer, versus training directly on SAT-100-430 | Graph-Q-SAT · SAT-100-430 | MRIR | Helped |
| evaluate on unSAT instead of SAT (generalization shift) | Graph-Q-SAT · 250-1065 variable problems | MRIR: 3.91 -> 1.54 | Hurt |
Closest papers by meaning
- Learning from Algorithm Feedback: One-Shot SAT Solver Guidance with GNNs (ICLR 2026 · similarity 0.95)
- Learning Local Search Heuristics for Boolean Satisfiability (NeurIPS 2019 · similarity 0.92)
- Learning How to Cube (NeurIPS 2026 · similarity 0.89)
- NeuroBack: Improving CDCL SAT Solving using Graph Neural Networks (ICLR 2024 · similarity 0.87)
- SAT-Based Tree Decomposition with Iterative Cascading Policy Selection (AAAI 2024 · similarity 0.86)
- HardCore Generation: Generating Hard UNSAT Problems for Data Augmentation (NeurIPS 2024 · similarity 0.85)
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.