几乎线性时间的差分隐私合成图释放

Jun, 2024

几乎线性时间的差分隐私合成图释放

Almost linear time differentially private release of synthetic graphs

Jingcheng Liu, Jalaj Upadhyay, Zongrui Zou

TL;DR给定输入为具有 n 个顶点 m 条边的图 G，本论文提出了第一个时间复杂度为 O (m)、空间复杂度为 O (m) 的差分隐私算法，用于输出近似于 G 的所有切割和谱的顶点数为 n、边数为 O (m) 的合成图，同时实现了与非隐私设置相匹配的时间和空间复杂性以及先前工作在更实际的稀疏区域内达到相同（或更好）的效用，并且该算法能够扩展到私密图分析和持续观察下。

Abstract

In this paper, we give an almost linear time and space algorithms to sample from an exponential mechanism with an $\ell_1$-score function defined over an exponentially large non-convex set. As a direct result, on input an $n$ vertex $m$ edges graph $G$, we present the \textit{first} $\

exponential mechanism synthetic graph differential privacy graph analysis continual observation

发现论文，激发创造

在线差分私有合成数据生成

在线差分隐私合成数据生成算法，针对数据流和无限时间范围内的超立方体数据，通过在线算法在每个时间 t 生成差分隐私合成数据集，实现在 1-Wasserstein 距离下的近似最优精确度约束。

Feb, 2024

迭代构造与私有数据发布

本文研究在保护差分隐私的情况下近似发布图割函数的问题，并在交互和非交互设置中提出了新算法，其中交互算法是通过重新审视关于数据库上发布差分隐私，近似答案的大量查询的问题来实现的，并给出了一个新的通用框架，在其中新的（高效）IDC 算法产生了新的（高效）交互式私有查询发布机制。非交互算法则是通过随机响应和 Alon 和 Naor 的基于 SDP 的，常数因子逼近割范数的非私有实现的算法来发布保密合成数据。最后，我们给出了一个基于 IDC 框架的约简，表明计算足够精确的秩 1 矩阵逼近的高效，私有算法将导致发布保密合成数据的改进有效算法。

Jul, 2011

私人合成数据发布的新型高效算法

提出了三种新的算法，用于构建差分隐私合成数据，且算法在最坏情况下具有差分隐私，通过理论分析和实证评估，确保准确性与隐私性。

Jul, 2020

稀疏图的私有图汇估计

本文提出了一种基于节点差分隐私的非参数块模型逼近算法，可以保护个体成员隐私信息而又能在保证正确性的前提下对高维稀疏网络的多路径割进行估算，并给出了误差界限。

Jun, 2015

马尔科夫链的近线性时间算法和有向图的新谱基元

本文提出了一种面向有向图的射影逼近概念，并利用该方法构建了一个广泛启发自 Peng-Spielman 的对称线性系统求解框架，通过结合近乎线性时间的稀疏化算法，得到求解定向 Laplacian 线性系统的近乎线性时间算法，本算法的时间复杂度优于现有最优解。

Nov, 2016

通过自适应投影实现差分隐私查询发布

提出了一种新的算法，用于发布对包括 k 路边际在内的非常大量的统计查询回答，该算法采用连续松弛的投影机制，使其在隐私数据集上回答查询并尝试找到最接近噪声回答的合成数据集，并通过不断适应地发现在其（松弛的）合成数据上具有高误差的查询，以达到节省隐私预算的目的，通过使用 ML 优化技术和工具，该方法在许多情况下优于现有算法。

Mar, 2021

利用含噪度进行推断：差分隐私 β- 模型和合成图

本文利用 $eta$-model of random graphs 建立隐私机制并研究了 MLE 存在条件问题，提出了一种私有的参数估计器并证明了其一致性和渐近正态分布特性，同时解决了通过隐私机制释放的数据如何有效地进行统计推断的基础问题。

May, 2012

高维图统计和节点私有度分布的高效 Lipschitz 扩展

本文主要研究了基于 Lipschitz extensions 的多维函数计算，并使用推广指数机制设计了有差分隐私的图的度数分布的近似计算算法。

Apr, 2015

非交互式数据库隐私的学习理论方法

论文证明，私人发布用于大量查询的合成数据库是可能的，但仅针对离散领域，并提供了一种新的数据隐私概念：分布隐私。

Sep, 2011

基于和平方的私有图信息估计

首次开发纯节点差分隐私算法，用于学习随机块模型和多项式时间估计图论，其统计效能保证与先前最佳的信息理论（指数时间）节点私有机制相匹配。该算法基于一个指数机制，用于基于二次优化的得分函数，其水平取决于区块数。我们结果的关键要素是：（1）在可双重随机矩阵的多面体上进行的一个二次优化问题，描述了区块图模式之间的距离；（2）多项式优化在任意多面体上的通用二次收敛结果；（3）对得分函数进行利普希茨扩展的通用方法，作为二次优化算法范例的一部分。

Mar, 2024