Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More
Fuente:
arXiv
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912142236581888 |
|---|---|
| author | Chandra, Rishi Dinitz, Michael Fan, Chenglin Zou, Zongrui |
| author_facet | Chandra, Rishi Dinitz, Michael Fan, Chenglin Zou, Zongrui |
| contents | In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum $k$-cut. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. Motivated by multiway cut, we propose the shifting mechanism, a general framework for private combinatorial optimization problems. This framework allows us to develop an efficient private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm, improving over previous private algorithms that have provably worse multiplicative loss. We then provide a tight information-theoretic lower bound on the additive error, demonstrating that for constant $k$, our algorithm is optimal in terms of the privacy cost. The shifting mechanism also allows us to design private algorithm for the multicut and max-cut problems, with runtimes determined by the best non-private algorithms for these tasks. For the minimum $k$-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate $k$-cuts to get the first private algorithm with optimal additive error of $O(k\log n)$ (for a fixed privacy parameter). We also establish an information-theoretic lower bound that matches this additive error. Furthermore, we provide an efficient private algorithm even for non-constant $k$, including a polynomial-time 2-approximation with an additive error of $\tilde{O}(k^{1.5})$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2407_06911 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More Chandra, Rishi Dinitz, Michael Fan, Chenglin Zou, Zongrui Cryptography and Security Data Structures and Algorithms In this paper, we address the challenge of differential privacy in the context of graph cuts, specifically focusing on the multiway cut and the minimum $k$-cut. We introduce edge-differentially private algorithms that achieve nearly optimal performance for these problems. Motivated by multiway cut, we propose the shifting mechanism, a general framework for private combinatorial optimization problems. This framework allows us to develop an efficient private algorithm with a multiplicative approximation ratio that matches the state-of-the-art non-private algorithm, improving over previous private algorithms that have provably worse multiplicative loss. We then provide a tight information-theoretic lower bound on the additive error, demonstrating that for constant $k$, our algorithm is optimal in terms of the privacy cost. The shifting mechanism also allows us to design private algorithm for the multicut and max-cut problems, with runtimes determined by the best non-private algorithms for these tasks. For the minimum $k$-cut problem we use a different approach, combining the exponential mechanism with bounds on the number of approximate $k$-cuts to get the first private algorithm with optimal additive error of $O(k\log n)$ (for a fixed privacy parameter). We also establish an information-theoretic lower bound that matches this additive error. Furthermore, we provide an efficient private algorithm even for non-constant $k$, including a polynomial-time 2-approximation with an additive error of $\tilde{O}(k^{1.5})$. |
| title | Differentially Private Algorithms for Graph Cuts: A Shifting Mechanism Approach and More |
| topic | Cryptography and Security Data Structures and Algorithms |
| url | https://arxiv.org/abs/2407.06911 |