Barriers for the performance of graph neural networks (GNN) in discrete
  random structures. A comment
  on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}
David Gamarnik
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~\cite{schuetz2022combinatorial},\cite{schuetz2022graph}.
  The publication~\cite{schuetz2022combinatorial} stirred a debate whether GNN
based method was adequately benchmarked against best prior methods. In
particular, critical commentaries~\cite{angelini2023modern}
and~\cite{boettcher2023inability} 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~\cite{schuetz2023reply} 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~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{boettcher2023inability},\cite{schuetz2023reply}.
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 \emph{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~\cite{angelini2023modern} and~\cite{boettcher2023inability}.