# Maximum Independent Set: Self-Training through Dynamic Programming

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 59 references that are in the map.
- First posted on arXiv 28 Oct 2023.

## Builds on (most cited first, 30 of 32)

- [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)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Graph Attention Networks](https://mlsanity.com/paper/1710.10903/) (2017)
- [Layer Normalization](https://mlsanity.com/paper/1607.06450/) (2016)
- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Gaussian Error Linear Units (GELUs)](https://mlsanity.com/paper/1606.08415/) (2016)
- [A Comprehensive Survey on Graph Neural Networks](https://mlsanity.com/paper/1901.00596/) (2019)
- [Pointer Networks](https://mlsanity.com/paper/1506.03134/) (2015)
- [Link Prediction Based on Graph Neural Networks](https://mlsanity.com/paper/1802.09691/) (2018)
- [TUDataset: A collection of benchmark datasets for learning with graphs](https://mlsanity.com/paper/2007.08663/) (2020)
- [Reinforcement Learning for Solving the Vehicle Routing Problem](https://mlsanity.com/paper/1802.04240/) (2018)
- [Exact Combinatorial Optimization with Graph Convolutional Neural Networks](https://mlsanity.com/paper/1906.01629/) (2019)
- [Neural Bellman-Ford Networks: A General Graph Neural Network Framework for Link Prediction](https://mlsanity.com/paper/2106.06935/) (2021)
- [A Fair Comparison of Graph Neural Networks for Graph Classification](https://mlsanity.com/paper/1912.09893/) (2019)
- [Reinforcement Learning for Combinatorial Optimization: A Survey](https://mlsanity.com/paper/2003.03600/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [Learning to Dispatch for Job Shop Scheduling via Deep Reinforcement Learning](https://mlsanity.com/paper/2010.12367/) (2020)
- [Erdos Goes Neural: an Unsupervised Learning Framework for Combinatorial Optimization on Graphs](https://mlsanity.com/paper/2006.10643/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Learning to Solve NP-Complete Problems - A Graph Neural Network for Decision TSP](https://mlsanity.com/paper/1809.02721/) (2018)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Graph Colouring Meets Deep Learning: Effective Graph Neural Network Models for Combinatorial Problems](https://mlsanity.com/paper/1903.04598/) (2019)
- [Unsupervised Learning for Combinatorial Optimization with Principled Objective Relaxation](https://mlsanity.com/paper/2207.05984/) (2022)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [It's Not What Machines Can Learn, It's What We Cannot Teach](https://mlsanity.com/paper/2002.09398/) (2020)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Revised Note on Learning Algorithms for Quadratic Assignment with Graph Neural Networks](https://mlsanity.com/paper/1706.07450/) (2017)
- [Unsupervised Learning for Combinatorial Optimization Needs Meta-Learning](https://mlsanity.com/paper/2301.03116/) (2023)
- [Deep Reinforcement Learning for Combinatorial Optimization: Covering Salesman Problems](https://mlsanity.com/paper/2102.05875/) (2021)

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

- [DISCO: Efficient Diffusion Solver for Large-Scale Combinatorial Optimization Problems](https://mlsanity.com/paper/2406.19705/) (2024)
- [Learning-augmented Maximum Independent Set](https://mlsanity.com/paper/2407.11364/) (2024)
- [Harmonizing Human Insights and AI Precision: Hand in Hand for Advancing Knowledge Graph Task](https://mlsanity.com/paper/2405.09477/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [Dual-GNN Multilevel Coarsening for Maximum Independent Set](https://mlsanity.com/paper/2609.25149/) (2026)

## Abstract (arXiv)

This work presents a graph neural network (GNN) framework for solving the maximum independent set (MIS) problem, inspired by dynamic programming (DP). Specifically, given a graph, we propose a DP-like recursive algorithm based on GNNs that firstly constructs two smaller sub-graphs, predicts the one with the larger MIS, and then uses it in the next recursive call. To train our algorithm, we require annotated comparisons of different graphs concerning their MIS size. Annotating the comparisons with the output of our algorithm leads to a self-training process that results in more accurate self-annotation of the comparisons and vice versa. We provide numerical evidence showing the superiority of our method vs prior methods in multiple synthetic and real-world datasets.