Research map / Federated learning and privacy / Differential privacy
A Differentially Private Clustering Algorithm for Well-Clustered Graphs
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.
Gives an efficient (epsilon,delta)-DP algorithm for clustering k-well-clustered graphs by solving a noisy-SDP-plus-spectral-clustering pipeline, with near-optimal misclassification, plus a pure epsilon-DP lower bound.
Problem
Differentially private recovery of clusters in well-clustered graphs (small outer and high inner conductance), where prior DP work only handled two-cluster SBMs.
Approach
Solve an SDP with a quadratic regularizer on a Gram matrix (strongly convex, so solution is stable under edge changes), add Gaussian noise to the scaled solution, then run spectral embedding and k-means; sensitivity is bounded via generalized strong convexity.
Key results
- On SBM graphs with n=100-150, the proposed algorithm reaches AMI up to 0.57 versus 0.06-0.10 for RR+SDP in the low-signal settings (e.g., n=150, k=3, p=0.25, q=0.05 gives 0.57 vs 0.06).
- Theorem gives misclassification (vol-based) O(k^4/c^2 * phi_out/phi_in^2) under phi_out/phi_in^2 = O(k^-4), matching the best non-private k^3 bound up to a k factor for balanced graphs.
- Lower bound: any zeta-approximate pure epsilon-DP algorithm for 2-cluster well-clustered d-regular graphs needs epsilon >= 2ln(1/(9e zeta))/d, so no pure DP algorithm achieves constant misclassification for epsilon=Omega(1).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private clustering algorithm instead of RR+SDP | Clustering on synthetic SBM graphs · SBM(n=100, k=2, p=0.20, q=0.00); SBM(n=100, k=2, p=0.25, q=0.05); SBM(n=100, k=2, p=0.30, q=0.10); SBM(n=150, k=3, p=0.20, q=0.00); SBM(n=150, k=3, p=0.25, q=0. | AMI: 0.10 -> 0.17; 0.10 -> 0.14; 0.09 -> 0.26; 0.07 -> 0.19; 0.06 -> 0.57; 0.06 -> 0.35 | Helped |
| Use the proposed private clustering algorithm instead of RR+SDP | Clustering on synthetic SBM graphs · SBM(n=100, k=2, p=0.20, q=0.00); SBM(n=100, k=2, p=0.25, q=0.05); SBM(n=100, k=2, p=0.30, q=0.10); SBM(n=150, k=3, p=0.20, q=0.00); SBM(n=150, k=3, p=0.25, q=0. | NMI: 0.11 -> 0.19; 0.11 -> 0.15; 0.10 -> 0.27; 0.08 -> 0.20; 0.06 -> 0.58; 0.07 -> 0.55 | Helped |
Surprising findings
- Pure epsilon-DP recovery of well-clustered graphs incurs large error, so approximate (epsilon,delta)-DP is needed for constant misclassification at epsilon=Omega(1).
Limitations
- Experiments only on small synthetic SBM graphs (n up to 150 in the table), with running time growing steeply in n.
- Misclassification bound has k^4 dependence and requires phi_out/phi_in^2 = O(k^-4), weaker than the best non-private k^3 bound.
- Algorithm requires knowledge of the balance parameter b (set from cluster volumes) and a tuned trade-off parameter lambda.
Experimental setup
Datasets: synthetic stochastic block model graphs SBM(n,k,p,q)
Benchmarks: synthetic SBM graphs
Metrics: AMI NMI misclassification ratio (theoretical)
Baselines: randomized response + SDP (RR+SDP)
Builds on: Chen et al. NeurIPS 2023 DP SBM recovery Peng et al. spectral clustering for well-clustered graphs Gaussian mechanism Davis-Kahan theorem
Closest papers by meaning
- Differentially private exact recovery for stochastic block models (ICML 2024 · similarity 0.89)
- Online Differentially Private Consistent Clustering (NeurIPS 2026 · similarity 0.89)
- On the Price of Differential Privacy for Hierarchical Clustering (ICLR 2025 · similarity 0.89)
- Differentially Private Gomory-Hu Trees (NeurIPS 2025 · similarity 0.88)
- On the Robustness of Spectral Algorithms for Semirandom Stochastic Block Models (NeurIPS 2024 · similarity 0.88)
- Optimal Graph Clustering without Edge Density Signals (NeurIPS 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.