# COMBHelper: A Neural Approach to Reduce Search Space for Graph Combinatorial Problems

arXiv: https://arxiv.org/abs/2312.09086 · HTML: https://mlsanity.com/paper/2312.09086/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 17 of its 43 references that are in the map.
- First posted on arXiv 14 Dec 2023.

## Builds on (most cited first, 17 of 17)

- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Distilling the Knowledge in a Neural Network](https://mlsanity.com/paper/1503.02531/) (2015)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Neural Machine Translation by Jointly Learning to Align and Translate](https://mlsanity.com/paper/1409.0473/) (2014)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Graph-less Neural Networks: Teaching Old MLPs New Tricks via Distillation](https://mlsanity.com/paper/2110.08727/) (2021)
- [Discriminative Embeddings of Latent Variable Models for Structured Data](https://mlsanity.com/paper/1603.05629/) (2016)
- [Distilling Knowledge from Graph Convolutional Networks](https://mlsanity.com/paper/2003.10477/) (2020)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Graph-Free Knowledge Distillation for Graph Neural Networks](https://mlsanity.com/paper/2105.07519/) (2021)
- [AdaGCN: Adaboosting Graph Convolutional Networks into Deep Models](https://mlsanity.com/paper/1908.05081/) (2019)
- [Boosting Graph Neural Networks via Adaptive Knowledge Distillation](https://mlsanity.com/paper/2210.05920/) (2022)
- [Learning to Sparsify Travelling Salesman Problem Instances](https://mlsanity.com/paper/2104.09345/) (2021)
- [Learning Multi-Stage Sparsification for Maximum Clique Enumeration](https://mlsanity.com/paper/1910.00517/) (2019)
- [Learning fine-grained search space pruning and heuristics for combinatorial optimization](https://mlsanity.com/paper/2001.01230/) (2020)

## Built on by (most cited first, 3 of 3)

- [Game-theoretic Counterfactual Explanation for Graph Neural Networks](https://mlsanity.com/paper/2402.06030/) (2024)
- [Theoretically Grounded Pruning of Large Ground Sets for Constrained, Discrete Optimization](https://mlsanity.com/paper/2410.17945/) (2024)
- [GES-TSP: Graph Edge Sparsification for TSP](https://mlsanity.com/paper/2607.09708/) (2026)

## Abstract (arXiv)

Combinatorial Optimization (CO) problems over graphs appear routinely in many applications such as in optimizing traffic, viral marketing in social networks, and matching for job allocation. Due to their combinatorial nature, these problems are often NP-hard. Existing approximation algorithms and heuristics rely on the search space to find the solutions and become time-consuming when this space is large. In this paper, we design a neural method called COMBHelper to reduce this space and thus improve the efficiency of the traditional CO algorithms based on node selection. Specifically, it employs a Graph Neural Network (GNN) to identify promising nodes for the solution set. This pruned search space is then fed to the traditional CO algorithms. COMBHelper also uses a Knowledge Distillation (KD) module and a problem-specific boosting module to bring further efficiency and efficacy. Our extensive experiments show that the traditional CO algorithms with COMBHelper are at least 2 times faster than their original versions.