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.

使用哈希函数来减少子图在边缘局部差分隐私下的通信成本，通过将沟通成本降低为 $s^2$ 倍的采样速率方法，减少三角计数的误差 1000 倍。