- Rating
- 2
- Confidence
- 3
- Informativeness
- 2
- Presentation
- 3
- Soundness
- 3
Read review
Paper summary
This paper studies the hierarchical clustering (HC) problem, which aims to construct an optimal or near-optimal tree capturing the multiscale clustering of input points. The optimality here is measured by a cost function originally proposed in (Dasgupta, 2016) and the goal is to compute or approximate an optimal tree minimizes this cost. The computational problem is NP-hard (and hard to approximate as well under SSE-Hypothesis) in the general case, hence this paper considers the special case on the so-called "well-clustered" graphs. The authors develop a very simple bucketing-and-concatenation procedure and bound its approximation factor. Most interestingly, this strategy naturally aligns with the dynamic setting, and allows for constant update time per edge or (isolated-) vertex insertion/deletion event, while maintaining the approximate optimality of the resulting HC tree. Some experiments are provided: the main advantage of the new HC algorithm is its compelling running time.
Critical strengths
++ The new algorithm is very simple, essentially just bin the input vertices based on degrees. This makes it simple and efficient to handle the dynamic edge insertion / deletion. (The vertex insertion / deletion can be handled too, but only when that vertex is isolated.)
++ Better theoretical bounds despite a very simple algorithm.
Overall, I think the simplicity of the proposed algorithm both conceptually and in experiments is its most compelling strength.
Critical weaknesses
-- The HC tree is for the well-clustered graphs, where intuitively, the input graph admits a k-cluster partition. This is a very strong assumption: Models with such assumptions (including stochastic block models) are nice for theoretical studies but I am not sure how practical it is for real-world data. This is somewhat reflected in the experiments for real-world datasets, where simple average-linkage works much better.
-- Related to the above: by construction, the final HC tree has the shape of a "caterpillar" tree. This makes sense for the well-clustered graphs (which has a more flat clustering flavor). Is this suitable for practical data? Would the challenging practical data require more complex trees?
-- While the new algorithm is very efficient, especially in the dynamic setting, the empirical performance is not the best, especially for practical data. In fact, simple average-linkage algorithm appears to perform really well. (The average-link is much slower and perhaps it could be interesting to develop some variant that is much faster).
Minor comments:
- The theoretical bound essentially is dominated by the inner conductance of a k-partitioning. The internal hierarchal structure within this k-clusters does not seem to be leveraged. This I think is also why the constructed HC-tree can have that caterpillar shape. It might be interesting to develop an algorithm that can adapt more to the HC structure even within these good clusters.
Questions for authors
see Weakness
Response to Reviewer gBVZ
We thank the reviewer for the positive comments on the simplicity of the algorithm and on our bounds.
W1: The well-clustered assumption is strong.
Assumption 1 is weaker than it may appear. It asks only that some partition have high inner conductance. It places no condition on the outer conductance and no constraint on how the clusters connect to each other, unlike the SBM-type and spectral-gap conditions used in prior work (Manghiuc & Sun 2021; Laenen et al. 2023). Beyond these two papers, well-clusterability is a well-defined and commonly used assumption, e.g., in [1, 2, 3, 4, 5].
For the datasets used in our paper, we report ϕin (static graphs) below. Since computing the exact ϕin is NP-hard, we report λk of each graph. A lower bound on ϕin can be estimated by Proposition 1 of our paper, i.e., ϕin=Ω(λk/k2). Therefore, we believe that λk and ϕin are large enough for our algorithm to obtain a good approximation.
[1] Richard Peng, He Sun, and Luca Zanetti. Partitioning well-clustered graphs: Spectral clustering works! COLT 2015; SIAM J. Comput. 2017.
[2] Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. NeurIPS 2002.
[3] Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.
[4] Michael Kapralov, Akash Kumar, Silvio Lattanzi, Aida Mousavifar, and Weronika Wrzos-Kaminska. Approximating Dasgupta cost in sublinear time from a few random seeds. ICALP 2025.
[5] Ashish Chiplunkar, Michael Kapralov, Sanjeev Khanna, Aida Mousavifar, and Yuval Peres. Testing graph clusterability: Algorithms and lower bounds. FOCS 2018.
Q: "Related to the above: by construction, the final HC tree has the shape of a 'caterpillar' tree. This makes sense for well-clustered graphs (which have more of a flat-clustering flavor). Is this suitable for practical data? Would challenging practical data require more complex trees?"
In theory, we proved that the simple "caterpillar" tree provides a constant-factor approximation guarantee for Dasgupta's cost on well-clustered graphs, a condition that many real-world datasets satisfy. The shape of the final tree over the buckets directly affects the approximation ratio. Here, we list several possible tree shapes for more complex cases. Manghiuc & Sun (2021) use a variant of the caterpillar tree, which guarantees an O(k22) approximation, and Laenen et al. (2023) use WRSC (a cut-based HC algorithm) to achieve an O(k23) approximation. For the most general case (without clusterability), Charikar & Chatziafratis (2017) use sparsest cut to achieve an O(logn) approximation.
In practice, we acknowledge that many real-world datasets do not have a clearly well-clustered structure. However, Proposition 1 in our paper shows that any connected graph can be decomposed into k parts with some inner conductance; i.e., our framework applies to every graph, but the approximation ratio depends on how strong the clusterability is. Our experimental results show that our algorithm works well on most real-world datasets. Designing tree shapes other than the caterpillar to improve the HC approximation is an interesting question.
W2: "While the new algorithm is very efficient, especially in the dynamic setting, the empirical performance is not the best."
First, in Table 1, BCA beats SpecWRSC on 3 of the 4 datasets and is within 6–13% of AverageLink on MNIST and CIFAR10, while running about 20× faster (0.13 s vs. 2.71 s on MNIST). AverageLink provides no approximation guarantee for Dasgupta's cost and has no known fully dynamic version.
Second, as far as we know, the methods with the best empirical performance (AverageLink and Linkage++) have no approximation guarantee for Dasgupta's cost, whereas ours does. There is a simple way to close this gap between theory and practice. Our BCA algorithm is a general framework that can be combined with other algorithms to perform better in practice while maintaining the same theoretical guarantee. We have added Appendix D.5, in which we implement BCA+AverageLink and compare it with the other baselines (Figure 13). BCA+AverageLink achieves practical performance similar to AverageLink while maintaining the theoretical guarantee.