Differentially Private Hierarchical Spectral Clustering

Abstract

We study hierarchical spectral graph clustering under edge differential privacy (DP) through the lens of iterative eigenvector estimation on adjacency matrices. We propose a differentially private recursive spectral framework, where each binary partition is obtained via a rank-one noisy power method applied to induced adjacency sub-matrices. At each iteration, carefully calibrated Gaussian noise is injected into the matrix–vector multiplication, ensuring (ε,δ)-edge DP under cumulative privacy accounting across both power iterations and recursive hierarchy levels while preserving the essential convergence properties of the classical power method. We provide a non-asymptotic analysis of the resulting noisy iterations, characterizing the trade-off between privacy and accuracy via explicit bounds on the eigenvector estimation error. In particular, we quantify how the noise variance, number of iterations, eigengap, and hierarchy depth jointly influence the accuracy of each recursive split and the overall clustering performance. Empirical evaluations on synthetic and real-world networks validate the theoretical predictions and demonstrate that the proposed method achieves strong multi-scale clustering performance under meaningful privacy budgets.