Research map / Graph learning / Graph algorithms and clustering
COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes COMBHelper, a GCN-based node pruning framework that shrinks the search space for graph CO problems (MVC, MIS), enhanced with knowledge distillation and problem-specific AdaBoost-style weighting, so that LP, greedy, and local search run at least 2x faster.
Problem
Traditional node-selection combinatorial optimization algorithms (LP, greedy, local search) for NP-hard graph problems such as minimum vertex cover and maximum independent set are slow when the search space is large.
Approach
Train a GCN on labels from exact/heuristic solutions to classify nodes as promising or not, prune unpromising nodes, then run the traditional CO algorithm only on the reduced node set; further compress the GCN via knowledge distillation and reweight training nodes with an AdaBoost-style, degree-based problem-specific boosting scheme.
Key results
- LP+COMBHelper achieves 100.00% edge coverage on Pubmed MVC with solution size 3806, matching the LP baseline's near-optimal result.
- Local search with COMBHelper gains a speed-up of 11.0 to 102.7 on MVC and about 80x on MIS on real-world datasets, per the paper.
- GD with COMBHelper is about 2 to 6 times faster than the general GD, and the paper claims at least 2x speed-up across all baselines.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| prune the search space with COMBHelper | LP · Pubmed MVC | coverage | Helped |
| prune the search space with COMBHelper | LP · OTC MVC | solution size: 1535 -> 1538 | Mixed |
| prune the search space with COMBHelper | LP · OTC MIS | solution size: 4346 -> 4289 | Hurt |
| prune the search space with COMBHelper | GD · OTC MVC | solution size: 1555 -> 1551 | Helped |
| prune the search space with COMBHelper | LS · OTC MVC | solution size: 1564 -> 1552 | Helped |
| add knowledge distillation, replacing the teacher GCN with a student GCN (ablation) | COMBHelper node classifier · synthetic and real-world datasets | inference time | Helped |
| add KD without problem-specific boosting (ablation) | COMBHelper node classifier · synthetic and real-world datasets | recall | Mixed |
| add problem-specific boosting to the KD student GCN (ablation) | COMBHelper node classifier · synthetic and real-world datasets | recall | Helped |
| add problem-specific boosting to KD (ablation) | COMBHelper · MVC real-world datasets | coverage | Helped |
| add problem-specific boosting to KD (ablation) | COMBHelper · MIS real-world datasets | solution size | Helped |
Surprising findings
- The greedy speed-up is limited because greedy efficiency depends on the problem structure, so gains for GD are smaller than for LP and LS.
- COMBHelper does not always cover all MVC edges; the authors attribute this to GCN overlooking low-degree nodes.
Limitations
- Does not always achieve full edge coverage for MVC, since the GCN can overlook low-degree nodes needed for the cover.
- Evaluated on only two CO problems (MVC and MIS) and three base algorithms.
- Greedy algorithm speed-up is limited by its inherent structure.
Experimental setup
Datasets: BA-1K synthetic graphs Cora
Benchmarks: Alpha OTC DBLP Pubmed Brightkite Slashdot0811 Slashdot0922 Gowalla BA5K BA10K BA20K BA50K
Metrics: solution size edge coverage running time speed-up recall
Baselines: LP (CPLEX) greedy algorithm local search COMBHelper_pt
Builds on: GCN knowledge distillation AdaBoost GCOMB
Closest papers by meaning
- Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs (NeurIPS 2020 · similarity 0.91)
- Are Graph Neural Networks Optimal Approximation Algorithms? (NeurIPS 2024 · similarity 0.89)
- 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)
- Neural Solver Selection for Combinatorial Optimization (ICML 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.