A Differentially Private Clustering Algorithm for Well-Clustered Graphs
Weiqiang He Hendrik Fichtenberger Pan Peng
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 ($\epsilon$,$\delta$)-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) $\epsilon$-DP algorithm would result in substantial error.