Learning Combinatorial Node Labeling Algorithms

Lukas Gianinazzi, Maximilian Fries, Nikoli Dryden, Tal Ben-Nun, Torsten Hoefler

We present a graph neural network to learn graph coloring heuristics using reinforcement learning. Our learned deterministic heuristics give better solutions than classical degree-based greedy heuristics and only take seconds to evaluate on graphs with tens of thousands of vertices. As our approach is based on policy-gradients, it also learns a probabilistic policy as well. These probabilistic policies outperform all greedy coloring baselines and a machine learning baseline. Our approach generalizes several previous machine-learning frameworks, which applied to problems like minimum vertex cover. We also demonstrate that our approach outperforms two greedy heuristics on minimum vertex cover.

Knowledge Graph

arrow_drop_up

Comments

Sign up or login to leave a comment