Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds
复制标题
DOI：
10.48550/arxiv.2206.07554
复制
发表时间：
2022-06
期刊：
影响因子：
--
通讯作者：
Sepehr Assadi;Vaggos Chatziafratis;Jakub Lacki;V. Mirrokni;Chen Wang
中科院分区：
文献类型：
--
作者：
Sepehr Assadi;Vaggos Chatziafratis;Jakub Lacki;V. Mirrokni;Chen Wang
层次聚类（HC）问题包括建立一个层次的聚类来表示给定的数据集。受现代大规模应用的启发，我们研究了流模型中的问题，在流模型中，内存受到严重限制，并且只允许一次或很少的输入通过。具体来说，我们研究是否可以得到一个好的层次聚类，或者至少我们是否可以近似估计最优层次的值。为了衡量层次结构的质量，我们使用Dasgupta Dasgupta（2016）引入的HC最小化目标。假设输入是一个n顶点加权图，其边到达流中，我们得出了空间与精度权衡的以下结果：•使用O（n·polylogn）空间，我们开发了一种单遍算法，其近似比率与当前最好的离线算法Charikar和Chatziafratis（2017）相匹配。•当空间更有限时，即n1−o(1)，我们证明了没有任何算法甚至可以在o（logn log logn）因子内估计最优层次树的值，即使允许polylogn通过输入和指数时间。•在文献中广泛研究的最严格的多项式空间设置中，我们排除了甚至可以区分“高度”与“差”可聚类图的算法，即在其HC目标值之间具有n1/2−o(1)个因子差距的图。•最后，我们证明了任何计算最优HC聚类的单次流算法都需要存储几乎整个输入，即使允许指数时间。我们的算法结果建立了一个一般的结构结果，证明了输入图的切割稀疏器可以将“平衡”层次树的成本保持在一个常数因子内，因此在求解HC时可以代替原始（密集）图。我们的下界结果包括一个新的流下界的新问题“一对多扩展”，这可以是独立的兴趣。
The Hierarchical Clustering (HC) problem consists of building a hierarchy of clusters to represent a given dataset. Motivated by the modern large-scale applications, we study the problem in the streaming model, in which the memory is heavily limited and only a single or very few passes over the input are allowed. Specifically, we investigate whether a good hierarchical clustering can be obtained, or at least whether we can approximately estimate the value of the optimal hierarchy. To measure the quality of a hierarchy, we use the HC minimization objective introduced by Dasgupta Dasgupta (2016). Assuming that the input is an n-vertex weighted graph whose edges arrive in a stream, we derive the following results on space-vs-accuracy tradeoffs: • With O(n · polylogn) space, we develop a single-pass algorithm, whose approximation ratio matches the currently best offline algorithm Charikar and Chatziafratis (2017). • When the space is more limited, namely, n1−o(1), we prove that no algorithm can even estimate the value of the optimum hierarchical tree to within an o( logn log logn ) factor, even when allowed polylogn passes over the input and exponential time. • In the most stringent setting of polylogn space, studied extensively in the literature, we rule out algorithms that can even distinguish between “highly”-vs-“poorly” clusterable graphs, namely, graphs that have an n1/2−o(1) factor gap between their HC objective value. • Finally, we prove that any single-pass streaming algorithm that computes an optimal HC clustering requires storing almost the entire input even if allowed exponential time. Our algorithmic results establish a general structural result that proves that cut sparsifiers of input graphs can preserve the cost of “balanced” hierarchical trees to within a constant factor, and thus can be used in place of the original (dense) graphs when solving HC. Our lower bound results include a new streaming lower bound for a novel problem “One-vs-Many-Expanders”, which can be of independent interest.