論文の概要: 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アルゴリズムよりも優れていることが示されている。
この議論はまた、ヒューリスティックスの評価に共通する誤解があることも強調している。
関連論文リスト
- Assessing and Enhancing Graph Neural Networks for Combinatorial Optimization: Novel Approaches and Application in Maximum Independent Set Problems [0.0]
Graph Neural Networks (GNNs)は、コンビネーション最適化(CO)問題の解決における研究者の約束を示す。
本研究では,最大独立集合(MIS)問題の解法におけるGNNの有効性について検討した。
論文 参考訳（メタデータ） (2024-11-06T09:12:31Z) - Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。
QUBO緩和による損失関数の最小化による教師なし学習に依存している。
実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
論文 参考訳（メタデータ） (2024-07-23T13:34:35Z) - LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。
本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文 参考訳（メタデータ） (2024-07-18T22:05:21Z) - Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs [40.99368410911088]
二次計画法 (QP) は非線形計画法において最も広く適用されている分野である。
QPタスクにグラフニューラルネットワーク(GNN)を適用する最近の研究は、GNNが最適化インスタンスの重要な特徴を捉えることができることを示している。
本稿では,2次プログラムの重要な特性を確実に表現できるメッセージパスGNNの存在を実証する。
論文 参考訳（メタデータ） (2024-06-09T23:57:47Z) - 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) - A Biased Graph Neural Network Sampler with Near-Optimal Regret [57.70126763759996]
グラフニューラルネットワーク(GNN)は、グラフおよびリレーショナルデータにディープネットワークアーキテクチャを適用する手段として登場した。
本論文では,既存の作業に基づいて,GNN近傍サンプリングをマルチアームバンディット問題として扱う。
そこで本研究では,分散を低減し,不安定かつ非限定的な支払いを回避すべく設計されたバイアスをある程度導入した報酬関数を提案する。
論文 参考訳（メタデータ） (2021-03-01T15:55:58Z) - 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 [19.600193617583955]
本稿では,ニューラルネットワークが複雑なアルゴリズムに適用される方法について述べる。
単一の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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。