Privacy-preserving clustering groups data points in an unsupervised manner
whilst ensuring that sensitive information remains protected. Previous
privacy-preserving clustering focused on identifying concentration of point
clouds. In this paper, we take another path and focus on identifying
appropriate separators that split a data set. We introduce the novel
differentially private clustering algorithm DPM that searches for accurate data
point separators in a differentially private manner. DPM addresses two key
challenges for finding accurate separators: identifying separators that are
large gaps between clusters instead of small gaps within a cluster and, to
efficiently spend the privacy budget, prioritising separators that split the
data into large subparts. Using the differentially private Exponential
Mechanism, DPM randomly chooses cluster separators with provably high utility:
For a data set $D$, if there is a wide low-density separator in the central
$60\%$ quantile, DPM finds that separator with probability $1 -
\exp(-\sqrt{|D|})$. Our experimental evaluation demonstrates that DPM achieves
significant improvements in terms of the clustering metric inertia. With the
inertia results of the non-private KMeans++ as a baseline, for $\varepsilon =
1$ and $\delta=10^{-5}$ DPM improves upon the difference to the baseline by up
to $50\%$ for a synthetic data set and by up to $62\%$ for a real-world data
set compared to a state-of-the-art clustering algorithm by Chang and Kamath.

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

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

DPM: Clustering Sensitive Data through Separation

Clustering is a fundamental problem in data analysis. In differentially
private clustering, the goal is to identify $k$ cluster centers without
disclosing information on individual data points. Despite significant research
progress, the problem had so far resisted practical solutions. In this work we
aim at providing simple implementable differentially private clustering
algorithms that provide utility when the data is "easy," e.g., when there
exists a significant separation between the clusters.
We propose a framework that allows us to apply non-private clustering
algorithms to the easy instances and privately combine the results. We are able
to get improved sample complexity bounds in some cases of Gaussian mixtures and
$k$-means. We complement our theoretical analysis with an empirical evaluation
on synthetic data.

本文研究的是隐私保护聚类算法，提出了一个依据难易程度来组合本来不带保护性质的聚类算法和隐私保护结果的框架，并在高斯混合数据和 $k$-means 算法中实现了样本复杂度较小的聚类效果进行了实证评估。

易实例的不同 ially-Private 聚类

Differentially-Private Clustering of Easy Instances

We study the task of differentially private clustering. For several basic
clustering problems, including Euclidean DensestBall, 1-Cluster, k-means, and
k-median, we give efficient differentially private algorithms that achieve
essentially the same approximation ratios as those that can be obtained by any
non-private algorithm, while incurring only small additive errors. This
improves upon existing efficient algorithms that only achieve some large
constant approximation factors.
Our results also imply an improved algorithm for the Sample and Aggregate
privacy framework. Furthermore, we show that one of the tools used in our
1-Cluster algorithm can be employed to get a faster quantum algorithm for
ClosestPair in a moderate number of dimensions.

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

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

Differentially Private Clustering: Tight Approximation Ratios

In this paper, we present the first differentially private clustering method
for arbitrary-shaped node clusters in a graph. This algorithm takes as input
only an approximate Minimum Spanning Tree (MST) $\mathcal{T}$ released under
weight differential privacy constraints from the graph. Then, the underlying
nonconvex clustering partition is successfully recovered from cutting optimal
cuts on $\mathcal{T}$. As opposed to existing methods, our algorithm is
theoretically well-motivated. Experiments support our theoretical findings.

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