Locally Differentially Private Graph Clustering via the Power Iteration Method
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_ | 1866918022212485120 |
|---|---|
| author | Suppakitpaisarn, Vorapong Mukherjee, Sayan |
| author_facet | Suppakitpaisarn, Vorapong Mukherjee, Sayan |
| contents | We propose a locally differentially private graph clustering algorithm. Previous works have explored this problem, including approaches that apply spectral clustering to graphs generated via the randomized response algorithm. However, these methods only achieve accurate results when the privacy budget is in $Ω(\log n)$, which is unsuitable for many practical applications. In response, we present an interactive algorithm based on the power iteration method. Given that the noise introduced by the largest eigenvector constant can be significant, we incorporate a technique to eliminate this constant. As a result, our algorithm attains local differential privacy with a constant privacy budget when the graph is well-clustered and has a minimum degree of $\tildeΩ(\sqrt{n})$. In contrast, while randomized response has been shown to produce accurate results under the same minimum degree condition, it is limited to graphs generated from the stochastic block model. We perform experiments to demonstrate that our method outperforms spectral clustering applied to randomized response results. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_11169 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Locally Differentially Private Graph Clustering via the Power Iteration Method Suppakitpaisarn, Vorapong Mukherjee, Sayan Data Structures and Algorithms Social and Information Networks We propose a locally differentially private graph clustering algorithm. Previous works have explored this problem, including approaches that apply spectral clustering to graphs generated via the randomized response algorithm. However, these methods only achieve accurate results when the privacy budget is in $Ω(\log n)$, which is unsuitable for many practical applications. In response, we present an interactive algorithm based on the power iteration method. Given that the noise introduced by the largest eigenvector constant can be significant, we incorporate a technique to eliminate this constant. As a result, our algorithm attains local differential privacy with a constant privacy budget when the graph is well-clustered and has a minimum degree of $\tildeΩ(\sqrt{n})$. In contrast, while randomized response has been shown to produce accurate results under the same minimum degree condition, it is limited to graphs generated from the stochastic block model. We perform experiments to demonstrate that our method outperforms spectral clustering applied to randomized response results. |
| title | Locally Differentially Private Graph Clustering via the Power Iteration Method |
| topic | Data Structures and Algorithms Social and Information Networks |
| url | https://arxiv.org/abs/2505.11169 |