论文标题

在洗牌模型中差异私人三角形和4周期计数

Differentially Private Triangle and 4-Cycle Counting in the Shuffle Model

论文作者

Imola, Jacob, Murakami, Takao, Chaudhuri, Kamalika

论文摘要

子图计数对于分析图形数据中的连接模式或聚类趋势是基本的。最近的研究应用了LDP(当地的差异隐私)来进行子图计数,以保护用户隐私,即使在社交网络中的数据收集器中也是如此。但是,现有的本地算法遭受了极大的估计错误或在用户和数据收集器之间的多轮交互,这需要大量的用户工作和同步。 在本文中,我们专注于一次交互作用,并通过引入最近研究的洗牌模型提出准确的子图计数算法。我们首先提出了一种称为Wedge Shuffling的基本技术,以发送楔形信息,这是几个子图的主要组成部分,具有微小的噪音。然后,我们将楔形改组应用于计数三角形和四个循环(用于分析聚类趋势的基本子图),并采用了其他几种技术。我们还显示了每种算法的估计误差的上限。我们通过全面的实验表明,我们的单轮洗牌算法在准确性方面显着优于单轮本地算法,并以合理的隐私预算(例如,在Edge DP中大于1)实现小估计错误。

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.

扫码加入交流群

加入微信交流群

微信交流群二维码

扫码加入学术交流群,获取更多资源