Fugu-MT 論文翻訳(概要): Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}

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

arxiv url: http://arxiv.org/abs/2306.02555v1
Date: Mon, 5 Jun 2023 03:05:43 GMT
ステータス: 処理完了
システム内更新日: 2023-06-06 17:08:38.346933
Title: Barriers for the performance of graph neural networks (GNN) in discrete random structures. A comment on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}
Title（参考訳）: 離散ランダム構造におけるグラフニューラルネットワーク(GNN)の性能の障壁 an comment on~\cite{schuetz2022combinatorial},\cite{angelini2023modern},\cite{schuetz2023reply}
Authors: David Gamarnik
Abstract要約: 近年,グラフニューラルネットワーク(GNN)に基づくアルゴリズムが提案され,様々な最適化課題が解決された。 citeschuetz2022combinatorialは、GNNベースの手法が最良の先行手法に対して適切にベンチマークされているかどうかの議論を巻き起こした。
参考スコア（独自算出の注目度）: 8.046124216594908
License: http://creativecommons.org/licenses/by/4.0/
Abstract: 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}.
Abstract（参考訳）: 近年,グラフニューラルネットワーク(gnn)に基づくアルゴリズムが提案され,最大カット問題,最大独立集合問題,および同様の問題である----cite{schuetz2022combinatorial},-cite{schuetz2022graph} など,様々な組合せ最適化問題を解く。 The publication~\cite{schuetz2022combinatorial} は、GNN ベースの手法が最高の先行手法に対して適切にベンチマークされているかどうかの議論を巻き起こした。特に、批判的なコメンタリー~\cite{angelini2023 Modern} と~\cite{boettcher2023inability} は、単純なグレディアルゴリズムはランダムグラフの設定においてGNNよりも優れた性能を示し、実際より洗練された手法でより強いアルゴリズム性能に到達することができる。著者たちの反応は~\cite{schuetz2023reply}は、パラメータをチューニングすることでgnnのパフォーマンスをさらに改善できると指摘した。議論と反論のメリットを論じるつもりはありません。~\cite{schuetz2022combinatorial},\cite{angelini2023 Modern},\cite{boettcher2023inability},\cite{schuetz2023reply}。むしろ、これらの参照で考慮されたランダムグラフ上でGNNを実行するための基本的な制限を、GNNアーキテクチャの幅広い選択のために確立する。これらの制限は、古典的および量子的な多くのアルゴリズムにとって障壁となるオーバーラップギャップ特性(ogp)相転移の存在から生じる。本稿では,gnnの局所的な構造から,gnnへの障壁でもあることを示す。我々は、単純な欲望アルゴリズムから、メッセージパッシングに基づくより洗練されたアルゴリズムまで、既知のアルゴリズムが、これらの問題に対して、ogp位相遷移の最良の結果をもたらすことに注意する。このことは、GNNが既知のアルゴリズムより優れる余地をほとんど残さず、この結果に基づいて、~\cite{angelini2023 Modern} と~\cite{boettcher2023inability} の結論に沿う。

関連論文リスト

Combinatorial Optimization with Automated Graph Neural Networks [28.19349828026972]
NP-hard CO 問題,すなわち textbfAutoGNP を解決するために,textbfAUTOmated textbfGNN のクラスを新たに提案する。 AutoGNPの考え方は、グラフニューラルアーキテクチャ検索アルゴリズムを使用して、与えられたNPハード最適化問題に対して最適なGNNを自動的に見つけることである。
論文参考訳（メタデータ） (2024-06-05T02:43:41Z)
Robust Graph Neural Network based on Graph Denoising [10.564653734218755]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータセットを扱う学習問題に対して、悪名高い代替手段として登場した。本研究は,観測トポロジにおける摂動の存在を明示的に考慮した,GNNの堅牢な実装を提案する。
論文参考訳（メタデータ） (2023-12-11T17:43:57Z)
T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文参考訳（メタデータ） (2023-10-05T02:58:29Z)
Towards Better Out-of-Distribution Generalization of Neural Algorithmic Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文参考訳（メタデータ） (2022-11-01T18:33:20Z)
Robust Graph Neural Networks using Weighted Graph Laplacian [1.8292714902548342]
グラフニューラルネットワーク(GNN)は、入力データにおけるノイズや敵攻撃に対して脆弱である。重み付きラプラシアンGNN(RWL-GNN)として知られるGNNの強化のための汎用フレームワークを提案する。
論文参考訳（メタデータ） (2022-08-03T05:36:35Z)
Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文参考訳（メタデータ） (2022-07-13T18:12:36Z)
Graph Neural Networks are Dynamic Programmers [0.0]
グラフニューラルネットワーク(GNN)は動的プログラミング(DP)と一致すると主張されるここでは、理論と抽象代数学の手法を用いて、GNNとDPの間に複雑な関係が存在することを示す。
論文参考訳（メタデータ） (2022-03-29T13:27:28Z)
Exploiting Neighbor Effect: Conv-Agnostic GNNs Framework for Graphs with Heterophily [58.76759997223951]
我々はフォン・ノイマンエントロピーに基づく新しい計量を提案し、GNNのヘテロフィリー問題を再検討する。また、異種データセット上でのほとんどのGNNの性能を高めるために、Conv-Agnostic GNNフレームワーク(CAGNN)を提案する。
論文参考訳（メタデータ） (2022-03-19T14:26:43Z)
VQ-GNN: A Universal Framework to Scale up Graph Neural Networks using Vector Quantization [70.8567058758375]
VQ-GNNは、Vector Quantization(VQ)を使用して、パフォーマンスを損なうことなく、畳み込みベースのGNNをスケールアップするための普遍的なフレームワークである。我々のフレームワークは,グラフ畳み込み行列の低ランク版と組み合わせた量子化表現を用いて,GNNの「隣の爆発」問題を回避する。
論文参考訳（メタデータ） (2021-10-27T11:48:50Z)
BlockGNN: Towards Efficient GNN Acceleration Using Block-Circulant Weight Matrices [9.406007544032848]
グラフニューラルネットワーク(GNN)は、非ユークリッドグラフデータを分析するための最先端のアルゴリズムです。リアルタイムにGNNを推論する方法は、リソース制限のあるエッジコンピューティングプラットフォームでは難しい問題となっている。効率的なGNN加速を実現するソフトウェアハードウェアの共同設計手法であるBlockGNNを提案する。
論文参考訳（メタデータ） (2021-04-13T14:09:22Z)
Optimization and Generalization Analysis of Transduction through Gradient Boosting and Application to Multi-scale Graph Neural Networks [60.22494363676747]
現在のグラフニューラルネットワーク(GNN)は、オーバースムーシング(over-smoothing)と呼ばれる問題のため、自分自身を深くするのは難しいことが知られている。マルチスケールGNNは、オーバースムーシング問題を緩和するための有望なアプローチである。マルチスケールGNNを含むトランスダクティブ学習アルゴリズムの最適化と一般化を保証する。
論文参考訳（メタデータ） (2020-06-15T17:06:17Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。