# Learning Heuristics over Large Graphs via Deep Reinforcement Learning

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

## Key facts

- Cited by 23 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 8 Mar 2019.

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

- [Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning](https://mlsanity.com/paper/2106.01086/) (2021)
- [Link Scheduling using Graph Neural Networks](https://mlsanity.com/paper/2109.05536/) (2021)
- [Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration](https://mlsanity.com/paper/2205.14105/) (2022)
- [Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems](https://mlsanity.com/paper/2102.05875/) (2021)
- [Learning Combinatorial Node Labeling Algorithms](https://mlsanity.com/paper/2106.03594/) (2021)
- [Reversible Action Design for Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/2102.07210/) (2021)
- [Neural Combinatorial Optimization: a New Player in the Field](https://mlsanity.com/paper/2205.01356/) (2022)
- [Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning](https://mlsanity.com/paper/2111.10810/) (2021)
- [A Unified Framework for Combinatorial Optimization Based on Graph Neural Networks](https://mlsanity.com/paper/2406.13125/) (2024)
- [Learning to Branch in Combinatorial Optimization with Graph Pointer Networks](https://mlsanity.com/paper/2307.01434/) (2023)
- [Learning to repeatedly solve routing problems](https://mlsanity.com/paper/2212.08101/) (2022)
- [Revisit the Algorithm Selection Problem for TSP with Spatial Information Enhanced Graph Neural Networks](https://mlsanity.com/paper/2302.04035/) (2023)
- [DeepGANTT: A Scalable Deep Learning Scheduler for Backscatter Networks](https://mlsanity.com/paper/2112.12985/) (2021)
- [Multi-objective Pointer Network for Combinatorial Optimization](https://mlsanity.com/paper/2204.11860/) (2022)
- [A hybrid deep-learning-metaheuristic framework for bi-level network design problems](https://mlsanity.com/paper/2303.06024/) (2023)
- [Threshold-aware Learning to Generate Feasible Solutions for Mixed Integer Programs](https://mlsanity.com/paper/2308.00327/) (2023)
- [Unveiling the Limits of Learned Local Search Heuristics: Are You the Mightiest of the Meek?](https://mlsanity.com/paper/2310.19990/) (2023)
- [A Note on Machine Learning Approach for Computational Imaging](https://mlsanity.com/paper/2202.11883/) (2022)
- [Deep Reinforcement Learning for Online Routing of Unmanned Aerial Vehicles with Wireless Power Transfer](https://mlsanity.com/paper/2204.11477/) (2022)
- [Network Aware Compute and Memory Allocation in Optically Composable Data Centres with Deep Reinforcement Learning and Graph Neural Networks](https://mlsanity.com/paper/2211.02466/) (2022)
- [Robust Generalization of Graph Neural Networks for Carrier Scheduling](https://mlsanity.com/paper/2407.08479/) (2024)
- [DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs](https://mlsanity.com/paper/2505.23131/) (2025)
- [Projecting Latent RL Actions: Towards Generalizable and Scalable Graph Combinatorial Optimization](https://mlsanity.com/paper/2605.19721/) (2026)

## Abstract (arXiv)

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.