acceptodds
Under review as a conference paper at ICLR 2027

Fully Dynamic Hierarchical Clustering for Well-Clustered Graphs

Abstract

*Hierarchical Clustering* (HC) is a fundamental problem in data science. Its objective is to compute a hierarchical partition of the input data while minimizing the cost function (Dasgupta, STOC 2016). We study the HC problem on well-clustered graphs, which admit a partition into clusters with high inner conductance . We show that such a -decomposition always exists for every connected graph, and that our assumption can be naturally derived from other notions of clusterability in the literature. We prove that a simple bucketing-and-concatenation procedure achieves an -approximation for this problem, which becomes an -approximation for constant values of and , with linear running time. Our result requires strictly weaker assumptions, and achieves a substantially better approximation ratio in less time than the previous state-of-the-art method (Laenen et al., ICML 2023). Due to its simplicity, our algorithm is directly applicable in the fully dynamic setting and, with an update time of , achieves the same approximation guarantee in the static setting. The excellent performance of our algorithm is demonstrated by the experiments on both synthetic and real-world graphs.

Primary area:
unsupervised, self-supervised, semi-supervised, and supervised representation learning
Keywords:
Hierarchical Clustering, Fully Dynamic Algorithms, Graph Clustering, Approximate Algorithms, Well-Clustered Graphs

Reviews

Among:
Shape:
1234this paper, Top 49%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.33 over 3 reviews, above 51% of the others.
Reviewer_gBVZOpenReview ↗
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

1 comment
AuthorsOpenReview ↗

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\phi_{in} (static graphs) below. Since computing the exact ϕin\phi_{in} is NP-hard, we report λk\lambda_k of each graph. A lower bound on ϕin\phi_{in} can be estimated by Proposition 1 of our paper, i.e., ϕin=Ω(λk/k2)\phi_{in} = \Omega(\lambda_k/k^2). Therefore, we believe that λk\lambda_k and ϕin\phi_{in} are large enough for our algorithm to obtain a good approximation.

Datasetnnkkλk\lambda_k
SBM, q=0.10q = 0.1010001000550.82540.8254
SBM, q=0.15q = 0.1510001000550.85490.8549
SBM, q=0.20q = 0.2010001000550.87490.8749
SBM, q=0.25q = 0.2510001000550.88910.8891
WINE178178550.03630.0363
CANCER569569550.06030.0603
MNIST1000100010100.16910.1691
CIFAR101000100010100.34770.3477

[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)O(k^{22}) approximation, and Laenen et al. (2023) use WRSC (a cut-based HC algorithm) to achieve an O(k23)O(k^{23}) approximation. For the most general case (without clusterability), Charikar & Chatziafratis (2017) use sparsest cut to achieve an O(log⁡n)O(\sqrt{\log n}) 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 kk 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.

Reviewer_US8cOpenReview ↗
Rating
2
Confidence
4
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies hierarchical clustering (HC) under the Dasgupta (2016) cost on well-clustered graphs, with two contributions.

  1. A simpler static algorithm (BCA). Vertices are bucketed by powers of two of their (global weighted) degree, an arbitrary HC tree is built inside each bucket, and the buckets are chained into a caterpillar ordered by degree. No spectral decomposition, no parameter kk, no distance matrix is needed. Theorem 1 gives a linear-time O(k/ϕin)O(k/\phi_{in})-approximation, which is O(1)O(1) when kk and ϕin\phi_{in} are both constant.

  2. A fully dynamic extension of BCA (DynBCA). Because the tree is fully determined by vertex degrees, it suffices to maintain each vertex's degree and the bucket-to-caterpillar structure. Theorem 2 states an O(k′/ϕin)O(k'/\phi_{in})-approximation at every time step with O(1)O(1) worst-case update time, assuming every queried graph satisfies the well-clustered condition.

Experiments compare BCA against SpecWRSC, AverageLink, and Linkage++ on SBM and four real datasets (WINE, CANCER, MNIST, CIFAR10), and DynBCA against GRINCH and DynHAC on insertion/deletion streams. Codes for all methods are provided.

