# Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~citeschuetz2022combinatorial,citeangelini2023modern,citeschuetz2023reply

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 9 of its 26 references that are in the map.
- First posted on arXiv 5 Jun 2023.

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

- [Combinatorial Optimization with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2107.01188/) (2021)
- [Modern graph neural networks do worse than classical greedy algorithms in solving combinatorial optimization problems like maximum independent set](https://mlsanity.com/paper/2206.13211/) (2022)
- [Graph Coloring with Physics-Inspired Graph Neural Networks](https://mlsanity.com/paper/2202.01606/) (2022)
- [Limits of local algorithms over sparse random graphs](https://mlsanity.com/paper/1304.1831/) (2013)
- [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)
- [Optimal Low-Degree Hardness of Maximum Independent Set](https://mlsanity.com/paper/2010.06563/) (2020)
- [Local algorithms for independent sets are half-optimal](https://mlsanity.com/paper/1402.0485/) (2014)
- [Tight Lipschitz Hardness for Optimizing Mean Field Spin Glasses](https://mlsanity.com/paper/2110.07847/) (2021)
- [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)

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

- [Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods](https://mlsanity.com/paper/2310.05309/) (2023)

## Abstract (arXiv)

Recently graph neural network (GNN) based algorithms were proposed to solve a variety of combinatorial optimization problems, including Maximum Cut problem, Maximum Independent Set problem and similar other problems~citeschuetz2022combinatorial,citeschuetz2022graph. The publication~citeschuetz2022combinatorial stirred a debate whether GNN based method was adequately benchmarked against best prior methods. In particular, critical commentaries~citeangelini2023modern and~citeboettcher2023inability point out that simple greedy algorithm performs better than GNN in the setting of random graphs, and in fact stronger algorithmic performance can be reached with more sophisticated methods. A response from the authors~citeschuetz2023reply pointed out that GNN performance can be improved further by tuning up the parameters better. We do not intend to discuss the merits of arguments and counter-arguments in~citeschuetz2022combinatorial,citeangelini2023modern,citeboettcher2023inability,citeschuetz2023reply. Rather in this note we establish a fundamental limitation for running GNN on random graphs considered in these references, for a broad range of choices of GNN architecture. These limitations arise from the presence of the Overlap Gap Property (OGP) phase transition, which is a barrier for many algorithms, both classical and quantum. As we demonstrate in this paper, it is also a barrier to GNN due to its local structure. We note that at the same time known algorithms ranging from simple greedy algorithms to more sophisticated algorithms based on message passing, provide best results for these problems up to the OGP phase transition. This leaves very little space for GNN to outperform the known algorithms, and based on this we side with the conclusions made in~citeangelini2023modern and~citeboettcher2023inability.