論文の概要: Reply to: Modern graph neural networks do worse than classical greedy
algorithms in solving combinatorial optimization problems like maximum
independent set
- arxiv url: http://arxiv.org/abs/2302.03602v1
- Date: Fri, 3 Feb 2023 17:21:02 GMT
- ステータス: 処理完了
- システム内更新日: 2023-02-08 15:39:40.996352
- Title: Reply to: Modern graph neural networks do worse than classical greedy
algorithms in solving combinatorial optimization problems like maximum
independent set
- Title(参考訳): 答え: 現代のグラフニューラルネットワークは、最大独立集合のような組合せ最適化問題を解く際、古典的な欲望アルゴリズムよりも悪い。
- Authors: Martin J. A. Schuetz, J. Kyle Brubaker, Helmut G. Katzgraber
- Abstract要約: 我々は、Chiara Angelini と Federico Ricci-Tersenghi のコメントが、特定の非表現的な例を1つ挙げていると主張している。
本稿では,Angelini と Ricci-Tersenghi が提示した結果よりも,実行時のスケーリングが優れていることを示す。
我々は、グラフニューラルネットワークの内部(並列)解剖は、グリードアルゴリズムの(逐次)性質とは大きく異なると論じる。
- 参考スコア(独自算出の注目度): 0.0
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide a comprehensive reply to the comment written by Chiara Angelini
and Federico Ricci-Tersenghi [arXiv:2206.13211] and argue that the comment
singles out one particular non-representative example problem, entirely
focusing on the maximum independent set (MIS) on sparse graphs, for which
greedy algorithms are expected to perform well. Conversely, we highlight the
broader algorithmic development underlying our original work, and (within our
original framework) provide additional numerical results showing sizable
improvements over our original results, thereby refuting the comment's
performance statements. We also provide results showing run-time scaling
superior to the results provided by Angelini and Ricci-Tersenghi. Furthermore,
we show that the proposed set of random d-regular graphs does not provide a
universal set of benchmark instances, nor do greedy heuristics provide a
universal algorithmic baseline. Finally, we argue that the internal (parallel)
anatomy of graph neural networks is very different from the (sequential) nature
of greedy algorithms and emphasize that graph neural networks have demonstrated
their potential for superior scalability compared to existing heuristics such
as parallel tempering. We conclude by discussing the conceptual novelty of our
work and outline some potential extensions.
- Abstract(参考訳): 我々は、Chiara Angelini と Federico Ricci-Tersenghi (arXiv:2206.13211) によって書かれたコメントに対する包括的な回答を提供し、このコメントは、厳密なアルゴリズムがうまく動作するであろうスパースグラフ上の最大独立集合 (MIS) に完全に焦点を絞って、特定の非表現的な例問題を単体化していると主張する。
逆に、元の作業の基盤となるより広範なアルゴリズム開発を強調し、(元のフレームワークで)元の結果よりも大きな改善を示す追加の数値結果を提供し、コメントのパフォーマンスステートメントを否定する。
また,Angelini と Ricci-Tersenghi による結果よりも実行時のスケーリングが優れていることを示す。
さらに,提案するランダムなd-正則グラフの集合は,ベンチマークインスタンスの普遍的な集合を提供しておらず,また,欲欲的ヒューリスティックスが普遍的なアルゴリズムベースラインを提供していないことを示す。
最後に、グラフニューラルネットワークの内部(並列)解剖学は、欲望アルゴリズムの(系列的な)性質とは大きく異なり、グラフニューラルネットワークが並列テンパリングのような既存のヒューリスティックに比べて優れたスケーラビリティの可能性を実証していることを強調する。
結論として,本研究の概念的新しさを議論し,その拡張の可能性について概説する。
関連論文リスト
- Generalization Error of Graph Neural Networks in the Mean-field Regime [16.485222855592422]
本研究は,グラフニューラルネットワークを用いたグラフ分類タスクの一般化誤差を評価するための理論的枠組みを提供する。
グラフ畳み込みニューラルネットワークとメッセージパッシンググラフニューラルネットワークという,広く利用されている2種類のグラフニューラルネットワークについて検討する。
論文 参考訳(メタデータ) (2024-02-10T19:12:31Z) - Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on
Graph Diffusion [17.70434437597516]
本稿では,グラフニューラルネットワークの特徴拡散行列の最大特異値でスケールする一般化境界について述べる。
これらの境界は実世界のグラフの以前の境界よりも数値的にはるかに小さい。
ヘッセン語を用いた雑音摂動に対するグラフニューラルネットワークの安定性を測定する。
論文 参考訳(メタデータ) (2023-02-09T05:54:17Z) - 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) - Relation Embedding based Graph Neural Networks for Handling
Heterogeneous Graph [58.99478502486377]
我々は、同種GNNが不均一グラフを扱うのに十分な能力を持つように、シンプルで効率的なフレームワークを提案する。
具体的には、エッジ型関係と自己ループ接続の重要性を埋め込むために、関係1つのパラメータのみを使用する関係埋め込みベースのグラフニューラルネットワーク(RE-GNN)を提案する。
論文 参考訳(メタデータ) (2022-09-23T05:24:18Z) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - Counting Substructures with Higher-Order Graph Neural Networks:
Possibility and Impossibility Results [58.277290855841976]
グラフニューラルネットワーク(GNN)の計算コストと表現力のトレードオフについて検討する。
新しいモデルでは、$k$のサブグラフをカウントでき、低次GNNの既知の制限を克服できることを示す。
いくつかの場合において、提案アルゴリズムは既存の高階$k$-GNNに比べて計算量を大幅に削減することができる。
論文 参考訳(メタデータ) (2020-12-06T03:42:54Z) - Revisiting Graph Convolutional Network on Semi-Supervised Node
Classification from an Optimization Perspective [10.178145000390671]
グラフ畳み込みネットワーク(GCN)は、様々なグラフベースのタスクにおいて有望な性能を達成した。
しかし、より多くのレイヤを積み重ねる際には、過剰なスムーシングに悩まされる。
本稿では,この観測を定量的に研究し,より深いGCNに対する新たな洞察を開拓する。
論文 参考訳(メタデータ) (2020-09-24T03:36:43Z) - Towards Deeper Graph Neural Networks [63.46470695525957]
グラフ畳み込みは近傍の集約を行い、最も重要なグラフ操作の1つである。
いくつかの最近の研究で、この性能劣化は過度に滑らかな問題に起因している。
本研究では,大きな受容領域からの情報を適応的に組み込むディープ適応グラフニューラルネットワーク(DAGNN)を提案する。
論文 参考訳(メタデータ) (2020-07-18T01:11:14Z) - Bayesian Deep Learning and a Probabilistic Perspective of Generalization [56.69671152009899]
ディープアンサンブルはベイズ辺化を近似する有効なメカニズムであることを示す。
また,アトラクションの流域内での辺縁化により,予測分布をさらに改善する関連手法を提案する。
論文 参考訳(メタデータ) (2020-02-20T15:13:27Z) - Block-Approximated Exponential Random Graphs [77.4792558024487]
指数乱グラフ(ERG)の分野における重要な課題は、大きなグラフ上の非自明なERGの適合である。
本稿では,非自明なERGに対する近似フレームワークを提案する。
我々の手法は、数百万のノードからなるスパースグラフにスケーラブルである。
論文 参考訳(メタデータ) (2020-02-14T11:42:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。