Differentially Private Sketch-and-Solve for Community Detection via Semidefinite Programming

Mohamed Seif, Yanxi Chen, Andrea J. Goldsmith, H. Vincent Poor

Research output: Contribution to journalArticlepeer-review

Abstract

We study the community detection problem over binary symmetric stochastic block models (SBMs) while preserving the privacy of the individual connections between the vertices. We present and analyze the associated information-theoretic tradeoff for differentially private exact recovery of the underlying communities by deriving sufficient separation conditions between the intra-community and inter-community connection probabilities while taking into account the privacy budget and graph sketching as a speed-up technique to improve the computational complexity of maximum likelihood (ML) based recovery algorithms.

Original languageEnglish (US)
Pages (from-to)331-346
Number of pages16
JournalIEEE Journal on Selected Areas in Information Theory
Volume5
DOIs
StatePublished - 2024
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Computer Networks and Communications
  • Media Technology
  • Artificial Intelligence
  • Applied Mathematics

Keywords

  • Differential privacy
  • community detection
  • graph sketching
  • graphs
  • subsampling

Fingerprint

Dive into the research topics of 'Differentially Private Sketch-and-Solve for Community Detection via Semidefinite Programming'. Together they form a unique fingerprint.

Cite this