論文の概要: Learning Topological Representations with Bidirectional Graph Attention
Network for Solving Job Shop Scheduling Problem
- arxiv url: http://arxiv.org/abs/2402.17606v1
- Date: Tue, 27 Feb 2024 15:33:20 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-28 15:46:05.823911
- Title: Learning Topological Representations with Bidirectional Graph Attention
Network for Solving Job Shop Scheduling Problem
- Title（参考訳）: ジョブショップスケジューリング問題を解決するための双方向グラフアテンションネットワークによるトポロジ表現の学習
- Authors: Cong Zhang, Zhiguang Cao, Yaoxin Wu, Wen Song, Jing Sun
- Abstract要約: 既存の学習に基づくジョブショップスケジューリング問題(JSSP)の解法は、通常、非方向グラフに適した既製のGNNモデルを使用する。
本稿では,JSSP を解決するための DG を局所検索フレームワークに組み込むためのトポロジ対応双方向グラフアテンションネットワーク (TBGAT) を提案する。
- 参考スコア（独自算出の注目度）: 29.936902745759728
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Existing learning-based methods for solving job shop scheduling problem
(JSSP) usually use off-the-shelf GNN models tailored to undirected graphs and
neglect the rich and meaningful topological structures of disjunctive graphs
(DGs). This paper proposes the topology-aware bidirectional graph attention
network (TBGAT), a novel GNN architecture based on the attention mechanism, to
embed the DG for solving JSSP in a local search framework. Specifically, TBGAT
embeds the DG from a forward and a backward view, respectively, where the
messages are propagated by following the different topologies of the views and
aggregated via graph attention. Then, we propose a novel operator based on the
message-passing mechanism to calculate the forward and backward topological
sorts of the DG, which are the features for characterizing the topological
structures and exploited by our model. In addition, we theoretically and
experimentally show that TBGAT has linear computational complexity to the
number of jobs and machines, respectively, which strengthens the practical
value of our method. Besides, extensive experiments on five synthetic datasets
and seven classic benchmarks show that TBGAT achieves new SOTA results by
outperforming a wide range of neural methods by a large margin.
- Abstract（参考訳）: 既存の学習に基づくジョブショップスケジューリング問題(JSSP)の解法は、通常、非方向グラフに適した既製のGNNモデルを使用し、解離グラフ(DG)のリッチで有意義なトポロジ構造を無視する。
本稿では,このアテンション機構に基づく新しいGNNアーキテクチャである,トポロジ対応双方向グラフアテンションネットワーク(TBGAT)を提案し,JSSPをローカル検索フレームワークに組み込む。
具体的には、TBGATは、それぞれ前方と後方のビューからDGを埋め込み、ビューの異なるトポロジに従ってメッセージが伝播し、グラフの注意を通して集約される。
そこで本研究では,dg の前方および後方の位相的特徴を計算し,その特徴をモデルによって活用するためのメッセージパス機構に基づく新しい演算子を提案する。
さらに, TBGATは, ジョブ数とマシン数に線形計算複雑性があることを理論的, 実験的に示し, 本手法の実用的価値を高める。
さらに、5つの合成データセットと7つの古典的なベンチマークに関する広範な実験により、TBGATは幅広いニューラルネットワークよりも大きなマージンで、新しいSOTA結果を達成することが示された。
関連論文リスト
- TANGNN: a Concise, Scalable and Effective Graph Neural Networks with Top-m Attention Mechanism for Graph Representation Learning [7.879217146851148]
本稿では,Top-mアテンション機構アグリゲーションコンポーネントと近傍アグリゲーションコンポーネントを統合した,革新的なグラフニューラルネットワーク(GNN)アーキテクチャを提案する。
提案手法の有効性を評価するため,提案手法をGNN分野において未探索の新たな課題である引用感情予測に適用した。
論文 参考訳（メタデータ） (2024-11-23T05:31:25Z) - Representation Learning on Heterophilic Graph with Directional
Neighborhood Attention [8.493802098034255]
Graph Attention Network(GAT)は、最も人気のあるGraph Neural Network(GNN)アーキテクチャの1つである。
GATは、長距離およびグローバルグラフ情報をキャプチャする能力に欠けており、いくつかのデータセットで不満足なパフォーマンスをもたらす。
本稿では,特徴に基づく注意と,グラフトポロジから抽出したグローバルな方向性情報を組み合わせるために,DGAT(Directional Graph Attention Network)を提案する。
論文 参考訳（メタデータ） (2024-03-03T10:59:16Z) - DEGREE: Decomposition Based Explanation For Graph Neural Networks [55.38873296761104]
我々は,GNN予測に対する忠実な説明を提供するためにDGREEを提案する。
GNNの情報生成と集約機構を分解することにより、DECREEは入力グラフの特定のコンポーネントのコントリビューションを最終的な予測に追跡することができる。
また,従来の手法で見過ごされるグラフノード間の複雑な相互作用を明らかにするために,サブグラフレベルの解釈アルゴリズムを設計する。
論文 参考訳（メタデータ） (2023-05-22T10:29:52Z) - 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) - Automatic Relation-aware Graph Network Proliferation [182.30735195376792]
GNNを効率的に検索するためのARGNP(Automatic Relation-Aware Graph Network Proliferation)を提案する。
これらの操作は階層的なノード/リレーショナル情報を抽出し、グラフ上のメッセージパッシングのための異方的ガイダンスを提供する。
4つのグラフ学習タスクのための6つのデータセットの実験により、我々の手法によって生成されたGNNは、現在最先端の手作りおよび検索に基づくGNNよりも優れていることが示された。
論文 参考訳（メタデータ） (2022-05-31T10:38:04Z) - Towards Unsupervised Deep Graph Structure Learning [67.58720734177325]
本稿では,学習したグラフトポロジを外部ガイダンスなしでデータ自身で最適化する,教師なしグラフ構造学習パラダイムを提案する。
具体的には、元のデータから"アンカーグラフ"として学習目標を生成し、対照的な損失を用いてアンカーグラフと学習グラフとの一致を最大化する。
論文 参考訳（メタデータ） (2022-01-17T11:57:29Z) - Learning to Drop: Robust Graph Neural Network via Topological Denoising [50.81722989898142]
グラフニューラルネットワーク(GNN)のロバスト性および一般化性能を向上させるために,パラメータ化トポロジカルデノイングネットワークであるPTDNetを提案する。
PTDNetは、パラメータ化されたネットワークでスパーシファイドグラフ内のエッジ数をペナル化することで、タスク非関連エッジを創出する。
PTDNetはGNNの性能を著しく向上させ,さらにノイズの多いデータセットでは性能が向上することを示す。
論文 参考訳（メタデータ） (2020-11-13T18:53:21Z) - Hierarchical Message-Passing Graph Neural Networks [12.207978823927386]
本稿では,新しい階層型メッセージパッシンググラフニューラルネットワークフレームワークを提案する。
鍵となるアイデアは、フラットグラフ内のすべてのノードをマルチレベルなスーパーグラフに再編成する階層構造を生成することである。
階層型コミュニティ対応グラフニューラルネットワーク(HC-GNN)と呼ばれる,このフレームワークを実装した最初のモデルを提案する。
論文 参考訳（メタデータ） (2020-09-08T13:11:07Z) - CAGNN: Cluster-Aware Graph Neural Networks for Unsupervised Graph
Representation Learning [19.432449825536423]
教師なしグラフ表現学習は、教師なしの低次元ノード埋め込みを学習することを目的としている。
本稿では、自己教師付き手法を用いた教師なしグラフ表現学習のための新しいクラスタ対応グラフニューラルネットワーク(CAGNN)モデルを提案する。
論文 参考訳（メタデータ） (2020-09-03T13:57:18Z) - Graph Neural Networks Including Sparse Interpretability [0.0]
本稿では,重要なグラフ構造とノード特徴を解釈するためのモデルに依存しないフレームワークを提案する。
GISSTモデルは、合成データセットにおいて優れたノード特徴とエッジ説明精度を実現する。
論文 参考訳（メタデータ） (2020-06-30T21:35:55Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。