Research map / Federated learning and privacy / Differential privacy
Differentially private exact recovery for stochastic block models
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Derives conditions for edge-DP exact recovery in asymmetric, censored, and general-structure stochastic block models using a stability mechanism applied to an SDP estimator, plus a polynomial-time variant.
Problem
Exact recovery of community structure in stochastic block models under edge differential privacy; prior private results covered only symmetric SBMs and were exponential/quasi-polynomial time or had constant-factor gaps from non-private thresholds.
Approach
Apply the stability mechanism to an SDP estimator, and prove that a C-concentration property holds w.h.p. for each SBM variant, persists under log n edge flips, and yields a deterministic dual certificate. A fast variant tests C-concentration to avoid the expensive distance-to-instability computation, giving polynomial time.
Key results
- For the binary asymmetric SBM with rho=1/2, exact recovery under edge DP holds when sqrt(a)-sqrt(b) >= sqrt(2)*sqrt(1+c/eps), matching the non-private threshold as eps grows.
- The fast stability mechanism runs in O(poly(n)) time w.h.p. and retains the privacy and exact recovery guarantees of the exponential-time version.
- Exact recovery conditions are derived for censored binary SBM (a(sqrt(1-xi)-sqrt(xi))^2 > 1 with privacy term) and general structure SBM with outliers.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| use the polynomial-time fast stability mechanism with the SDP estimator | Binary Symmetric SBM under edge differential privacy · Binary Symmetric SBM | recovery threshold: \sqrt{a} - \sqrt{b} \geq \sqrt{2}\sqrt{1 + 2/\epsilon} vs. \sqrt{a} - \sqrt{b} \geq \sqrt{2}\sqrt{2 + 3/(2\epsilon)} | Helped |
| apply the SDP stability mechanism to unequal-sized clusters | Binary Asymmetric SBM · Binary Asymmetric SBM | exact recovery | Helped |
| apply the SDP stability mechanism to labeled edges | Binary Censored SBM · Binary Censored SBM | exact recovery | Helped |
| apply the SDP stability mechanism to multiple clusters with outliers | General Structure SBM · General Structure SBM | exact recovery | Helped |
| use the fast stability mechanism instead of computing distance to instability directly | SDP-based stability mechanism · Binary Asymmetric, Binary Censored, and General Structure SBMs | running time: n^{O(\log{n})} -> O(poly(n)) | Helped |
| take the privacy parameter toward infinity | proposed private algorithms · Binary Asymmetric, Binary Censored, and General Structure SBMs | recovery threshold | Helped |
Limitations
- Oracle assumptions (known sigma* and a,b up to factor) are needed for the fast algorithm, replaced by estimates w.h.p. in analysis.
- Results are for dense regime p=a log n/n, q=b log n/n and only for asymmetric, censored, and general-structure variants with specific parameter constraints.
- Some thresholds are not tight and the general structure guarantee is given only through lengthy conditions.
Experimental setup
Metrics: exact recovery threshold privacy guarantee (epsilon, delta)-DP running time
Baselines: MLE-Stability SDP-Stability RR + SDP Gaussian-mechanism SDP method (symmetric SBM)
Builds on: Stability mechanism (Vullikanti/Nguyen prior work on private SBM recovery) SDP relaxation for SBM exact recovery (Abbe-Bandeira-Hall style) Talagrand concentration inequality
Closest papers by meaning
- Query-Limited Community Recovery in Stochastic Block Models (NeurIPS 2026 · similarity 0.90)
- A Differentially Private Clustering Algorithm for Well-Clustered Graphs (ICLR 2024 · similarity 0.89)
- Exact Community Recovery under Side Information: Optimality of Spectral Algorithms (ICLR 2025 · similarity 0.89)
- Harnessing Multiple Correlated Networks for Exact Community Recovery (NeurIPS 2024 · similarity 0.88)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.88)
- Revisiting Instance-Optimal Cluster Recovery in the Labeled Stochastic Block Model (ICML 2025 · similarity 0.88)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.