Learning Heuristics over Large Graphs via Deep Reinforcement Learning

2019/03/08 by Sahil Manchanda, Manchanda, Sahil, Akash Mittal +10 · 7 citations
Computer Science · Mathematics · Physics and Astronomy · #Advanced Graph Neural Networks #Artificial Intelligence (cs.AI) #Complex Network Analysis Techniques #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Reinforcement Learning in Robotics #cs.AI #cs.LG #stat.ML

paper · pdf · doi:10.48550/arxiv.1903.03332

To appear in NeurIPS 2020 https://papers.nips.cc/paper/2020/hash/e7532dbeff7ef901f2e70daacb3f452d-Abstract.html

openalex publication_date 2019/03/08 · arxiv created 2020/12/03 · arxiv updated 2020/12/04 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Cited by

• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• DOPPLER: Dual-Policy Learning for Device Assignment in Asynchronous Dataflow Graphs
• Learning Combinatorial Node Labeling Algorithms
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems
• Optimizing Memory Placement using Evolutionary Graph Reinforcement Learning

Related

• A Distributed Training Architecture For Combinatorial Optimization
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration
• Learning Combinatorial Optimization Algorithms over Graphs
• A Benchmark Study of Deep-RL Methods for Maximum Coverage Problems over Graphs