Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2023
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866911104332988416 |
|---|---|
| author | Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo |
| author_facet | Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo |
| contents | We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. While various algorithms exist for computing graph statistics, including the count of subgraphs, under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression is a typical approach in differential privacy, its application in local differential privacy requires a form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. With a sampling rate of $s$, our method can cut communication costs by a factor of $s^2$, albeit at the cost of increasing variance in the published graph statistic by a factor of $s$. The experimental results indicate that, when matched for communication costs, our method achieves a reduction in the $\ell_2$-error for triangle counts by up to 1000 times compared to the performance of leading algorithms. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2312_07055 |
| institution | arXiv |
| publishDate | 2023 |
| record_format | arxiv |
| spellingShingle | Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions Hillebrand, Quentin Suppakitpaisarn, Vorapong Shibuya, Tetsuo Cryptography and Security Artificial Intelligence We suggest the use of hash functions to cut down the communication costs when counting subgraphs under edge local differential privacy. While various algorithms exist for computing graph statistics, including the count of subgraphs, under the edge local differential privacy, many suffer with high communication costs, making them less efficient for large graphs. Though data compression is a typical approach in differential privacy, its application in local differential privacy requires a form of compression that every node can reproduce. In our study, we introduce linear congruence hashing. With a sampling rate of $s$, our method can cut communication costs by a factor of $s^2$, albeit at the cost of increasing variance in the published graph statistic by a factor of $s$. The experimental results indicate that, when matched for communication costs, our method achieves a reduction in the $\ell_2$-error for triangle counts by up to 1000 times compared to the performance of leading algorithms. |
| title | Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions |
| topic | Cryptography and Security Artificial Intelligence |
| url | https://arxiv.org/abs/2312.07055 |