Papers › Learning Heuristics over Large Graphs via Deep Reinforcement Learning

Learning Heuristics over Large Graphs via Deep Reinforcement Learning

8 Mar 2019NeurIPS 2020 12arXiv:1903.03332archive 2025-07-28

Sahil Manchanda, Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, Ambuj Singh

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.

Paper PDF Conference PDF Code

In Syntology Open this paper in Syntology's Atlas, the map of the papers in Syntology's graph and their citations.

Code

idea-iitd/GCOMB officialmentioned in papermentioned on GitHub report

gcomb/GCOMB mentioned on GitHub report

Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.

Code Syntology ran Syntology

Not run by Syntology. Nothing on this page verifies that the listed code works.

Tasks

Combinatorial Optimization Deep Reinforcement Learning Q-Learning Reinforcement Learning Reinforcement Learning (RL)reinforcement-learning

Results from the paper archive 2025-07-28

No leaderboard rows for this paper in the archive.

Methods

Q-Learning

Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections