English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Recently graph neural network (GNN) based algorithms were proposed to solve avariety of combinatorial optimization problems, including Maximum Cut problem,Maximum Independent Set problem and similar otherproblems~\cite{schuetz2022combinatorial},\cite{schuetz2022graph}.  The publication~\cite{schuetz2022combinatorial} stirred a debate whether GNNbased method was adequately benchmarked against best prior methods. Inparticular, critical commentaries~\cite{angelini2023modern}and~\cite{boettcher2023inability} point out that simple greedy algorithmperforms better than GNN in the setting of random graphs, and in fact strongeralgorithmic performance can be reached with more sophisticated methods. Aresponse from the authors~\cite{schuetz2023reply} pointed out that GNNperformance can be improved further by tuning up the parameters better.  We do not intend to discuss the merits of arguments and counter-argumentsin~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{boettcher2023inability},\cite{schuetz2023reply}.Rather in this note we establish a fundamental limitation for running GNN onrandom graphs considered in these references, for a broad range of choices ofGNN architecture. These limitations arise from the presence of the Overlap GapProperty (OGP) phase transition, which is a barrier for many algorithms, bothclassical and quantum. As we demonstrate in this paper, it is also a barrier toGNN due to its local structure. We note that at the same time known algorithmsranging from simple greedy algorithms to more sophisticated algorithms based onmessage passing, provide best results for these problems \emph{up to} the OGPphase transition. This leaves very little space for GNN to outperform the knownalgorithms, and based on this we side with the conclusions madein~\cite{angelini2023modern} and~\cite{boettcher2023inability}.

Barriers for the performance of graph neural networks (GNN) in discrete  random structures. A comment  on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}