Critical strengths
  1. The core idea is genuinely simple and the guarantee is clean. Degree-bucketing + arbitrary intra-bucket trees + a caterpillar is about the simplest construction one could propose, but the proof establishes a O(k/ϕin)O(k/\phi_{in}) bound that becomes O(1)O(1) under constant parameters.

  2. The assumptions are weaker and more robust assumptions than prior work. The analysis does not require λkλ_k to be small (used by Laenen et al. (2023) and Manghiuc & Sun (2021)) and only needs the existence of a good decomposition rather than computing one. Proposition 1 (via a strengthened existential result over the ϕin\phi_{in} notion, rather than the induced-subgraph conductance of Oveis Gharan & Trevisan) gives a principled bridge to other clusterability notions.

  3. The fully dynamic result is a genuine new point. Prior dynamic HC methods either optimize other objectives or are heuristic. Providing the first fully-dynamic HC with a provable guarantee w.r.t. the Dasgupta cost and O(1)O(1) worst-case update time is a clear contribution that follows naturally from the simplicity of BCA.

Critical weaknesses
  1. The degree-only design is counter-intuitive, and its speed is won at the cost of accuracy. BCA clusters purely by degree, disregarding which vertices are actually connected by edges. This design is highly counter-intuitive, and the experimental comparisons of BCA against the linkage baselines in Figure 2 and Table 1 bear out this point, entirely as one would expect. It is likewise unsurprising that such a purely degree-based algorithm, which does not even consider the graph structure, beats the other baselines in running time, since that speed comes at a serious sacrifice of clustering accuracy. In my view, this substantially limits BCA's practical usefulness.

  2. The dynamic guarantee rests on a strong, unverified assumption. Theorem 2 requires the graph at every query time to satisfy the well-clustered condition with k′k' clusters. In the experiments the streams are built so clusters persist, but k′k' and ϕin\phi_{in} are never measured along the stream. If these parameters drift (a cluster splits or merges), the O(k′/ϕin)O(k'/\phi_{in}) guarantee becomes vacuous at some times. Reporting the realized k′/ϕink'/\phi_{in} over the tested streams would substantially strengthen the dynamic claim.

  3. GRINCH and DynHAC take feature vectors per point, whereas DynBCA operates directly on the graph. Scoring all on the induced-graph Dasgupta cost is a reasonable common metric, but the comparison is against methods not designed for the Dasgupta objective. So it seems that the dynamic baselines solve a different problem, and the "competitive cost" result should be stated with that caveat.

Questions for authors
  1. What is the substantive value of a degree-only (static or dynamic) clustering algorithm? Please refer to Weakness 1, which is the major concern that materially affects my assessment.

  2. How accurately does the returned tree recover the planted clusters in the SBM experiments? The evaluation reports only the Dasgupta cost and running time, not the cluster-reconstruction accuracy.

  3. Along the insertion/deletion streams, what are the realized values of k′k' and ϕin\phi_{in} at the query times? Is the well-clustered assumption actually satisfied at every step of the tested streams?

  4. Why do the authors say O(k3)O(k^3)-approximation in Line 210, while the guarantee is O(k/ϕin)O(k/\phi_{in}) in Theorem 1?

5 comments
AuthorsOpenReview ↗

Response to Reviewer US8c

We thank the reviewer for the careful reading and the detailed questions.

W1/Q1: What is the value of a degree-only algorithm?

First, we provide a better guarantee with a much simpler proof. Manghiuc & Sun (2021) and Laenen et al. (2023) use a stronger assumption (Line 207), only guarantee an O(k22)O(k^{22}) approximation, and need more than 30 pages of proof. Our O(k)O(k) guarantee is clearly better, our algorithm is simpler and faster and works in the dynamic setting, and the main text contains almost the full proof.

Second, perhaps counter-intuitively, avoiding kk-clustering benefits the approximation, because kk-clustering itself may introduce a larger error. Prior works proved that degree buckets achieve a constant approximation on high-conductance expanders, so they split the graph into kk high-conductance parts, build the degree-based tree inside each part, and concatenate the parts. However, even on well-clustered graphs, no known algorithm finds kk parts of high inner conductance with good guarantees; expander decomposition and spectral clustering cost those works an O(k22)O(k^{22}) or worse factor. Our key point is that the splitting step can be skipped: bucketing by global degree introduces only an O(k)O(k) factor from the merging step (Line 259). The result is a strictly weaker assumption, a better ratio, and linear time.

Third, since the tree depends only on degrees, it can be maintained in O(1)O(1) time per update. To our knowledge, this is the first fully dynamic HC algorithm with a provable guarantee for Dasgupta's cost. Prior works rely on a kk-way decomposition with no fast dynamic version, so they must rerun the whole algorithm whenever the graph changes.

Last, our algorithm is a general framework that can be combined with other algorithms: inside each bucket, any tree achieves a constant approximation, so a linkage-based algorithm can be used there to improve empirical results while keeping the guarantee. In the new Appendix D.5 (Figure 13), BCA+AverageLink performs similarly to AverageLink while maintaining our theoretical guarantee.

Q2: Cluster recovery.

Our goal is to construct a hierarchy rather than a flat clustering, and Dasgupta's cost is one of the most popular metrics for hierarchies. A flat clustering often cannot fit the real graph structure: Manghiuc & Sun (2021, page 7, Figure 1) show that if a flat cluster contains a dense region, a constant-factor approximate HC solution cannot recover the flat clustering.

Nevertheless, we extract the kk-partition of each hierarchy closest to the ground truth and report its ARI on SBM (BCA runs AverageLink inside each bucket, the same setting with Appendix D.5):

qqBCASpecWRSCAverageLinkLinkage++Spectral Clustering
0.0050.9911.0000.9911.0001.000
0.010.9791.0000.9791.0001.000
0.020.7051.0000.9591.0001.000
0.030.5571.0000.9331.0001.000
0.040.7161.0000.9071.0001.000
0.050.8201.0000.8201.0001.000
0.0750.4651.0000.5971.0001.000

SC is spectral clustering, which is designed for flat kk-clustering, while HC is not. Since SpecWRSC is based on spectral clustering, both achieve the best ARI here.

W2/Q3: Realized k′k' and ϕin\phi_{in} along the streams.

k′k' is very stable, since each dataset has kk ground-truth clusters, which upper-bounds k′k'. Computing ϕin\phi_{in} exactly is NP-hard, so we report λk\lambda_k along the streams; by Proposition 1, ϕin=Ω(λk/k2)\phi_{in} = \Omega(\lambda_k/k^2). We believe these values are large enough for a good approximation.

Datasetnnkkλk\lambda_k
SBM, q=0.10q=0.10500–100050.7596–0.8268
SBM, q=0.15q=0.15500–100050.7981–0.8554
SBM, q=0.20q=0.20500–100050.8243–0.8759
SBM, q=0.25q=0.25500–100050.8453–0.8897
WINE89–17850.0171–0.1438
CANCER284–56950.0381–0.0811
MNIST500–1000100.1144–0.1747
CIFAR10500–1000100.2744–0.3634

Q4: O(k3)O(k^3) vs. O(k/ϕin)O(k/\phi_{in}).

Lines 207–210 compare our result with Laenen et al. (2023), who assume a lower bound on λk+1\lambda_{k+1} rather than on ϕin\phi_{in}. Using ϕin≥λk+1/(80k2)\phi_{in} \ge \lambda_{k+1}/(80k^2) (Line 193), our O(k/ϕin)O(k/\phi_{in}) becomes O(k3/λk+1)O(k^3/\lambda_{k+1}), compared with their O(k23/λk+1)O(k^{23}/\lambda_{k+1}); with λk+1=Ω(1)\lambda_{k+1}=\Omega(1), these are O(k3)O(k^3) and O(k23)O(k^{23}). We will make this conversion explicit in the text.

Thank the authors for their response and supplementary experiments. I acknowledge that, from the standpoint of approximation algorithms, the paper has some theoretical merit. However, my concern is not how good an approximation ratio a degree-only algorithm can attain; it is that, even with a strong approximation ratio, the resulting clustering fails to match our intuitive notion of a meaningful clustering. The cluster-recovery experiments added by the authors bear this out: on the communities planted in the SBM, BCA does not achieve a strong ARI. The SBM is still a random graph model with relatively homogeneous degree distributions. If the degree distribution within each cluster were skewed (for instance, following a power law), I would expect BCA to perform even worse. The latter, however, is the more realistic scenario for real-world networks.

The authors remark that "Manghiuc & Sun (2021, page 7, Figure 1) show that if a flat cluster contains a dense region, a constant-factor approximate HC solution cannot recover the flat clustering." This claim is itself counter-intuitive: why should a hierarchically refined HC discard the intuitively meaningful communities? Why can these communities not be preserved among the internal clusters of the HC tree? This may well be a limitation inherent to the Dasgupta cost itself. Nevertheless, as a clustering algorithm intended for the machine-learning setting, its practical usefulness should remain a central consideration.

For the reasons above, I maintain my previous score. I thank the authors once again for their response and supplementary experiments.

We thank the reviewer for the further discussion and detailed explanation. We agree with the reviewer’s point about the difference between Dasgupta optimization and flat clustering: flat clustering focuses on cluster recovery, while Dasgupta focuses more on the structure of the data, reflecting the density of and connections between vertices, which is why degree-based algorithms make sense for optimization, especially for the Dasgupta objective. This is an interesting question exploring the connection and differences between these two objectives. Finally, we want to emphasize our major contribution: a framework with a better theoretical approximation ratio, which can also be combined with other practical methods.

Reviewer_3jsZOpenReview ↗
Rating
3
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

This paper studies static and dynamic algorithms for hierarchical clustering on graphs. In the static setting, this paper presents a simple linear-time algorithm that constructs an O(k/\phi_in)-approximate hierarchical clustering tree. For dynamic graphs undergoing edge insertions and deletions, it provides an algorithm that maintains the same approximation guarantee with O(1) update time. The paper improves upon previous algorithms in both running time and approximation guarantees, simplifies the existing algorithmic framework, and demonstrates empirical improvements.

Critical strengths

1.The paper provides a linear-time O(k/\phi_in)-approximation algorithm under weaker conditions than previous spectral-clustering-based approaches, improving both efficiency and approximation guarantees. 2.The algorithms are simple and practically effective and simplifies the previous framework.

Critical weaknesses
  1. The synthetic experiments focus on dense SBM graphs with equal-sized clusters and a fixed number of clusters. Additional experiments with stronger cluster separation, imbalanced cluster sizes, and heterogeneous degree distributions would better demonstrate the algorithm’s practical scope.
  2. The dynamic experiments only evaluate consecutive vertex insertions or consecutive vertex deletions. They do not evaluate mixed edge-insertion/deletion streams.
Questions for authors

see weaknesses

1 comment
AuthorsOpenReview ↗

Rebuttal to Reviewer 3jsZ

We thank the reviewer for the careful reading and the detailed questions.

W1: "The synthetic experiments focus on ... Additional experiments with stronger cluster separation, imbalanced cluster sizes, and heterogeneous degree distributions would better demonstrate the algorithm's practical scope."

We have added experiments in a more separated, imbalanced, and degree-heterogeneous setting. We use n=1500n=1500 and p=0.15p=0.15, and set q=0.03q = 0.03 and q=0.1q = 0.1 (q≪pq \ll p ensures well-separation). We give each cluster a different size, with the largest cluster 88 times as large as the smallest, and vertex degrees vary across clusters. The following table reports the ratio of each method's Dasgupta cost to that of SpecWRSC in different settings (mean of 3 seeds; all baselines receive the true kk).

settingBCAAverageLinkLinkage++
k=3k=3, q=0.03q=0.031.051.031.04
k=3k=3, q=0.1q=0.11.071.011.03
k=4k=4, q=0.03q=0.031.161.041.04
k=4k=4, q=0.1q=0.11.091.031.09
k=5k=5, q=0.03q=0.031.451.061.03
k=5k=5, q=0.1q=0.11.081.021.08

BCA builds every tree in 0.01–0.02 s, 30–100× faster than SpecWRSC (0.6–1.6 s) and AverageLink (0.3–1.3 s).

W2: "The dynamic experiments only evaluate consecutive vertex insertions or consecutive vertex deletions. They do not evaluate mixed edge-insertion/deletion streams."

We have added experiments comparing our algorithm with the baselines on mixed insertion/deletion streams in Appendix D.4 of our revised paper; the newly added part is in blue. The results on mixed streams are very similar to those on vertex insertion/deletion streams. This is as expected, since our algorithm handles vertex and edge streams in the same way.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.