Near-optimal node-private community estimation in polynomial-time
Laurentiu Marchis, Olga Klopp, Po-Ling Loh, Ilias Zadik
math.ST, stat.ML
Submitted: 2026-07-10
Comments: 40 pages
License: http://creativecommons.org/licenses/by/4.0/
The gist: 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
Terminology
Abstract
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.
Sources
- High-Dimensional Private Linear Regression with Optimal Rates
- PriME: Privacy-aware Membership profile Estimation in networks
- Finite Sample Differentially Private Confidence Intervals
- Node-Private Community Detection in Stochastic Block Models
- Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds
Related papers
- Conformal Prediction for Dyadic Regression Under Complex Missingness
- Sharp Asymptotic Theory of Maximum Likelihood Estimation for Gaussian Processes with an RBF Kernel
- Bentkus-type asymptotic e-values
- High-Dimensional Asymptotics of Differentially Private PCA
- A proximal gradient algorithm for composite log-concave sampling
- KL Convergence Guarantees for Score diffusion models under minimal data assumptions