A Differentially Private Clustering Algorithm for Well-Clustered Graphs
This work addresses privacy-preserving clustering for theoretical graph analysis, but it is incremental as it extends prior DP methods from two to k clusters.
The paper tackles the problem of differentially private clustering for well-clustered graphs with k nearly-balanced clusters, achieving a misclassification ratio that nearly matches the best non-private algorithms, as validated by experiments on datasets with ground truth clusters.
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.