On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models

• URL: http://arxiv.org/abs/2505.05816v1
• Date: Fri, 09 May 2025 06:34:56 GMT
• Title: On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
• Authors: Antti Koskela, Mohamed Seif, Andrea J. Goldsmith,
• Abstract summary: We investigate privacy-preserving spectral clustering for community detection within block models (SBMs)<n>Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery.
• Score: 15.713997170792846
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We investigate privacy-preserving spectral clustering for community detection within stochastic block models (SBMs). Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery. Our work explores the fundamental trade-offs between the privacy budget and the accurate recovery of community labels. Furthermore, we establish information-theoretic conditions that guarantee the accuracy of our methods, providing theoretical assurances for successful community recovery under edge DP.

Related papers

• Locally Differentially Private Thresholding Bandits [3.8916312075738273]
  This work investigates the impact of ensuring local differential privacy in the thresholding bandit problem.<n>We propose methods that utilize private responses, obtained through a Bernoulli-based differentially private mechanism, to identify arms with expected rewards exceeding a predefined threshold.
  arXiv  Detail & Related papers  (2025-07-30T20:08:30Z)
• ImprovDML: Improved Trade-off in Private Byzantine-Resilient Distributed Machine Learning [22.85986751447643]
  A common strategy involves integrating Byzantine-resilient aggregation rules with differential privacy mechanisms.<n>We propose ImprovDML, that achieves model accuracy while simultaneously ensuring privacy preservation.<n>We demonstrate that it enables an improved trade-off between model accuracy and differential privacy.
  arXiv  Detail & Related papers  (2025-06-18T06:53:52Z)
• Urania: Differentially Private Insights into AI Use [104.7449031243196]
  $Urania$ provides end-to-end privacy protection by leveraging DP tools such as clustering, partition selection, and histogram-based summarization.<n>Results show the framework's ability to extract meaningful conversational insights while maintaining stringent user privacy.
  arXiv  Detail & Related papers  (2025-06-05T07:00:31Z)
• Differentially Private Random Feature Model [52.468511541184895]
  We produce a differentially private random feature model for privacy-preserving kernel machines.<n>We show that our method preserves privacy and derive a generalization error bound for the method.
  arXiv  Detail & Related papers  (2024-12-06T05:31:08Z)
• Convergent Differential Privacy Analysis for General Federated Learning: the $f$-DP Perspective [57.35402286842029]
  Federated learning (FL) is an efficient collaborative training paradigm with a focus on local privacy. differential privacy (DP) is a classical approach to capture and ensure the reliability of private protections.
  arXiv  Detail & Related papers  (2024-08-28T08:22:21Z)
• Private Online Community Detection for Censored Block Models [60.039026645807326]
  We study the private online change detection problem for dynamic communities, using a censored block model (CBM) We propose an algorithm capable of identifying changes in the community structure, while maintaining user privacy.
  arXiv  Detail & Related papers  (2024-05-09T12:35:57Z)
• Privacy-Preserving Community Detection for Locally Distributed Multiple Networks [11.693304974549893]
  We propose a new method for consensus community detection and estimation in a multi-layer block model. A novel algorithm named Distributed Spectral Clustering (ppDSC) is developed.
  arXiv  Detail & Related papers  (2023-06-27T08:36:13Z)
• 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)
• Decentralized Stochastic Optimization with Inherent Privacy Protection [103.62463469366557]
  Decentralized optimization is the basic building block of modern collaborative machine learning, distributed estimation and control, and large-scale sensing. Since involved data, privacy protection has become an increasingly pressing need in the implementation of decentralized optimization algorithms.
  arXiv  Detail & Related papers  (2022-05-08T14:38:23Z)

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.