标题： 大小为$k$的图元计数在局部差分隐私下的应用 显示英文标题

标题： Counting Graphlets of Size $k$ under Local Differential Privacy

摘要： 计数满足局部差分隐私的子图或图let的问题是一个重要的挑战，已经引起了研究人员的广泛关注。 然而，现有的大部分工作集中在小图let上，如三角形或$k$-星型。 在本文中，我们提出了一种非交互式的、局部差分隐私算法，能够计数任何大小的图let$k$。 当$n$是输入图中的节点数时，我们证明了我们算法的期望 $\ell_2$误差为$O(n^{k - 1})$。 此外，我们证明存在一类输入图和大小为$k$的图小片，对于这些情况，任何非交互式计数算法都会产生期望的$\ell_2$误差为$\Omega(n^{k - 1})$，从而证明了我们结果的最优性。 此外，我们建立了一种对于某些输入图和图小片，任何局部差分隐私算法都必须具有期望的$\ell_2$误差为$\Omega(n^{k - 1.5})$。 我们的实验结果表明，我们的算法比经典的随机响应方法更准确。 显示英文摘要

摘要： 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 $\Omega(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 $\Omega(n^{k - 1.5})$. Our experimental results show that our algorithm is more accurate than the classical randomized response method.