Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913108812890112 |
|---|---|
| author | Koskela, Antti Seif, Mohamed Poor, H. Vincent Goldsmith, Andrea J. |
| author_facet | Koskela, Antti Seif, Mohamed Poor, H. Vincent Goldsmith, Andrea J. |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2510_07136 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency Koskela, Antti Seif, Mohamed Poor, H. Vincent Goldsmith, Andrea J. Information Theory Cryptography and Security Machine Learning Social and Information Networks 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. |
| title | Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency |
| topic | Information Theory Cryptography and Security Machine Learning Social and Information Networks |
| url | https://arxiv.org/abs/2510.07136 |