論文の概要: Cracking nuts with a sledgehammer: when modern graph neural networks do
worse than classical greedy algorithms
- arxiv url: http://arxiv.org/abs/2206.13211v1
- Date: Mon, 27 Jun 2022 11:54:01 GMT
- ステータス: 処理完了
- システム内更新日: 2022-06-28 21:44:06.809209
- Title: Cracking nuts with a sledgehammer: when modern graph neural networks do
worse than classical greedy algorithms
- Title（参考訳）: クラゲハンマーでナッツを割る:現代のグラフニューラルネットワークが古典的な欲求アルゴリズムよりも悪いとき
- Authors: Maria Chiara Angelini, Federico Ricci-Tersenghi
- Abstract要約: ほぼ線形時間で実行される単純なグリージーアルゴリズムは、GNNよりもはるかに優れた品質のMIS問題の解を見つけることができることを示す。
これらのGNNでMISを解く理由や、ハンマーを使ってナッツを割る理由がよく分からない。
- 参考スコア（独自算出の注目度）: 2.436681150766912
- License: http://creativecommons.org/licenses/by-sa/4.0/
- Abstract: The recent work ``Combinatorial Optimization with Physics-Inspired Graph
Neural Networks'' [Nat Mach Intell 4 (2022) 367] introduces a physics-inspired
unsupervised Graph Neural Network (GNN) to solve combinatorial optimization
problems on sparse graphs. To test the performances of these GNNs, the authors
of the work show numerical results for two fundamental problems: maximum cut
and maximum independent set (MIS). They conclude that "the graph neural network
optimizer performs on par or outperforms existing solvers, with the ability to
scale beyond the state of the art to problems with millions of variables."
In this comment, we show that a simple greedy algorithm, running in almost
linear time, can find solutions for the MIS problem of much better quality than
the GNN. The greedy algorithm is faster by a factor of $10^4$ with respect to
the GNN for problems with a million variables. We do not see any good reason
for solving the MIS with these GNN, as well as for using a sledgehammer to
crack nuts.
In general, many claims of superiority of neural networks in solving
combinatorial problems are at risk of being not solid enough, since we lack
standard benchmarks based on really hard problems. We propose one of such hard
benchmarks, and we hope to see future neural network optimizers tested on these
problems before any claim of superiority is made.
- Abstract（参考訳）: 近年の '‘Combinatorial Optimization with Physics-Inspired Graph Neural Networks'' [Nat Mach Intell 4 (2022) 367] は、スパースグラフの組合せ最適化問題を解決するために、物理にインスパイアされた教師なしグラフニューラルネットワーク (GNN) を導入している。
これらのGNNの性能をテストするため、著者らは最大カットと最大独立セット(MIS)という2つの基本的な問題に対して数値的な結果を示した。
彼らは、"グラフニューラルネットワークオプティマイザは、既存のソルバを同等あるいは上回るパフォーマンスで実行し、最先端のスケールを数百万の変数の問題に拡張する能力を持つ"と結論付けている。このコメントでは、ほぼ線形時間で実行される単純なグレディアルゴリズムが、GNNよりもはるかに優れた品質のMIS問題の解決策を見つけることができることを示した。
グレディアルゴリズムは、100万変数の問題に対して、GNNに対して10^4$の係数で高速である。
これらのGNNでMISを解く理由や、ハンマーを使ってナッツを割る理由がよく分からない。
一般に、組合せ問題の解決におけるニューラルネットワークの優位性の主張の多くは、本当に難しい問題に基づく標準ベンチマークが欠如しているため、十分に堅固でないリスクがある。
このようなハードベンチマークの1つを提案し、優越性が主張される前に、将来のニューラルネットワークオプティマイザがこれらの問題でテストされることを望んでいる。
関連論文リスト
- LinSATNet: The Positive Linear Satisfiability Neural Networks [116.65291739666303]
本稿では,ニューラルネットワークに人気の高い正の線形満足度を導入する方法について検討する。
本稿では,古典的なシンクホーンアルゴリズムを拡張し,複数の辺分布の集合を共同で符号化する,最初の微分可能満足層を提案する。
論文 参考訳（メタデータ） (2024-07-18T22:05:21Z) - 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) - Towards Better Out-of-Distribution Generalization of Neural Algorithmic
Reasoning Tasks [51.8723187709964]
ニューラルネットワーク推論タスクのOOD一般化について検討する。
目標は、ディープニューラルネットワークを使用して入出力ペアからアルゴリズムを学ぶことである。
論文 参考訳（メタデータ） (2022-11-01T18:33:20Z) - Inability of a graph neural network heuristic to outperform greedy
algorithms in solving combinatorial optimization problems like Max-Cut [0.0]
Nature Machine Intelligence 4, 367 (2022) において、Schuetzらは、様々な古典的なNPハード最適化問題を解決するためにニューラルネットワーク(GNN)を使用するスキームを提供している。
ネットワークがサンプルインスタンス上でどのようにトレーニングされているかを説明し、その結果のGNNは、広く使われているテクニックを適用して、その成功の可能性を判断する。
しかし, より綿密な検査により, このGNNの報告結果は勾配降下率よりもわずかに優れており, グリーディアルゴリズムにより性能が向上していることがわかった。
論文 参考訳（メタデータ） (2022-10-02T20:50:33Z) - Graph Neural Network Bandits [89.31889875864599]
グラフ構造データ上で定義された報酬関数を用いた帯域最適化問題を考察する。
この設定の主な課題は、大きなドメインへのスケーリングと、多くのノードを持つグラフへのスケーリングである。
グラフニューラルネットワーク(GNN)を用いて報酬関数を推定できることを示す。
論文 参考訳（メタデータ） (2022-07-13T18:12:36Z) - Can Graph Neural Networks Learn to Solve MaxSAT Problem? [22.528432249712637]
我々は,理論的および実践的両面から,マックスサット問題の解法学習におけるGNNの能力について検討した。
我々はベンチマークからMaxSATインスタンスの解法を学ぶために2種類のGNNモデルを構築し、実験によりGNNがMaxSAT問題を解く魅力的な可能性を示す。
また,アルゴリズムアライメント理論に基づいて,GNN が MaxSAT 問題のある程度の解法を学習できるという理論的な説明も提示する。
論文 参考訳（メタデータ） (2021-11-15T07:33:33Z) - Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。
最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
論文 参考訳（メタデータ） (2021-06-15T08:50:10Z) - The Surprising Power of Graph Neural Networks with Random Node
Initialization [54.4101931234922]
グラフニューラルネットワーク(GNN)は、関係データ上での表現学習に有効なモデルである。
標準 GNN はその表現力に制限があり、Weisfeiler-Leman グラフ同型(英語版)の能力以外の区別はできない。
本研究では,ランダムノード(RNI)を用いたGNNの表現力の解析を行う。
我々はこれらのモデルが普遍的であることを証明し、GNNが高次特性の計算に頼らない最初の結果である。
論文 参考訳（メタデータ） (2020-10-02T19:53:05Z) - 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) - Random Features Strengthen Graph Neural Networks [40.60905158071766]
グラフニューラルネットワーク(GNN)は、さまざまなグラフ学習タスクのための強力な機械学習モデルである。
本稿では,各ノードにランダムな特徴を加えるだけで,GNNが強力になることを示す。
本稿では, グラフ畳み込みネットワーク (GCN) やグラフ同型ネットワーク (GIN) など, 通常のGNNでは解けない様々な問題を, ランダムな特徴の追加によりGNNが解決できることを示す。
論文 参考訳（メタデータ） (2020-02-08T12:47:29Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。