# Communication Cost Reduction for Subgraph Counting under Local Differential Privacy via Hash Functions

arXiv: https://arxiv.org/abs/2312.07055 · HTML: https://mlsanity.com/paper/2312.07055/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 15 of its 55 references that are in the map.
- First posted on arXiv 12 Dec 2023.

## Builds on (most cited first, 15 of 15)

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Privacy Amplification by Subsampling: Tight Analyses via Couplings and Divergences](https://mlsanity.com/paper/1807.01647/) (2018)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Locally Private Graph Neural Networks](https://mlsanity.com/paper/2006.05535/) (2020)
- [Optimal Algorithms for Mean Estimation under Local Differential Privacy](https://mlsanity.com/paper/2205.02466/) (2022)
- [Locally Differentially Private Analysis of Graph Statistics](https://mlsanity.com/paper/2010.08688/) (2020)
- [Estimating Numerical Distributions under Local Differential Privacy](https://mlsanity.com/paper/1912.01051/) (2019)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Degree-Preserving Randomized Response for Graph Neural Networks under Local Differential Privacy](https://mlsanity.com/paper/2202.10209/) (2022)
- [Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs](https://mlsanity.com/paper/2211.10887/) (2022)
- [A centrality measure for quantifying spread on weighted, directed networks](https://mlsanity.com/paper/2303.09684/) (2023)
- [Communication-Efficient Triangle Counting under Local Differential Privacy](https://mlsanity.com/paper/2110.06485/) (2021)
- [Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model](https://mlsanity.com/paper/2205.01429/) (2022)
- [Network change point localisation under local differential privacy](https://mlsanity.com/paper/2205.07144/) (2022)
- [Triangle Counting with Local Edge Differential Privacy](https://mlsanity.com/paper/2305.02263/) (2023)

## Abstract (arXiv)

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.