大规模平衡分区和层次聚类

lixia01

解决大规模优化问题通常从图分区开始，这意味着将图的顶点划分为集群，以便在不同的机器上进行处理。需要确保集群的大小几乎相等，这引发了平衡图分区问题。简而言之，我们需要将给定图的顶点划分为 k 个几乎相等的集群，同时尽量减少分区切割的边数。这个NP难题在实践中非常困难，因为小型实例的最佳近似算法依赖于半定规划，而这对于较大的实例来说是不切实际的。
这篇文章介绍了我们开发的更适用于大型实例的分布式算法。我们在WSDM 2016 论文中介绍了这种平衡图分区算法，并将这种方法应用于 Google 内部的多个应用程序。我们最近的NIPS 2017 论文通过理论和实证研究提供了该算法的更多细节。
通过线性嵌入实现平衡分区
我们的算法首先将图的顶点嵌入到一条线上，然后按照线性嵌入顺序以分布式方式处理顶点。我们研究了各种查找初始嵌入的方法，并应用四种不同的技术（例如局部交换和动态规划）来获得最终分区。最佳初始嵌入基于“亲和力聚类”。
亲和力层次聚类亲和力聚类是一种基于Borůvka 的经典最大成本生成树算法
的凝聚层次图聚类。如上所述，该算法是我们平衡分区工具的关键部分。该算法首先将每个顶点放置在它自己的聚类中：v0、v1，等等。然后，在每次迭代中，选择每个集群中成本最高的边，以产生更大的合并集群：第一轮选择A 0、 A 1、 A 2等，第二轮选择 B 0、 B 1等，依此类推。合并集自然会产生层次聚类，并产生叶顶点（度为 1 的顶点）的线性排序。下图演示了这一点，底部的数字对应于顶点的排序。
我们的NIPS'17 论文解释了我们如何在大规模并行计算 (MPC) 模型中高效运行亲和力聚类，特别是使用分布式哈希表 ( DHT ) 来显著减少运行时间。本文还对该算法进行了理论研究。我们报告了具有数十万亿条边的图的聚类结果，并且还观察到亲和力聚类在“聚类质量”方面经验上优于 k 均值等其他聚类算法。该视频包含结果摘要，并解释了与顺序单链接凝聚算法相比，这种并行算法如何可以产生更高质量的聚类。
与以前工作的比较
在将我们的算法与 (分布式) 平衡图分区中的以前工作进行比较时，我们重点关注FENNEL、Spinner、METIS和最近基于标签传播的算法。我们报告了几个公共社交网络以及一个大型私人地图图的结果。对于Twitter 关注者图，我们发现与之前的结果（ Ugander 和 Backstrom，2013）相比，结果持续提升了 15-25% ；对于 LiveJournal 图，除了 k = 2 之外，我们的算法在所有情况下都优于其他所有算法，而当 k = 2 时，我们的算法略差于 FENNEL 算法。
下表列出了通过不同算法在不同 k 值（聚类数）下获得的 Twitter 图中切边比例。括号中的数字表示大小不平衡因子：即最大和最小聚类大小的相对差异。此处的“Vanilla 亲和聚类”表示我们算法的第一阶段，其中仅构建层次聚类，并且不对切边执行进一步处理。请注意，这已经与之前最好的工作（显示在下面的前两列中）一样好，切边比例较小，同时实现完美（因此更好）的平衡（即 0% 的不平衡）。表中的最后一列包括我们的算法经过后处理的最终结果。
我们将平衡图分区应用于多个应用程序，包括Google 地图行车路线、网络搜索的服务后端以及为实验设计寻找治疗组。例如，在 Google 地图中，世界地图图形存储在多个分片中。跨多个分片的导航查询比在一个分片内处理的导航查询要昂贵得多。使用我们论文中描述的方法，我们可以通过将分片不平衡因子从 0% 增加到 10% 来减少 21% 的跨分片查询。正如我们论文中所讨论的，对实际流量进行的实时实验表明，与基线希尔伯特嵌入技术相比，我们的切割优化技术的多分片查询数量减少了 40% 。这反过来又降低了查询响应的 CPU 使用率。在未来的博客文章中，我们将讨论这项工作在网络搜索服务后端的应用，其中平衡分区帮助我们设计了一个缓存感知的负载平衡系统，大大降低了我们的缓存未命中率。
致谢
我们特别感谢 Vahab Mirrokni，他的指导和技术贡献对于开发这些算法和撰写本文起到了重要作用。我们还要感谢其他合著者和同事的贡献：Raimondas Kiveris、Soheil Behnezhad、Mahsa Derakhshan、MohammadTaghi Hajiaghayi、Silvio Lattanzi、Aaron Archer 以及NYC 算法和优化研究团队的其他成员。