論文の概要: RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations

• arxiv url: http://arxiv.org/abs/2210.10737v2
• Date: Sun, 2 Jul 2023 22:54:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-07-04 15:29:57.395286
• Title: RSC: Accelerating Graph Neural Networks Training via Randomized Sparse Computations
• Title（参考訳）: RSC:ランダムスパース計算によるグラフニューラルネットワークトレーニングの高速化
• Authors: Zirui Liu, Shengyuan Chen, Kaixiong Zhou, Daochen Zha, Xiao Huang, Xia Hu
• Abstract要約: トレーニンググラフニューラルネットワーク(GNN)は、疎グラフベースの操作がハードウェアによって加速することが難しいため、時間を要する。 我々は,サンプリングに基づく近似による時間的複雑性を低減するために,計算精度のトレードオフを検討する。 本稿では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。
• 参考スコア（独自算出の注目度）: 56.59168541623729
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The training of graph neural networks (GNNs) is extremely time consuming because sparse graph-based operations are hard to be accelerated by hardware. Prior art explores trading off the computational precision to reduce the time complexity via sampling-based approximation. Based on the idea, previous works successfully accelerate the dense matrix based operations (e.g., convolution and linear) with negligible accuracy drop. However, unlike dense matrices, sparse matrices are stored in the irregular data format such that each row/column may have different number of non-zero entries. Thus, compared to the dense counterpart, approximating sparse operations has two unique challenges (1) we cannot directly control the efficiency of approximated sparse operation since the computation is only executed on non-zero entries; (2) sub-sampling sparse matrices is much more inefficient due to the irregular data format. To address the issues, our key idea is to control the accuracy-efficiency trade off by optimizing computation resource allocation layer-wisely and epoch-wisely. Specifically, for the first challenge, we customize the computation resource to different sparse operations, while limit the total used resource below a certain budget. For the second challenge, we cache previous sampled sparse matrices to reduce the epoch-wise sampling overhead. Finally, we propose a switching mechanisms to improve the generalization of GNNs trained with approximated operations. To this end, we propose Randomized Sparse Computation, which for the first time demonstrate the potential of training GNNs with approximated operations. In practice, rsc can achieve up to $11.6\times$ speedup for a single sparse operation and a $1.6\times$ end-to-end wall-clock time speedup with negligible accuracy drop.
• Abstract（参考訳）: グラフニューラルネットワーク(gnns)のトレーニングは、ハードウェアによってスパースグラフベースの操作を加速することが難しいため、非常に時間がかかる。 先行技術は、サンプリングに基づく近似による時間の複雑さを減らすために計算精度をトレードオフする。 この考えに基づいて、以前の研究は無視できる精度の低下で密度行列に基づく演算(例えば畳み込みや線形)を加速させることに成功した。 しかし、密度行列とは異なり、スパース行列は不規則なデータ形式に格納され、各行/カラムは異なる数の非ゼロエントリを持つ。 したがって、密接な比較により、スパース演算の近似化には、(1)非ゼロエントリでのみ計算を行うため、近似スパース演算の効率を直接制御できないこと、(2)サブサンプリングスパース行列は不規則なデータフォーマットのため、はるかに非効率である。 この問題に対処するためには,計算資源割当を階層的に,画期的に最適化することにより,精度と効率のトレードオフを制御することが重要となる。 具体的には、最初の課題として、計算リソースを異なるスパース操作にカスタマイズし、使用済みリソースの合計を予算未満に制限する。 第2の課題として、サンプリング済みスパース行列をキャッシュし、エポックワイズサンプリングオーバーヘッドを削減する。 最後に,近似演算で学習したgnnの一般化を改善するスイッチング機構を提案する。 そこで本研究では,GNNを近似演算でトレーニングする可能性を初めて示すランダム化スパース計算を提案する。 実際には、rscは1回のスパース操作で最大11.6\times$ speedupを達成でき、エンドツーエンドのウォールクロックタイムスピードアップは1.6\times$である。

関連論文リスト

