# Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut

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

## Key facts

- Cited by 19 papers in the map (data through 14 Oct 2026).
- Builds on 1 of its 11 references that are in the map.
- First posted on arXiv 2 Oct 2022.

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

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)

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

- [Controlling Continuous Relaxation for Combinatorial Optimization](https://mlsanity.com/paper/2309.16965/) (2023)
- [Message Passing Variational Autoregressive Network for Solving Intractable Ising Models](https://mlsanity.com/paper/2404.06225/) (2024)
- [Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems](https://mlsanity.com/paper/2303.12096/) (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)
- [Deep reinforced learning heuristic tested on spin-glass ground states: The larger picture](https://mlsanity.com/paper/2302.10848/) (2023)
- [Decision-focused Graph Neural Networks for Combinatorial Optimization](https://mlsanity.com/paper/2406.03647/) (2024)
- [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)
- [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)
- [Binarizing Physics-Inspired GNNs for Combinatorial Optimization](https://mlsanity.com/paper/2507.13703/) (2025)
- [Learning Structural Hardness for Combinatorial Auctions: Instance-Dependent Algorithm Selection via Graph Neural Networks](https://mlsanity.com/paper/2602.14772/) (2026)
- [Graph neural networks and the energetic cavity method for combinatorial optimization](https://mlsanity.com/paper/2609.07456/) (2026)

## Abstract (arXiv)

In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme to employ graph neural networks (GNN) as a heuristic to solve a variety of classical, NP-hard combinatorial optimization problems. It describes how the network is trained on sample instances and the resulting GNN heuristic is evaluated applying widely used techniques to determine its ability to succeed. Clearly, the idea of harnessing the powerful abilities of such networks to ``learn'' the intricacies of complex, multimodal energy landscapes in such a hands-off approach seems enticing. And based on the observed performance, the heuristic promises to be highly scalable, with a computational cost linear in the input size n, although there is likely a significant overhead in the pre-factor due to the GNN itself. However, closer inspection shows that the reported results for this GNN are only minutely better than those for gradient descent and get outperformed by a greedy algorithm, for example, for Max-Cut. The discussion also highlights what I believe are some common misconceptions in the evaluations of heuristics.