{"id":"arxiv/2605.15943","url":"https://arxiv.org/abs/2605.15943","tags":["math.ST","stat.ML"],"score":0,"title":"Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds","domain":"math.ST","source":"arxiv","authors":["Laurentiu Marchis","Ethan D'souza","Tomáš Flídr","Po-Ling Loh"],"reviews":0,"subject":"math.ST","summary":"We study the classical problem of community recovery in stochastic block models with a fixed number of communities, with a twist: We seek algorithms that are stable with respect to node-wise changes in the graph structure, formally defined as a differential privacy constraint. The algorithms we develop are based on spectral clustering, where we introduce privacy to the community recovery pipeline in the form of directly privatizing the adjacency matrix; private PCA; private convex optimization; private low-rank matrix estimation; and private approximate subspace estimation. Straightforward…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-05-15","reactions":{}}