  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.
