Differentially Private Community Detection for Stochastic Block Models

• URL: http://arxiv.org/abs/2202.00636v2
• Date: Fri, 18 Aug 2023 01:18:04 GMT
• Title: Differentially Private Community Detection for Stochastic Block Models
• Authors: Mohamed Seif, Dung Nguyen, Anil Vullikanti, Ravi Tandon
• Abstract summary: 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.
• Score: 22.526853379896252
• 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.

Related papers

• Decentralized Privacy Preservation for Critical Connections in Graphs [25.50872357997492]
  This paper delves into the problem of identifying and protecting critical information of entity connections for individual participants in a graph based on cohesive subgraph searches. A user's connections within a fortress are obfuscated when being released, to protect critical information about the user. We prove that, under the decentralized differential privacy (DDP) mechanism, one's response satisfies $(varepsilon, delta)$-DDP when its critical connections are protected while the rest remains unperturbed.
  arXiv  Detail & Related papers  (2024-05-20T01:22:21Z)
• Privacy Amplification for the Gaussian Mechanism via Bounded Support [64.86780616066575]
  Data-dependent privacy accounting frameworks such as per-instance differential privacy (pDP) and Fisher information loss (FIL) confer fine-grained privacy guarantees for individuals in a fixed training dataset. We propose simple modifications of the Gaussian mechanism with bounded support, showing that they amplify privacy guarantees under data-dependent accounting.
  arXiv  Detail & Related papers  (2024-03-07T21:22:07Z)
• Unified Enhancement of Privacy Bounds for Mixture Mechanisms via $f$-Differential Privacy [41.51051636162107]
  This paper focuses on improving privacy bounds for shuffling models and one-iteration differentially private gradient descent. We derive a closed-form expression of the trade-off function for shuffling models that outperforms the most up-to-date results. We also study an $f$-DP analog of the advanced joint convexity of the hockey-stick divergence related to $(epsilon,delta)$-DP.
  arXiv  Detail & Related papers  (2023-10-30T19:37:51Z)
• Chained-DP: Can We Recycle Privacy Budget? [18.19895364709435]
  We propose a novel Chained-DP framework enabling users to carry out data aggregation sequentially to recycle the privacy budget. We show the mathematical nature of the sequential game, solve its Nash Equilibrium, and design an incentive mechanism with provable economic properties. Our numerical simulation validates the effectiveness of Chained-DP, showing that it can significantly save privacy budget and lower estimation error compared to the traditional LDP mechanism.
  arXiv  Detail & Related papers  (2023-09-12T08:07:59Z)
• A Robustness Analysis of Blind Source Separation [91.3755431537592]
  Blind source separation (BSS) aims to recover an unobserved signal from its mixture $X=f(S)$ under the condition that the transformation $f$ is invertible but unknown. We present a general framework for analysing such violations and quantifying their impact on the blind recovery of $S$ from $X$. We show that a generic BSS-solution in response to general deviations from its defining structural assumptions can be profitably analysed in the form of explicit continuity guarantees.
  arXiv  Detail & Related papers  (2023-03-17T16:30:51Z)
• Breaking the Communication-Privacy-Accuracy Tradeoff with $f$-Differential Privacy [51.11280118806893]
  We consider a federated data analytics problem in which a server coordinates the collaborative data analysis of multiple users with privacy concerns and limited communication capability. We study the local differential privacy guarantees of discrete-valued mechanisms with finite output space through the lens of $f$-differential privacy (DP) More specifically, we advance the existing literature by deriving tight $f$-DP guarantees for a variety of discrete-valued mechanisms.
  arXiv  Detail & Related papers  (2023-02-19T16:58:53Z)
• Causal Bandits for Linear Structural Equation Models [58.2875460517691]
  This paper studies the problem of designing an optimal sequence of interventions in a causal graphical model. It is assumed that the graph's structure is known and has $N$ nodes. Two algorithms are proposed for the frequentist (UCB-based) and Bayesian settings.
  arXiv  Detail & Related papers  (2022-08-26T16:21:31Z)
• Community Detection in the Hypergraph SBM: Exact Recovery Given the Similarity Matrix [1.74048653626208]
  We study the performance of algorithms which operate on the $similarity$matrix $W$, where $W_ij$ reports the number of hyperedges containing both $i$ and $j$. We design a simple and highly efficient spectral algorithm with nearly linear runtime and show that it achieves the min-bisection threshold.
  arXiv  Detail & Related papers  (2022-08-23T15:22:05Z)
• The Poisson binomial mechanism for secure and private federated learning [19.399122892615573]
  We introduce a discrete differential privacy mechanism for distributed mean estimation (DME) with applications to federated learning and analytics. We provide a tight analysis of its privacy guarantees, showing that it achieves the same privacy-accuracy trade-offs as the continuous Gaussian mechanism.
  arXiv  Detail & Related papers  (2022-07-09T05:46:28Z)
• Normalized/Clipped SGD with Perturbation for Differentially Private Non-Convex Optimization [94.06564567766475]
  DP-SGD and DP-NSGD mitigate the risk of large models memorizing sensitive training data. We show that these two algorithms achieve similar best accuracy while DP-NSGD is comparatively easier to tune than DP-SGD.
  arXiv  Detail & Related papers  (2022-06-27T03:45:02Z)
• Comprehensive Graph-conditional Similarity Preserving Network for Unsupervised Cross-modal Hashing [97.44152794234405]
  Unsupervised cross-modal hashing (UCMH) has become a hot topic recently. In this paper, we devise a deep graph-neighbor coherence preserving network (DGCPN) DGCPN regulates comprehensive similarity preserving losses by exploiting three types of data similarities.
  arXiv  Detail & Related papers  (2020-12-25T07:40:59Z)

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.