Differentially private analysis of graphs is widely used for releasing
statistics from sensitive graphs while still preserving user privacy. Most
existing algorithms however are in a centralized privacy model, where a trusted
data curator holds the entire graph. As this model raises a number of privacy
and security issues -- such as, the trustworthiness of the curator and the
possibility of data breaches, it is desirable to consider algorithms in a more
decentralized local model where no server holds the entire graph.
In this work, we consider a local model, and present algorithms for counting
subgraphs -- a fundamental task for analyzing the connection patterns in a
graph -- with LDP (Local Differential Privacy). For triangle counts, we present
algorithms that use one and two rounds of interaction, and show that an
additional round can significantly improve the utility. For $k$-star counts, we
present an algorithm that achieves an order optimal estimation error in the
non-interactive local model. We provide new lower-bounds on the estimation
error for general graph statistics including triangle counts and $k$-star
counts. Finally, we perform extensive experiments on two real datasets, and
show that it is indeed possible to accurately estimate subgraph counts in the
local differential privacy model.

在本研究中，我们考虑了一种本地模型，提出了使用局部差分隐私的子图计数算法，包括三角形计数和 K 星计数，并证明了另一个轮可以显著提高效用，在实验中表明可以在局部差分隐私模型中准确估计子图计数。