論文の概要: 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-正則グラフの集合は,ベンチマークインスタンスの普遍的な集合を提供しておらず,また,欲欲的ヒューリスティックスが普遍的なアルゴリズムベースラインを提供していないことを示す。 最後に、グラフニューラルネットワークの内部(並列)解剖学は、欲望アルゴリズムの(系列的な)性質とは大きく異なり、グラフニューラルネットワークが並列テンパリングのような既存のヒューリスティックに比べて優れたスケーラビリティの可能性を実証していることを強調する。 結論として,本研究の概念的新しさを議論し,その拡張の可能性について概説する。

関連論文リスト

• Graph as a feature: improving node classification with non-neural graph-aware logistic regression [2.952177779219163]
  Graph-aware Logistic Regression (GLR) はノード分類タスク用に設計された非神経モデルである。 GNNにアクセスできる情報のごく一部しか使わない従来のグラフアルゴリズムとは異なり、提案モデルではノードの特徴とエンティティ間の関係を同時に活用する。
  論文  参考訳（メタデータ） (2024-11-19T08:32:14Z)
• 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)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  機械学習の幅広い問題にまたがる正規化誤差フィードバックアルゴリズムに対する収束の最初の証明を提供する。 提案手法では,許容可能なステップサイズが大きくなったため,新しい正規化エラーフィードバックアルゴリズムは,各種タスクにおける非正規化エラーよりも優れていた。
  論文  参考訳（メタデータ） (2024-10-22T10:19:27Z)
• Unitary convolutions for learning on graphs and groups [0.9899763598214121]
  我々は、訓練中により安定したより深いネットワークを可能にするユニタリグループ畳み込みについて研究する。 論文の主な焦点はグラフニューラルネットワークであり、ユニタリグラフの畳み込みがオーバー・スムーシングを確実に回避していることを示す。 実験結果から,ベンチマークデータセット上でのユニタリグラフ畳み込みネットワークの競合性能が確認できた。
  論文  参考訳（メタデータ） (2024-10-07T21:09:14Z)
• Improving the interpretability of GNN predictions through conformal-based graph sparsification [9.550589670316523]
  グラフニューラルネットワーク(GNN)は、グラフ分類タスクの解決において最先端のパフォーマンスを達成した。 エッジやノードを除去することで,最も予測可能なサブグラフを見つけるGNNエンハンチング手法を提案する。 我々は、共形予測に基づく報奨関数で得られる二段階最適化を解決するために強化学習を頼りにしている。
  論文  参考訳（メタデータ） (2024-04-18T17:34:47Z)
• Generalization in Graph Neural Networks: Improved PAC-Bayesian Bounds on Graph Diffusion [17.70434437597516]
  本稿では,グラフニューラルネットワークの特徴拡散行列の最大特異値でスケールする一般化境界について述べる。 これらの境界は実世界のグラフの以前の境界よりも数値的にはるかに小さい。 ヘッセン語を用いた雑音摂動に対するグラフニューラルネットワークの安定性を測定する。
  論文  参考訳（メタデータ） (2023-02-09T05:54:17Z)
• 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)
• 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)

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

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