Fugu-MT 論文翻訳(概要): Scalable and Certifiable Graph Unlearning: Overcoming the Approximation Error Barrier

論文の概要: 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-11-08 07:07:05.246482
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: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
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で利用可能です。

関連論文リスト

Community-Centric Graph Unlearning [10.906555492206959]
我々は、新しいグラフ構造マッピング・アンラーニング・パラダイム(GSMU)と、それに基づく新しい手法CGE(Community-centric Graph Eraser)を提案する。 CGEは、コミュニティのサブグラフをノードにマッピングすることで、少ないマップ付きグラフ内でノードレベルの未学習操作の再構築を可能にする。
論文参考訳（メタデータ） (2024-08-19T05:37:35Z)
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)

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

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