論文の概要: Scalable and Certifiable Graph Unlearning via Lazy Local Propagation
- arxiv url: http://arxiv.org/abs/2408.09212v1
- Date: Sat, 17 Aug 2024 14:41:02 GMT
- ステータス: 処理完了
- システム内更新日: 2024-08-20 21:50:21.934517
- Title: Scalable and Certifiable Graph Unlearning via Lazy Local Propagation
- Title(参考訳): Lazy Local Propagationによるスケーラブルで認証可能なグラフアンラーニング
- Authors: Lu Yi, Zhewei Wei,
- Abstract要約: ScaleGUNは、数十億のエッジグラフにスケールする、最初の認定可能なグラフアンラーニングメカニズムである。
実世界のデータセットの実験はScaleGUNの有効性と有効性を示している。
- 参考スコア(独自算出の注目度): 28.482705188786703
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: With the recent adoption of laws supporting the ``right to be forgotten'' and the widespread use of Graph Neural Networks for modeling graph-structured data, graph unlearning has emerged as a crucial research area. Current studies focus on the efficient update of model parameters. However, they often overlook the time-consuming re-computation of graph propagation required for each removal, significantly limiting their scalability on large graphs. In this paper, we present ScaleGUN, the first certifiable graph unlearning mechanism that scales to billion-edge graphs. ScaleGUN employs a lazy local propagation method to facilitate efficient updates of the embedding matrix during data removal. Such lazy local propagation can be proven to ensure certified unlearning under all three graph unlearning scenarios, including node feature, edge, and node unlearning. Extensive experiments on real-world datasets demonstrate the efficiency and efficacy of ScaleGUN. Remarkably, ScaleGUN accomplishes $(\epsilon,\delta)=(1,10^{-4})$ certified unlearning on the billion-edge graph ogbn-papers100M in 20 seconds for a $5K$-random-edge removal request -- of which only 5 seconds are required for updating the embedding matrix -- compared to 1.91 hours for retraining and 1.89 hours for re-propagation. Our code is available online.
- Abstract(参考訳): グラフ構造化データのモデリングにグラフニューラルネットワークが広く使用されるようになったことで、グラフアンラーニングは重要な研究分野となった。
最近の研究は、モデルパラメータの効率的な更新に焦点を当てている。
しかし、各削除に要するグラフの伝播の計算に要する時間がかかり、大きなグラフのスケーラビリティが著しく制限されるのをしばしば見落としている。
本稿では,10億のエッジグラフにスケールする最初の認証済みグラフアンラーニング機構であるScaleGUNを提案する。
ScaleGUNは遅延局所伝搬法を用いて,データ削除時の埋め込み行列の効率的な更新を容易にする。
このような遅延ローカルな伝搬は、ノード機能、エッジ、ノードアンラーニングを含む3つのグラフアンラーニングシナリオのすべてにおいて、認証されたアンラーニングを保証するために証明できる。
実世界のデータセットに関する大規模な実験は、ScaleGUNの効率性と有効性を示している。
注目すべきは、ScaleGUNが$(\epsilon,\delta)=(1,10^{-4})の認定アンラーニングを達成したことだ。
私たちのコードはオンラインで利用可能です。
関連論文リスト
- Graph Coarsening via Supervised Granular-Ball for Scalable Graph Neural Network Training [30.354103857690777]
グラフデータを効果的に圧縮するために粒度計算を用いる。
我々は、純度閾値に基づいてグラフをグラニュラーボールに繰り返し分割することにより、粗いグラフネットワークを構築する。
我々のアルゴリズムは、予め定義された粗大化率を必要とせずに、スプリッティングを適応的に行うことができる。
論文 参考訳(メタデータ) (2024-12-18T13:36:03Z) - GraphGuard: Detecting and Counteracting Training Data Misuse in Graph
Neural Networks [69.97213941893351]
グラフデータ分析におけるグラフニューラルネットワーク(GNN)の出現は、モデルトレーニング中のデータ誤用に関する重要な懸念を引き起こしている。
既存の手法は、データ誤用検出または緩和のいずれかに対応しており、主にローカルGNNモデル用に設計されている。
本稿では,これらの課題に対処するため,GraphGuardという先駆的なアプローチを導入する。
論文 参考訳(メタデータ) (2023-12-13T02:59:37Z) - NodeFormer: A Scalable Graph Structure Learning Transformer for Node
Classification [70.51126383984555]
本稿では,任意のノード間のノード信号を効率的に伝搬する全ペアメッセージパッシング方式を提案する。
効率的な計算は、カーナライズされたGumbel-Softmax演算子によって実現される。
グラフ上のノード分類を含む様々なタスクにおいて,本手法の有望な有効性を示す実験を行った。
論文 参考訳(メタデータ) (2023-06-14T09:21:15Z) - Unlearning Graph Classifiers with Limited Data Resources [39.29148804411811]
制御されたデータ削除は、データに敏感なWebアプリケーションのための機械学習モデルの重要機能になりつつある。
グラフニューラルネットワーク(GNN)の効率的な機械学習を実現する方法はまだほとんど知られていない。
我々の主な貢献は GST に基づく非線形近似グラフアンラーニング法である。
第2の貢献は、提案した未学習機構の計算複雑性の理論解析である。
第3のコントリビューションは広範囲なシミュレーションの結果であり、削除要求毎のGNNの完全再トレーニングと比較して、新しいGSTベースのアプローチは平均10.38倍のスピードアップを提供する。
論文 参考訳(メタデータ) (2022-11-06T20:46:50Z) - Training Graph Neural Networks on Growing Stochastic Graphs [114.75710379125412]
グラフニューラルネットワーク(GNN)は、ネットワーク化されたデータの意味のあるパターンを活用するために、グラフ畳み込みに依存している。
我々は,成長するグラフ列の極限オブジェクトであるグラフオンを利用して,非常に大きなグラフ上のGNNを学習することを提案する。
論文 参考訳(メタデータ) (2022-10-27T16:00:45Z) - SCARA: Scalable Graph Neural Networks with Feature-Oriented Optimization [23.609017952951454]
グラフ計算のための特徴指向最適化を備えたスケーラブルグラフニューラルネットワーク(GNN)であるSCARAを提案する。
SCARAはノードの特徴からグラフの埋め込みを効率的に計算し、機能の結果を選択して再利用することでオーバーヘッドを減らします。
利用可能な最大10億のGNNデータセットであるPapers100M(1110万ノード、1.6Bエッジ)を100秒でプリ計算するのが効率的である。
論文 参考訳(メタデータ) (2022-07-19T10:32:11Z) - Comprehensive Graph Gradual Pruning for Sparse Training in Graph Neural
Networks [52.566735716983956]
本稿では,CGPと呼ばれるグラフの段階的プルーニングフレームワークを動的にGNNに提案する。
LTHに基づく手法とは異なり、提案手法では再学習を必要とせず、計算コストを大幅に削減する。
提案手法は,既存の手法の精度を一致させたり,あるいは超えたりしながら,トレーニングと推論の効率を大幅に向上させる。
論文 参考訳(メタデータ) (2022-07-18T14:23:31Z) - Certified Graph Unlearning [39.29148804411811]
グラフ構造化データは実際にユビキタスであり、しばしばグラフニューラルネットワーク(GNN)を使用して処理される
我々は,GNNのemph認定グラフアンラーニングのための最初のフレームワークを紹介する。
ノード機能、エッジ、ノードアンラーニングの3つの異なるタイプのアンラーニング要求を検討する必要がある。
論文 参考訳(メタデータ) (2022-06-18T07:41:10Z) - Neural Graph Matching for Pre-training Graph Neural Networks [72.32801428070749]
グラフニューラルネットワーク(GNN)は、構造データのモデリングにおいて強力な能力を示している。
GMPTと呼ばれる新しいグラフマッチングベースのGNN事前学習フレームワークを提案する。
提案手法は,完全自己指導型プレトレーニングと粗粒型プレトレーニングに適用できる。
論文 参考訳(メタデータ) (2022-03-03T09:53:53Z) - GraphMI: Extracting Private Graph Data from Graph Neural Networks [59.05178231559796]
GNNを反転させてトレーニンググラフのプライベートグラフデータを抽出することを目的とした textbfGraph textbfModel textbfInversion attack (GraphMI) を提案する。
具体的には,グラフ特徴の空間性と滑らかさを保ちながら,グラフエッジの離散性に対処する勾配モジュールを提案する。
エッジ推論のためのグラフトポロジ、ノード属性、ターゲットモデルパラメータを効率的に活用するグラフ自動エンコーダモジュールを設計する。
論文 参考訳(メタデータ) (2021-06-05T07:07:52Z) - GraphTheta: A Distributed Graph Neural Network Learning System With
Flexible Training Strategy [5.466414428765544]
新しい分散グラフ学習システムGraphThetaを紹介します。
複数のトレーニング戦略をサポートし、大規模グラフ上で効率的でスケーラブルな学習を可能にします。
この仕事は、文学における10億規模のネットワーク上で実施された最大のエッジアトリビュートGNN学習タスクを表します。
論文 参考訳(メタデータ) (2021-04-21T14:51:33Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。