Research map / Graph learning / GNN architectures
Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
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 |
|---|---|---|---|
| Use graph convolutional predictions with diverse solution maps and guided tree search instead of S2V-DQN | SATLIB test set SAT solving · SATLIB test set | solved SAT instances: 0.0% -> 100.0% | Helped |
| Add graph reduction and local search to S2V-DQN | S2V-DQN · SATLIB test set | solved SAT instances: 0.0% -> 8.9% | Helped |
| Use diverse probability maps with tree search instead of the Basic solver (ablation) | proposed MIS solver · SATLIB validation set | solved SAT instances: 18.8% -> 59.2% | Helped |
| Add diversity loss to the tree-search solver (ablation) | Basic+Tree · SATLIB validation set | solved SAT instances: 59.2% -> 98.8% | Helped |
| Add local search (ablation) | full proposed solver · SATLIB validation set | solved SAT instances: 42.4% -> 98.8% | Helped |
| Add graph reduction (ablation) | full proposed solver · SATLIB validation set | solved SAT instances: 91.0% -> 98.8% | Helped |
| Add parallelization (ablation) | full proposed solver · SATLIB validation set | solved SAT instances: 98.8% -> 100.0% | Helped |
| Increase the number of output maps up to M=32 (ablation) | proposed GCN · SATLIB validation set | solved SAT instances | Helped |
| Increase the number of output maps beyond M=32 (ablation) | proposed GCN · SATLIB validation set | solved SAT instances | No clear effect |
| Train on synthetic SAT graphs and apply to the BUAA-MC benchmark | proposed solver · BUAA-MC | MC instances solved optimally: 25.0% -> 62.5% | Helped |
| Set intermediate width to C=32 rather than C=16 (ablation) | proposed GCN · SATLIB validation set | solved SAT instances: 97.0% -> 98.8% | Helped |
| Increase intermediate width from C=32 to C=64 or C=128 (ablation) | proposed GCN · SATLIB validation set | solved SAT instances: 98.8% -> 97.6%; 98.8% -> 97.2% | Hurt |
Closest papers by meaning
- What’s Wrong with Deep Learning in Tree Search for Combinatorial Optimization (ICLR 2022 · similarity 0.95)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.90)
- COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems (AAAI 2024 · similarity 0.90)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.88)
- Geometric Algorithms for Neural Combinatorial Optimization with Constraints (NeurIPS 2025 · similarity 0.88)
- GOAL: A Generalist Combinatorial Optimization Agent Learner (ICLR 2025 · similarity 0.88)
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.