Node-Differentially Private Estimation of the Number of Connected Components
Node-Differentially Private Estimation of the Number of Connected Components
复制标题
DOI：
10.1145/3584372.3588671
复制
发表时间：
2023-04
期刊：
影响因子：
--
通讯作者：
Iden Kalemaj;Sofya Raskhodnikova;Adam D. Smith;Charalampos E. Tsourakakis
中科院分区：
文献类型：
--
作者：
Iden Kalemaj;Sofya Raskhodnikova;Adam D. Smith;Charalampos E. Tsourakakis
我们设计了第一个节点差分私有算法来逼近图中连接组件的数量。给定一个表示n顶点图G和隐私参数ε的数据库，我们的算法在多项式时间内运行，并且在概率为1- 0(1)的情况下，具有可加性误差Õ（Δ^*łnłn nε），其中Δ^*是生成森林G的最小可能最大值。为连接组件的数量设计这样一种算法的一个主要障碍是，该图统计数据对于添加一个具有任意连接的节点（节点差分隐私被设计为隐藏的一种更改）不具有鲁棒性：每个图都是连接图的邻居。我们通过设计一组可有效计算的Lipschitz扩展来克服这个问题，这些扩展是关于连通组件的数量，或者等价地，关于生成森林的大小。扩展的构造是我们算法的核心，它基于g的森林多边形。我们证明了关于生成森林的几个组合事实，特别是没有诱导Δ-stars的图有一个最多度为Δ的生成森林。利用这一事实，我们证明了连通分量数的Lipschitz扩展等于最大可能单调图族的函数的真值。更一般地说，在所有单调的图集上，我们的Lipschitz扩展的l∞误差几乎是最优的。
We design the first node-differentially private algorithm for approximating the number of connected components in a graph. Given a database representing an n-vertex graph G and a privacy parameter ε, our algorithm runs in polynomial time and, with probability 1-o(1), has additive error Õ(Δ^*łnłn nε ), where Δ^* is the smallest possible maximum degree of a spanning forest of G. Node-differentially private algorithms are known only for a small number of database analysis tasks. A major obstacle for designing such an algorithm for the number of connected components is that this graph statistic is not robust to adding one node with arbitrary connections (a change that node-differential privacy is designed to hide): every graph is a neighbor of a connected graph. We overcome this by designing a family of efficiently computable Lipschitz extensions of the number of connected components or, equivalently, the size of a spanning forest. The construction of the extensions, which is at the core of our algorithm, is based on the forest polytope of G. We prove several combinatorial facts about spanning forests, in particular, that a graph with no induced Δ-stars has a spanning forest of degree at most Δ. With this fact, we show that our Lipschitz extensions for the number of connected components equal the true value of the function for the largest possible monotone families of graphs. More generally, on all monotone sets of graphs, the l∞ error of our Lipschitz extensions is nearly optimal.