# Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set

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

## Key facts

- Cited by 33 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 18 references that are in the map.
- First posted on arXiv 27 Jun 2022.

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

- [Machine Learning for Combinatorial Optimization: a Methodological Tour d'Horizon](https://mlsanity.com/paper/1811.06128/) (2018)
- [Combinatorial optimization and reasoning with graph neural networks](https://mlsanity.com/paper/2102.09544/) (2021)
- [Learning a SAT Solver from Single-Bit Supervision](https://mlsanity.com/paper/1802.03685/) (2018)
- [End-to-End Constrained Optimization Learning: A Survey](https://mlsanity.com/paper/2103.16378/) (2021)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Graph Neural Networks for Maximum Constraint Satisfaction](https://mlsanity.com/paper/1909.08387/) (2019)
- [Monte Carlo algorithms are very effective in finding the largest independent set in sparse random graphs](https://mlsanity.com/paper/1904.02231/) (2019)
- [Parallel Tempering for the planted clique problem](https://mlsanity.com/paper/1802.05903/) (2018)
- [Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning](https://mlsanity.com/paper/2201.01825/) (2022)

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

- [Variational Annealing on Graphs for Combinatorial Optimization](https://mlsanity.com/paper/2311.14156/) (2023)
- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [FrontierCO: Real-World and Large-Scale Evaluation of Machine Learning Solvers for Combinatorial Optimization](https://mlsanity.com/paper/2505.16952/) (2025)
- [Reply to: Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2302.03602/) (2023)
- [Optimization by Parallel Quasi-Quantum Annealing with Gradient-Based Sampling](https://mlsanity.com/paper/2409.02135/) (2024)
- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)
- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)
- [Demonstrating Real Advantage of Machine-Learning-Enhanced Monte Carlo for Combinatorial Optimization](https://mlsanity.com/paper/2510.19544/) (2025)
- [Quantum approximate optimization via learning-based adaptive optimization](https://mlsanity.com/paper/2303.14877/) (2023)
- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Continuous Parallel Relaxation for Finding Diverse Solutions in Combinatorial Optimization Problems](https://mlsanity.com/paper/2402.02190/) (2024)
- [A Benchmark for Maximum Cut: Towards Standardization of the Evaluation of Learned Heuristics for Combinatorial Optimization](https://mlsanity.com/paper/2406.11897/) (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)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply](https://mlsanity.com/paper/2306.02555/) (2023)
- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2308.13978/) (2023)
- [Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems](https://mlsanity.com/paper/2411.05834/) (2024)
- [Nonlocal Monte Carlo via Reinforcement Learning](https://mlsanity.com/paper/2508.10520/) (2025)
- [Graph Neural Networks are Heuristics](https://mlsanity.com/paper/2601.13465/) (2026)
- [GNN-Guided Graph Coarsening and Adaptive QUBO Penalties for the Capacitated Vehicle Routing Problem with Time Windows on a Quantum Annealer](https://mlsanity.com/paper/2609.04593/) (2026)
- [A Graph Neural Network-Based QUBO-Formulated Hamiltonian-Inspired Loss Function for Combinatorial Optimization using Reinforcement Learning](https://mlsanity.com/paper/2311.16277/) (2023)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [Unsupervised Learning of Local Updates for Maximum Independent Set in Dynamic Graphs](https://mlsanity.com/paper/2505.13754/) (2025)
- [How do Probabilistic Graphical Models and Graph Neural Networks Look at Network Data?](https://mlsanity.com/paper/2506.11869/) (2025)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [Neural Tractability via Structure: Learning-Augmented Algorithms for Graph Combinatorial Optimization](https://mlsanity.com/paper/2511.19573/) (2025)
- [Placing Degree Scales After LayerNorm](https://mlsanity.com/paper/2606.14022/) (2026)
- [On the Potential of Graph Neural Networks as Metamodels for Supply Chain Optimization: Dataset, Architectures, and Directions](https://mlsanity.com/paper/2607.16769/) (2026)
- [Anatomy of a Sound Neural Reasoner: One-Shot Amortization, First-Pass Poisoning, and Search Inertness in Clue-Rich Completion](https://mlsanity.com/paper/2607.19635/) (2026)

## Abstract (arXiv)

The recent work ``Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired unsupervised Graph Neural Network (GNN) to solve combinatorial optimization problems on sparse graphs. To test the performances of these GNNs, the authors of the work show numerical results for two fundamental problems: maximum cut and maximum independent set (MIS). They conclude that "the graph neural network optimizer performs on par or outperforms existing solvers, with the ability to scale beyond the state of the art to problems with millions of variables." In this comment, we show that a simple greedy algorithm, running in almost linear time, can find solutions for the MIS problem of much better quality than the GNN. The greedy algorithm is faster by a factor of 104 with respect to the GNN for problems with a million variables. We do not see any good reason for solving the MIS with these GNN, as well as for using a sledgehammer to crack nuts. In general, many claims of superiority of neural networks in solving combinatorial problems are at risk of being not solid enough, since we lack standard benchmarks based on really hard problems. We propose one of such hard benchmarks, and we hope to see future neural network optimizers tested on these problems before any claim of superiority is made.