論文の概要: Differentially Private Community Detection for Stochastic Block Models
- arxiv url: http://arxiv.org/abs/2202.00636v1
- Date: Mon, 31 Jan 2022 18:59:19 GMT
- ステータス: 処理完了
- システム内更新日: 2022-02-02 16:00:04.053445
- Title: Differentially Private Community Detection for Stochastic Block Models
- Title（参考訳）: 確率ブロックモデルに対する差分私的コミュニティ検出
- Authors: Mohamed Seif, Dung Nguyen, Anil Vullikanti, Ravi Tandon
- Abstract要約: 本研究では,個々の接続のプライバシを保ちながら,コミュニティ検出問題について検討する。
本稿では,3つの異なる地域社会回復機構の幅広いクラスについて,関連する情報トレードオフを提示し,分析する。
- 参考スコア（独自算出の注目度）: 23.311409463444793
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The goal of community detection over graphs is to recover underlying
labels/attributes of users (e.g., political affiliation) given the connectivity
between users (represented by adjacency matrix of a graph). There has been
significant recent progress on understanding the fundamental limits of
community detection when the graph is generated from a stochastic block model
(SBM). Specifically, sharp information theoretic limits and efficient
algorithms have been obtained for SBMs as a function of $p$ and $q$, which
represent the intra-community and inter-community connection probabilities. In
this paper, we study the community detection problem while preserving the
privacy of the individual connections (edges) between the vertices. Focusing on
the notion of $(\epsilon, \delta)$-edge differential privacy (DP), we seek to
understand the fundamental tradeoffs between $(p, q)$, DP budget $(\epsilon,
\delta)$, and computational efficiency for exact recovery of the community
labels.
To this end, we present and analyze the associated information-theoretic
tradeoffs for three broad classes of differentially private community recovery
mechanisms: a) stability based mechanism; b) sampling based mechanisms; and c)
graph perturbation mechanisms. Our main findings are that stability and
sampling based mechanisms lead to a superior tradeoff between $(p,q)$ and the
privacy budget $(\epsilon, \delta)$; however this comes at the expense of
higher computational complexity. On the other hand, albeit low complexity,
graph perturbation mechanisms require the privacy budget $\epsilon$ to scale as
$\Omega(\log(n))$ for exact recovery. To the best of our knowledge, this is the
first work to study the impact of privacy constraints on the fundamental limits
for community detection.
- Abstract（参考訳）: グラフ上のコミュニティ検出の目標は、ユーザ間の接続性(グラフの隣接行列で表される)によって、ユーザの基礎となるラベル/属性(例えば、政治的関連)を回復することである。
確率ブロックモデル (SBM) からグラフを生成する際に, コミュニティ検出の基本的な限界を理解するための重要な進歩があった。
具体的には、SBMに対して、コミュニティ内およびコミュニティ間接続確率を表す$p$と$q$の関数として、鋭い情報理論の限界と効率的なアルゴリズムが得られた。
本稿では,頂点間の個々の接続(エッジ)のプライバシを保ちながら,コミュニティ検出問題について検討する。
我々は、$(\epsilon, \delta)$-edge differential privacy (dp)の概念に着目し、$(p, q)$, dp budget $(\epsilon, \delta)$, and computational efficiency for exact recovery of the community labels という基本的なトレードオフを理解しようとしている。
この目的のために,我々は3種類の異なる個人的コミュニティ・リカバリメカニズムについて,関連する情報理論上のトレードオフを提示・分析する。
a) 安定性に基づく機構
b) サンプリングに基づく機構,及び
c) グラフ摂動機構
主な発見は、安定性とサンプリングに基づくメカニズムによって、$(p,q)$とプライバシ予算$(\epsilon, \delta)$の間の優れたトレードオフがもたらされるということです。
一方、複雑さの低いグラフ摂動機構では、正確なリカバリのために、プライバシー予算$\epsilon$を$\Omega(\log(n))$にスケールする必要がある。
私たちの知る限りでは、これはコミュニティ検出の基本的な限界に対するプライバシー制約の影響を研究する最初の研究である。
関連論文リスト
- Decentralized Privacy Preservation for Critical Connections in Graphs [25.50872357997492]
本稿では,結合的なサブグラフ探索に基づいて,個々の参加者に対するエンティティ接続の重要情報を識別し,保護する問題について考察する。
要塞内のユーザ接続は、解放されると難読化され、ユーザに関する重要な情報を保護する。
分散ディファレンシャルプライバシ(DDP)メカニズムの下では、重要な接続が保護され、残りの接続が未飽和状態にある場合に、その応答が$(varepsilon, delta)$-DDPを満たすことが証明されている。
論文 参考訳（メタデータ） (2024-05-20T01:22:21Z) - Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
インスタンスごとの差分プライバシー(pDP)やフィッシャー情報損失(FIL)といったデータ依存のプライバシ会計フレームワークは、固定されたトレーニングデータセット内の個人に対してきめ細かいプライバシー保証を提供する。
本稿では,データ依存会計下でのプライバシ保証を向上することを示すとともに,バウンドサポートによるガウス機構の簡単な修正を提案する。
論文 参考訳（メタデータ） (2024-03-07T21:22:07Z) - Unified Enhancement of Privacy Bounds for Mixture Mechanisms via
$f$-Differential Privacy [41.51051636162107]
本稿では、シャッフルモデルと1点差分勾配勾配のプライバシー境界の改善に焦点をあてる。
シャッフルモデルに対するトレードオフ関数のクローズドフォーム式を導出し、最新の結果よりも優れる。
また, ホッケースティックの進行した関節凸性の$f$-DPアナログを, $(epsilon,delta)$-DPに関連するホッケースティックのばらつきについて検討した。
論文 参考訳（メタデータ） (2023-10-30T19:37:51Z) - Chained-DP: Can We Recycle Privacy Budget? [18.19895364709435]
本稿では,ユーザが順次データアグリゲーションを実行し,プライバシ予算を再利用することのできる,新しいChained-DPフレームワークを提案する。
逐次ゲームの数学的性質を示し、そのナッシュ平衡を解き、証明可能な経済特性を持つインセンティブメカニズムを設計する。
提案手法の有効性を数値シミュレーションにより検証し,従来のLPP機構と比較して,プライバシ予算の大幅な削減と推定誤差の低減を図った。
論文 参考訳（メタデータ） (2023-09-12T08:07:59Z) - A Robustness Analysis of Blind Source Separation [91.3755431537592]
ブラインドソース分離(BSS)は、変換$f$が可逆であるが未知であるという条件の下で、その混合である$X=f(S)$から観測されていない信号を復元することを目的としている。
このような違反を分析し、その影響を$X$から$S$のブラインドリカバリに与える影響を定量化するための一般的なフレームワークを提案する。
定義された構造的仮定からの偏差に対する一般的なBSS溶出は、明示的な連続性保証という形で、利益的に分析可能であることを示す。
論文 参考訳（メタデータ） (2023-03-17T16:30:51Z) - Breaking the Communication-Privacy-Accuracy Tradeoff with
$f$-Differential Privacy [51.11280118806893]
サーバが複数のユーザの協調的なデータ分析を,プライバシの懸念と限られた通信能力で調整する,フェデレートされたデータ分析問題を考える。
有限出力空間を有する離散値機構の局所的差分プライバシー保証を$f$-differential privacy (DP) レンズを用いて検討する。
より具体的には、様々な離散的評価機構の厳密な$f$-DP保証を導出することにより、既存の文献を前進させる。
論文 参考訳（メタデータ） (2023-02-19T16:58:53Z) - Causal Bandits for Linear Structural Equation Models [58.2875460517691]
本稿では,因果図形モデルにおける最適な介入順序を設計する問題について検討する。
グラフの構造は知られており、ノードは$N$である。
頻繁性(UCBベース)とベイズ的設定に2つのアルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-26T16:21:31Z) - Community Detection in the Hypergraph SBM: Exact Recovery Given the
Similarity Matrix [1.74048653626208]
我々は$similarity$matrix$W$で動作するアルゴリズムの性能を調査し、$W_ij$は$i$と$j$の両方を含むハイパーエッジの数を報告する。
ほぼ線形な実行時間を持つ単純かつ高効率なスペクトルアルゴリズムを設計し,min-bisectionしきい値を達成することを示す。
論文 参考訳（メタデータ） (2022-08-23T15:22:05Z) - The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
本稿では,分散平均推定(DME)のための離散的差分プライバシー機構を導入し,フェデレーション学習と分析に応用する。
我々は、プライバシー保証の厳密な分析を行い、連続的なガウス機構と同じプライバシーと精度のトレードオフを達成することを示す。
論文 参考訳（メタデータ） (2022-07-09T05:46:28Z) - Normalized/Clipped SGD with Perturbation for Differentially Private
Non-Convex Optimization [94.06564567766475]
DP-SGDとDP-NSGDは、センシティブなトレーニングデータを記憶する大規模モデルのリスクを軽減する。
DP-NSGD は DP-SGD よりも比較的チューニングが比較的容易であるのに対して,これらの2つのアルゴリズムは同様の精度を実現する。
論文 参考訳（メタデータ） (2022-06-27T03:45:02Z) - Comprehensive Graph-conditional Similarity Preserving Network for
Unsupervised Cross-modal Hashing [97.44152794234405]
教師なしクロスモーダルハッシュ(UCMH)は近年ホットトピックとなっている。
本稿では,dgcpn(deep graph-neighbor coherence preservation network)を考案する。
DGCPNは3種類のデータ類似性を利用して、損失を保存する包括的な類似性を管理する。
論文 参考訳（メタデータ） (2020-12-25T07:40:59Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。