Differentially Private Community Detection for Stochastic Block Models

Mohamed Seif, Dung Nguyen, Anil Vullikanti, Ravi Tandon

Research output: Contribution to journalConference articlepeer-review

11 Scopus citations

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. 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 between the vertices. Focusing on the notion of (ϵ, δ)-edge differential privacy (DP), we seek to understand the fundamental tradeoffs between (p, q), DP budget (ϵ, δ), and computational efficiency for exact recovery of community labels. To this end, we present and analyze the associated information-theoretic tradeoffs for three 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 (ϵ, δ); however this comes at the expense of higher computational complexity. On the other hand, albeit low complexity, graph perturbation mechanisms require the privacy budget ϵ to scale as Ω(log(n)) for exact recovery.

Original languageEnglish (US)
Pages (from-to)15858-15894
Number of pages37
JournalProceedings of Machine Learning Research
Volume162
StatePublished - 2022
Event39th International Conference on Machine Learning, ICML 2022 - Baltimore, United States
Duration: Jul 17 2022Jul 23 2022

ASJC Scopus subject areas

  • Artificial Intelligence
  • Software
  • Control and Systems Engineering
  • Statistics and Probability

Fingerprint

Dive into the research topics of 'Differentially Private Community Detection for Stochastic Block Models'. Together they form a unique fingerprint.

Cite this