Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866911785369468928 |
|---|---|
| author | Henzinger, Monika Sricharan, A. R. Zhu, Leqi |
| author_facet | Henzinger, Monika Sricharan, A. R. Zhu, Leqi |
| contents | Computing the core decomposition of a graph is a fundamental problem that has recently been studied in the differentially private setting, motivated by practical applications in data mining. In particular, Dhulipala et al. [FOCS 2022] gave the first mechanism for approximate core decomposition in the challenging and practically relevant setting of local differential privacy. One of the main open problems left by their work is whether the accuracy, i.e., the approximation ratio and additive error, of their mechanism can be improved. We show the first lower bounds on the additive error of approximate and exact core decomposition mechanisms in the centralized and local model of differential privacy, respectively. We also give mechanisms for exact and approximate core decomposition in the local model, with almost matching additive error bounds. Our mechanisms are based on a black-box application of continual counting. They also yield improved mechanisms for the approximate densest subgraph problem in the local model. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2402_18020 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph Henzinger, Monika Sricharan, A. R. Zhu, Leqi Data Structures and Algorithms Cryptography and Security Computing the core decomposition of a graph is a fundamental problem that has recently been studied in the differentially private setting, motivated by practical applications in data mining. In particular, Dhulipala et al. [FOCS 2022] gave the first mechanism for approximate core decomposition in the challenging and practically relevant setting of local differential privacy. One of the main open problems left by their work is whether the accuracy, i.e., the approximation ratio and additive error, of their mechanism can be improved. We show the first lower bounds on the additive error of approximate and exact core decomposition mechanisms in the centralized and local model of differential privacy, respectively. We also give mechanisms for exact and approximate core decomposition in the local model, with almost matching additive error bounds. Our mechanisms are based on a black-box application of continual counting. They also yield improved mechanisms for the approximate densest subgraph problem in the local model. |
| title | Tighter Bounds for Local Differentially Private Core Decomposition and Densest Subgraph |
| topic | Data Structures and Algorithms Cryptography and Security |
| url | https://arxiv.org/abs/2402.18020 |