Hierarchical Clustering in Graph Streams: Single-Pass Algorithms and Space Lower Bounds

Authors: Sepehr Assadi, Vaggos Chatziafratis, Jakub Łącki, Vahab Mirrokni, Chen Wang.
Conference: 35th Annual Conference on Learning Theory (COLT 2022)
Abstract: 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 [STOC’16].

Assuming that the input is an 𝑛-vertex weighted graph whose edges arrive in a stream, we derive the following results on space-vs-accuracy tradeoffs:

  • With O(n polylog n) space, we develop a single-pass algorithm, whose approximation ratio matches the currently best offline algorithm by Charikar and Chatziafratis [SODA’17].

  • When the space is more limited, namely, 𝑛^{1−𝑜(1)}, we prove that no algorithm can even estimate the value of the optimum hierarchical tree to within an 𝑜(log(𝑛)/loglog(𝑛)) factor, even when allowed polylog(n) passes over the input and exponential time.

  • In the most stringent setting of polylog(n) 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 𝑛^{1/2−𝑜(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 some constant factor, and thus can be used in place of the original (dense) graphs when solving HC. Our lower bound results involve establishing a new streaming lower bound for a novel problem “One-vs-Many-Expanders”, which can be of independent interest.
Conference version: [PMLR]
Full version: [arXiv]
BibTex: [DBLP]