基于图的差分隐私聚类
研究了针对良好聚类图中恢复聚类的差分隐私算法,这些图的顶点集可以被划分为少量集合,每个集合引导高内部电导和小外部电导的子图,这些图在谱聚类的理论分析中具有普遍应用。提供了一种针对这种图特别定制的高效(ε,δ)差分隐私算法。该算法灵感来自 Chen 等人最近的工作,他们在图仅包含两个几乎平衡聚类的情况下开发了差分隐私算法。我们的算法适用于具有 k 个几乎平衡聚类的良好聚类图,误分类比率接近最佳非隐私算法。通过在已知的地面真实聚类的数据集上进行实验评估,证实了我们算法的能力。还表明任何(纯的)ε- 差分隐私算法将导致显著的误差。
Mar, 2024
提出了一种基于最小权重生成树的可微聚类方法,通过线性规划的随机扰动实现平滑和高效的梯度计算,从而在端对端可训练流水线中进行聚类,并演示其在高噪声和具有挑战性的数据集上的性能和用于半监督任务的。
May, 2023
通过使用 Morse 理论,构建子高斯簇将复杂簇分布与不同隐私保护保持一定的性能平衡,由于差分隐私子簇是通过现有方法进行获得的,所以所提出的方法几乎不存在额外的隐私损失。实验结果表明,在相同的隐私级别下,我们的方法能够实现更好的聚类性能。
Apr, 2023
本文研究了在输入稳定性假设下的差分隐私聚类问题,提出了一种简单的算法,分析了其在 Wasserstein 距离和 k-means 代价等方面的效用,可直接应用于 “好” 的 k - 中位数实例和本地模型的差分隐私。
Jun, 2021
本论文研究了不同 ially private clustering 任务,为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法,同时只产生小的附加误差,从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外,我们展示了在适度的维数下,可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。
Aug, 2020
通过利用树嵌入和标准的降维技术,我们提出了一种高效易实现的算法,能够解决 $k$- 中位数和 $k$- 均值的私有聚类问题,具有很好的时间和空间复杂度,适用于大规模分布式计算环境,并有可观的隐私保障.
Jun, 2022
本文提出了一种新的差分隐私机制,该机制支持对敏感数据库上通过一些关系代数计算的结果的线性统计量进行近似,并且支持不受限制的连接操作,其误差边界大致与查询的经验灵敏度成正比,对于任何一种子图,本文提供了能够实现节点差分隐私的第一种解决方案。
Apr, 2013
在本研究中,我们考虑了一种本地模型,提出了使用局部差分隐私的子图计数算法,包括三角形计数和 K 星计数,并证明了另一个轮可以显著提高效用,在实验中表明可以在局部差分隐私模型中准确估计子图计数。
Oct, 2020