Google Research 2022 年度总结：算法进展

谷歌的整个系统都依赖于稳健的算法设计，尤其是在处理 ML 和 AI 模型方面更是如此。因此，为了支持各种服务，如搜索、广告、地图和 YouTube，我们一直致力于开发更高效、更具性能和速度的算法。谷歌研究院一直在该领域的前沿工作，致力于开发从隐私安全的推荐系统到大规模 ML 的可扩展创新解决方案。在 2022 年，我们将继续前进，并在几个相关领域推进最先进的技术。在这里， 将重点介绍我们在可扩展性、隐私、市场算法和算法基础等方面取得的进展。

可扩展算法：图形、聚类和优化

随着处理大规模数据集的需求不断增加，这要求算法具备更高的可扩展性和可靠性，同时具备更高的速度和解释性。 我们继续努力开发用于处理各个领域的大型数据集的新算法，包括 无监督 和 半监督学习、基于图的学​​习、聚类 和大规模优化。

在大规模数据集处理中，构建 相似度图 是一个重要的组成部分，用于表示对象之间的相似性关系。为了实现可扩展性和速度，这个图需要是稀疏的，而且不能影响计算质量。我们提出了一种叫做 STAR 的 2-hop spanner 技术，作为高效的分布式图构建策略，并展示了如何显著减少相似性计算的数量，同时产生高质量的图学习或聚类输出。例如，对于一个具有 10T 边的图，我们展示了约 100 倍的成对相似性比较改进和显著的运行时间加速，同时质量损失可忽略不计。我们之前使用这个技术开发了用于度量和最小大小聚类的大规模并行算法。同时，在聚类的背景下，我们开发了第一个线性时间的 层次凝聚聚类 (HAC) 算法以及 DBSCAN，这是第一个并行具有对数深度的 HAC 算法，在 100B 边图上实现了 50 倍的加速。此外，我们还为不同类型的聚类问题设计了改进的次线性算法，例如 几何链接聚类、常数轮相关聚类 和 完全动态 k 聚类。

受到 GBBS 等多核处理技术成功的启发，我们开发了一套能够在单个多核机器上处理具有 100B 条边的图的图挖掘算法。其中最大的挑战是实现快速的并行运行时间（例如亚线性深度）。在之前完成的社区检测和相关聚类工作之后，我们为 HAC 开发了一种名为 ParHAC 的算法。该算法具有可证明的多对数深度和近线性运行时间，并实现了 50 倍的加速。例如，ParHAC 只需要大约 10 分钟就可以在超过 100B 条边的图上找到近似的亲和力层次结构，而在一台机器上找到完整的 HAC 需要大约 3 小时。在我们之前关于分布式 HAC 的工作中，我们将这些多核算法用作分布式算法中的子例程，以处理万亿级图。

2022 年，我们在 图神经网络 (GNN)领域也获得了一些有趣的结果。我们提出了一种 基于模型的分类法，它可以统一许多图学习方法。此外，我们通过对 GNN 模型在数千个具有不同结构的图上的表现进行研究，发现了对 GNN 模型的一些新的见解。我们还提出了一种 新的混合架构 来克服现有 GNN 的深度要求，以解决基本的图形问题，例如最短路径和最小生成树。

此外，我们还发布了三个版本的旗舰建模库，用于在 TensorFlow 中构建图神经网络 (TF-GNN)，以将其中一些进步带给更广泛的社区。亮点包括模型库和模型编排 API，可以轻松构建 GNN 解决方案。继我们在 NeurIPS’20 上举办的大规模图挖掘和学习研讨会之后，我们还在 ICML’22 和 NeurIPS’22 分别举办了基于图的学习研讨会和 TensorFlow 中的 GNN 教程。

在论文《Robust Routing Using Electrical Flows》中，我们介绍了一篇 最新 的论文，该论文提出了一种用于 Google 地图的解决方案，可以有效地计算道路网络中的备用路径，以应对可能出现的故障，例如道路关闭或事故。我们展示了这种方法在现实世界的道路网络中的表现，证明其优于目前最先进的 高原法和惩罚法。

