論文の概要: A GREAT Architecture for Edge-Based Graph Problems Like TSP
- arxiv url: http://arxiv.org/abs/2408.16717v1
- Date: Thu, 29 Aug 2024 17:07:43 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-30 12:51:37.094618
- Title: A GREAT Architecture for Edge-Based Graph Problems Like TSP
- Title（参考訳）: TSPのようなエッジベースのグラフ問題に対するGREATアーキテクチャ
- Authors: Attila Lischka, Jiaming Wu, Morteza Haghir Chehreghani, Balázs Kulcsár,
- Abstract要約: グラフニューラルネットワーク(GNN)は、ルーティング問題などの高密度グラフを操作するには適していない。
グラフエッジ注意ネットワーク(GREAT)と呼ばれる新しいGNN関連エッジベースニューラルモデルを提案する。
GREATは最適エッジの大部分を維持しながらスパースグラフを生成することができることを示す。
- 参考スコア（独自算出の注目度）: 8.922883855120416
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: In the last years, many neural network-based approaches have been proposed to tackle combinatorial optimization problems such as routing problems. Many of these approaches are based on graph neural networks (GNNs) or related transformers, operating on the Euclidean coordinates representing the routing problems. However, GNNs are inherently not well suited to operate on dense graphs, such as in routing problems. Furthermore, models operating on Euclidean coordinates cannot be applied to non-Euclidean versions of routing problems that are often found in real-world settings. To overcome these limitations, we propose a novel GNN-related edge-based neural model called Graph Edge Attention Network (GREAT). We evaluate the performance of GREAT in the edge-classification task to predict optimal edges in the Traveling Salesman Problem (TSP). We can use such a trained GREAT model to produce sparse TSP graph instances, keeping only the edges GREAT finds promising. Compared to other, non-learning-based methods to sparsify TSP graphs, GREAT can produce very sparse graphs while keeping most of the optimal edges. Furthermore, we build a reinforcement learning-based GREAT framework which we apply to Euclidean and non-Euclidean asymmetric TSP. This framework achieves state-of-the-art results.
- Abstract（参考訳）: 近年、ルーティング問題などの組合せ最適化問題に対処するために、多くのニューラルネットワークベースのアプローチが提案されている。
これらのアプローチの多くはグラフニューラルネットワーク(GNN)または関連するトランスフォーマーに基づいており、ルーティング問題を表すユークリッド座標で動作する。
しかし、GNNは本質的にルーティング問題など、密度の高いグラフを操作するのに適していない。
さらに、ユークリッド座標で動作するモデルは、現実の環境でよく見られるルーティング問題の非ユークリッドバージョンには適用できない。
これらの制限を克服するために,グラフエッジ注意ネットワーク(GREAT)と呼ばれる,GNN関連エッジベースニューラルモデルを提案する。
我々は,旅行セールスマン問題(TSP)における最適エッジを予測するために,エッジ分類タスクにおけるGREATの性能を評価する。
このような訓練されたGREATモデルを使ってスパースなTSPグラフインスタンスを生成することができ、GREATが期待できるエッジのみを保持することができます。
TSPグラフをスパース化する他の非学習ベースの方法と比較して、GREATは最適なエッジの大部分を保持しながら、非常にスパースなグラフを生成することができる。
さらに、強化学習に基づくGREATフレームワークを構築し、ユークリッドおよび非ユークリッド非対称TSPに適用する。
このフレームワークは最先端の結果を達成する。
関連論文リスト
- Scalable Graph Compressed Convolutions [68.85227170390864]
ユークリッド畳み込みのための入力グラフのキャリブレーションに置換を適用する微分可能手法を提案する。
グラフキャリブレーションに基づいて,階層型グラフ表現学習のための圧縮畳み込みネットワーク(CoCN)を提案する。
論文 参考訳（メタデータ） (2024-07-26T03:14:13Z) - T-GAE: Transferable Graph Autoencoder for Network Alignment [79.89704126746204]
T-GAEはグラフオートエンコーダフレームワークで、GNNの転送性と安定性を活用して、再トレーニングなしに効率的なネットワークアライメントを実現する。
実験の結果、T-GAEは最先端の最適化手法と最高のGNN手法を最大38.7%、50.8%で上回っていることがわかった。
論文 参考訳（メタデータ） (2023-10-05T02:58:29Z) - Learning Cooperative Beamforming with Edge-Update Empowered Graph Neural
Networks [29.23937571816269]
グラフエッジ上での協調ビームフォーミングを学習するためのエッジグラフニューラルネットワーク(Edge-GNN)を提案する。
提案したEdge-GNNは、最先端の手法よりも計算時間をはるかに短くして、より高い和率を達成する。
論文 参考訳（メタデータ） (2022-11-23T02:05:06Z) - GNN at the Edge: Cost-Efficient Graph Neural Network Processing over
Distributed Edge Servers [24.109721494781592]
グラフニューラルネットワーク(GNN)はまだ探索中であり、その広範な採用に対する大きな違いを示している。
本稿では,多層ヘテロジニアスエッジネットワーク上での分散GNN処理のコスト最適化について検討する。
提案手法は, 高速収束速度で95.8%以上のコスト削減を行い, デファクトベースラインよりも優れた性能が得られることを示す。
論文 参考訳（メタデータ） (2022-10-31T13:03:16Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳（メタデータ） (2022-07-18T14:23:31Z) - Graph Neural Networks for Graph Drawing [17.983238300054527]
グラフニューラルネットワーク(GND)の開発のための新しいフレームワークを提案する。
GNDは、効率的で複雑な地図を構築するために、ニューラルネットワークに依存している。
このメカニズムは、フィードフォワードニューラルネットワークによって計算された損失関数によって導出可能であることを実証する。
論文 参考訳（メタデータ） (2021-09-21T09:58:02Z) - Edgeless-GNN: Unsupervised Inductive Edgeless Network Embedding [7.391641422048645]
ネットワークを新たに入力したユーザなど,エッジレスノードを埋め込む問題について検討する。
我々は,非教師付き帰納学習により,エッジレスノードに対してもノード埋め込みを生成可能な新しいフレームワークであるEdgeless-GNNを提案する。
論文 参考訳（メタデータ） (2021-04-12T06:37:31Z) - Learning to Drop: Robust Graph Neural Network via Topological Denoising [50.81722989898142]
グラフニューラルネットワーク(GNN)のロバスト性および一般化性能を向上させるために,パラメータ化トポロジカルデノイングネットワークであるPTDNetを提案する。
PTDNetは、パラメータ化されたネットワークでスパーシファイドグラフ内のエッジ数をペナル化することで、タスク非関連エッジを創出する。
PTDNetはGNNの性能を著しく向上させ,さらにノイズの多いデータセットでは性能が向上することを示す。
論文 参考訳（メタデータ） (2020-11-13T18:53:21Z) - A Generative Graph Method to Solve the Travelling Salesman Problem [1.552282932199974]
我々は,旅行セールスマン問題(TSP)を概ね解決するために,生成的アプローチである新しいグラフ学習ネットワーク(GLN)を提案する。
GLNモデルは、トレーニングデータセットとしてTSPインスタンスのパターンを直接学習し、グラフプロパティをエンコードし、異なるノードの埋め込みをマージして、最適なツアーを出力する。
論文 参考訳（メタデータ） (2020-07-09T17:23:55Z) - Towards an Efficient and General Framework of Robust Training for Graph
Neural Networks [96.93500886136532]
グラフニューラルネットワーク(GNN)は、いくつかの基本的な推論タスクに大きく進歩している。
GNNの目覚ましい性能にもかかわらず、グラフ構造上の摂動を慎重に作り、誤った予測を下すことが観察されている。
我々は,強靭なGNNを得るために,欲求探索アルゴリズムとゼロ階法を利用する汎用フレームワークを提案する。
論文 参考訳（メタデータ） (2020-02-25T15:17:58Z) - EdgeNets:Edge Varying Graph Neural Networks [179.99395949679547]
本稿では、EdgeNetの概念を通じて、最先端グラフニューラルネットワーク(GNN)を統一する一般的なフレームワークを提案する。
EdgeNetはGNNアーキテクチャであり、異なるノードが異なるパラメータを使って異なる隣人の情報を測定することができる。
これは、ノードが実行でき、既存のグラフ畳み込みニューラルネットワーク(GCNN)とグラフアテンションネットワーク(GAT)の1つの定式化の下で包含できる一般的な線形で局所的な操作である。
論文 参考訳（メタデータ） (2020-01-21T15:51:17Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。