# A Differentially Private Clustering Algorithm for Well-Clustered Graphs

arXiv: https://arxiv.org/abs/2403.14332 · HTML: https://mlsanity.com/paper/2403.14332/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 16 of its 49 references that are in the map.
- First posted on arXiv 21 Mar 2024.

## Builds on (most cited first, 16 of 16)

- [Better Guarantees for k-Means and Euclidean k-Median by Primal-Dual Algorithms](https://mlsanity.com/paper/1612.07925/) (2016)
- [Differentially Private Clustering: Tight Approximation Ratios](https://mlsanity.com/paper/2008.08007/) (2020)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [Private estimation algorithms for stochastic block models and mixture models](https://mlsanity.com/paper/2301.04822/) (2023)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Differentially Private Correlation Clustering](https://mlsanity.com/paper/2102.08885/) (2021)
- [Testing Graph Clusterability: Algorithms and Lower Bounds](https://mlsanity.com/paper/1808.04807/) (2018)
- [Improved Analysis of Spectral Algorithm for Clustering](https://mlsanity.com/paper/1912.02997/) (2019)
- [Partitioning into Expanders](https://mlsanity.com/paper/1309.3223/) (2013)
- [Testing Cluster Structure of Graphs](https://mlsanity.com/paper/1504.03294/) (2015)
- [Robust Clustering Oracle and Local Reconstructor of Cluster Structure of Graphs](https://mlsanity.com/paper/1904.09710/) (2019)
- [Spectral Clustering Oracles in Sublinear Time](https://mlsanity.com/paper/2101.05549/) (2021)
- [Consistent Spectral Clustering of Network Block Models under Local Differential Privacy](https://mlsanity.com/paper/2105.12615/) (2021)
- [Near-Optimal Correlation Clustering with Privacy](https://mlsanity.com/paper/2203.01440/) (2022)
- [Spectral concentration and greedy k-clustering](https://mlsanity.com/paper/1404.1008/) (2014)
- [Better Private Algorithms for Correlation Clustering](https://mlsanity.com/paper/2202.10747/) (2022)

## Built on by (most cited first, 2 of 2)

- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Metric Embedding Initialization-Based Differentially Private and Explainable Graph Clustering](https://mlsanity.com/paper/2509.06214/) (2025)

## Abstract (arXiv)

We study differentially private (DP) algorithms for recovering clusters in well-clustered graphs, which are graphs whose vertex set can be partitioned into a small number of sets, each inducing a subgraph of high inner conductance and small outer conductance. Such graphs have widespread application as a benchmark in the theoretical analysis of spectral clustering. We provide an efficient (ε,δ)-DP algorithm tailored specifically for such graphs. Our algorithm draws inspiration from the recent work of Chen et al., who developed DP algorithms for recovery of stochastic block models in cases where the graph comprises exactly two nearly-balanced clusters. Our algorithm works for well-clustered graphs with k nearly-balanced clusters, and the misclassification ratio almost matches the one of the best-known non-private algorithms. We conduct experimental evaluations on datasets with known ground truth clusters to substantiate the prowess of our algorithm. We also show that any (pure) ε-DP algorithm would result in substantial error.