論文の概要: GNNSampler: Bridging the Gap between Sampling Algorithms of GNN and
Hardware
- arxiv url: http://arxiv.org/abs/2108.11571v1
- Date: Thu, 26 Aug 2021 04:13:52 GMT
- ステータス: 処理完了
- システム内更新日: 2021-08-27 13:55:40.786166
- Title: GNNSampler: Bridging the Gap between Sampling Algorithms of GNN and
Hardware
- Title(参考訳): GNNSampler: GNNとハードウェアのサンプリングアルゴリズムのギャップを埋める
- Authors: Xin Liu, Mingyu Yan, Shuhan Song, Zhengyang Lv, Wenming Li, Guangyu
Sun, Xiaochun Ye, Dongrui Fan
- Abstract要約: GNNSamplerと呼ばれるメインストリームサンプリングアルゴリズムのための統一型プログラミングモデルを提案する。
我々は,サンプリング中の不規則なメモリアクセスを軽減するために,実世界のデータセットでノードとその隣人のデータの局所性を探索する。
提案手法は主流サンプリングアルゴリズムに普遍的であり,GNNのトレーニング時間を短縮する。
- 参考スコア(独自算出の注目度): 8.15489210461058
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Sampling is a critical operation in the training of Graph Neural Network
(GNN) that helps reduce the cost. Previous works have explored improving
sampling algorithms through mathematical and statistical methods. However,
there is a gap between sampling algorithms and hardware. Without consideration
of hardware, algorithm designers merely optimize sampling at the algorithm
level, missing the great potential of promoting the efficiency of existing
sampling algorithms by leveraging hardware features. In this paper, we first
propose a unified programming model for mainstream sampling algorithms, termed
GNNSampler, covering the key processes for sampling algorithms in various
categories. Second, we explore the data locality among nodes and their
neighbors (i.e., the hardware feature) in real-world datasets for alleviating
the irregular memory access in sampling. Third, we implement locality-aware
optimizations in GNNSampler for diverse sampling algorithms to optimize the
general sampling process in the training of GNN. Finally, we emphatically
conduct experiments on large graph datasets to analyze the relevance between
the training time, model accuracy, and hardware-level metrics, which helps
achieve a good trade-off between time and accuracy in GNN training. Extensive
experimental results show that our method is universal to mainstream sampling
algorithms and reduces the training time of GNN (range from 4.83% with
layer-wise sampling to 44.92% with subgraph-based sampling) with comparable
accuracy.
- Abstract(参考訳): サンプリングはグラフニューラルネットワーク(GNN)のトレーニングにおいて重要な操作であり、コスト削減に役立つ。
従来の研究は、数学的および統計的手法によるサンプリングアルゴリズムの改善を検討してきた。
しかし、サンプリングアルゴリズムとハードウェアの間にはギャップがある。
ハードウェアを考慮せずに、アルゴリズム設計者は単にアルゴリズムレベルでサンプリングを最適化するだけで、ハードウェア機能を活用することで既存のサンプリングアルゴリズムの効率を向上する大きな可能性を欠いている。
本稿では,まず,GNNSamplerと呼ばれるメインストリームサンプリングアルゴリズムの統一プログラミングモデルを提案する。
第2に,サンプリング時の不規則なメモリアクセスを緩和するために,実世界のデータセットにおけるノードとその周辺ノード(ハードウェア機能)間のデータの局所性を検討する。
第3に,GNNSamplerにおける局所性を考慮した多種多様なサンプリングアルゴリズムを実装し,GNNのトレーニングにおける一般的なサンプリングプロセスを最適化する。
最後に,大規模グラフデータセットに関する実験を行い,学習時間,モデル精度,ハードウェアレベルのメトリクスの関連性を分析し,gnnトレーニングにおける時間と精度の良好なトレードオフを実現する。
広範な実験結果から,本手法は主流サンプリングアルゴリズムに普遍的であり,gnnの学習時間(層別サンプリングでは4.83%からサブグラフベースサンプリングでは44.92%)を同等の精度で削減できることがわかった。
関連論文リスト
- YOSO: You-Only-Sample-Once via Compressed Sensing for Graph Neural Network Training [9.02251811867533]
YOSO(You-Only-Sample-Once)は、予測精度を維持しながら効率的なトレーニングを実現するアルゴリズムである。
YOSOは、正規直交基底計算のような従来の圧縮センシング(CS)法で高価な計算を避けるだけでなく、高い確率精度の保持も保証している。
論文 参考訳(メタデータ) (2024-11-08T16:47:51Z) - CBAGAN-RRT: Convolutional Block Attention Generative Adversarial Network
for Sampling-Based Path Planning [0.0]
本稿では,畳み込みブロック注意生成ネットワークを用いた新しい画像ベース学習アルゴリズム(CBAGAN-RRT)を提案する。
GANモデルから生成された経路の確率分布を用いて,RRTアルゴリズムのサンプリングプロセスを導出する。
我々は、citezhang 2021によって生成されたデータセット上で、我々のネットワークをトレーニングし、テストし、我々のアルゴリズムが過去の最先端アルゴリズムより優れていることを示す。
論文 参考訳(メタデータ) (2023-05-13T20:06:53Z) - Towards Automated Imbalanced Learning with Deep Hierarchical
Reinforcement Learning [57.163525407022966]
不均衡学習はデータマイニングにおいて基本的な課題であり、各クラスにトレーニングサンプルの不均等な比率が存在する。
オーバーサンプリングは、少数民族のための合成サンプルを生成することによって、不均衡な学習に取り組む効果的な手法である。
我々は,異なるレベルの意思決定を共同で最適化できる自動オーバーサンプリングアルゴリズムであるAutoSMOTEを提案する。
論文 参考訳(メタデータ) (2022-08-26T04:28:01Z) - Communication-Efficient Sampling for Distributed Training of Graph
Convolutional Networks [3.075766050800645]
隣のノードからデータを集約する必要があるため、トレーニンググラフ畳み込みネットワーク(GCN)は高価です。
先行研究では,少数の隣人を対象に,収集結果を推定する様々な近傍サンプリング手法が提案されている。
本稿では, 局所サンプリング確率を判定し, スクイード隣りのサンプリングがトレーニングの収束度に大きく影響しないことを確かめるアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-19T16:12:44Z) - A Systematic Characterization of Sampling Algorithms for Open-ended
Language Generation [71.31905141672529]
本稿では,自己回帰型言語モデルに広く採用されている祖先サンプリングアルゴリズムについて検討する。
エントロピー低減, 秩序保存, 斜面保全の3つの重要な特性を同定した。
これらの特性を満たすサンプリングアルゴリズムのセットが,既存のサンプリングアルゴリズムと同等に動作することがわかった。
論文 参考訳(メタデータ) (2020-09-15T17:28:42Z) - Nearly Linear Row Sampling Algorithm for Quantile Regression [54.75919082407094]
データの次元にほぼ線形なサンプル複雑性を持つ量子化損失関数の行サンプリングアルゴリズムを提案する。
行サンプリングアルゴリズムに基づいて、量子レグレッションの最も高速なアルゴリズムと、バランスの取れた有向グラフのグラフスペーシフィケーションアルゴリズムを提案する。
論文 参考訳(メタデータ) (2020-06-15T13:40:07Z) - Bandit Samplers for Training Graph Neural Networks [63.17765191700203]
グラフ畳み込みネットワーク(GCN)の訓練を高速化するために, ばらつきを低減したサンプリングアルゴリズムが提案されている。
これらのサンプリングアルゴリズムは、グラフ注意ネットワーク(GAT)のような固定重みよりも学習重量を含む、より一般的なグラフニューラルネットワーク(GNN)には適用できない。
論文 参考訳(メタデータ) (2020-06-10T12:48:37Z) - Learning with Optimized Random Features: Exponential Speedup by Quantum
Machine Learning without Sparsity and Low-Rank Assumptions [8.08640000394814]
我々は,実行時特性を最適化した分布からサンプリングする量子アルゴリズムを開発した。
我々のアルゴリズムは、このサンプリングタスクの既知の古典的アルゴリズムと比較して、D$の指数的な高速化を実現している。
論文 参考訳(メタデータ) (2020-04-22T18:00:00Z) - Active Model Estimation in Markov Decision Processes [108.46146218973189]
マルコフ決定過程(MDP)をモデル化した環境の正確なモデル学習のための効率的な探索の課題について検討する。
マルコフに基づくアルゴリズムは,本アルゴリズムと極大エントロピーアルゴリズムの両方を小サンプル方式で上回っていることを示す。
論文 参考訳(メタデータ) (2020-03-06T16:17:24Z) - Channel Assignment in Uplink Wireless Communication using Machine
Learning Approach [54.012791474906514]
本稿では,アップリンク無線通信システムにおけるチャネル割り当て問題について検討する。
我々の目標は、整数チャネル割り当て制約を受ける全ユーザの総和率を最大化することです。
計算複雑性が高いため、機械学習アプローチは計算効率のよい解を得るために用いられる。
論文 参考訳(メタデータ) (2020-01-12T15:54:20Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。