Learning Heuristics over Large Graphs via Deep Reinforcement Learning

  • 2019-03-08 09:23:08
  • Akash Mittal, Anuj Dhawan, Sourav Medya, Sayan Ranu, Ambuj Singh
  • 6

Abstract

In this paper, we propose a deep reinforcement learning framework calledGCOMB to learn algorithms that can solve combinatorial problems over largegraphs. GCOMB mimics the greedy algorithm in the original problem andincrementally constructs a solution. The proposed framework utilizes GraphConvolutional Network (GCN) to generate node embeddings that predicts thepotential nodes in the solution set from the entire node set. These embeddingsenable an efficient training process to learn the greedy policy via Q-learning.Through extensive evaluation on several real and synthetic datasets containingup to a million nodes, we establish that GCOMB is up to 41% better than thestate of the art, up to seven times faster than the greedy algorithm, robustand scalable to large dynamic networks.

 

Introduction (beta)

None

 

Conclusion (beta)

None