A Differentially Private Clustering Algorithm for Well-Clustered Graphs

arXiv:2403.14332v1 Announce Type: cross
Abstract: 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 …

algorithm algorithms application arxiv benchmark can clustering clusters cs.cr cs.ds cs.lg graphs high private study vertex