Hierarchical DeepPruner: A Novel Framework for Search Space Reduction

Combinatorial optimization (CO) problems on graphs arise in various applications across diverse domains. Many of these problems are NP-hard, and heuristics have been developed to provide near-optimal solutions. In the big data era, the high dimensionality of these problems poses significant challenges for existing heuristic methods, which struggle to scale efficiently. In this paper, we propose Hierarchical DeepPruner, an adaptive framework that employs a two-stage approach to efficiently prune the search space of CO problems on graphs. Compared to state-of-the-art pruning heuristics, our algorithm offers two key advantages: 1) it does not require extensive feature engineering or domain-specific knowledge, and 2) it outperforms all previous methods while consistently pruning over 95% of the ground set, resulting in up to several of tenfold speedups—typically with minimal impact on solution quality. Additionally, our algorithm can successfully reduce the search space of instances even if they lie outside the training distribution, resulting in small optimality gaps across multiple budgets