Node-private community estimation in stochastic block models: Tractable algorithms and lower bounds

Laurentiu Marchis, Ethan D'souza, Tomáš Flídr, Po-Ling Loh

arXivarxiv/2605.15943May 15, 2026math.STscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2605.15943
curl -X POST /api/v1/records/arxiv/2605.15943/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2605.15943/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'