論文の概要: Symmetry-preserving graph attention network to solve routing problems at multiple resolutions

• arxiv url: http://arxiv.org/abs/2310.15543v2
• Date: Sun, 19 Nov 2023 22:24:59 GMT
• ステータス: 処理完了
• システム内更新日: 2023-11-22 17:05:25.032487
• Title: Symmetry-preserving graph attention network to solve routing problems at multiple resolutions
• Title（参考訳）: 複数の解像度でのルーティング問題を解決する対称性保存グラフアテンションネットワーク
• Authors: Cong Dao Tran, Thong Bach, Truong Son Hy
• Abstract要約: 問題解決のために,最初の完全同変モデルとトレーニングを導入する。 入力グラフのマルチスケール構造を捉えることが不可欠である。 本稿では,Equi Graph Attention Network (mEGAT) アーキテクチャと組み合わせたマルチレゾリューション方式を提案する。
• 参考スコア（独自算出の注目度）: 1.9304772860080408
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Travelling Salesperson Problems (TSPs) and Vehicle Routing Problems (VRPs) have achieved reasonable improvement in accuracy and computation time with the adaptation of Machine Learning (ML) methods. However, none of the previous works completely respects the symmetries arising from TSPs and VRPs including rotation, translation, permutation, and scaling. In this work, we introduce the first-ever completely equivariant model and training to solve combinatorial problems. Furthermore, it is essential to capture the multiscale structure (i.e. from local to global information) of the input graph, especially for the cases of large and long-range graphs, while previous methods are limited to extracting only local information that can lead to a local or sub-optimal solution. To tackle the above limitation, we propose a Multiresolution scheme in combination with Equivariant Graph Attention network (mEGAT) architecture, which can learn the optimal route based on low-level and high-level graph resolutions in an efficient way. In particular, our approach constructs a hierarchy of coarse-graining graphs from the input graph, in which we try to solve the routing problems on simple low-level graphs first, then utilize that knowledge for the more complex high-level graphs. Experimentally, we have shown that our model outperforms existing baselines and proved that symmetry preservation and multiresolution are important recipes for solving combinatorial problems in a data-driven manner. Our source code is publicly available at https://github.com/HySonLab/Multires-NP-hard
• Abstract（参考訳）: トラベリングセールスパーソン問題 (TSP) と車両ルーティング問題 (VRP) は,機械学習 (ML) 手法の適応により,精度と計算時間を合理的に向上した。 しかし、以前の作品では、回転、翻訳、置換、スケーリングを含む、tspsとvrpから生じる対称性を完全に尊重していない。 本研究では,組合わせ問題を解くために,最初の完全同値モデルとトレーニングを導入する。 さらに、特に大きなグラフや長距離グラフの場合において、入力グラフのマルチスケール構造(ローカルからグローバル情報)を捉えることが不可欠であり、従来の手法は局所的あるいは準最適解に繋がるローカル情報のみを抽出することに限定されていた。 上記の制限に対処するため,マルチレゾリューション方式と等価グラフアテンションネットワーク(mEGAT)アーキテクチャを併用して,低レベルおよび高レベルグラフレゾリューションに基づく最適経路を効率的に学習する手法を提案する。 特に, 入力グラフから粗粒グラフの階層構造を構築し, まずは単純な低レベルグラフのルーティング問題を解き, その知識をより複雑な高レベルグラフに活用する。 実験により,本モデルが既存のベースラインより優れており,対称性の保存とマルチレゾリューションがデータ駆動方式で組合せ問題を解くための重要なレシピであることを実証した。 私たちのソースコードはhttps://github.com/HySonLab/Multires-NP-hardで公開されています。

関連論文リスト

• Learnable Graph Matching: A Practical Paradigm for Data Association [74.28753343714858]
  これらの問題に対処するための一般的な学習可能なグラフマッチング法を提案する。 提案手法は,複数のMOTデータセット上での最先端性能を実現する。 画像マッチングでは,一般的な屋内データセットであるScanNetで最先端の手法より優れている。
  論文  参考訳（メタデータ） (2023-03-27T17:39:00Z)
• Learning to Optimize Permutation Flow Shop Scheduling via Graph-based Imitation Learning [70.65666982566655]
  置換フローショップスケジューリング(PFSS)は製造業で広く使われている。 我々は,より安定かつ正確に収束を加速する専門家主導の模倣学習を通じてモデルを訓練することを提案する。 我々のモデルのネットワークパラメータはわずか37%に減少し、エキスパートソリューションに対する我々のモデルの解のギャップは平均6.8%から1.3%に減少する。
  論文  参考訳（メタデータ） (2022-10-31T09:46:26Z)
