# Learning Combinatorial Node Labeling Algorithms

arXiv: https://arxiv.org/abs/2106.03594 · HTML: https://mlsanity.com/paper/2106.03594/

## Key facts

- Cited by 10 papers in the map (data through 14 Oct 2026).
- Builds on 21 of its 63 references that are in the map.
- First posted on arXiv 7 Jun 2021.

## Builds on (most cited first, 21 of 21)

- [Attention Is All You Need](https://mlsanity.com/paper/1706.03762/) (2017)
- [Deep Residual Learning for Image Recognition](https://mlsanity.com/paper/1512.03385/) (2015)
- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift](https://mlsanity.com/paper/1502.03167/) (2015)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Neural Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1611.09940/) (2016)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem](https://mlsanity.com/paper/1906.01227/) (2019)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Exploratory Combinatorial Optimization with Reinforcement Learning](https://mlsanity.com/paper/1909.04063/) (2019)
- [Combinatorial Optimization by Graph Pointer Networks and Hierarchical Reinforcement Learning](https://mlsanity.com/paper/1911.04936/) (2019)
- [Combining Reinforcement Learning and Constraint Programming for Combinatorial Optimization](https://mlsanity.com/paper/2006.01610/) (2020)
- [Massive Exploration of Neural Machine Translation Architectures](https://mlsanity.com/paper/1703.03906/) (2017)
- [Attention Models in Graphs: A Survey](https://mlsanity.com/paper/1807.07984/) (2018)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time](https://mlsanity.com/paper/2006.03750/) (2020)
- [Learning Heuristics over Large Graphs via Deep Reinforcement Learning](https://mlsanity.com/paper/1903.03332/) (2019)
- [Coloring Big Graphs with AlphaGoZero](https://mlsanity.com/paper/1902.10162/) (2019)
- [Fully Dynamic Approximate Maximum Matching and Minimum Vertex Cover in O(log3 n) Worst Case Update Time](https://mlsanity.com/paper/1704.02844/) (2017)
- [A Massively Parallel Algorithm for Minimum Weight Vertex Cover](https://mlsanity.com/paper/2005.10566/) (2020)

## Built on by (most cited first, 10 of 10)

- [Graph of Thoughts: Solving Elaborate Problems with Large Language Models](https://mlsanity.com/paper/2308.09687/) (2023)
- [Demystifying Chains, Trees, and Graphs of Thoughts](https://mlsanity.com/paper/2401.14295/) (2024)
- [Parallel and Distributed Graph Neural Networks: An In-Depth Concurrency Analysis](https://mlsanity.com/paper/2205.09702/) (2022)
- [Neural Graph Databases](https://mlsanity.com/paper/2209.09732/) (2022)
- [HOT: Higher-Order Dynamic Graph Representation Learning with Efficient Transformers](https://mlsanity.com/paper/2311.18526/) (2023)
- [Cached Operator Reordering: A Unified View for Fast GNN Training](https://mlsanity.com/paper/2308.12093/) (2023)
- [Demystifying Higher-Order Graph Neural Networks](https://mlsanity.com/paper/2406.12841/) (2024)
- [Generating a Graph Colouring Heuristic with Deep Q-Learning and Graph Neural Networks](https://mlsanity.com/paper/2304.04051/) (2023)
- [Learning Robust Heterogeneous Graph Representations via Contrastive-Reconstruction under Sparse Semantics](https://mlsanity.com/paper/2506.06682/) (2025)
- [Performance Foundations of Parallel & Distributed Reasoning Language Models](https://mlsanity.com/paper/2608.27046/) (2026)

## Abstract (arXiv)

We present a novel neural architecture to solve graph optimization problems where the solution consists of arbitrary node labels, allowing us to solve hard problems like graph coloring. We train our model using reinforcement learning, specifically policy gradients, which gives us both a greedy and a probabilistic policy. Our architecture builds on a graph attention network and uses several inductive biases to improve solution quality. Our learned deterministic heuristics for graph coloring give better solutions than classical degree-based greedy heuristics and only take seconds to apply to graphs with tens of thousands of vertices. Moreover, our probabilistic policies outperform all greedy state-of-the-art coloring baselines and a machine learning baseline. Finally, we show that our approach also generalizes to other problems by evaluating it on minimum vertex cover and outperforming two greedy heuristics.