Barriers for the performance of graph neural networks (GNN) in discrete random structures.
Barriers for the performance of graph neural networks (GNN) in discrete random structures.
复制标题
DOI：
10.1073/pnas.2314092120
复制
发表时间：
2023-11-14
影响因子：
11.1
通讯作者：
Weitz, David
中科院分区：
文献类型：
--
作者：
Weitz, David
最近，提出了基于图神经网络（GNN）的算法来解决各种组合优化问题[M. J. Schuetz、J. K. Brubaker、H. G. Katzgraber、Nat。马赫。 Intel.4, 367–377 (2022)]。 GNN 特别在这些问题的随机生成实例上进行了测试。出版物[M. J. Schuetz、J. K. Brubaker、H. G. Katzgraber、Nat。马赫。 Intel.4, 367–377 (2022)] 引发了关于基于 GNN 的方法是否与最佳先验方法进行了充分基准测试的争论。特别是批评性评论[M. C. Angelini，F. Ricci-Tersenghi，Nat。马赫。 Intel.5, 29–31 (2023)] 和 [S.博彻、纳特.马赫。 Intel.5, 24–25 (2023)]指出简单的贪心算法比 GNN 表现更好。我们无意讨论这些论文中的论点和反论点的优点。相反，在本文中，我们为在这些参考文献中考虑的随机实例上运行 GNN 建立了一个基本限制，以实现 GNN 架构的广泛选择。具体来说，当 GNN 的深度不随图大小缩放时，这些障碍成立（我们注意到 [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell.4, 367–377 (2022)] 的实验中使用了深度 2），而且重要的是，无论 GNN 架构的任何其他参数如何，这些障碍都成立。这些限制是由于重叠间隙特性（OGP）相变的存在而产生的，这对许多算法来说是一个障碍，包括重要的局部算法，GNN 就是一个例子。与此同时，在 GNN 引入之前已知的一些算法为这些问题提供了最佳结果，直至 OGP 相变。这使得 GNN 超越已知算法的空间非常小，基于此，我们支持 [M. C. Angelini，F. Ricci-Tersenghi，Nat。马赫。 Intel.5, 29–31 (2023)] 和 [S.博彻、纳特.马赫。 Intel.5, 24–25 (2023)]。
Recently, graph neural network (GNN)-based algorithms were proposed to solve a variety of combinatorial optimization problems [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell.4, 367–377 (2022)]. GNN was tested in particular on randomly generated instances of these problems. The publication [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell.4, 367–377 (2022)] stirred a debate whether the GNN-based method was adequately benchmarked against best prior methods. In particular, critical commentaries [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher, Nat. Mach. Intell.5, 24–25 (2023)] point out that a simple greedy algorithm performs better than the GNN. We do not intend to discuss the merits of arguments and counterarguments in these papers. Rather, in this note, we establish a fundamental limitation for running GNN on random instances considered in these references, for a broad range of choices of GNN architecture. Specifically, these barriers hold when the depth of GNN does not scale with graph size (we note that depth 2 was used in experiments in [M. J. Schuetz, J. K. Brubaker, H. G. Katzgraber, Nat. Mach. Intell.4, 367–377 (2022)]), and importantly, these barriers hold regardless of any other parameters of GNN architecture. These limitations arise from the presence of the overlap gap property (OGP) phase transition, which is a barrier for many algorithms, including importantly local algorithms, of which GNN is an example. At the same time, some algorithms known prior to the introduction of GNN 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 [M. C. Angelini, F. Ricci-Tersenghi, Nat. Mach. Intell.5, 29–31 (2023)] and [S. Boettcher, Nat. Mach. Intell.5, 24–25 (2023)].
登录
查看更多内容
影响因子：
2.3
作者：
Chen, Wei-Kuo;Gamarnik, David;Rahman, Mustazee
通讯作者：
Rahman, Mustazee
影响因子：
2.3
作者：
Bayati, Mohsen;Gamarnik, David;Tetali, Prasad
通讯作者：
Tetali, Prasad
影响因子：
2.3
作者：
Rahman, Mustazee;Virag, Balint
通讯作者：
Virag, Balint
影响因子：
1
作者：
Coppersmith, D;Gamarnik, D;Sorkin, GB
通讯作者：
Sorkin, GB
影响因子：
1.4
作者：
FRIEZE, AM;LUCZAK, T
通讯作者：
LUCZAK, T