論文の概要: 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頂点のグラフに一般化する場合、高いパフォーマンスを維持する。
関連論文リスト
- Graph Transformers for Large Graphs [57.19338459218758]
この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。
この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。
ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
論文 参考訳(メタデータ) (2023-12-18T11:19:23Z) - Efficient Heterogeneous Graph Learning via Random Projection [65.65132884606072]
不均一グラフニューラルネットワーク(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) - A Scalable Graph-Theoretic Distributed Framework for Cooperative
Multi-Agent Reinforcement Learning [18.04270684579841]
大規模協調型マルチエージェント強化学習(MARL)の課題は2つある。
第一のアプローチは、問題自体の本質的な分解可能性特性を利用する。
第二のアプローチは近似解を提供し、任意のグラフに適用できる。
論文 参考訳(メタデータ) (2022-02-26T03:01:51Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。