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



Sign up or login to leave a comment