mlsanityData to 7 Oct 2026

Near-optimal node-private community estimation in polynomial-time

arXiv 2607.09441 ↗First posted 10 Jul 2026math.ST stat.ML stat.THcited by 0

Not on the map. Why?

Abstract (arXiv)

In this paper, we resolve an open question of Klopp & Zadik (2026) by providing a high-probability polynomial-time, node-private algorithm which nearly matches the performance of their exponential-time node-private algorithm for exact recovery in stochastic block models. Our result involves an explicitly constructed Lipschitz surrogate for the penalized likelihood function, as well as a carefully devised accept-reject algorithm that samples community labels from the corresponding exponential mechanism in polynomial-time. We rigorously analyze the privacy, runtime, and utility of our proposed algorithm, showing that even when the number of communities K grows logarithmically with the number of nodes n, we can achieve the minimax rates for exact recovery with the privacy parameter epsilon growing as log(n), thus matching known lower bounds on the cost of privacy for this setting.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 23 of its 50 references that are in the map. First posted on arXiv 10 Jul 2026.

Builds on

23 of 50 references.

References · 23

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2016Concentrated Differential Privacy: Simplifications, Extensions, and Lower Boundscited by 339
  3. 2017Community Detection and Stochastic Block Modelscited by 317
  4. 2020Auditing Differentially Private Machine Learning: How Private is Private SGD?cited by 213
  5. 2023Privacy Auditing with One (1) Training Runcited by 119
  6. 2016Minimax Optimal Procedures for Locally Private Estimationcited by 103
  7. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  8. 2018Privately Learning High-Dimensional Distributionscited by 103
  9. 2021Optimal Accounting of Differential Privacy via Characteristic Functioncited by 83
  10. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  11. 2015Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlocited by 61
  12. 2018Detecting Violations of Differential Privacycited by 37
11 more
  1. 2015Minimax Rates of Community Detection in Stochastic Block Modelscited by 25
  2. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  3. 2022Differentially Private Community Detection for Stochastic Block Modelscited by 15
  4. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  5. 2021Consistent Spectral Clustering of Network Block Models under Local Differential Privacycited by 6
  6. 2021Privacy-Aware Rejection Samplingcited by 5
  7. 2024Differentially private exact recovery for stochastic block modelscited by 4
  8. 2024Private graphon estimation via sum-of-squarescited by 3
  9. 2024PriME: Privacy-aware Membership profile Estimation in networkscited by 3
  10. 2025On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Modelscited by 2
  11. 2026Node-private community estimation in stochastic block models: Tractable algorithms and lower boundscited by 1

Built on by

Not cited yet.