# What's Wrong with Deep Learning in Tree Search for Combinatorial Optimization

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

## Key facts

- Cited by 37 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 79 references that are in the map.
- First posted on arXiv 25 Jan 2022.

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

- [Adam: A Method for Stochastic Optimization](https://mlsanity.com/paper/1412.6980/) (2014)
- [Proximal Policy Optimization Algorithms](https://mlsanity.com/paper/1707.06347/) (2017)
- [Semi-Supervised Classification with Graph Convolutional Networks](https://mlsanity.com/paper/1609.02907/) (2016)
- [Inductive Representation Learning on Large Graphs](https://mlsanity.com/paper/1706.02216/) (2017)
- [Attention, Learn to Solve Routing Problems!](https://mlsanity.com/paper/1803.08475/) (2018)
- [Learning Combinatorial Optimization Algorithms over Graphs](https://mlsanity.com/paper/1704.01665/) (2017)
- [Photographic Image Synthesis with Cascaded Refinement Networks](https://mlsanity.com/paper/1707.09405/) (2017)
- [How Neural Networks Extrapolate: From Feedforward to Graph Neural Networks](https://mlsanity.com/paper/2009.11848/) (2020)
- [Combinatorial Optimization with Graph Convolutional Networks and Guided Tree Search](https://mlsanity.com/paper/1810.10659/) (2018)
- [OSMnx: New Methods for Acquiring, Constructing, Analyzing, and Visualizing Complex Street Networks](https://mlsanity.com/paper/1611.01890/) (2016)
- [Learning to Branch](https://mlsanity.com/paper/1803.10150/) (2018)
- [Learning What to Defer for Maximum Independent Sets](https://mlsanity.com/paper/2006.09607/) (2020)
- [Finding Near-Optimal Independent Sets at Scale](https://mlsanity.com/paper/1509.00764/) (2015)
- [Exploiting Social Network Structure for Person-to-Person Sentiment Analysis](https://mlsanity.com/paper/1409.2450/) (2014)
- [Warmstarting of Model-based Algorithm Configuration](https://mlsanity.com/paper/1709.04636/) (2017)
- [Exact Algorithms for Maximum Independent Set](https://mlsanity.com/paper/1312.6260/) (2013)
- [Exactly Solving the Maximum Weight Independent Set Problem on Large Real-World Graphs](https://mlsanity.com/paper/1810.10834/) (2018)
- [Scalable Kernelization for Maximum Independent Sets](https://mlsanity.com/paper/1708.06151/) (2017)
- [New instances for maximum weight independent set from a vehicle routing application](https://mlsanity.com/paper/2105.12623/) (2021)
- [The Power of Pivoting for Exact Clique Counting](https://mlsanity.com/paper/2001.06784/) (2020)
- [Efficiently Generating Geometric Inhomogeneous and Hyperbolic Random Graphs](https://mlsanity.com/paper/1905.06706/) (2019)
- [Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model](https://mlsanity.com/paper/1705.05646/) (2017)
- [Targeted Branching for the Maximum Independent Set Problem](https://mlsanity.com/paper/2102.01540/) (2021)

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

- [DIFUSCO: Graph-based Diffusion Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2302.08224/) (2023)
- [DIMES: A Differentiable Meta Solver for Combinatorial Optimization Problems](https://mlsanity.com/paper/2210.04123/) (2022)
- [A Diffusion Model Framework for Unsupervised Neural Combinatorial Optimization](https://mlsanity.com/paper/2406.01661/) (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)
- [Scalable Discrete Diffusion Samplers: Combinatorial Optimization and Statistical Physics](https://mlsanity.com/paper/2502.08696/) (2025)
- [CO-Bench: Benchmarking Language Model Agents in Algorithm Search for Combinatorial Optimization](https://mlsanity.com/paper/2504.04310/) (2025)
- [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)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Regularized Langevin Dynamics for Combinatorial Optimization](https://mlsanity.com/paper/2502.00277/) (2025)
- [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)
- [Moco: A Learnable Meta Optimizer for Combinatorial Optimization](https://mlsanity.com/paper/2402.04915/) (2024)
- [RLOR: A Flexible Framework of Deep Reinforcement Learning for Operation Research](https://mlsanity.com/paper/2303.13117/) (2023)
- [LLM-Guided Search for Deletion-Correcting Codes](https://mlsanity.com/paper/2504.00613/) (2025)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (2024)
- [MARCO: A Memory-Augmented Reinforcement Framework for Combinatorial Optimization](https://mlsanity.com/paper/2408.02207/) (2024)
- [Graph-SCP: Accelerating Set Cover Problems with Graph Neural Networks](https://mlsanity.com/paper/2310.07979/) (2023)
- [Unrealized Expectations: Comparing AI Methods vs Classical Algorithms for Maximum Independent Set](https://mlsanity.com/paper/2502.03669/) (2025)
- [Unsupervised Diffusion Solver for Combinatorial Optimization via Combinatorial Adjoint Matching](https://mlsanity.com/paper/2605.30920/) (2026)
- [Learning Branching Heuristics from Graph Neural Networks](https://mlsanity.com/paper/2211.14405/) (2022)
- [Network Interdiction Goes Neural](https://mlsanity.com/paper/2405.16409/) (2024)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [A Denoising Diffusion-Based Evolutionary Algorithm Framework: Application to the Maximum Independent Set Problem](https://mlsanity.com/paper/2510.08627/) (2025)
- [Deep Distance Sensitivity Oracles](https://mlsanity.com/paper/2211.02681/) (2022)
- [On lower bounds of the density of planar periodic sets without unit distances](https://mlsanity.com/paper/2411.13248/) (2024)
- [Enabling Population-Based Architectures for Neural Combinatorial Optimization](https://mlsanity.com/paper/2601.08696/) (2026)

## Abstract (arXiv)

Combinatorial optimization lies at the core of many real-world problems. Especially since the rise of graph neural networks (GNNs), the deep learning community has been developing solvers that derive solutions to NP-hard problems by learning the problem-specific solution structure. However, reproducing the results of these publications proves to be difficult. We make three contributions. First, we present an open-source benchmark suite for the NP-hard Maximum Independent Set problem, in both its weighted and unweighted variants. The suite offers a unified interface to various state-of-the-art traditional and machine learning-based solvers. Second, using our benchmark suite, we conduct an in-depth analysis of the popular guided tree search algorithm by Li et al. [NeurIPS 2018], testing various configurations on small and large synthetic and real-world graphs. By re-implementing their algorithm with a focus on code quality and extensibility, we show that the graph convolution network used in the tree search does not learn a meaningful representation of the solution structure, and can in fact be replaced by random values. Instead, the tree search relies on algorithmic techniques like graph kernelization to find good solutions. Thus, the results from the original publication are not reproducible. Third, we extend the analysis to compare the tree search implementations to other solvers, showing that the classical algorithmic solvers often are faster, while providing solutions of similar quality. Additionally, we analyze a recent solver based on reinforcement learning and observe that for this solver, the GNN is responsible for the competitive solution quality.