Research map / Graph learning / Graph algorithms and clustering
Exact Combinatorial Optimization with Graph Convolutional Neural Networks
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 GCNN branching instead of the strongest reported baseline | branch-and-bound solver · Set Covering Hard | solving time (s): 222.54 -> 114.16 | Helped |
| use GCNN branching instead of the strongest reported baseline | branch-and-bound solver · Combinatorial Auction Hard | solving time (s): 582.38 -> 563.36 | Helped |
| use GCNN branching instead of the strongest reported baseline | branch-and-bound solver · Capacitated Facility Location Hard | solving time (s): 2045.61 -> 2024.37 | Helped |
| use GCNN branching instead of the strongest reported baseline | branch-and-bound solver · Maximum Independent Set Hard | solving time (s): 1677.02 -> 1489.91 | Helped |
| use GCNN branching instead of the strongest reported baseline | branch-and-bound solver · Set Covering Easy | solving time (s): 1.79 -> 1.85 | Hurt |
| replace sum convolutions with mean convolutions (ablation) | GCNN on Set Covering · Set Covering Hard | solving time (s): 1489.9 -> 1593.0 | Hurt |
| replace sum convolutions with mean convolutions (ablation) | GCNN on Set Covering · Set Covering Hard | nodes: 56348 -> 62227 | Hurt |
| remove prenorm layers from sum convolutions (ablation) | GCNN on Set Covering · Set Covering Hard | solving time (s): 1489.9 -> 1511.7 | Hurt |
| remove prenorm layers from sum convolutions (ablation) | GCNN on Set Covering · Set Covering Hard | nodes: 56348 -> 57864 | Hurt |
Closest papers by meaning
- Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search (NeurIPS 2018 · similarity 0.93)
- Towards General Algorithm Discovery for Combinatorial Optimization: Learning Symbolic Branching Policy from Bipartite Graph (ICML 2024 · similarity 0.89)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.89)
- Sample Complexity of Algorithm Selection Using Neural Networks and Its Applications to Branch-and-Cut (NeurIPS 2024 · similarity 0.88)
- Rethinking the Capacity of Graph Neural Networks for Branching Strategy (NeurIPS 2024 · 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.