{"ID":2858844,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.07136","arxiv_id":"2510.07136","title":"Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency","abstract":"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. We develop a unified error analysis framework -- based on Davis--Kahan perturbation theory and a classification-margin bound -- that gives explicit misclassification rates for all the mechanisms considered as a function of the privacy budget, eigengap, and number of communities. Applying this framework, we show that the matrix shuffling mechanism achieves an error rate scaling of $\\tilde{O}(1/n)$, a clear improvement over two canonical DP baselines from the private PCA literature: the Gaussian mechanism applied directly to the adjacency matrix (Analyze Gauss) and the noisy power method, both of which scale as $\\tilde{O}(1)$ in $n$. We further propose a private spectral gap detection algorithm for estimating the number of communities. Experiments on synthetic and real-world networks validate our theoretical findings.","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2510.07136","url_pdf":"https://arxiv.org/pdf/2510.07136v2","authors":"[\"Antti Koskela\",\"Mohamed Seif\",\"H. Vincent Poor\",\"Andrea J. Goldsmith\"]","published":"2025-10-08T15:30:27Z","proceeding":"cs.IT","tasks":"[\"cs.IT\",\"cs.CR\",\"cs.LG\",\"cs.SI\"]","methods":"[]","has_code":false}