Papers › Counting Graphlets of Size k under Local Differential Privacy
Counting Graphlets of Size k under Local Differential Privacy
Vorapong Suppakitpaisarn, Donlapark Ponnoprat, Nicha Hirankarn, Quentin Hillebrand
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
The problem of counting subgraphs or graphlets under local differential privacy is an important challenge that has attracted significant attention from researchers. However, much of the existing work focuses on small graphlets like triangles or k-stars. In this paper, we propose a non-interactive, locally differentially private algorithm capable of counting graphlets of any size k. When n is the number of nodes in the input graph, we show that the expected ℓ₂ error of our algorithm is O(n^(k - 1)). Additionally, we prove that there exists a class of input graphs and graphlets of size k for which any non-interactive counting algorithm incurs an expected ℓ₂ error of Ω(n^(k - 1)), demonstrating the optimality of our result. Furthermore, we establish that for certain input graphs and graphlets, any locally differentially private algorithm must have an expected ℓ₂ error of Ω(n^(k - 1.5)). Our experimental results show that our algorithm is more accurate than the classical randomized response method.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections