Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
Differential Privacy from Locally Adjustable Graph Algorithms: k-Core Decomposition, Low Out-Degree Ordering, and Densest Subgraphs
复制标题
DOI：
10.1109/focs54457.2022.00077
复制
发表时间：
2022-10
期刊：
影响因子：
--
通讯作者：
Laxman Dhulipala;Quanquan C. Liu;Sofya Raskhodnikova;Jessica Shi;Julian Shun;Shangdi Yu
中科院分区：
文献类型：
--
作者：
Laxman Dhulipala;Quanquan C. Liu;Sofya Raskhodnikova;Jessica Shi;Julian Shun;Shangdi Yu
差异私有算法允许大规模数据分析，同时保护用户隐私。随着对个体之间各种（敏感）关系进行建模的大型网络的增长，为图数据设计这样的算法变得越来越重要。虽然在这个领域有丰富的重要文献历史，但据我们所知，没有结果形式化某些并行和分布式图算法与差分私有图分析之间的关系。本文定义了局部可调图算法，并证明了这种算法可以转化为差分私有算法。我们的形式化是由我们在差分隐私的中心和局部模型中提出的一系列结果所激发的，这些结果适用于许多问题，包括k核分解、低出位排序和最密集子图。首先，我们设计了一个$\varepsilon$ -edge差分私有（DP）算法，该算法返回一个节点子集，该节点子集诱导密度至少为$ \frac{D^{*}}{1+\eta}-O(\operatorname{poly}(\log n)/\varepsilon)$的子图，其中$D^{*}$是输入图中密度最大的子图的密度（对于任意常数$\eta\gt 0$）。该算法在保持近线性运行时的同时，实现了先前最著名的私有最密集子图算法的乘法近似因子的两倍改进。然后，我们提出了一种用于k核分解的$\varepsilon$ -局部边缘差分私有（LEDP）算法。我们的LEDP算法提供了近似的核心数字（对于任何常数$\eta\gt 0$）与$(2+\eta)$乘法和$O(\operatorname{poly}(\log n)/\varepsilon)$加法误差。这是第一个输出私有k核分解统计信息的差分私有算法。我们还修改了我们的算法，以返回节点的差分私有低出度排序，其中从排序中较早的节点向排序中较晚的节点定向的边最多导致出度$O(d+$ poly $(\log n)/\varepsilon$)（其中d是图的简并度）。对该算法的一个小修改还产生了$(4+\eta,O(\operatorname{poly}(\log n)/\varepsilon))$近似最密集子图的$\varepsilon$ -LEDP算法（它返回子图中的节点集及其密度）。我们的算法在管理员和各个节点之间使用$O(\log^{2}n)$轮通信。
Differentially private algorithms allow large-scale data analytics while preserving user privacy. Designing such algorithms for graph data is gaining importance with the growth of large networks that model various (sensitive) relationships between individuals. While there exists a rich history of important literature in this space, to the best of our knowledge, no results formalize a relationship between certain parallel and distributed graph algorithms and differentially private graph analysis. In this paper, we define locally adjustable graph algorithms and show that algorithms of this type can be transformed into differentially private algorithms. Our formalization is motivated by a set of results that we present in the central and local models of differential privacy for a number of problems, including k-core decomposition, low out-degree ordering, and densest subgraphs. First, we design an $\varepsilon$-edge differentially private (DP) algorithm that returns a subset of nodes that induce a subgraph of density at least $ \frac{D^{*}}{1+\eta}-O(\operatorname{poly}(\log n)/\varepsilon)$, where $D^{*}$ is the density of the densest subgraph in the input graph (for any constant $\eta\gt 0$). This algorithm achieves a two-fold improvement on the multiplicative approximation factor of the previously best-known private densest subgraph algorithms while maintaining a near-linear runtime. Then, we present an $\varepsilon$-locally edge differentially private (LEDP) algorithm for k-core decompositions. Our LEDP algorithm provides approximates the core numbers (for any constant $\eta\gt 0$) with $(2+\eta)$ multiplicative and $O(\operatorname{poly}(\log n)/\varepsilon)$ additive error. This is the first differentially private algorithm that outputs private k-core decomposition statistics. We also modify our algorithm to return a differentially private low out-degree ordering of the nodes, where orienting the edges from nodes earlier in the ordering to nodes later in the ordering results in out-degree at most $O(d+$ poly $(\log n)/\varepsilon$) (where d is the degeneracy of the graph). A small modification to the algorithm also yields a $\varepsilon$-LEDP algorithm for $(4+\eta,O(\operatorname{poly}(\log n)/\varepsilon))$ approximate densest subgraph (which returns both the set of nodes in the subgraph and its density). Our algorithm uses $O(\log^{2}n)$ rounds of communication between the curator and individual nodes.