Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model
Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model
复制标题
DOI：
10.1145/3548606.3560659
复制
发表时间：
2022-05
期刊：
影响因子：
--
通讯作者：
Jacob Imola;Takao Murakami;Kamalika Chaudhuri
中科院分区：
文献类型：
--
作者：
Jacob Imola;Takao Murakami;Kamalika Chaudhuri
子图计数是分析图数据中的连接模式或聚类趋势的基础。最近的研究已经将LDP（局部差分隐私）应用于子图计数，以保护用户隐私，即使是针对社交网络中的数据收集器。然而，现有的本地算法遭受极大的估计误差或假设用户和数据收集器之间的多轮交互，这需要大量的用户努力和同步。在本文中，我们专注于一轮的互动，并提出准确的子图计数算法，通过引入最近研究的洗牌模型。首先，我们提出了一个基本的技术，称为楔形洗牌发送楔形信息，几个子图的主要组成部分，小噪音。然后，我们应用我们的楔形洗牌计数三角形和4-循环-分析聚类趋势的基本子图-与几个额外的技术。我们还显示了每个算法的估计误差的上界。我们通过全面的实验表明，我们的一轮洗牌算法在准确性方面显着优于一轮本地算法，并在合理的隐私预算下实现小的估计误差，例如，小于1 in edge DP。
Subgraph counting is fundamental for analyzing connection patterns or clustering tendencies in graph data. Recent studies have applied LDP (Local Differential Privacy) to subgraph counting to protect user privacy even against a data collector in social networks. However, existing local algorithms suffer from extremely large estimation errors or assume multi-round interaction between users and the data collector, which requires a lot of user effort and synchronization. In this paper, we focus on a one-round of interaction and propose accurate subgraph counting algorithms by introducing a recently studied shuffle model. We first propose a basic technique called wedge shuffling to send wedge information, the main component of several subgraphs, with small noise. Then we apply our wedge shuffling to counting triangles and 4-cycles -- basic subgraphs for analyzing clustering tendencies -- with several additional techniques. We also show upper bounds on the estimation error for each algorithm. We show through comprehensive experiments that our one-round shuffle algorithms significantly outperform the one-round local algorithms in terms of accuracy and achieve small estimation errors with a reasonable privacy budget, e.g., smaller than 1 in edge DP.