論文の概要: Bonsai: Gradient-free Graph Distillation for Node Classification
- arxiv url: http://arxiv.org/abs/2410.17579v2
- Date: Thu, 24 Oct 2024 05:24:53 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-28 17:07:39.337717
- Title: Bonsai: Gradient-free Graph Distillation for Node Classification
- Title(参考訳): Bonsai: ノード分類のためのグラディエントフリーグラフ蒸留
- Authors: Mridul Gupta, Samyak Jain, Vansh Ramani, Hariprasad Kodamana, Sayan Ranu,
- Abstract要約: グラフ蒸留は、GNNのスケーラブルなトレーニングを可能にするための有望な道として登場した。
本研究は, 現行のグラフ蒸留技術において, 重大な欠点を明らかにするものである。
本稿では,テキスト計算木がメッセージパッシングGNNの基本処理単位を形成するという観察により,新しいグラフ蒸留法であるボンサイについて述べる。
- 参考スコア(独自算出の注目度): 16.96628744692792
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: Graph distillation has emerged as a promising avenue to enable scalable training of GNNs by compressing the training dataset while preserving essential graph characteristics. Our study uncovers significant shortcomings in current graph distillation techniques. First, the majority of the algorithms paradoxically require training on the full dataset to perform distillation. Second, due to their gradient-emulating approach, these methods require fresh distillation for any change in hyperparameters or GNN architecture, limiting their flexibility and reusability. Finally, they fail to achieve substantial size reduction due to synthesizing fully-connected, edge-weighted graphs. To address these challenges, we present Bonsai, a novel graph distillation method empowered by the observation that \textit{computation trees} form the fundamental processing units of message-passing GNNs. Bonsai distills datasets by encoding a careful selection of \textit{exemplar} trees that maximize the representation of all computation trees in the training set. This unique approach imparts Bonsai as the first linear-time, model-agnostic graph distillation algorithm for node classification that outperforms existing baselines across $6$ real-world datasets on accuracy, while being $22$ times faster on average. Bonsai is grounded in rigorous mathematical guarantees on the adopted approximation strategies making it robust to GNN architectures, datasets, and parameters.
- Abstract(参考訳): グラフ蒸留は、トレーニングデータセットを圧縮し、重要なグラフ特性を保持しながら、GNNのスケーラブルなトレーニングを可能にするための、有望な道として登場した。
本研究は, 現行のグラフ蒸留技術において, 重大な欠点を明らかにするものである。
第一に、アルゴリズムの大半はパラドックス的に全データセットのトレーニングを必要として蒸留を行う。
第二に、勾配エミュレーションのアプローチのため、これらの手法はハイパーパラメータやGNNアーキテクチャの変更に対して新鮮な蒸留を必要とし、柔軟性と再利用性を制限する。
最後に、完全に連結されたエッジ重み付きグラフを合成するため、相当なサイズの縮小を達成できない。
これらの課題に対処するため,<textit{computation tree} がメッセージパッシングGNNの基本処理単位を形成するという観測により,新しいグラフ蒸留法であるボンサイを提案する。
Bonsaiは、トレーニングセット内のすべての計算ツリーの表現を最大化する‘textit{exemplar}木’を慎重に選択することで、データセットを蒸留する。
このユニークなアプローチは、Bonsaiを、ノード分類のための最初の線形時間モデルに依存しないグラフ蒸留アルゴリズムとして生み出す。
Bonsaiは、GNNアーキテクチャやデータセット、パラメータに対して堅牢な近似戦略を採用した厳密な数学的保証を基礎としている。
関連論文リスト
- Virtual Node Generation for Node Classification in Sparsely-Labeled Graphs [2.0060301665996016]
本稿では,グラフに付加されたラベル付きノードとして,少数の高品質な合成ノードを注入する新しいノード生成手法を提案する。
一般的なグラフ事前学習(自己教師付き学習)、半教師付き学習、メタ学習法と互換性がある。
実験では、公開されている10のデータセットに対して、14のベースラインに対して統計的に有意なパフォーマンス改善を実証した。
論文 参考訳(メタデータ) (2024-09-12T02:36:44Z) - GSTAM: Efficient Graph Distillation with Structural Attention-Matching [13.673737442696154]
本稿では,グラフ分類データセットを凝縮する新しい手法であるGSTAM(Graph Distillation with Structure Attention Matching)を紹介する。
GSTAMは、GNNの注意マップを利用して、元のデータセットから合成グラフに構造情報を抽出する。
総合的な実験では、GSTAMは既存の方法よりも優れており、極端な凝縮比では0.45%から6.5%の性能が向上している。
論文 参考訳(メタデータ) (2024-08-29T19:40:04Z) - Graph Data Condensation via Self-expressive Graph Structure Reconstruction [7.4525875528900665]
我々は textbfSelf-presentive Graph Structure textbfReconstruction による textbfGraph Data textbfCondensation という新しいフレームワークを紹介した。
提案手法は,元のグラフ構造を凝縮過程に明示的に組み込んで,凝縮ノード間の不規則な相互依存性を捕捉する。
論文 参考訳(メタデータ) (2024-03-12T03:54:25Z) - Disentangled Condensation for Large-scale Graphs [29.384060761810172]
グラフニューラルネットワーク(GNN)の高価なトレーニングコストを節約するための興味深いテクニックとして、グラフ凝縮が登場した。
本稿では, 凝縮過程を2段階のGNNフリーパラダイムに分解し, ノードを独立に凝縮し, エッジを生成することを提案する。
この単純で効果的なアプローチは、中規模グラフの精度に匹敵する精度で最先端の手法よりも少なくとも10倍早く達成できる。
論文 参考訳(メタデータ) (2024-01-18T09:59:00Z) - Deep Manifold Graph Auto-Encoder for Attributed Graph Embedding [51.75091298017941]
本稿では,属性付きグラフデータに対する新しいDeep Manifold (Variational) Graph Auto-Encoder (DMVGAE/DMGAE)を提案する。
提案手法は,最先端のベースラインアルゴリズムを,一般的なデータセット間でのダウンストリームタスクの差を大きく越える。
論文 参考訳(メタデータ) (2024-01-12T17:57:07Z) - Efficient Heterogeneous Graph Learning via Random Projection [58.4138636866903]
不均一グラフニューラルネットワーク(HGNN)は、異種グラフを深層学習するための強力なツールである。
最近のプリ計算ベースのHGNNは、一時間メッセージパッシングを使用して不均一グラフを正規形テンソルに変換する。
我々はRandom Projection Heterogeneous Graph Neural Network (RpHGNN) というハイブリッド計算前HGNNを提案する。
論文 参考訳(メタデータ) (2023-10-23T01:25:44Z) - Mirage: Model-Agnostic Graph Distillation for Graph Classification [16.764894668661952]
グラフ蒸留は、元のトレーニングデータからより小さな合成トレーニングセットを構築するための試みである。
Mirageは、メッセージパスGNNが入力グラフを複数の計算ツリーに分解する、という洞察に基づいて構築されている。
論文 参考訳(メタデータ) (2023-10-14T04:21:52Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Structure-free Graph Condensation: From Large-scale Graphs to Condensed
Graph-free Data [91.27527985415007]
既存のグラフ凝縮法は、凝縮グラフ内のノードと構造の合同最適化に依存している。
我々は、大規模グラフを小さなグラフノード集合に蒸留する、SFGCと呼ばれる新しい構造自由グラフ凝縮パラダイムを提唱する。
論文 参考訳(メタデータ) (2023-06-05T07:53:52Z) - Addressing Heterophily in Node Classification with Graph Echo State
Networks [11.52174067809364]
ノード分類のためのグラフエコー状態ネットワーク(GESN)を用いた異種グラフの課題に対処する。
GESNはグラフのための貯水池計算モデルであり、ノードの埋め込みは訓練されていないメッセージパッシング関数によって計算される。
実験の結果, 貯水池モデルでは, ほぼ完全に訓練された深層モデルに対して, より優れた精度あるいは同等の精度が得られることがわかった。
論文 参考訳(メタデータ) (2023-05-14T19:42:31Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳(メタデータ) (2022-07-18T14:23:31Z) - Condensing Graphs via One-Step Gradient Matching [50.07587238142548]
ネットワーク重みを訓練せずに1ステップのみの勾配マッチングを行う1ステップ勾配マッチング方式を提案する。
我々の理論的分析は、この戦略が実際のグラフの分類損失を減少させる合成グラフを生成することができることを示している。
特に、元のパフォーマンスの最大98%を近似しながら、データセットサイズを90%削減することが可能です。
論文 参考訳(メタデータ) (2022-06-15T18:20:01Z) - Training Robust Graph Neural Networks with Topology Adaptive Edge
Dropping [116.26579152942162]
グラフニューラルネットワーク(GNN)は、グラフ構造情報を利用してネットワークデータから表現をモデル化する処理アーキテクチャである。
彼らの成功にもかかわらず、GNNは限られた訓練データから得られる準最適一般化性能に悩まされている。
本稿では、一般化性能を改善し、堅牢なGNNモデルを学習するためのトポロジ適応エッジドロップ法を提案する。
論文 参考訳(メタデータ) (2021-06-05T13:20:36Z) - Heuristic Semi-Supervised Learning for Graph Generation Inspired by
Electoral College [80.67842220664231]
本稿では,新たなノードやエッジを自動的に拡張して,高密度サブグラフ内のラベル類似性を向上する,新しい前処理手法であるElectoral College(ELCO)を提案する。
テストされたすべての設定において、我々の手法はベースモデルの平均スコアを4.7ポイントの広いマージンで引き上げるとともに、常に最先端のモデルよりも優れています。
論文 参考訳(メタデータ) (2020-06-10T14:48:48Z) - Graph Ordering: Towards the Optimal by Learning [69.72656588714155]
グラフ表現学習は、ノード分類、予測、コミュニティ検出など、多くのグラフベースのアプリケーションで顕著な成功を収めている。
しかし,グラフ圧縮やエッジ分割などのグラフアプリケーションでは,グラフ表現学習タスクに還元することは極めて困難である。
本稿では,このようなアプリケーションの背後にあるグラフ順序付け問題に対して,新しい学習手法を用いて対処することを提案する。
論文 参考訳(メタデータ) (2020-01-18T09:14:16Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。