由Google研究的Graph Mining团队的Vincent Cohen-Addad和Alessandro Epasto发布
聚类是无监督机器学习（ML）中的一个核心问题，广泛应用于行业和学术研究的多个领域。在其核心，聚类包括以下问题：给定一组数据元素，目标是将数据元素分成组，使得相似的对象在同一组中，而不相似的对象在不同的组中。60多年来，这个问题在数学、计算机科学、运筹学和统计学中以其无数的变体进行了研究。聚类的两种常见形式是度量聚类，其中元素是度量空间中的点，例如k-means问题，和图聚类，其中元素是图的节点，其边表示它们之间的相似性。
 |
| 在k-means聚类问题中，我们给出了度量空间中的一组点，目标是识别k个代表点，称为中心（在此处表示为三角形），以最小化每个点到其最近中心的平方距离之和。来源，版权：CC-BY-SA-4.0 |
尽管算法设计方面的聚类文献很广泛，但很少有实际工作专注于在聚类过程中严格保护用户的隐私。当聚类应用于个人数据（例如用户所做的查询）时，有必要考虑在实际系统中使用聚类解决方案的隐私影响以及输出解决方案揭示有关输入数据的信息量。
为了在严格意义上保护隐私，一个解决方案是开发差分隐私（DP）聚类算法。这些算法确保聚类的输出不会揭示有关特定数据元素（例如，用户是否进行了给定查询）或有关输入图中的敏感数据（例如，社交网络中的关系）的私有信息。鉴于隐私保护在无监督机器学习中的重要性，在最近几年中，Google一直在研究不同ially private metric或graph clustering和各种情境下的差分隐私，例如热图或设计DP算法的工具。
今天我们很高兴地宣布两个重要的更新：1）一种新的差分隐私层次图聚类算法，我们将在ICML 2023上展示，2）可扩展的差分隐私k-means算法代码的开源发布。此代码使用分布式计算将差分隐私k-means聚类应用于大规模数据集。在这里，我们还将讨论我们在健康领域最近推出的用于向公共卫生当局提供信息的聚类技术的工作。
差分隐私层次聚类
层次聚类是一种流行的聚类方法，它包括将数据集递归地分成越来越细的群集。生物学中著名的层次聚类的例子是分类系统，其中地球上的所有生命都被分成越来越细的组（例如，王国、门、纲、目等）。层次聚类算法接收表示实体相似性的图作为输入，并以无监督的方式学习这种递归分区。然而，在我们的研究中，尚不知道任何算法可以计算带有边缘隐私的图的层次聚类，即保护顶点交互的隐私。
在“带有可证明逼近保证的差分隐私层次聚类”中，我们考虑在DP上下文中可以对问题进行多好逼近，并对隐私保证建立了坚实的上限和下限。我们设计了一种多项式运行时间的逼近算法（其类型的第一个算法），它具有随节点数n（约为n 2.5 ）缩放的附加误差和O（log ½ n）的乘法逼近，其中乘法误差与非私有设置相同。我们进一步为任何私有算法提供了一个新的附加误差下限（约为n 2 ），并提供了一个与此下限相匹配的指数时间算法。此外，我们的论文包括一种超越最坏情况的分析，重点关注分层随机块模型，这是一种展现自然分层聚类结构的标准随机图模型，并引入了一种私有算法，其返回与最优解相比可以忽略不计的附加成本，这再次匹配非私有状态下的最先进方法。我们相信这项工作扩展了图数据上隐私保护算法的理解，并将使这些设置中的新应用成为可能。
大规模差分隐私聚类
我们现在转换话题，讨论我们在度量空间聚类方面的工作。在差分隐私度量聚类的先前工作中，大多数专注于提高算法在 k-means 目标上的逼近保证，而忽略了可伸缩性问题。确实，不清楚非私有算法，如 k-means++ 或 k-means//，如何在不牺牲逼近保证或可伸缩性的情况下实现差分隐私。另一方面，在 Google，可伸缩性和隐私都是重要的。因此，我们最近发表了多篇论文，解决了设计高效的差分隐私聚类算法以适应海量数据集的问题。我们的目标是为大规模输入数据集提供可扩展性，即使目标中心数 k 较大。
我们在大规模并行计算（MPC）模型中工作，这是一种代表现代分布式计算体系结构的计算模型。该模型由几台机器组成，每台机器只持有部分输入数据，它们共同努力解决全局问题，同时尽量减少机器之间的通信量。我们提出了一种差分隐私常数因子逼近算法，适用于只需要进行常数轮同步的 k-means。我们的算法建立在我们先前解决的问题上（代码在此处可用），那是第一个具有可证明逼近保证且可以在 MPC 模型中工作的差分隐私聚类算法。
DP 常数因子逼近算法采用两阶段方法，大幅改进了以前的工作。在初始阶段，它计算出一个粗略的逼近值，以“种子”第二阶段，该阶段由更复杂的分布式算法组成。配备第一步逼近，第二阶段依赖于核心集文献中的结果，对输入点的相关子样本进行子采样，并找到输入点的良好差分隐私聚类解。然后，我们证明了这个解可以近似地推广到整个输入。
通过 DP 聚类获得疫苗搜索见解
然后，我们将这些差分隐私聚类的进展应用于实际应用。其中一个例子是我们应用差分隐私聚类解决方案来发布与 COVID 疫苗相关的查询，同时为用户提供强大的隐私保护。
Vaccination Search Insights (VSI) 的目标是帮助公共卫生决策者（卫生部门、政府机构和非营利组织）识别和响应有关 COVID 疫苗的社区信息需求。为了实现这一目标，该工具允许用户在不同的地理位置粒度下（美国的邮政编码、县和州级别）探索用户关于 COVID 查询的热门主题。特别是，该工具可视化关于趋势查询的统计信息，这些查询在给定的地点和时间内引起了兴趣。
 |
| 该工具的输出截图。左侧显示了与 Covid 疫苗相关的热门搜索，时间为 2022 年 10 月 10 日至 16 日。右侧显示了在同一时期内相较于上周重要性有所上升的查询。 |
为了更好地帮助识别趋势搜索的主题，该工具基于它们的语义相似性对搜索查询进行聚类。这是通过运行基于 k-means 的自定义设计算法来完成的，该算法对已使用 DP 高斯机制进行匿名处理的搜索数据进行加噪和去除低计数查询（从而得到差分聚类）。该方法确保了对用户数据的强差分隐私保证。
该工具提供了有关 COVID 疫苗在精细数据上的认知，这在理解受 COVID 不平等影响的边缘化社区的需求方面尤为重要。该项目突出了我们在差分隐私和无监督机器学习方法研究方面的投资的影响。我们正在寻找其他重要领域，可以应用这些聚类技术来帮助指导围绕全球卫生挑战的决策，例如与气候变化相关的挑战，如空气质量或极端高温的搜索查询。
致谢
我们感谢我们的合作者Jacob Imola、Silvio Lattanzi、Jason Lee、Mohammad Mahdian、Vahab Mirrokni、Andres Munoz Medina、Shyam Narayanan、Mark Phillips、David Saulpic、Chris Schwiegelshohn、Sergei Vassilvitskii、Peilin Zhong以及使VSI发布成为可能的Health AI团队成员：Shailesh Bavadekar、Adam Boulanger、Tague Griffith、Mansi Kansal、Chaitanya Kamath、Akim Kumok、Yael Mayer、Tomer Shekel、Megan Shum、Charlotte Stanton、Mimi Sun、Swapnil Vispute和Mark Young。
有关图挖掘团队（算法和优化的一部分）的更多信息，请访问我们的页面。