• MultiScale MeshGraphNets [65.26373813797409]
  我々はMeshGraphNetsからフレームワークを改善するための2つの補完的なアプローチを提案する。 まず、より粗いメッシュ上で高解像度システムの正確なサロゲートダイナミクスを学習できることを実証する。 次に、2つの異なる解像度でメッセージを渡す階層的アプローチ(MultiScale MeshGraphNets)を導入する。
  論文  参考訳（メタデータ） (2022-10-02T20:16:20Z)
• LeNSE: Learning To Navigate Subgraph Embeddings for Large-Scale Combinatorial Optimisation [6.316693022958222]
  ユークリッド部分グラフの埋め込みを地図として用いて,可能な部分グラフの空間をナビゲートする方法を学習する強化学習アルゴリズムを提案する。 LeNSEは、グラフ全体への埋め込みの実行によって見いだされたソリューションに匹敵するソリューションをもたらす小さなサブグラフを識別するが、全体の実行時間のごく一部にはならない。
  論文  参考訳（メタデータ） (2022-05-20T11:54:03Z)
• A Differentiable Approach to Combinatorial Optimization using Dataless Neural Networks [20.170140039052455]
  我々は、ソリューションを生成するニューラルネットワークのトレーニングにデータを必要としないという、根本的に異なるアプローチを提案する。 特に、最適化問題をニューラルネットワークに還元し、データレストレーニングスキームを用いて、それらのパラメータが関心の構造をもたらすように、ネットワークのパラメータを洗練する。
  論文  参考訳（メタデータ） (2022-03-15T19:21:31Z)
• GLAN: A Graph-based Linear Assignment Network [29.788755291070462]
  深層グラフネットワークに基づく学習可能な線形代入問題の解法を提案する。 合成データセットによる実験結果から,本手法は最先端のベースラインよりも優れていることがわかった。 また,提案手法を一般的なマルチオブジェクトトラッキング(MOT)フレームワークに組み込んで,エンド・ツー・エンドでトラッカーをトレーニングする。
  論文  参考訳（メタデータ） (2022-01-05T13:18:02Z)
• Gaussian Graphical Model Selection for Huge Data via Minipatch Learning [1.2891210250935146]
  グラフィカルモデル選択の問題を解決するために,MPGraph (Minipatch Graph) 推定器を提案する。 MPGraphは、観測とノードの両方の小さなランダムなサブセットに適合する閾値グラフ推定器の一般化である。 本アルゴリズムは有限サンプルグラフ選択の整合性を実現する。
  論文  参考訳（メタデータ） (2021-10-22T21:06:48Z)
• A Bi-Level Framework for Learning to Solve Combinatorial Optimization on Graphs [91.07247251502564]
  本稿では,2つの世界の長所を結合するハイブリッドな手法を提案する。この手法では,グラフを最適化する上層学習手法とバイレベルフレームワークを開発する。 このような二段階のアプローチは、元のハードCOでの学習を単純化し、モデルキャパシティの需要を効果的に軽減することができる。
  論文  参考訳（メタデータ） (2021-06-09T09:18:18Z)
• Learnable Graph Matching: Incorporating Graph Partitioning with Deep Feature Learning for Multiple Object Tracking [58.30147362745852]
  フレーム間のデータアソシエーションは、Multiple Object Tracking(MOT)タスクの中核にある。 既存の手法は、主にトラックレットとフレーム内検出の間のコンテキスト情報を無視する。 そこで本研究では,学習可能なグラフマッチング手法を提案する。
  論文  参考訳（メタデータ） (2021-03-30T08:58:45Z)
• Learning to Solve Combinatorial Optimization Problems on Real-World Graphs in Linear Time [12.43303621344215]
  専門知識のないグラフ上での最適化問題を解くための新しいフレームワークを開発する。 本手法は,グラフのラベル付きトレーニングセット上で強化学習を用いてグラフニューラルネットワークを訓練する。 最適性ギャップが 1 に近い 2 つのNP-ハード問題に対して,本手法がよく一般化可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-06T01:35:45Z)
• Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
  グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。 しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。 本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
  論文  参考訳（メタデータ） (2020-01-18T09:14:16Z)

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

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