2023/12/12 by Quentin Hillebrand, Hillebrand, Quentin, Vorapong Suppakitpaisarn +3 · 2 citations
Computer Science · Social Sciences · #Artificial Intelligence (cs.AI) #Caching and Content Delivery #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #Privacy, Security, and Data Protection #Privacy-Preserving Technologies in Data
paper · pdf · doi:10.48550/arxiv.2312.07055
openalex publication_date 2023/12/12 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 s2, 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 ℓ2-error for triangle counts by up to 1000 times compared to the performance of leading algorithms.