論文の概要: Inability of a graph neural network heuristic to outperform greedy
algorithms in solving combinatorial optimization problems like Max-Cut
- arxiv url: http://arxiv.org/abs/2210.00623v1
- Date: Sun, 2 Oct 2022 20:50:33 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-04 14:48:58.536272
- Title: Inability of a graph neural network heuristic to outperform greedy
algorithms in solving combinatorial optimization problems like Max-Cut
- Title（参考訳）: max-cut のような組合せ最適化問題の解法におけるグラフニューラルネットワークのヒューリスティック性
- Authors: Stefan Boettcher (Emory University)
- Abstract要約: Nature Machine Intelligence 4, 367 (2022) において、Schuetzらは、様々な古典的なNPハード最適化問題を解決するためにニューラルネットワーク(GNN)を使用するスキームを提供している。
ネットワークがサンプルインスタンス上でどのようにトレーニングされているかを説明し、その結果のGNNは、広く使われているテクニックを適用して、その成功の可能性を判断する。
しかし, より綿密な検査により, このGNNの報告結果は勾配降下率よりもわずかに優れており, グリーディアルゴリズムにより性能が向上していることがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In Nature Machine Intelligence 4, 367 (2022), Schuetz et al provide a scheme
to employ graph neural networks (GNN) as a heuristic to solve a variety of
classical, NP-hard combinatorial optimization problems. It describes how the
network is trained on sample instances and the resulting GNN heuristic is
evaluated applying widely used techniques to determine its ability to succeed.
Clearly, the idea of harnessing the powerful abilities of such networks to
``learn'' the intricacies of complex, multimodal energy landscapes in such a
hands-off approach seems enticing. And based on the observed performance, the
heuristic promises to be highly scalable, with a computational cost linear in
the input size $n$, although there is likely a significant overhead in the
pre-factor due to the GNN itself. However, closer inspection shows that the
reported results for this GNN are only minutely better than those for gradient
descent and get outperformed by a greedy algorithm, for example, for Max-Cut.
The discussion also highlights what I believe are some common misconceptions in
the evaluations of heuristics.
- Abstract（参考訳）: Nature Machine Intelligence 4, 367 (2022) において、Schuetzらはグラフニューラルネットワーク(GNN)を様々な古典的なNPハード組合せ最適化問題を解くためのヒューリスティックなスキームを提供する。
ネットワークをサンプルインスタンスでトレーニングし、その結果のGNNヒューリスティックを評価し、広く使われているテクニックを適用して、その成功の能力を決定する。
明らかに、このようなネットワークの強力な能力を利用して、このようなハンズオフアプローチで複雑でマルチモーダルなエネルギーランドスケープの複雑さを ‘learn’' させるというアイデアは魅力的だ。
そして、観測されたパフォーマンスに基づいて、ヒューリスティックは高いスケーラビリティを約束しており、入力サイズで線形な計算コストは$n$である。
しかし、より綿密な検査では、GNNの報告結果が勾配降下の結果よりもわずかに優れており、例えばMax-Cutのgreedyアルゴリズムよりも優れていることが示されている。
この議論はまた、ヒューリスティックスの評価に共通する誤解があることも強調している。
関連論文リスト
- Sparsity May Cry: Let Us Fail (Current) Sparse Neural Networks Together! [100.19080749267316]
Sparsity May Cry"ベンチマーク(SMC-Bench)は、慎重に計算された4つのタスクと10のデータセットのコレクションである。
SMC-Benchは、よりスケーラブルで一般化可能なスパースアルゴリズムの開発を奨励するように設計されている。
論文 参考訳（メタデータ） (2023-03-03T18:47:21Z) - Learning Branching Heuristics from Graph Neural Networks [1.4660170768702356]
まず,確率論的手法を用いて設計した新しいグラフニューラルネットワーク(GNN)モデルを提案する。
我々のアプローチは、AIで使用される古典的なバックトラッキングアルゴリズムの強化にGNNを適用する新しい方法を導入する。
論文 参考訳（メタデータ） (2022-11-26T00:01:01Z) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Deep Architecture Connectivity Matters for Its Convergence: A
Fine-Grained Analysis [94.64007376939735]
我々は、勾配降下訓練におけるディープニューラルネットワーク(DNN)の収束に対する接続パターンの影響を理論的に特徴づける。
接続パターンの単純なフィルタリングによって、評価対象のモデルの数を削減できることが示される。
論文 参考訳（メタデータ） (2022-05-11T17:43:54Z) - Graph Neural Network based scheduling : Improved throughput under a
generalized interference model [3.911413922612859]
本稿では,アドホックネットワークのためのグラフ畳み込みニューラルネットワーク(GCN)に基づくスケジューリングアルゴリズムを提案する。
この研究で注目すべき特徴は、ニューラルネットワークをトレーニングするためにラベル付きデータセット(NP-hard to compute)を必要としないことである。
論文 参考訳（メタデータ） (2021-10-31T10:36:11Z) - Leveraging power grid topology in machine learning assisted optimal
power flow [0.5076419064097734]
機械学習支援最適電力フロー(OPF)は、非線形および非制約電力フロー問題の計算複雑性を低減することを目的としている。
我々は,機械支援OPFの2つの基本的アプローチに対して,さまざまなFCNN,CNN,GNNモデルの性能を評価する。
相互接続されたユーティリティを持ついくつかの合成格子に対して,特徴変数と対象変数の間の局所性特性は乏しいことを示す。
論文 参考訳（メタデータ） (2021-10-01T10:39:53Z) - A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
グラフニューラルネットワーク(GNN)は、グラフおよびリレーショナルデータにディープネットワークアーキテクチャを適用する手段として登場した。
本論文では,既存の作業に基づいて,GNN近傍サンプリングをマルチアームバンディット問題として扱う。
そこで本研究では,分散を低減し,不安定かつ非限定的な支払いを回避すべく設計されたバイアスをある程度導入した報酬関数を提案する。
論文 参考訳（メタデータ） (2021-03-01T15:55:58Z) - Graph Neural Networks for Scalable Radio Resource Management:
Architecture Design and Theoretical Analysis [31.372548374969387]
本稿では,大規模無線資源管理問題にグラフニューラルネットワーク(GNN)を適用することを提案する。
提案手法はスケーラビリティが高く,1つのGPU上で1,000ドルのトランシーバペアを6ミリ秒以内で行う干渉チャネルにおけるビームフォーミング問題を解くことができる。
論文 参考訳（メタデータ） (2020-07-15T11:43:32Z) - 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) - Neural Bipartite Matching [0.0]
本稿では,ニューラルネットワークが複雑なアルゴリズムに適用される方法について述べる。
単一のGNNから生成された機能のみに基づいて、ニューラル実行によって実現される。
評価の結果,ネットワークがほぼ100%の時間で最適なマッチングを達成できることが示唆された。
論文 参考訳（メタデータ） (2020-05-22T17:50:38Z) - Towards an Efficient and General Framework of Robust Training for Graph
Neural Networks [96.93500886136532]
グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。
GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。
我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-25T15:17:58Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。