論文の概要: Tuple Packing: Efficient Batching of Small Graphs in Graph Neural Networks

• arxiv url: http://arxiv.org/abs/2209.06354v1
• Date: Wed, 14 Sep 2022 00:32:51 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-15 13:46:08.009575
• Title: Tuple Packing: Efficient Batching of Small Graphs in Graph Neural Networks
• Title（参考訳）: タプルパッキング:グラフニューラルネットワークにおける小さなグラフの効率的なバッチ化
• Authors: Mario Michael Krell, Manuel Lopez, Sreenidhi Anand, Hatem Helal, Andrew William Fitzgibbon
• Abstract要約: いくつかの小さなグラフを1つの全体グラフに組み合わせることで、処理を高速化し、パディングのオーバーヘッドを減らすことが一般的である。 小さいグラフのサイズはノード数やエッジ数によって大きく異なるため、組み合わせたグラフのサイズは依然としてかなり異なる。 本稿では、最小限のオーバーヘッドを引き起こすバッチを生成するための新しいアプローチであるパッキングを提案する。
• 参考スコア（独自算出の注目度）: 0.4893345190925178
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: When processing a batch of graphs in machine learning models such as Graph Neural Networks (GNN), it is common to combine several small graphs into one overall graph to accelerate processing and reduce the overhead of padding. This is for example supported in the PyG library. However, the sizes of small graphs can vary substantially with respect to the number of nodes and edges, and hence the size of the combined graph can still vary considerably, especially for small batch sizes. So the costs of excessive padding and wasted compute are still incurred. This paper proposes a new approach -- tuple packing -- for generating batches that cause minimal overhead. The algorithm extends recently introduced sequence packing approaches to work on the 2D tuples of (|nodes|, |edges|). A monotone heuristic is applied to the 2D histogram of tuple values to define a priority for packing histogram bins together with the objective to reach a limit on the number of nodes as well as the number of edges. Experiments verify the effectiveness of the algorithm on multiple datasets.
• Abstract（参考訳）: グラフニューラルネットワーク(GNN)のような機械学習モデルでグラフのバッチを処理する場合、複数の小さなグラフを1つのグラフに組み合わせて処理を高速化し、パディングのオーバーヘッドを低減することが一般的である。 これは例えば、PyGライブラリでサポートされている。 しかし、小さなグラフのサイズはノード数やエッジ数によって大きく異なるため、特に小さなバッチサイズでは、結合グラフのサイズが依然として大きく変化する可能性がある。 したがって、過剰なパディングと無駄な計算のコストはいまだに発生しています。 本稿では,最小のオーバヘッドを発生させるバッチ生成のための新しいアプローチであるタプルパッキングを提案する。 このアルゴリズムは(|nodes|, |edges|)の2dタプルに取り組むために最近導入されたシーケンスパッキングアプローチを拡張している。 タプル値の2次元ヒストグラムにモノトンヒューリスティックを適用し、ヒストグラムビンをパックする優先事項と、ノード数とエッジ数に限界に達する目的を定義する。 実験は、複数のデータセットにおけるアルゴリズムの有効性を検証する。

関連論文リスト

• Learning on Large Graphs using Intersecting Communities [13.053266613831447]
  MPNNは、各ノードの隣人からのメッセージを集約することで、入力グラフ内の各ノードの表現を反復的に更新する。 MPNNは、あまりスパースではないため、すぐに大きなグラフの禁止になるかもしれない。 本稿では,入力グラフを交差するコミュニティグラフ (ICG) として近似することを提案する。
  論文  参考訳（メタデータ） (2024-05-31T09:26:26Z)
• NodeFormer: A Scalable Graph Structure Learning Transformer for Node Classification [70.51126383984555]
  本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。 効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。 グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
  論文  参考訳（メタデータ） (2023-06-14T09:21:15Z)
• DOTIN: Dropping Task-Irrelevant Nodes for GNNs [119.17997089267124]
  最近のグラフ学習アプローチでは、学習のためのグラフのサイズを減らすためのプール戦略が導入されている。 我々はDOTIN(underlineDrunderlineopping underlineTask-underlineIrrelevant underlineNodes)と呼ばれる新しいアプローチを設計し、グラフのサイズを減らす。 本手法は,グラフ分類やグラフ編集距離を含むグラフレベルのタスクにおいて,GATを約50%高速化する。
  論文  参考訳（メタデータ） (2022-04-28T12:00:39Z)
• Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
  グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。 GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。 提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
  論文  参考訳（メタデータ） (2022-03-03T09:53:53Z)
• Neighbor2Seq: Deep Learning on Massive Graphs by Transforming Neighbors to Sequences [55.329402218608365]
  本研究では,各ノードの階層的近傍をシーケンスに変換するためにNeighbor2Seqを提案する。 1100万以上のノードと160億のエッジを持つ大規模グラフ上で,本手法の評価を行った。 その結果,提案手法は大規模グラフに対してスケーラブルであり,大規模グラフと中規模グラフにまたがる優れた性能を実現する。
  論文  参考訳（メタデータ） (2022-02-07T16:38:36Z)
• RaWaNet: Enriching Graph Neural Network Input via Random Walks on Graphs [0.0]
  グラフニューラルネットワーク(GNN)の人気が高まっており、グラフで表されるデータに対して非常に有望な結果を示している。 本稿では,3つの選択された長さに基づいて,グラフのランダムなウォークデータ処理を提案する。すなわち,グラフ上の局所的および大域的ダイナミクスを捉えるために,長さ1,2の(正規)ウォークと長さ0,1$の分節ウォークを提案する。 本手法は, 処理ノードの特徴をネットワークに渡すことによって, 様々な分子データセット上で検証し, 分類および回帰処理を行う。
  論文  参考訳（メタデータ） (2021-09-15T20:04:01Z)
• FeatGraph: A Flexible and Efficient Backend for Graph Neural Network Systems [23.258185277825888]
  FeatGraphは多様なGNNモデルを表現するためのフレキシブルなプログラミングインターフェースを提供する。 FeatGraphは、エンドツーエンドのGNNトレーニングと推論をCPUで最大32倍、GPUで最大7倍高速化する。
  論文  参考訳（メタデータ） (2020-08-26T03:17:05Z)
• Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
  GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。 高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。 このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
  論文  参考訳（メタデータ） (2020-07-03T09:30:07Z)
• Sequential Graph Convolutional Network for Active Learning [53.99104862192055]
  逐次グラフ畳み込みネットワーク(GCN)を用いた新しいプールベースアクティブラーニングフレームワークを提案する。 少数のランダムなサンプル画像がシードラベル付き例であるので、グラフのパラメータを学習してラベル付きノードと非ラベル付きノードを区別する。 我々はGCNの特性を利用してラベル付けされたものと十分に異なる未ラベルの例を選択する。
  論文  参考訳（メタデータ） (2020-06-18T00:55:10Z)

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

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