Mar, 2024

一种用于良好聚类图的差分隐私聚类算法

PDF
TL;DR研究了针对良好聚类图中恢复聚类的差分隐私算法，这些图的顶点集可以被划分为少量集合，每个集合引导高内部电导和小外部电导的子图，这些图在谱聚类的理论分析中具有普遍应用。提供了一种针对这种图特别定制的高效（ε，δ）差分隐私算法。该算法灵感来自 Chen 等人最近的工作，他们在图仅包含两个几乎平衡聚类的情况下开发了差分隐私算法。我们的算法适用于具有 k 个几乎平衡聚类的良好聚类图，误分类比率接近最佳非隐私算法。通过在已知的地面真实聚类的数据集上进行实验评估，证实了我们算法的能力。还表明任何（纯的）ε- 差分隐私算法将导致显著的误差。
differentially private algorithmsclusterswell-clustered graphsspectral clusteringstochastic block models
发现论文，激发创造
  • 基于图的差分隐私聚类

    本文提出了一种针对图中任意形状节点簇的差分隐私聚类算法，该算法仅使用在权重差分隐私约束下释放的近似最小生成树作为输入，并通过最优剪切方法从中成功恢复底层的非凸聚类分区。与现有方法不同，我们的算法在理论上得到了很好的支持，并且实验证实了我们的理论发现。

    Mar, 2018

  • 图统计数据的局部差分隐私分析

    在本研究中，我们考虑了一种本地模型，提出了使用局部差分隐私的子图计数算法，包括三角形计数和 K 星计数，并证明了另一个轮可以显著提高效用，在实验中表明可以在局部差分隐私模型中准确估计子图计数。

    Oct, 2020

  • 差分隐私聚类：紧密逼近比率

    本论文研究了不同 ially private clustering 任务，为 Euclidean DensestBall、1-Cluster、k-means 和 k-median 等基本聚类问题提供了有效的差分隐私算法，同时只产生小的附加误差，从而实现了与任何非私有算法可以获得的近似比例基本相同的近似比例。这改进了现有的仅实现某些大常数逼近因子的有效算法。我们的结果还暗示了改进的 Sample and Aggregate 隐私框架算法。此外，我们展示了在适度的维数下，可以利用我们的 1-Cluster 算法中使用的工具来获得更快的 ClosestPair 量子算法。

    Aug, 2020

  • 具有差分隐私的因果推断（聚类）结果

    基于随机实验估计因果效应只有在参与者同意透露潜在敏感回应的情况下才可行。我们提出了一种新的差分隐私机制 “Cluster-DP”，通过利用数据的任何给定的聚类结构来实现更强的隐私保证和更低的方差损失，同时仍然允许因果效应的估计。

    Aug, 2023

  • 学习高斯及更高模型的私有与多项式时间算法

    提出了一个将差分隐私统计估计转化为无差分隐私的框架，并给出了用于学习高斯分布和鲁棒学习高斯分布的多项式时间差分隐私算法，该方法中学习高斯分布的样本复杂度和已知的信息论样本复杂度的上限相匹配，并且还证明了相似的结果，其中鲁棒学习高斯分布的样本复杂度更低。

    Nov, 2021

  • 数据流中的差分隐私聚类

    论文提出了不同隐私性水平的 k-means 和 k-median 流式聚类算法，采用核心集算法作为黑盒子并使用多项式空间达到恒定乘性错误和多项式加性错误。

    Jul, 2023

  • 本地差分隐私数据收集与分析

    本文提出一种实现高精度（ε，δ）-LDP （可保持个人数据隐私）的机制，分别针对多维数值数据和分类属性进行收集，实现了对数据的安全保护和更高的准确性，实验证明其在数据统计和机器学习模型中具有很高的数据实用性。

    Jun, 2019

  • 差分隐私下的社区检测

    本篇研究基于微分隐私解决复杂网络隐私保护问题，提出了基于 Louvain 方法的输入扰动方案 LouvainDP 和基于指数机制的算法扰动方案 ModDivisive，并在真实数据集上进行了充分评估，验证了其优越性。

    Jul, 2016

  • 连续观察下的聚类差分隐私

    我们考虑在 $ R^d $ 中进行隐私数据集聚类的问题

    Jul, 2023

  • DPM：通过分离对敏感数据进行聚类

    通过优化数据集的分割器，以差分隐私方式搜索准确的数据点分隔符的差分隐私聚类算法 DPM 在聚类度量不变性方面取得了显著的改善。

    Jul, 2023