在优化领域，我们开源了 Vizier，这是我们在谷歌的旗舰 黑盒优化 和超参数调整库。此外，我们开发了新技术来解决 线性规划（LP）求解器的可扩展性限制问题，这些限制是由它们依赖矩阵分解而导致的，这限制了并行和分布式方法的机会。为此，我们开源了一种用于LP的 原始对偶混合梯度（PDHG）解决方案，称为 原始对偶线性规划（PDLP），这是一个新的大规模LP问题的一阶求解器。PDLP 已被用于解决具有多达12B 个非零元素（以及扩展到 92B 个非零元素的内部分布式版本）的实际问题。PDLP 的有效性归功于 理论发展 和 算法工程 的结合。

隐私和联邦学习

在 Google 系统中，我们仍然把尊重用户隐私作为提供高质量服务的首要任务。这一领域的研究涉及到很多产品，并且使用了 差分隐私 (DP) 和 联邦学习 等原则来保护用户隐私。

我们取得了一系列算法进步，解决了使用差分隐私来训练大型神经网络的问题。我们早期的工作使我们能够推出基于 DP-FTRL 算法的 DP 神经网络，然后我们开发了 矩阵分解 DP-FTRL 方法。这项工作表明，我们可以设计数学程序来优化大量可能的 DP 机制，以找到最适合特定学习问题的机制。我们还为神经网络和基于内核的方法的 DP 学习建立了独立于输入特征维度的保证。我们进一步将这一概念扩展到更广泛的机器学习任务，与基准性能相匹配，计算量减少了 300 倍。对于大型模型的微调，我们认为一旦经过预训练，这些模型（即使使用 DP）基本上在低维子空间上运行，从而避免了 DP 强加的维数诅咒。在所有这些算法进步中，我们始终尊重用户的隐私，确保我们的算法可以提供高质量的服务。

在算法方面，我们取得了不少进展来估计高维分布的熵。我们开发了 局部 DP 机制，即使每个样本只有一位可用，也能够工作。此外，我们还开发了高效的 shuffle DP 机制。我们提出了一种更准确的方法，以私有方式同时估计数据库中前k个最受欢迎的项目，并在 Plume 库中采用了这种方法。另外，我们还展示了用于 DP 聚类 的近最优近似算法，在 大规模并行计算（MPC）模型中进一步改进了我们之前针对可扩展和分布式设置的工作。

另一个令人兴奋的研究方向是隐私和流媒体领域的交叉。我们取得了重要进展，包括获得了私有频率矩的接近最优的近似空间权衡，以及一种用于对滑动窗口流模型中不同元素进行私有计数的新算法。此外，我们还提出了一个通用 混合框架，用于研究对抗流问题。

我们开发了一些专注于安全和隐私的应用程序，其中涉及交叉点的算法。这些算法是安全、保密和通信高效的，可用于跨发布者的范围和频率测量。这些算法已被 世界广告商联合会 采用作为其 衡量系统 的一部分。我们还开发了新的协议，用于在差分隐私的双服务器模型中计算稀疏直方图。这些协议结合了草图、密码学、多方计算和差分隐私的工具和技术，从计算和通信的角度来看都非常高效，并比标准方法产生的效果更好。

虽然我们已经使用差分隐私算法对 BERT 和 Transformer 进行了训练，但了解大型语言模型（LLM）中训练示例的记忆是评估其隐私的一种启发式方法。我们特别调查了法律硕士在训练期间遗忘（或保留）训练示例的时间和原因。我们的研究结果表明，早期出现的示例可能会以牺牲后期出现的示例为代价，以观察隐私利益。此外，我们还对 LLM 发出的记忆训练数据的程度进行了量化。

市场算法和因果推理

我们持续 研究如何改进在线广告拍卖，特别是自动竞价广告。在这种广告拍卖中，代理竞标者代表广告商进行竞标，以优化广告商的利益。由于广告商、用户、竞标者和广告平台之间的复杂关系，这个领域有很多挑战。我们正在研究如何改进自动竞价算法，以平衡不同方面的利益，例如用户体验和广告商预算。我们发现，即使在不真实的拍卖中，使用机器学习建议和随机化技术可以有效地提高自动竞价算法的效果，从而提高整体福利。

