OpenGraphGym-MG: Using Reinforcement Learning to Solve Large Graph Optimization Problems on MultiGPU Systems

Abstract

Large scale graph optimization problems arise in many fields. This paper presents an extensible, high performance framework (named OpenGraphGym-MG) that uses deep reinforcement learning and graph embedding to solve large graph optimization problems with multiple GPUs. The paper uses a common RL algorithm (deep Q-learning) and a representative graph embedding (structure2vec) to demonstrate the extensibility of the framework and, most importantly, to illustrate the novel optimization techniques, such as spatial parallelism, graph-level and node-level batched processing, distributed sparse graph storage, efficient parallel RL training and inference algorithms, repeated gradient descent iterations, and adaptive multiple-node selections. This study performs a comprehensive performance analysis on parallel efficiency and memory cost that proves the parallel RL training and inference algorithms are efficient and highly scalable on a number of GPUs. This study also conducts a range of large graph experiments, with both generated graphs (over 30 million edges) and real-world graphs, using a single compute node (with six GPUs) of the Summit supercomputer. Good scalability in both RL training and inference is achieved: as the number of GPUs increases from one to six, the time of a single step of RL training and a single step of RL inference on large graphs with more than 30 million edges, is reduced from 316.4s to 54.5s, and 23.8s to 3.4s, respectively. The research results on a single node lay out a solid foundation for the future work to address graph optimization problems with a large number of GPUs across multiple nodes in the Summit.

References in corpus (19)

• Adam: A Method for Stochastic Optimization
• Statistical mechanics of complex networks
• PyTorch: An Imperative Style, High-Performance Deep Learning Library
• Inductive Representation Learning on Large Graphs
• Neural Message Passing for Quantum Chemistry
• word2vec Explained: deriving Mikolov et al.'s negative-sampling word-embedding method
• Fast Graph Representation Learning with PyTorch Geometric
• Learning Combinatorial Optimization Algorithms over Graphs
• Social Structure of Facebook Networks
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Learning Heuristics over Large Graphs via Deep Reinforcement Learning
• Highly Efficient Forward and Backward Propagation of Convolutional Neural Networks for Pixelwise Classification
• Acme: A Research Framework for Distributed Reinforcement Learning
• End to end learning and optimization on graphs
• DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs
• Solving NP-Hard Problems on Graphs with Extended AlphaGo Zero
• Ecole: A Gym-like Library for Machine Learning in Combinatorial Optimization Solvers
• Accelerating Reinforcement Learning through GPU Atari Emulation
• Parallel Complexity of Forward and Backward Propagation