• Exploiting Symmetric Temporally Sparse BPTT for Efficient RNN Training [20.49255973077044]
  この研究は、デルタRNNのトレーニングアルゴリズムを記述し、後方伝播フェーズにおける時間的間隔を利用してエッジでのトレーニングの計算要求を減らした。 その結果,Fluent Speech Commandsデータセット上で,56kパラメータのDelta LSTMをトレーニングするための行列演算の$sim$80%の削減効果が認められた。 提案したDelta RNNトレーニングは,限られたコンピューティングリソースを持つエッジデバイス上でのオンラインインクリメンタル学習に有用であることを示す。
  論文  参考訳（メタデータ） (2023-12-14T23:07:37Z)
• Eva: A General Vectorized Approximation Framework for Second-order Optimization [16.647611352181574]
  メモリ効率と時間効率の2次アルゴリズムであるEvaを2つの新しい手法で提案する。 我々はシャーマン・モリソンの公式を使用する逆計算を明示的に行わずに効率的な更新式を導出する。 実験によると、Evaは1次SGDと2次アルゴリズムと比較して、エンドツーエンドのトレーニング時間を2.05倍と2.42倍に短縮する。
  論文  参考訳（メタデータ） (2023-08-04T03:51:38Z)
• Learning the Positions in CountSketch [49.57951567374372]
  本稿では,まずランダムなスケッチ行列に乗じてデータを圧縮し,最適化問題を高速に解くスケッチアルゴリズムについて検討する。 本研究では,ゼロでないエントリの位置を最適化する学習ベースアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-06-11T07:28:35Z)
• Efficient Dataset Distillation Using Random Feature Approximation [109.07737733329019]
  本稿では,ニューラルネットワークガウス過程(NNGP)カーネルのランダム特徴近似(RFA)を用いた新しいアルゴリズムを提案する。 我々のアルゴリズムは、KIP上で少なくとも100倍のスピードアップを提供し、1つのGPUで実行できる。 RFA蒸留 (RFAD) と呼ばれる本手法は, 大規模データセットの精度において, KIP や他のデータセット凝縮アルゴリズムと競合して動作する。
  論文  参考訳（メタデータ） (2022-10-21T15:56:13Z)
• Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
  我々はスケッチを利用した新しい分散Adam型アルゴリズムのクラス(例:SketchedAMSGrad)を提案する。 我々の新しいアルゴリズムは、反復毎に$O(frac1sqrtnT + frac1(k/d)2 T)$の高速収束率を$O(k log(d))$の通信コストで達成する。
  論文  参考訳（メタデータ） (2022-10-14T01:42:05Z)
• Scalable Optimal Transport in High Dimensions for Graph Distances, Embedding Alignment, and More [7.484063729015126]
  最適輸送のためのコスト行列の2つの効率的な対数線形時間近似を提案する。 これらの近似は、複雑な高次元空間に対してもよく機能するエントロピー規則化OTに対する一般的な対数線形時間アルゴリズムを可能にする。 グラフ距離回帰のために,グラフニューラルネットワーク(GNN)と拡張シンクホーンを組み合わせたグラフトランスポートネットワーク(GTN)を提案する。
  論文  参考訳（メタデータ） (2021-07-14T17:40:08Z)
• Fast and Accurate Pseudoinverse with Sparse Matrix Reordering and Incremental Approach [4.710916891482697]
  擬逆は行列逆の一般化であり、機械学習で広く利用されている。 FastPIはスパース行列に対する新たなインクリメンタル特異値分解法(SVD)である。 我々は,FastPIが精度を損なうことなく,他の近似手法よりも高速に擬似逆計算を行うことを示す。
  論文  参考訳（メタデータ） (2020-11-09T07:47:10Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Learning Low-rank Deep Neural Networks via Singular Vector Orthogonality Regularization and Singular Value Sparsification [53.50708351813565]
  各ステップにSVDを適用することなく、トレーニング中に低ランクDNNを明示的に達成する最初の方法であるSVDトレーニングを提案する。 SVDトレーニングがDNN層のランクを著しく低減し,同じ精度で計算負荷の低減を実現することを実証的に示す。
  論文  参考訳（メタデータ） (2020-04-20T02:40:43Z)

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

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