除了自动竞价系统之外，我们还研究了在复杂环境中改进拍卖的方法，例如中介机构代表买家的设置，以及富媒体广告，其中每个广告都可以以多种可能的变体之一显示。我们最近的一项研究总结了我们在这一领域的工作。除了拍卖，我们还研究了在多代理和对抗环境中使用合同的方法。

在线随机优化仍然是在线广告系统的重要组成部分，可应用于最佳出价和预算计划。基于我们对在线分配的长期研究，我们最近发表了一篇关于 双镜下降 的博客，这是一种用于在线分配问题的新 算法，它简单、稳健且灵活。这种最先进的算法对广泛的对抗性和随机输入分布具有鲁棒性，并且可以优化经济效率以外的重要目标，例如公平性。我们还表明，通过为日益流行的 支出回报率 的特殊结构定制双镜下降约束，我们可以优化广告商价值。双镜下降法具有广泛的应用，随着时间的推移，它被用于帮助广告商通过更好的算法决策获得更多价值。

此外，根据我们最近在 ML、机制设计和市场相互作用方面的工作，我们研究了 非对称拍卖设计的转换器，为 无悔学习买家 设计了效用最大化策略，并开发了新的 学习算法 来在拍卖中出价或 定价。

任何复杂的在线服务都必须通过实验来衡量用户和其他参与者对新干预措施的反应，而估计这些因果效应的精确度量则面临着一个主要挑战，即如何处理控制和处理单元之间的复杂相互作用或干扰。在此领域中，我们结合了图形聚类和因果推理专业知识，以改进我们 之前的工作成果，尤其是在灵活的响应模型和新的实验设计下，能够处理分配和度量测量发生在双边平台的同一侧。此外，我们还展示了如何结合 综合控制和优化技术，设计更强大的实验，特别是在小数据范围内。

算法基础与理论

最后，我们在基础算法研究领域继续攻克长期悬而未决的问题。其中一篇简明的 论文 出人意料地解决了一个历经四十年的未决问题，即是否存在一种机制可以保证每当买方的价值微弱超过卖方的成本时 可获得的贸易收益 的比例恒定。另一篇最近的论文则获得了经典且广泛研究的 k-means 问题 的最先进近似解。此外，我们还改进了 相关聚类 的最佳近似算法，打破了 2 的障碍近似因子。最后，我们在动态数据结构上的工作解决了最小成本和其他网络流问题，这有助于在采用连续优化技术解决经典离散优化问题方面取得突破性进展。

结语

设计有效的算法和机制是许多谷歌系统中不可或缺的组成部分，这些系统需要在处理万亿级数据时始终考虑隐私和安全。我们的方法是开发具有坚实理论基础的算法，这些算法可以被高效地部署在我们的产品系统中。此外，我们通过开源一些最新的开发成果，并发布其中背后的高级算法，将其中的许多进步带给更广泛的社区。在这篇文章中，我们介绍了隐私、市场算法、可扩展算法、基于图的学习和优化等方面的算法进步的子集。随着我们朝着更加自动化的 AI-first Google 迈进，开发强大、可扩展且隐私安全的机器学习算法仍然是重中之重。

致谢

这篇文章总结了大量团队的研究，并受益于多位研究人员的意见，包括 Gagan Aggarwal、Amr Ahmed、David Applegate、Santiago Balseiro、Vincent Cohen-addad、Yuan Deng、Alessandro Epasto、Matthew Fahrbach、Badih Ghazi、Sreenivas Gollapudi、 Rajesh Jayaram、Ravi Kumar、Sanjiv Kumar、Silvio Lattanzi、Kuba Lacki、Brendan McMahan、Aranyak Mehta、Bryan Perozzi、Daniel Ramage、Ananda Theertha Suresh、Andreas Terzis、Sergei Vassilvitskii、Di Wang 和 Song Zuo。特别感谢 Ravi Kumar 对这篇文章的贡献。