論文の概要: Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration

• arxiv url: http://arxiv.org/abs/2205.14105v1
• Date: Fri, 27 May 2022 17:13:10 GMT
• ステータス: 処理完了
• システム内更新日: 2022-05-30 13:20:53.438751
• Title: Learning to Solve Combinatorial Graph Partitioning Problems via Efficient Exploration
• Title（参考訳）: 効率的な探索による組合せグラフ分割問題の解法
• Authors: Thomas D. Barrett, Christopher W.F. Parsonson and Alexandre Laterre
• Abstract要約: 実験により、ECORDは最大カット問題に対するRLアルゴリズムのための新しいSOTAを実現する。 最も近い競合と比較して、ECORDは最適性ギャップを最大73%削減する。
• 参考スコア（独自算出の注目度）: 72.15369769265398
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: From logistics to the natural sciences, combinatorial optimisation on graphs underpins numerous real-world applications. Reinforcement learning (RL) has shown particular promise in this setting as it can adapt to specific problem structures and does not require pre-solved instances for these, often NP-hard, problems. However, state-of-the-art (SOTA) approaches typically suffer from severe scalability issues, primarily due to their reliance on expensive graph neural networks (GNNs) at each decision step. We introduce ECORD; a novel RL algorithm that alleviates this expense by restricting the GNN to a single pre-processing step, before entering a fast-acting exploratory phase directed by a recurrent unit. Experimentally, ECORD achieves a new SOTA for RL algorithms on the Maximum Cut problem, whilst also providing orders of magnitude improvement in speed and scalability. Compared to the nearest competitor, ECORD reduces the optimality gap by up to 73% on 500 vertex graphs with a decreased wall-clock time. Moreover, ECORD retains strong performance when generalising to larger graphs with up to 10000 vertices.
• Abstract（参考訳）: ロジスティクスから自然科学まで、グラフ上の組合せ最適化は多くの実世界の応用を支える。 強化学習(rl)は、特定の問題構造に適応可能であり、これらの(しばしばnpハードな)問題に対して事前解決されたインスタンスを必要としないため、この設定で特に有望である。 しかし、最先端のSOTA(State-of-the-art)アプローチは一般的に、決定ステップ毎に高価なグラフニューラルネットワーク(GNN)に依存しているため、深刻なスケーラビリティの問題に悩まされる。 本稿では,gnnを単一前処理ステップに制限し,リカレントユニットが指示する高速探索フェーズに入ることで,このコストを軽減する新しいrlアルゴリズムであるecordを提案する。 実験的に、ECORDは最大カット問題において、RLアルゴリズムのための新しいSOTAを達成し、また、速度とスケーラビリティの桁違いの改善も提供する。 最寄りの競合と比較して、ECORDは、壁時計時間を短縮した500頂点グラフにおいて、最適性ギャップを最大73%削減する。 さらに、ECORDは、最大10000頂点のグラフに一般化する場合、高いパフォーマンスを維持する。

関連論文リスト

• MassiveGNN: Efficient Training via Prefetching for Massively Connected Distributed Graphs [11.026326555186333]
  本稿では,現在最先端のAmazon DistDGL分散GNNフレームワーク上に,パラメータ化された連続プリフェッチと消去方式を提案する。 NERSC(National Energy Research Scientific Computing Center)のPerlmutterスーパーコンピュータでは、エンドツーエンドのトレーニング性能が15～40%向上している。
  論文  参考訳（メタデータ） (2024-10-30T05:10:38Z)
• Enhancing GNNs Performance on Combinatorial Optimization by Recurrent Feature Update [0.09986418756990156]
  本稿では,組合せ最適化(CO)問題を効率よく解くために,GNNのパワーを活用して,QRF-GNNと呼ぶ新しいアルゴリズムを提案する。 QUBO緩和による損失関数の最小化による教師なし学習に依存している。 実験の結果、QRF-GNNは既存の学習ベースアプローチを大幅に上回り、最先端の手法に匹敵することがわかった。
  論文  参考訳（メタデータ） (2024-07-23T13:34:35Z)
• Pre-Training Identification of Graph Winning Tickets in Adaptive Spatial-Temporal Graph Neural Networks [5.514795777097036]
  Lottery Ticket hypothesis (LTH) から派生した Graph Winning Ticket (GWT) の概念を導入する。 事前決定された恒星トポロジーをGWTとしてトレーニング前に採用することにより、エッジの削減と効率的な情報伝達のバランスをとることができる。 提案手法は,48GBのメモリを備えた単一A6000を用いて,最大規模の時空間データセット上でASTGNNのトレーニングを可能にする。
  論文  参考訳（メタデータ） (2024-06-12T14:53:23Z)
• Spectral Greedy Coresets for Graph Neural Networks [61.24300262316091]
  ノード分類タスクにおける大規模グラフの利用は、グラフニューラルネットワーク(GNN)の現実的な応用を妨げる 本稿では,GNNのグラフコアセットについて検討し,スペクトル埋め込みに基づくエゴグラフの選択により相互依存の問題を回避する。 我々のスペクトルグレディグラフコアセット(SGGC)は、数百万のノードを持つグラフにスケールし、モデル事前学習の必要性を排除し、低ホモフィリーグラフに適用する。
  論文  参考訳（メタデータ） (2024-05-27T17:52:12Z)
• Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
  不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。 最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。 我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
  論文  参考訳（メタデータ） (2023-10-23T01:25:44Z)
• A Comprehensive Study on Large-Scale Graph Training: Benchmarking and Rethinking [124.21408098724551]
  グラフニューラルネットワーク(GNN)の大規模グラフトレーニングは、非常に難しい問題である 本稿では,既存の問題に対処するため,EnGCNという新たなアンサンブルトレーニング手法を提案する。 提案手法は,大規模データセット上でのSOTA(State-of-the-art)の性能向上を実現している。
  論文  参考訳（メタデータ） (2022-10-14T03:43:05Z)
• Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural Networks [52.566735716983956]
  本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。 LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。 提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
  論文  参考訳（メタデータ） (2022-07-18T14:23:31Z)
• Transferable Graph Optimizers for ML Compilers [18.353830282858834]
  計算グラフ最適化(GO)のためのエンドツーエンドで転送可能な深層強化学習法を提案する。 GOは個々のノードに対して自動回帰ではなく,グラフ全体の決定を生成する。 GOは、人間の専門家よりも21%改善し、先行技術よりも18%改善し、15倍早く収束する。
  論文  参考訳（メタデータ） (2020-10-21T20:28:33Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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