Spectral Graph Clustering under Differential Privacy: Balancing Privacy, Accuracy, and Efficiency
This work addresses privacy-preserving graph analysis for data analysts, but it is incremental as it builds on existing differential privacy methods.
The paper tackles spectral graph clustering under edge differential privacy by developing three mechanisms to enforce privacy while preserving spectral properties, achieving rigorous privacy guarantees and characterizing misclassification error rates, with experiments validating the trade-offs.
We study the problem of spectral graph clustering under edge differential privacy (DP). Specifically, we develop three mechanisms: (i) graph perturbation via randomized edge flipping combined with adjacency matrix shuffling, which enforces edge privacy while preserving key spectral properties of the graph. Importantly, shuffling considerably amplifies the guarantees: whereas flipping edges with a fixed probability alone provides only a constant epsilon edge DP guarantee as the number of nodes grows, the shuffled mechanism achieves (epsilon, delta) edge DP with parameters that tend to zero as the number of nodes increase; (ii) private graph projection with additive Gaussian noise in a lower-dimensional space to reduce dimensionality and computational complexity; and (iii) a noisy power iteration method that distributes Gaussian noise across iterations to ensure edge DP while maintaining convergence. Our analysis provides rigorous privacy guarantees and a precise characterization of the misclassification error rate. Experiments on synthetic and real-world networks validate our theoretical analysis and illustrate the practical privacy-utility trade-offs.