論文の概要: Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency

• arxiv url: http://arxiv.org/abs/2510.07136v1
• Date: Wed, 08 Oct 2025 15:30:27 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-10-09 16:41:20.598215
• Title: Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency
• Title（参考訳）: 異なるプライバシの下でのスペクトルグラフクラスタリング - プライバシ、正確性、効率のバランス
• Authors: Mohamed Seif, Antti Koskela, H. Vincent Poor, Andrea J. Goldsmith,
• Abstract要約: エッジ差分プライバシー(DP)下におけるスペクトルグラフクラスタリングの問題点について検討する。 具体的には, (i) エッジフリップによるグラフ摂動と, エッジプライバシを強制する隣接行列シャッフルを併用したグラフ摂動, (ii) 次元と複雑性の複雑さを低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフプロジェクション, (iii) 収束性を維持しながらエッジDPを確保するために反復的にガウス雑音を分散するノイズの多いパワーイテレーション手法である。
• 参考スコア（独自算出の注目度）: 53.98433419539793
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the problem of spectral graph clustering under edge differential privacy (DP). Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy while preserving key spectral properties of the graph. Importantly, shuffling considerably amplifies the guarantees: whereas flipping edges with a fixed probability alone provides only a constant epsilon edge DP guarantee as the number of nodes grows, the shuffled mechanism achieves (epsilon, delta) edge DP with parameters that tend to zero as the number of nodes increase; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence. Our analysis provides rigorous privacy guarantees and a precise characterization of the misclassification error rate. Experiments on synthetic and real-world networks validate our theoretical analysis and illustrate the practical privacy-utility trade-offs.
• Abstract（参考訳）: エッジ差分プライバシー(DP)下でのスペクトルグラフクラスタリングの問題点について検討する。 具体的には3つのメカニズムを開発します。 i) ランダム化エッジフリップによるグラフ摂動と隣接行列シャッフルの併用により, グラフの重要なスペクトル特性を保ちながら, エッジプライバシを強制する。 重要なことにシャッフルは保証をかなり増幅する: 固定確率のみのフリップエッジは、ノード数が増加するにつれて一定のエプシロンエッジDPしか保証しないが、シャッフル機構はノード数が増加するにつれて0となるパラメータを持つ(エプシロン、デルタ)エッジDPを達成する。 (ii)次元と計算複雑性を低減するために低次元空間における加法的ガウス雑音を伴うプライベートグラフ投影 3) 収束性を維持しつつエッジDPを確保するため, ガウス雑音を複数の繰り返しに分散する雑音の多い電力繰り返し方式。 我々の分析は、厳密なプライバシー保証と誤分類エラー率の正確な評価を提供する。 合成および実世界のネットワークの実験は、我々の理論的分析を検証し、実用的なプライバシーとユーティリティのトレードオフを例証する。

関連論文リスト

• Point Cloud Denoising With Fine-Granularity Dynamic Graph Convolutional Networks [58.050130177241186]
  ノイズの摂動は、しばしば3次元の点雲を破損させ、表面の再構成、レンダリング、さらなる処理といった下流のタスクを妨げる。 本稿では,GDGCNと呼ばれる粒度動的グラフ畳み込みネットワークについて紹介する。
  論文  参考訳（メタデータ） (2024-11-21T14:19:32Z)
• Privacy of SGD under Gaussian or Heavy-Tailed Noise: Guarantees without Gradient Clipping [15.348717323408652]
  重み付きノイズの理論的利点と経験的利益のギャップを、最適化とプライバシー保護のために橋渡しする。 ヘビーテールのノイズ発生スキームは、ライトテールのノイズの代替となる可能性があることを示す。
  論文  参考訳（メタデータ） (2024-03-04T13:53:41Z)
• On the Privacy of Selection Mechanisms with Gaussian Noise [44.577599546904736]
  ガウス雑音によるReport Noisy MaxとAbove Thresholdの分析を再検討する。 その結果,Report Noisy Max の純元 DP 境界と Above Threshold の純元 DP 境界を提供することが可能であることがわかった。
  論文  参考訳（メタデータ） (2024-02-09T02:11:25Z)
• Differentially Private SGD Without Clipping Bias: An Error-Feedback Approach [62.000948039914135]
  Differentially Private Gradient Descent with Gradient Clipping (DPSGD-GC) を使用して、差分プライバシ(DP)がモデルパフォーマンス劣化の犠牲となることを保証する。 DPSGD-GCに代わる新しいエラーフィードバック(EF)DPアルゴリズムを提案する。 提案アルゴリズムに対するアルゴリズム固有のDP解析を確立し,R'enyi DPに基づくプライバシ保証を提供する。
  論文  参考訳（メタデータ） (2023-11-24T17:56:44Z)
• Partial recovery and weak consistency in the non-uniform hypergraph Stochastic Block Model [6.681901523019242]
  非一様ハイパーグラフブロックモデル(HSBM)に基づくランダムハイパーグラフにおけるコミュニティ検出問題の検討 我々は,少なくとも$gamma$分の頂点を正しく分類した分割を出力するスペクトルアルゴリズムを提案し,$gammainはモデルの信号-雑音比(SNR)に依存する。 このアルゴリズムの理論的解析は、非一様ランダムハイパーグラフに対する隣接行列の濃度と正規化に依存しており、これは独立な関心を持つことができる。
  論文  参考訳（メタデータ） (2021-12-22T05:38:33Z)
• Smoothed Differential Privacy [55.415581832037084]
  微分プライバシー(DP)は、最悪のケース分析に基づいて広く受け入れられ、広く適用されているプライバシーの概念である。 本稿では, 祝賀されたスムーズな解析の背景にある最悪の平均ケースのアイデアに倣って, DPの自然な拡張を提案する。 サンプリング手順による離散的なメカニズムはDPが予測するよりもプライベートであるのに対して,サンプリング手順による連続的なメカニズムはスムーズなDP下では依然としてプライベートではないことが証明された。
  論文  参考訳（メタデータ） (2021-07-04T06:55:45Z)

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

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