Near-Optimal Differentially Private k-Core Decomposition
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2023
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909123125182464 |
|---|---|
| author | Dhulipala, Laxman Li, George Z. Liu, Quanquan C. |
| author_facet | Dhulipala, Laxman Li, George Z. Liu, Quanquan C. |
| contents | Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the $k$-core decomposition problem under differential privacy via a connection between low round/depth distributed/parallel graph algorithms and private algorithms with small error bounds. They showed that one can output differentially private approximate $k$-core numbers, while only incurring a multiplicative error of $(2 +η)$ (for any constant $η>0$) and additive error of $\poly(\log(n))/\eps$. In this paper, we revisit this problem. Our main result is an $\eps$-edge differentially private algorithm for $k$-core decomposition which outputs the core numbers with no multiplicative error and $O(\text{log}(n)/\eps)$ additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error. Our result relies on a novel generalized form of the sparse vector technique, which is especially well-suited for threshold-based graph algorithms; thus, we further strengthen the connection between distributed/parallel graph algorithms and differentially private algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07706 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Near-Optimal Differentially Private k-Core Decomposition Dhulipala, Laxman Li, George Z. Liu, Quanquan C. Data Structures and Algorithms Cryptography and Security Social and Information Networks Recent work by Dhulipala et al. \cite{DLRSSY22} initiated the study of the $k$-core decomposition problem under differential privacy via a connection between low round/depth distributed/parallel graph algorithms and private algorithms with small error bounds. They showed that one can output differentially private approximate $k$-core numbers, while only incurring a multiplicative error of $(2 +η)$ (for any constant $η>0$) and additive error of $\poly(\log(n))/\eps$. In this paper, we revisit this problem. Our main result is an $\eps$-edge differentially private algorithm for $k$-core decomposition which outputs the core numbers with no multiplicative error and $O(\text{log}(n)/\eps)$ additive error. This improves upon previous work by a factor of 2 in the multiplicative error, while giving near-optimal additive error. Our result relies on a novel generalized form of the sparse vector technique, which is especially well-suited for threshold-based graph algorithms; thus, we further strengthen the connection between distributed/parallel graph algorithms and differentially private algorithms. |
| title | Near-Optimal Differentially Private k-Core Decomposition |
| topic | Data Structures and Algorithms Cryptography and Security Social and Information Networks |
| url | https://arxiv.org/abs/2312.07706 |