# Learning What to Defer for Maximum Independent Sets

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

## Key facts

- Cited by 54 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Jun 2020.

## Built on by (most cited first, 30 of 54)

- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [Neural Combinatorial Optimization with Heavy Decoder: Toward Large Scale Generalization](https://mlsanity.com/paper/2310.07985/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [Sym-NCO: Leveraging Symmetricity for Neural Combinatorial Optimization](https://mlsanity.com/paper/2205.13209/) (2022)
- [Learning to Delegate for Large-scale Vehicle Routing](https://mlsanity.com/paper/2107.04139/) (2021)
- [RL4CO: an Extensive Reinforcement Learning for Combinatorial Optimization Benchmark](https://mlsanity.com/paper/2306.17100/) (2023)
- [Towards Omni-generalizable Neural Methods for Vehicle Routing Problems](https://mlsanity.com/paper/2305.19587/) (2023)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (2024)
- [Ant Colony Sampling with GFlowNets for Combinatorial Optimization](https://mlsanity.com/paper/2403.07041/) (2024)
- [Fast T2T: Optimization Consistency Speeds Up Diffusion-Based Training-to-Testing Solving for Combinatorial Optimization](https://mlsanity.com/paper/2502.02941/) (2025)
- [Let the Flows Tell: Solving Graph Combinatorial Optimization Problems with GFlowNets](https://mlsanity.com/paper/2305.17010/) (2023)
- [What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization](https://mlsanity.com/paper/2201.10494/) (2022)
- [Self-Improvement for Neural Combinatorial Optimization: Sample without Replacement, but Improvement](https://mlsanity.com/paper/2403.15180/) (2024)
- [ScheduleNet: Learn to solve multi-agent scheduling problems with reinforcement learning](https://mlsanity.com/paper/2106.03051/) (2021)
- [Challenges and Opportunities in Deep Reinforcement Learning with Graph Neural Networks: A Comprehensive review of Algorithms and Applications](https://mlsanity.com/paper/2206.07922/) (2022)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [Meta-SAGE: Scale Meta-Learning Scheduled Adaptation with Guided Exploration for Mitigating Scale Shift on Combinatorial Optimization](https://mlsanity.com/paper/2306.02688/) (2023)
- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Graph Reinforcement Learning for Combinatorial Optimization: A Survey and Unifying Perspective](https://mlsanity.com/paper/2404.06492/) (2024)
- [Are Graph Neural Networks Optimal Approximation Algorithms?](https://mlsanity.com/paper/2310.00526/) (2023)
- [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)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [Symmetric Replay Training: Enhancing Sample Efficiency in Deep Reinforcement Learning for Combinatorial Optimization](https://mlsanity.com/paper/2306.01276/) (2023)
- [Tackling Prevalent Conditions in Unsupervised Combinatorial Optimization: Cardinality, Minimum, Covering, and More](https://mlsanity.com/paper/2405.08424/) (2024)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Reheated Gradient-based Discrete Sampling for Combinatorial Optimization](https://mlsanity.com/paper/2503.04047/) (2025)
- [Maximum Independent Set: Self-Training through Dynamic Programming](https://mlsanity.com/paper/2310.18672/) (2023)
- [Moco: A Learnable Meta Optimizer for Combinatorial Optimization](https://mlsanity.com/paper/2402.04915/) (2024)

## Abstract (arXiv)

Designing efficient algorithms for combinatorial optimization appears ubiquitously in various scientific fields. Recently, deep reinforcement learning (DRL) frameworks have gained considerable attention as a new approach: they can automate the design of a solver while relying less on sophisticated domain knowledge of the target problem. However, the existing DRL solvers determine the solution using a number of stages proportional to the number of elements in the solution, which severely limits their applicability to large-scale graphs. In this paper, we seek to resolve this issue by proposing a novel DRL scheme, coined learning what to defer (LwD), where the agent adaptively shrinks or stretch the number of stages by learning to distribute the element-wise decisions of the solution at each stage. We apply the proposed framework to the maximum independent set (MIS) problem, and demonstrate its significant improvement over the current state-of-the-art DRL scheme. We also show that LwD can outperform the conventional MIS solvers on large-scale graphs having millions of vertices, under a limited time budget.