  There has been an increased interest in discovering heuristics for
combinatorial problems on graphs through machine learning. While existing
techniques have primarily focused on obtaining high-quality solutions,
scalability to billion-sized graphs has not been adequately addressed. In
addition, the impact of budget-constraint, which is necessary for many
practical scenarios, remains to be studied. In this paper, we propose a
framework called GCOMB to bridge these gaps. GCOMB trains a Graph Convolutional
Network (GCN) using a novel probabilistic greedy mechanism to predict the
quality of a node. To further facilitate the combinatorial nature of the
problem, GCOMB utilizes a Q-learning framework, which is made efficient through
importance sampling. We perform extensive experiments on real graphs to
benchmark the efficiency and efficacy of GCOMB. Our results establish that
GCOMB is 100 times faster and marginally better in quality than
state-of-the-art algorithms for learning combinatorial algorithms.
Additionally, a case-study on the practical combinatorial problem of Influence
Maximization (IM) shows GCOMB is 150 times faster than the specialized IM
algorithm IMM with similar quality.
