Daily Arxiv

This is a page that curates AI-related papers published worldwide.
All content here is summarized using Google Gemini and operated on a non-profit basis.
Copyright for each paper belongs to the authors and their institutions; please make sure to credit the source when sharing.

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

Created by
  • Haebom

Author

Quentin Hillebrand, Vorapong Suppakitpaisarn, Tetsuo Shibuya

Outline

This paper proposes a method to reduce communication costs by using hash functions in the process of counting the number of subgraphs under edge-local differential privacy. Existing graph statistics computation algorithms based on edge-local differential privacy have high communication costs, making them difficult to apply to large-scale graphs. In this paper, we introduce linear congruence hashing to solve this problem. Using a sampling rate $s$ can reduce the communication cost by $s^2$, but the variance of the published graph statistics increases by $s$. Experimental results show that the $\ell_2$-error for the triangle count is reduced by up to 1000 times compared to the existing state-of-the-art algorithms with the same communication cost.

Takeaways, Limitations

•
Takeaways:
◦
We present a novel method for efficiently counting the number of subgraphs in a large graph under edge-local differential privacy.
◦
We experimentally demonstrate that linear joint hashing can dramatically reduce communication costs.
◦
Compared to existing algorithms, the $\ell_2$-error can be significantly reduced.
•
Limitations:
◦
As the sampling rate increases, the variance of the published graph statistics increases.
◦
The effectiveness of the proposed method may depend on the specific hash function and sampling strategy.
◦
The experiments are limited to the number of triangles, and generalizability to other types of subgraphs requires further study.
👍
Made with Slashpage