論文の概要: Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier
- arxiv url: http://arxiv.org/abs/2408.09212v2
- Date: Thu, 10 Oct 2024 02:47:33 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-11 14:28:02.509404
- Title: Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier
- Title(参考訳): スケーラブルで認証可能なグラフアンラーニング - 近似エラーバリアの克服
- Authors: Lu Yi, Zhewei Wei,
- Abstract要約: 認定されたグラフを10億のエッジグラフにスケールする最初のアプローチであるScaleGUNを紹介する。
ScaleGUNは、20秒で10億のエッジグラフogbn-papers 100Mの認定アンラーニングを達成している(epsilon,delta)= (1,10-4)。
- 参考スコア(独自算出の注目度): 28.482705188786703
- License:
- Abstract: Graph unlearning has emerged as a pivotal research area for ensuring privacy protection, given the widespread adoption of Graph Neural Networks (GNNs) in applications involving sensitive user data. Among existing studies, certified graph unlearning is distinguished by providing robust privacy guarantees. However, current certified graph unlearning methods are impractical for large-scale graphs because they necessitate the costly re-computation of graph propagation for each unlearning request. Although numerous scalable techniques have been developed to accelerate graph propagation for GNNs, their integration into certified graph unlearning remains uncertain as these scalable approaches introduce approximation errors into node embeddings. In contrast, certified graph unlearning demands bounded model error on exact node embeddings to maintain its certified guarantee. To address this challenge, we present ScaleGUN, the first approach to scale certified graph unlearning to billion-edge graphs. ScaleGUN integrates the approximate graph propagation technique into certified graph unlearning, offering certified guarantees for three unlearning scenarios: node feature, edge, and node unlearning. Extensive experiments on real-world datasets demonstrate the efficiency and unlearning 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 5,000 random edge removal request -- of which only 5 seconds are required for updating the node embeddings -- compared to 1.91 hours for retraining and 1.89 hours for re-propagation. Our code is available at https://github.com/luyi256/ScaleGUN.
- Abstract(参考訳): 機密性の高いユーザデータに関わるアプリケーションにグラフニューラルネットワーク(GNN)が広く採用されていることを考えると、グラフアンラーニングはプライバシ保護を確実にするための重要な研究領域として現れている。
既存の研究の中で、認定されたグラフアンラーニングは、堅牢なプライバシー保証を提供することによって区別される。
しかし,現在認定されているグラフアンラーニング手法は,各未学習要求に対するグラフの計算に費用がかかるため,大規模グラフでは実用的ではない。
GNNのグラフ伝播を促進するために、多くのスケーラブルな技術が開発されているが、これらのスケーラブルなアプローチがノード埋め込みに近似誤差を導入しているため、認定グラフへの統合は不確実である。
これとは対照的に、認定されたグラフアンラーニングは、認証された保証を維持するために、正確なノード埋め込みに対する境界付きモデルエラーを要求する。
この課題に対処するために、認定されたグラフを10億のエッジグラフにスケールする最初のアプローチであるScaleGUNを紹介します。
ScaleGUNは、近似グラフ伝搬テクニックを認定グラフアンラーニングに統合し、ノード機能、エッジ、ノードアンラーニングという3つの未学習シナリオの保証を提供する。
実世界のデータセットに関する大規模な実験は、ScaleGUNの効率性と未学習の有効性を示している。
注目すべきは、ScaleGUNが5,000のランダムエッジ削除要求に対して、数十億のエッジグラフogbn-papers100Mで20秒で認定された未学習を達成していることだ。
私たちのコードはhttps://github.com/luyi256/ScaleGUNで利用可能です。
関連論文リスト
- 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。