Learning Heuristics over Large Graphs via Deep Reinforcement Learning

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.

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

References in corpus (7)

• Adam: A Method for Stochastic Optimization
• Playing Atari with Deep Reinforcement Learning
• Inductive Representation Learning on Large Graphs
• Learning Combinatorial Optimization Algorithms over Graphs
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search
• Exact Combinatorial Optimization with Graph Convolutional Neural Networks
• Sketch-based Influence Maximization and Computation: Scaling up with Guarantees

Cited by in corpus (17)

• Learning to schedule job-shop problems: Representation and policy learning using graph neural network and reinforcement learning
• An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem
• Deep Reinforcement Learning for Electric Vehicle Routing Problem with Time Windows
• Learning Combinatorial Optimization on Graphs: A Survey with Applications to Networking
• Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems
• Link Scheduling using Graph Neural Networks
• A Survey on Reinforcement Learning for Combinatorial Optimization
• Exploratory Combinatorial Optimization with Reinforcement Learning
• A Deep Reinforcement Learning Algorithm Using Dynamic Attention Model for Vehicle Routing Problems
• Where are the Keys? -- Learning Object-Centric Navigation Policies on Semantic Maps with Graph Convolutional Networks
• Learning to Scan: A Deep Reinforcement Learning Approach for Personalized Scanning in CT Imaging
• Reinforcement Learning Enhanced Quantum-inspired Algorithm for Combinatorial Optimization
• Reversible Action Design for Combinatorial Optimization with Reinforcement Learning
• Optimizing Memory Placement using Evolutionary Graph Reinforcement Learning
• Learning Combinatorial Node Labeling Algorithms
• Vulcan: Solving the Steiner Tree Problem with Graph Neural Networks and Deep Reinforcement Learning
• OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems