On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918014617649152 |
|---|---|
| author | Koskela, Antti Seif, Mohamed Goldsmith, Andrea J. |
| author_facet | Koskela, Antti Seif, Mohamed Goldsmith, Andrea J. |
| contents | We investigate privacy-preserving spectral clustering for community detection within stochastic block models (SBMs). Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery. Our work explores the fundamental trade-offs between the privacy budget and the accurate recovery of community labels. Furthermore, we establish information-theoretic conditions that guarantee the accuracy of our methods, providing theoretical assurances for successful community recovery under edge DP. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_05816 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models Koskela, Antti Seif, Mohamed Goldsmith, Andrea J. Social and Information Networks Cryptography and Security Information Theory Machine Learning We investigate privacy-preserving spectral clustering for community detection within stochastic block models (SBMs). Specifically, we focus on edge differential privacy (DP) and propose private algorithms for community recovery. Our work explores the fundamental trade-offs between the privacy budget and the accurate recovery of community labels. Furthermore, we establish information-theoretic conditions that guarantee the accuracy of our methods, providing theoretical assurances for successful community recovery under edge DP. |
| title | On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models |
| topic | Social and Information Networks Cryptography and Security Information Theory Machine Learning |
| url | https://arxiv.org/abs/2505.05816 |