Sublinear Algorithms for Hierarchical Clustering
Sublinear Algorithms for Hierarchical Clustering
复制标题
DOI：
10.48550/arxiv.2206.07633
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Arpit Agarwal;S. Khanna;Huan Li;Prathamesh Patil
中科院分区：
文献类型：
--
作者：
Arpit Agarwal;S. Khanna;Huan Li;Prathamesh Patil
图上的层次聚类是数据挖掘和机器学习中的一项基本任务，在遗传学、社会网络分析和信息检索等领域都有应用。具体来说，我们认为最近流行的目标函数的层次聚类由于Dasgupta。以前的算法（近似）最小化这个目标函数需要线性的时间/空间复杂度。在许多应用中，底层图的大小可能是巨大的，使得即使使用线性时间/空间算法来处理图也在计算上具有挑战性。因此，人们对设计仅使用次线性资源就可以执行全局计算的算法有着浓厚的兴趣。这项工作的重点是研究在三个研究得很好的次线性计算模型下的海量图的层次聚类，这些模型分别关注空间、时间和通信，作为优化的主要资源：（1）（动态）流模型，其中边被呈现为流，（2）查询模型，其中使用邻居和度查询来查询图，（3）MPC模型，其中图边缘在经由通信信道连接的若干机器上被划分。在上述三个模型中，我们设计了层次聚类的次线性算法。在我们的算法结果的核心是一个视图的目标在图中的削减，这使我们能够使用一个轻松的概念削减稀疏做层次聚类，同时只引入一个小的失真的目标函数。我们的主要算法的贡献，然后显示如何削减所需形式的稀疏可以有效地构建在查询模型和MPC模型。我们通过建立几乎匹配的下限来补充我们的算法结果，这些下限排除了在每个模型中设计更好算法的可能性。
Hierarchical clustering over graphs is a fundamental task in data mining and machine learning with applications in domains such as phylogenetics, social network analysis, and information retrieval. Specifically, we consider the recently popularized objective function for hierarchical clustering due to Dasgupta. Previous algorithms for (approximately) minimizing this objective function require linear time/space complexity. In many applications the underlying graph can be massive in size making it computationally challenging to process the graph even using a linear time/space algorithm. As a result, there is a strong interest in designing algorithms that can perform global computation using only sublinear resources. The focus of this work is to study hierarchical clustering for massive graphs under three well-studied models of sublinear computation which focus on space, time, and communication, respectively, as the primary resources to optimize: (1) (dynamic) streaming model where edges are presented as a stream, (2) query model where the graph is queried using neighbor and degree queries, (3) MPC model where the graph edges are partitioned over several machines connected via a communication channel. We design sublinear algorithms for hierarchical clustering in all three models above. At the heart of our algorithmic results is a view of the objective in terms of cuts in the graph, which allows us to use a relaxed notion of cut sparsifiers to do hierarchical clustering while introducing only a small distortion in the objective function. Our main algorithmic contributions are then to show how cut sparsifiers of the desired form can be efficiently constructed in the query model and the MPC model. We complement our algorithmic results by establishing nearly matching lower bounds that rule out the possibility of designing better algorithms in each of these models.