論文の概要: Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloring
- arxiv url: http://arxiv.org/abs/2408.05054v1
- Date: Fri, 9 Aug 2024 13:21:08 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-12 15:47:15.121689
- Title: Graph Neural Networks as Ordering Heuristics for Parallel Graph Coloring
- Title（参考訳）: 並列グラフカラー化のための順序付けヒューリスティックとしてのグラフニューラルネットワーク
- Authors: Kenneth Langedal, Fredrik Manne,
- Abstract要約: グラフニューラルネットワークに基づく順序付けを導入し、品質と性能の両方において、既存の強欲な順序よりも優れていることを示す。
実験結果から, 2層GNNモデルでは, カラー化品質を両立させながら, 最多次目(LF)と最少次目(SL)の順間の実行時間を達成できることがわかった。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: The graph coloring problem asks for an assignment of the minimum number of distinct colors to vertices in an undirected graph with the constraint that no pair of adjacent vertices share the same color. The problem is a thoroughly studied NP-hard combinatorial problem with several real-world applications. As such, a number of greedy heuristics have been suggested that strike a good balance between coloring quality, execution time, and also parallel scalability. In this work, we introduce a graph neural network (GNN) based ordering heuristic and demonstrate that it outperforms existing greedy ordering heuristics both on quality and performance. Previous results have demonstrated that GNNs can produce high-quality colorings but at the expense of excessive running time. The current paper is the first that brings the execution time down to compete with existing greedy heuristics. Our GNN model is trained using both supervised and unsupervised techniques. The experimental results show that a 2-layer GNN model can achieve execution times between the largest degree first (LF) and smallest degree last (SL) ordering heuristics while outperforming both on coloring quality. Increasing the number of layers improves the coloring quality further, and it is only at four layers that SL becomes faster than the GNN. Finally, our GNN-based coloring heuristic achieves superior scaling in the parallel setting compared to both SL and LF.
- Abstract（参考訳）: グラフ彩色問題は、隣接する頂点のペアが同じ色を共有しないという制約付き無向グラフの頂点に対して、最小数の異なる色を割り当てることを要求する。
この問題は、いくつかの実世界の応用において、NP-ハード組合せ問題として徹底的に研究されている。
そのため、色付け品質、実行時間、および並列スケーラビリティのバランスが良いと多くの欲求的ヒューリスティックが示唆されている。
本研究では,グラフニューラルネットワーク(GNN)に基づく注文ヒューリスティックを導入し,既存のグリーディ順序ヒューリスティックを品質と性能の両方で上回ることを示す。
これまでの結果、GNNは高品質な彩色を生成できるが、過剰なランニング時間を犠牲にしている。
現在の論文は、既存の強欲なヒューリスティックと競合するために実行時間を短縮した最初の論文です。
我々のGNNモデルは、教師なし技術と教師なし技術の両方を用いて訓練されている。
実験結果から, 2層GNNモデルでは, カラー化品質に優れながら, 最大次数(LF)と最小次数(SL)のヒューリスティックスの実行時間を達成できることが示唆された。
層数の増加は色付け品質をさらに向上させ、SLがGNNよりも高速になるのは4層のみである。
最後に,GNNをベースとしたカラーリングヒューリスティックは,SLとLFの双方と比較して並列設定でのスケーリングに優れる。
関連論文リスト
- Higher-Order GNNs Meet Efficiency: Sparse Sobolev Graph Neural Networks [6.080095317098909]
グラフニューラルネットワーク(GNN)は,グラフ内のノード間の関係をモデル化する上で,非常に有望であることを示す。
これまでの研究では、主にグラフ内の高次隣人からの情報を活用しようと試みてきた。
我々は基本的な観察を行い、ラプラシア行列の正則とアダマールの力はスペクトルでも同様に振る舞う。
グラフ信号のスパースなソボレフノルムに基づく新しいグラフ畳み込み演算子を提案する。
論文 参考訳（メタデータ） (2024-11-07T09:53:11Z) - Graph Ladling: Shockingly Simple Parallel GNN Training without
Intermediate Communication [100.51884192970499]
GNNは、グラフを学習するニューラルネットワークの強力なファミリーである。
GNNのスケーリングは、肥大化または拡大によって、不健康な勾配、過度なスムースメント、情報のスカッシングといった問題に悩まされる。
本稿では,現在のGNNの深層化や拡張ではなく,GNNに適したモデルスープをデータ中心の視点で表現することを提案する。
論文 参考訳（メタデータ） (2023-06-18T03:33:46Z) - Simple yet Effective Gradient-Free Graph Convolutional Networks [20.448409424929604]
近年,グラフ表現学習において線形化グラフニューラルネットワーク (GNN) が注目されている。
本稿では,過度な平滑化と消失する勾配現象を関連づけ,勾配のないトレーニングフレームワークを構築する。
提案手法は, ノード分類タスクにおいて, 深度や訓練時間を大幅に短縮して, より優れた, より安定した性能を実現する。
論文 参考訳（メタデータ） (2023-02-01T11:00:24Z) - Reducing Over-smoothing in Graph Neural Networks Using Relational
Embeddings [0.15619750966454563]
本稿では,GNNにおけるオーバー・スムーシング問題の影響を緩和する,シンプルで効率的な手法を提案する。
我々の手法は他の手法と組み合わせて最高の性能を与えることができる。
論文 参考訳（メタデータ） (2023-01-07T19:26:04Z) - Rethinking Graph Neural Networks for the Graph Coloring Problem [14.102597635893083]
我々は、最先端のGNNがグラフ彩色問題においてあまり成功していないことを観察する。
本稿では,一般的なGNNクラスである集約合成GNN(AC-GNN)に焦点を当てる。
本稿では,任意のAC-GNNが局所着色法であり,局所着色法はスパースランダムグラフ上の局所着色法の限界を探索することによって最適でないことを示す。
論文 参考訳（メタデータ） (2022-08-15T02:24:26Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳（メタデータ） (2022-03-03T09:53:53Z) - Very Deep Graph Neural Networks Via Noise Regularisation [57.450532911995516]
グラフニューラルネットワーク(GNN)は、入力グラフを介して学習されたメッセージパッシングを実行する。
最大100のメッセージパッシングステップを持つディープGNNをトレーニングし、いくつかの最先端の結果を得る。
論文 参考訳（メタデータ） (2021-06-15T08:50:10Z) - Boost then Convolve: Gradient Boosting Meets Graph Neural Networks [6.888700669980625]
グラデーションブースト決定木(gbdt)は,異種データに対して他の機械学習手法よりも優れていることが示されている。
我々は,gbdt と gnn を共同で訓練し,両世界のベストを勝ち取る新しいアーキテクチャを提案する。
我々のモデルは、GNNの勾配更新に新しい木を適合させることにより、エンドツーエンドの最適化の恩恵を受ける。
論文 参考訳（メタデータ） (2021-01-21T10:46:41Z) - Scalable Graph Neural Networks via Bidirectional Propagation [89.70835710988395]
グラフニューラルネットワーク(GNN)は、非ユークリッドデータを学習するための新興分野である。
本稿では、特徴ベクトルとトレーニング/テストノードの両方から局所的な双方向伝搬プロセスを利用するスケーラブルなGNNであるGBPを提案する。
実証実験により、GBPは、トレーニング/テスト時間を大幅に減らして最先端のパフォーマンスを達成することが示された。
論文 参考訳（メタデータ） (2020-10-29T08:55:33Z) - Combining Label Propagation and Simple Models Out-performs Graph Neural
Networks [52.121819834353865]
多くの標準的なトランスダクティブノード分類ベンチマークでは、最先端のGNNの性能を超えたり、一致させることができる。
これをC&S(Correct and Smooth)と呼ぶ。
我々のアプローチは、様々なベンチマークで最先端のGNNの性能を上回るか、ほぼ一致している。
論文 参考訳（メタデータ） (2020-10-27T02:10:52Z) - Distance Encoding: Design Provably More Powerful Neural Networks for
Graph Representation Learning [63.97983530843762]
グラフニューラルネットワーク(GNN)はグラフ表現学習において大きな成功を収めている。
GNNは、実際には非常に異なるグラフ部分構造に対して同一の表現を生成する。
より強力なGNNは、最近高階試験を模倣して提案され、基礎となるグラフ構造を疎結合にできないため、非効率である。
本稿では,グラフ表現学習の新たなクラスとして距離分解(DE)を提案する。
論文 参考訳（メタデータ） (2020-08-31T23:15:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。