{"id":"arxiv/2607.09441","url":"https://arxiv.org/abs/2607.09441","tags":["math.ST","stat.ML"],"score":0,"title":"Near-optimal node-private community estimation in polynomial-time","domain":"math.ST","source":"arxiv","authors":["Laurentiu Marchis","Olga Klopp","Po-Ling Loh","Ilias Zadik"],"reviews":0,"subject":"math.ST","summary":"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…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-07-10","reactions":{}}