# Reply to: Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems

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

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- Builds on 8 of its 11 references that are in the map.
- First posted on arXiv 3 Feb 2023.

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

- [How Powerful are Graph Neural Networks?](https://mlsanity.com/paper/1810.00826/) (2018)
- [Geometric Deep Learning: Grids, Groups, Graphs, Geodesics, and Gauges](https://mlsanity.com/paper/2104.13478/) (2021)
- [Understanding over-squashing and bottlenecks on graphs via curvature](https://mlsanity.com/paper/2111.14522/) (2021)
- [DistDGL: Distributed Graph Neural Network Training for Billion-Scale Graphs](https://mlsanity.com/paper/2010.05337/) (2020)
- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Inability of a graph neural network heuristic to outperform greedy algorithms in solving combinatorial optimization problems like Max-Cut](https://mlsanity.com/paper/2210.00623/) (2022)
- [The Potential of Quantum Annealing for Rapid Solution Structure Identification](https://mlsanity.com/paper/1912.01759/) (2019)

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

- [Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update](https://mlsanity.com/paper/2407.16468/) (2024)
- [Benchmarking Graph Neural Networks in Solving Hard Constraint Satisfaction Problems](https://mlsanity.com/paper/2602.18419/) (2026)
- [Graph Neural Networks are Heuristics](https://mlsanity.com/paper/2601.13465/) (2026)
- [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)

## Abstract (arXiv)

We provide a comprehensive reply to the comment written by Stefan Boettcher [arXiv:2210.00623] and argue that the comment singles out one particular non-representative example problem, entirely focusing on the maximum cut problem (MaxCut) on sparse graphs, for which greedy algorithms are expected to perform well. Conversely, we highlight the broader algorithmic development underlying our original work, and (within our original framework) provide additional numerical results showing sizable improvements over our original data, thereby refuting the comment's original performance statements. Furthermore, it has already been shown that physics-inspired graph neural networks (PI-GNNs) can outperform greedy algorithms, in particular on hard, dense instances. We also argue that the internal (parallel) anatomy of graph neural networks is very different from the (sequential) nature of greedy algorithms, and (based on their usage at the scale of real-world social networks) point out that graph neural networks have demonstrated their potential for superior scalability compared to existing heuristics such as extremal optimization. Finally, we conclude highlighting the conceptual novelty of our work and outline some potential extensions.