Coloring Big Graphs with AlphaGoZero

Abstract

We show that recent innovations in deep reinforcement learning can effectively color very large graphs -- a well-known NP-hard problem with clear commercial applications. Because the Monte Carlo Tree Search with Upper Confidence Bound algorithm used in AlphaGoZero can improve the performance of a given heuristic, our approach allows deep neural networks trained using high performance computing (HPC) technologies to transform computation into improved heuristics with zero prior knowledge. Key to our approach is the introduction of a novel deep neural network architecture (FastColorNet) that has access to the full graph context and requires $O(V)$ time and space to color a graph with $V$ vertices, which enables scaling to very large graphs that arise in real applications like parallel computing, compilers, numerical solvers, and design automation, among others. As a result, we are able to learn new state of the art heuristics for graph coloring.

References in corpus (4)

• Mastering Chess and Shogi by Self-Play with a General Reinforcement Learning Algorithm
• Learning Combinatorial Optimization Algorithms over Graphs
• Discriminative Embeddings of Latent Variable Models for Structured Data
• Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search

Cited by in corpus (12)

• Reinforcement Learning Applications
• Learning the Travelling Salesperson Problem Requires Rethinking Generalization
• RL4ReAl: Reinforcement Learning for Register Allocation
• Graph Neural Networks for Maximum Constraint Satisfaction
• Graph Learning for Combinatorial Optimization: A Survey of State-of-the-Art
• Costly Features Classification using Monte Carlo Tree Search
• A deep learning guided memetic framework for graph coloring problems
• Learning Combinatorial Node Labeling Algorithms
• Deployment Optimization for Shared e-Mobility Systems with Multi-agent Deep Neural Search
• Deep Momentum Uncertainty Hashing
• Deep Learning-based Hybrid Graph-Coloring Algorithm for Register Allocation
• Deep Learning Chromatic and Clique Numbers of Graphs