論文の概要: 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})の認定アンラーニングを達成したことだ。
私たちのコードはオンラインで利用可能です。
関連論文リスト
- Gradient Transformation: Towards Efficient and Model-Agnostic Unlearning for Dynamic Graph Neural Networks [66.70786325911124]
グラフアンラーニングは、ユーザのプライバシ保護と、望ましくないデータによるネガティブな影響軽減に不可欠なツールとして登場した。
DGNNの普及に伴い、動的グラフアンラーニングの実装を検討することが不可欠となる。
DGNNアンラーニングを実装するために,効率的,効率的,モデルに依存しない,事後処理手法を提案する。
論文 参考訳(メタデータ) (2024-05-23T10:26:18Z) - Graph Transformers for Large Graphs [57.19338459218758]
この研究は、モデルの特徴と重要な設計制約を識別することに焦点を当てた、単一の大規模グラフでの表現学習を前進させる。
この研究の重要な革新は、局所的な注意機構と組み合わされた高速な近傍サンプリング技術の作成である。
ogbn-products と snap-patents の3倍の高速化と16.8%の性能向上を報告し、ogbn-100M で LargeGT を5.9% の性能改善で拡張した。
論文 参考訳(メタデータ) (2023-12-18T11:19:23Z) - Less Can Be More: Unsupervised Graph Pruning for Large-scale Dynamic
Graphs [42.864057751606616]
動的グラフ上での教師なしグラフプルーニングの問題を提案し,検討する。
提案するSTEPフレームワークは,入力動的グラフから潜在的に冗長なエッジを取り除くことを学習する。
実世界の3つのデータセットに対する我々の結果は、GNNの有効性、堅牢性、効率性を改善する利点を実証している。
論文 参考訳(メタデータ) (2023-05-18T03:23:53Z) - Distributed Graph Embedding with Information-Oriented Random Walks [16.290803469068145]
グラフ埋め込みはグラフノードを低次元ベクトルにマッピングし、機械学習タスクで広く採用されている。
数十億のエッジグラフを埋め込むためにスケール可能な,汎用的で分散された情報中心のランダムウォークベースのグラフ埋め込みフレームワークであるDistGERを提案する。
D DistGERは2.33x-129x加速、機械間通信の45%削減、下流タスクの10%改善を示す。
論文 参考訳(メタデータ) (2023-03-28T03:11:21Z) - Localized Contrastive Learning on Graphs [110.54606263711385]
局所グラフコントラスト学習(Local-GCL)という,シンプルだが効果的なコントラストモデルを導入する。
その単純さにもかかわらず、Local-GCLは、様々なスケールと特性を持つグラフ上の自己教師付きノード表現学習タスクにおいて、非常に競争力のある性能を達成する。
論文 参考訳(メタデータ) (2022-12-08T23:36:00Z) - Unlearning Graph Classifiers with Limited Data Resources [39.29148804411811]
制御されたデータ削除は、データに敏感なWebアプリケーションのための機械学習モデルの重要機能になりつつある。
グラフニューラルネットワーク(GNN)の効率的な機械学習を実現する方法はまだほとんど知られていない。
我々の主な貢献は GST に基づく非線形近似グラフアンラーニング法である。
第2の貢献は、提案した未学習機構の計算複雑性の理論解析である。
第3のコントリビューションは広範囲なシミュレーションの結果であり、削除要求毎のGNNの完全再トレーニングと比較して、新しいGSTベースのアプローチは平均10.38倍のスピードアップを提供する。
論文 参考訳(メタデータ) (2022-11-06T20:46:50Z) - 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) - Optimal Propagation for Graph Neural Networks [51.08426265813481]
最適グラフ構造を学習するための二段階最適化手法を提案する。
また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
論文 参考訳(メタデータ) (2022-05-06T03:37:00Z) - GraphTheta: A Distributed Graph Neural Network Learning System With
Flexible Training Strategy [5.466414428765544]
新しい分散グラフ学習システムGraphThetaを紹介します。
複数のトレーニング戦略をサポートし、大規模グラフ上で効率的でスケーラブルな学習を可能にします。
この仕事は、文学における10億規模のネットワーク上で実施された最大のエッジアトリビュートGNN学習タスクを表します。
論文 参考訳(メタデータ) (2021-04-21T14:51:33Z) - Robust Optimization as Data Augmentation for Large-scale Graphs [117.2376815614148]
学習中に勾配に基づく逆方向摂動を伴うノード特徴を反復的に拡張するFLAG(Free Large-scale Adversarial Augmentation on Graphs)を提案する。
FLAGはグラフデータに対する汎用的なアプローチであり、ノード分類、リンク予測、グラフ分類タスクで普遍的に機能する。
論文 参考訳(メタデータ) (2020-10-19T21:51:47Z) - Scaling Graph Neural Networks with Approximate PageRank [64.92311737049054]
GNNにおける情報拡散の効率的な近似を利用したPPRGoモデルを提案する。
高速であることに加えて、PPRGoは本質的にスケーラブルであり、業界設定で見られるような大規模なデータセットに対して、自明に並列化することができる。
このグラフのすべてのノードに対するPPRGoのトレーニングとラベルの予測には1台のマシンで2分未満で、同じグラフ上の他のベースラインをはるかに上回ります。
論文 参考訳(メタデータ) (2020-07-03T09:30:07Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。