Differentially private exact recovery for stochastic block models

• URL: http://arxiv.org/abs/2406.02644v1
• Date: Tue, 4 Jun 2024 12:38:05 GMT
• Title: Differentially private exact recovery for stochastic block models
• Authors: Dung Nguyen, Anil Vullikanti,
• Abstract summary: We study the recoverability problem in block models (SBMs) when the network is private. Our private algorithms have running time w.r.t. the input graph's size, and match the recovery thresholds of the non-private setting.
• Score: 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.

Related papers

• Community Detection in the Multi-View Stochastic Block Model [47.43048484980115]
  This paper considers the problem of community detection on multiple potentially correlated graphs from antheoretical perspective. We first put forth a random graph model, called the multi-view information block model (MVSBM), designed to generate correlated graphs on the same set of nodes.
  arXiv  Detail & Related papers  (2024-01-17T13:39:38Z)
• Initialization Matters: Privacy-Utility Analysis of Overparameterized Neural Networks [72.51255282371805]
  We prove a privacy bound for the KL divergence between model distributions on worst-case neighboring datasets. We find that this KL privacy bound is largely determined by the expected squared gradient norm relative to model parameters during training.
  arXiv  Detail & Related papers  (2023-10-31T16:13:22Z)
• Monotone deep Boltzmann machines [86.50247625239406]
  Deep Boltzmann machines (DBMs) are multi-layered probabilistic models governed by a pairwise energy function. We develop a new class of restricted model, the monotone DBM, which allows for arbitrary self-connection in each layer. We show that a particular choice of activation results in a fixed-point iteration that gives a variational mean-field solution.
  arXiv  Detail & Related papers  (2023-07-11T03:02:44Z)
• Twice Regularized Markov Decision Processes: The Equivalence between Robustness and Regularization [64.60253456266872]
  Markov decision processes (MDPs) aim to handle changing or partially known system dynamics. Regularized MDPs show more stability in policy learning without impairing time complexity. Bellman operators enable us to derive planning and learning schemes with convergence and generalization guarantees.
  arXiv  Detail & Related papers  (2023-03-12T13:03:28Z)
• Differentially Private Community Detection for Stochastic Block Models [22.526853379896252]
  We study the community detection problem while preserving the privacy of the individual connections. We present and analyze the associated information tradeoffs for three broad classes of differentially private community recovery mechanisms.
  arXiv  Detail & Related papers  (2022-01-31T18:59:19Z)
• Probabilistic Gradient Boosting Machines for Large-Scale Probabilistic Regression [51.770998056563094]
  Probabilistic Gradient Boosting Machines (PGBM) is a method to create probabilistic predictions with a single ensemble of decision trees. We empirically demonstrate the advantages of PGBM compared to existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-03T08:32:13Z)
• Exact Recovery in the General Hypergraph Stochastic Block Model [92.28929858529679]
  This paper investigates fundamental limits of exact recovery in the general d-uniform hypergraph block model (d-HSBM) We show that there exists a sharp threshold such that exact recovery is achievable above the threshold and impossible below it.
  arXiv  Detail & Related papers  (2021-05-11T03:39:08Z)
• A class of network models recoverable by spectral clustering [11.635152494912003]
  We show that essentially the same algorithm used for the Block-Model (SBM) works on a wider class of Block-Models. We introduce clearly the free parameters needed to specify this class of models, and results in bounds that expose with more clarity the parameters that control the recovery error in this model class.
  arXiv  Detail & Related papers  (2021-04-21T04:22:18Z)
• Community Detection in Bipartite Networks with Stochastic Blockmodels [0.0]
  In bipartite networks, community structures are restricted to being disassortative, in that nodes of one type are grouped according to common patterns of connection with nodes of the other type. This makes the block model (SBM) an intuitive choice for bipartite community detection. We introduce a nonparametric formulation of the SBM and a corresponding algorithm to efficiently find communities in bipartite networks.
  arXiv  Detail & Related papers  (2020-01-22T05:58:19Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.