Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency

ArXi:2510.07136v2 Announce Type: replace-cross We study spectral graph clustering under edge differential privacy. We propose a matrix shuffling mechanism that combines randomized edge flipping with a random permutation of the adjacency matrix. While edge flipping alone provides only a constant $\varepsilon$ guarantee as the graph grows, shuffling amplifies privacy so that the effective $\varepsilon$ tends to zero with the number of nodes.