Differentially Private Hierarchical Clustering for Well-Clusterable Graphs

We present *Noisy-Degree Hierarchy*, a pure edge-differentially private algorithm for hierarchical clustering on well-clusterable graphs. It constructs a full hierarchy from noisy vertex degrees, without recovering the clusters, in $O(m+n\log n)$ time. Under the spectral well-clusterability conditions of Manghiuc and Sun (2021), it achieves an $O(k^6/({\lambda }_{k+1}^2ϵ))$ approximation to Dasgupta's cost with high probability, provided that the minimum weighted degree is at least one and $0<ϵ\le 1$. Here $k$ is the number of clusters, and ${\lambda }_{k+1}$ is the $(k+1)$st smallest eigenvalue of the input graph's normalized Laplacian. The private algorithm builds on our simpler non-private *Degree-Ordered Hierarchy*, whose $O(k^6/{\lambda }_{k+1}^2)$ approximation improves the previous $O(k^{22}/{\lambda }_{k+1}^{10})$ bound under the same conditions. With additional degree-regularity and conductance assumptions, the private approximation factor improves to $O(k/ϵ)$. We also prove an $\Omega (k)$ lower bound on disjoint regular expanders that matches this dependence on $k$ for fixed, sufficiently small $ϵ>0$. Experiments on synthetic and real-world graphs demonstrate the private algorithm's utility and efficiency.