論文の概要: Differentially private exact recovery for stochastic block models

• arxiv url: http://arxiv.org/abs/2406.02644v1
• Date: Tue, 4 Jun 2024 12:38:05 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-06 23:19:06.908063
• Title: Differentially private exact recovery for stochastic block models
• Title（参考訳）: 確率ブロックモデルに対する微分的私的精度回復
• Authors: Dung Nguyen, Anil Vullikanti,
• Abstract要約: ネットワークがプライベートな場合のブロックモデル(SBM)の回復可能性問題について検討する。 我々のプライベートアルゴリズムは、入力グラフのサイズに対して時間w.r.t.を実行し、非プライベート設定の回復しきい値と一致する。
• 参考スコア（独自算出の注目度）: 16.810982345283687
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Stochastic block models (SBMs) are a very commonly studied network model for community detection algorithms. In the standard form of an SBM, the $n$ vertices (or nodes) of a graph are generally divided into multiple pre-determined communities (or clusters). Connections between pairs of vertices are generated randomly and independently with pre-defined probabilities, which depend on the communities containing the two nodes. A fundamental problem in SBMs is the recovery of the community structure, and sharp information-theoretic bounds are known for recoverability for many versions of SBMs. Our focus here is the recoverability problem in SBMs when the network is private. Under the edge differential privacy model, we derive conditions for exact recoverability in three different versions of SBMs, namely Asymmetric SBM (when communities have non-uniform sizes), General Structure SBM (with outliers), and Censored SBM (with edge features). Our private algorithms have polynomial running time w.r.t. the input graph's size, and match the recovery thresholds of the non-private setting when $\epsilon\rightarrow\infty$. In contrast, the previous best results for recoverability in SBMs only hold for the symmetric case (equal size communities), and run in quasi-polynomial time, or in polynomial time with recovery thresholds being tight up to some constants from the non-private settings.
• Abstract（参考訳）: 確率ブロックモデル(SBM)は、コミュニティ検出アルゴリズムのための非常によく研究されているネットワークモデルである。 SBMの標準形式では、グラフの$n$頂点(またはノード)は、一般に複数の事前決定されたコミュニティ(またはクラスタ)に分けられる。 頂点のペア間の接続は、2つのノードを含むコミュニティに依存する事前定義された確率でランダムに独立に生成される。 SBMの基本的な問題は、コミュニティ構造の回復であり、鋭い情報理論境界は、多くのバージョンのSBMの回復可能性で知られている。 我々の焦点は、ネットワークがプライベートであるときのSBMの回復可能性の問題です。 エッジ差分プライバシモデルでは、非対称SBM(非一様サイズ)、一般構造SBM(外接型)、検閲SBM(エッジ特徴付き)の3つの異なるバージョンにおいて、正確な回復可能性の条件を導出する。 我々のプライベートアルゴリズムは、入力グラフのサイズの多項式実行時間を持ち、$\epsilon\rightarrow\infty$のときの非プライベート設定の回復しきい値と一致する。 対照的に、SBMの回復可能性に関する以前の最良の結果は、対称な場合(等間隔のコミュニティ)にのみ適用され、準多項式時間、または、リカバリしきい値が非プライベートな設定からいくつかの定数に密着した多項式時間で実行される。

関連論文リスト

• Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
  本稿では,無神論的な観点から,複数の潜在的相関グラフ上でのコミュニティ検出の問題について考察する。 我々はまず,同じノードの集合上で相関グラフを生成するために設計された多視点情報ブロックモデル (MVSBM) と呼ばれるランダムグラフモデルを考案した。
  論文  参考訳（メタデータ） (2024-01-17T13:39:38Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  我々は、最悪の近傍データセット上でのモデル分布間のKLばらつきのプライバシー境界を証明した。 このKLプライバシー境界は、トレーニング中にモデルパラメータに対して期待される2乗勾配ノルムによって決定される。
  論文  参考訳（メタデータ） (2023-10-31T16:13:22Z)
• Monotone deep Boltzmann machines [86.50247625239406]
  ディープボルツマンマシン(Deep Boltzmann Machine、DBM)は、双対エネルギー関数によって制御される多層確率モデルである。 我々は,各層で任意の自己接続が可能な新しい制限モデルであるモノトンDBMを開発した。 アクティベーションの特定の選択が、変動平均場解を与える固定点反復をもたらすことを示す。
  論文  参考訳（メタデータ） (2023-07-11T03:02:44Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  マルコフ決定プロセス(MDP)は、変化または部分的に知られているシステムのダイナミクスを扱うことを目的としている。 規則化されたMDPは、時間的複雑さを損なうことなく、ポリシー学習の安定性を高める。 ベルマン作用素は、収束と一般化を保証する計画と学習スキームを導出することができる。
  論文  参考訳（メタデータ） (2023-03-12T13:03:28Z)
• Differentially Private Community Detection for Stochastic Block Models [22.526853379896252]
  本研究では,個々の接続のプライバシを保ちながら,コミュニティ検出問題について検討する。 本稿では,3つの異なる地域社会回復機構の幅広いクラスについて,関連する情報トレードオフを提示し,分析する。
  論文  参考訳（メタデータ） (2022-01-31T18:59:19Z)
• Probabilistic Gradient Boosting Machines for Large-Scale Probabilistic Regression [51.770998056563094]
  PGBM(Probabilistic Gradient Boosting Machines)は、確率的予測を生成する手法である。 既存の最先端手法と比較してPGBMの利点を実証的に示す。
  論文  参考訳（メタデータ） (2021-06-03T08:32:13Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  本稿では,d-uniform hypergraph block model(d-HSBM)の正確な回復の基本的な限界について検討する。 精度の高いしきい値が存在し、正確な回復がしきい値の上に達成でき、その下には不可能であることを示す。
  論文  参考訳（メタデータ） (2021-05-11T03:39:08Z)
• A class of network models recoverable by spectral clustering [11.635152494912003]
  ブロックモデル (sbm) で使用されるアルゴリズムがブロックモデルのより広いクラスで動作することを示す。 このモデルのクラスを指定するのに必要な自由なパラメータを明確に紹介し、その結果、このモデルクラスのリカバリエラーを制御するパラメータをより明確に公開します。
  論文  参考訳（メタデータ） (2021-04-21T04:22:18Z)
• Community Detection in Bipartite Networks with Stochastic Blockmodels [0.0]
  バイパーティイトネットワークでは、あるタイプのノードは、他のタイプのノードとの共通の接続パターンに従ってグループ化される。 これにより、ブロックモデル(SBM)が2部構成のコミュニティ検出の直感的な選択となる。 我々はSBMの非パラメトリックな定式化とそれに対応するアルゴリズムを導入し、二部ネットワークのコミュニティを効率的に見つける。
  論文  参考訳（メタデータ） (2020-01-22T05:58:19Z)

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

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