Counting Graphlets of Size $k$ under Local Differential Privacy
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866915292669542400 |
|---|---|
| author | Suppakitpaisarn, Vorapong Ponnoprat, Donlapark Hirankarn, Nicha Hillebrand, Quentin |
| author_facet | Suppakitpaisarn, Vorapong Ponnoprat, Donlapark Hirankarn, Nicha Hillebrand, Quentin |
| contents | 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 $\ell_2$ 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 $\ell_2$ 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 $\ell_2$ error of $Ω(n^{k - 1.5})$. Our experimental results show that our algorithm is more accurate than the classical randomized response method. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_12954 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Counting Graphlets of Size $k$ under Local Differential Privacy Suppakitpaisarn, Vorapong Ponnoprat, Donlapark Hirankarn, Nicha Hillebrand, Quentin Social and Information Networks Computational Complexity Data Structures and Algorithms 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 $\ell_2$ 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 $\ell_2$ 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 $\ell_2$ error of $Ω(n^{k - 1.5})$. Our experimental results show that our algorithm is more accurate than the classical randomized response method. |
| title | Counting Graphlets of Size $k$ under Local Differential Privacy |
| topic | Social and Information Networks Computational Complexity Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.12954 |