Scalable Hierarchical Agglomerative Clustering

1 Introduction

• HAC takes O(N^2 log(N)) time, while online methods are sequential and randomized or distributed methods often trade scalability for accuracy.Affinity clustering improves computational efficiency but can over-merge clusters.Source: §1 · p. 2
• SCC is an accurate, scalable bottom-up hierarchical clustering algorithm designed for both hierarchical and flat clustering.The paper positions SCC as a response to scalability limitations in existing agglomerative methods.Source: §1 · p. 2
• SCC’s hierarchy contains the optimal flat partition under δ-separability and provides a constant-factor approximation to the DP-Means objective [11].The paper presents this as a novel use of hierarchical clustering for a non-parametric flat-clustering objective.Source: §1 · p. 3
• SCC generalizes HAC, recovering the same tree in the limit, while also addressing model-based separated data recoverable by HAC.These theoretical results connect SCC to established agglomerative clustering behavior.Source: §1 · p. 3
• SCC achieves state-of-the-art hierarchical and flat clustering results on public benchmarks and lower DP-Means costs than competing methods.The paper also evaluates cluster coherence on 30 billion user queries, where human evaluation favors SCC over Affinity clustering.Source: §1 · p. 3

2.1 Definitions

• A hierarchical clustering is a tree of nested partitions whose leaves are data points and whose internal nodes represent clusters.The tree encodes multiple tree-consistent flat partitions.Source: §2.1 · pp. 3–4
• Linkage functions measure dissimilarity between two point sets, supporting choices such as average or single linkage.The paper uses linkage functions to establish theoretical guarantees for SCC.Source: §2.1 · p. 4

2.2 Proposed Approach

• SCC starts with singleton clusters and repeatedly merges groups of previous-round clusters using increasing distance thresholds.Each round produces a flat partition, while the collection of rounds forms a hierarchical clustering with a non-parametric branching factor.Source: §2.2 · p. 5
• Two sub-clusters belong to the same component when connected by a path whose adjacent pairs satisfy nearest-neighbor conditions under threshold τ.Components can be viewed as connected components in a graph whose nodes are previous-round sub-clusters.Source: §2.2 · p. 5
• For each component, SCC unions its member sub-clusters to form the next partition and advances the threshold only when the previous round produced no merges.Any round can serve as a predicted flat clustering, and all rounds together define the hierarchy.Source: §2.2 · pp. 5–6
• SCC accepts a dataset, dissimilarity function, and increasing threshold sequence, and outputs one flat partition per round.The sub-cluster components in each round can be found efficiently using a connected-components algorithm.Source: §2.2 · p. 6

3.1 Recovering Target Clustering

• Under δ-separability with δ ≥ γ, one SCC round recovers the target flat clustering, with γ = 6 for all metrics and γ = 30 for ℓ2.Geometrically increasing thresholds ensure a round lies above the largest within-cluster distance and below the closest across-cluster distance.Source: §3.1 · p. 7
• Under model-based separation, some threshold sequence makes SCC’s hierarchy contain the target partition corresponding to graph connected components.The result assumes a symmetric injective linkage function and a target partition represented by connected components.Source: §3.1 · pp. 7–8

3.2 Relation to Nonparametric Clustering

• Under δ-separation, SCC’s hierarchy contains a 2-approximation to the DP-Means objective.The proof combines recovery of an optimal facility-location solution with a constant-factor comparison to DP-Means.Source: §3.2 · p. 8
• SCC provides the paper’s first stated connection between bottom-up hierarchical clustering and non-parametric objectives such as DP-Means, with empirical SOTA performance for DP-Means.DP-Means infers the number of clusters rather than fixing it in advance.Source: §3.2 · p. 8

3.3 Hierarchical Clustering Analysis

• With a symmetric, injective, reducible linkage function, an appropriate threshold sequence makes SCC produce exactly the same tree as HAC.Injectivity gives a unique merger order, while reducibility preserves the corresponding HAC decisions.Source: §3.3 · p. 9

3.4 Time Analysis

• SCC has worst-case running time O(N(T + S)) across rounds, and both nearest-neighbor construction and connected components are highly parallelizable.The worst case uses 2 ∗(N −1) rounds; sparse k-nearest-neighbor graphs can reduce nearest-neighbor computation to O(k) for several linkage functions.Source: §3.4 · pp. 9–10

4.1 Hierarchical Clustering

• SCC achieves the highest dendrogram purity on all benchmark datasets except CovType, while scaling to the 1.2M-image dataset without performance degradation.Affinity shows the same scaling behavior on the largest image dataset.Source: §4.1 · p. 12
• SCC remains much more efficient than HAC as dataset size grows while producing trees with comparable dendrogram purity.The experiments report quadratic time growth for HAC and substantially more constant runtime for SCC.Source: §4.1 · p. 12, Figure 4 · p. 13

4.2 Flat Clustering

• Geometric threshold progressions slightly outperform linear progressions, while SCC reaches high-quality results after only a few more rounds than Affinity.Performance saturates after a few hundred rounds.Source: §4.1 · p. 12, Figure 5 · p. 14
• SCC is the best-performing flat-clustering method on Speaker and ALOI, outperforms prior state-of-the-art results, and remains competitive with Affinity elsewhere.The comparison uses pairwise F1 and reports the best F1 achieved across rounds.Source: Table 2 · p. 13, §4.2 · p. 14

4.3 Approximation of DP-Means Objective

• Across λ values, SCC achieves the lowest DP-Means cost among the evaluated methods.The experiments compare SCC with SerialDPMeans and DPMeans++ across benchmark datasets and λ values.Source: Figure 2 · p. 12, §4.3 · pp. 14–15
• SCC’s best F1 is usually among the strongest results, although SerialDPMeans performs best on CovType and F1 is reported as uninformative there.The CovType maximum F1 of 0.536 occurs when all points form one cluster.Source: Figure 3 · p. 12, §4.3 · p. 15

• SCC and Affinity were evaluated on a random sample of 30 billion queries, making this one of the largest clustering evaluations reported.The evaluation was limited to these two methods because of the dataset’s massive size.Source: §5 · pp. 15–16
• Hashing accelerated query-distance computation for both methods, avoiding the O(N^2) pairwise dissimilarity bottleneck.Queries were represented with proprietary lexical and behavioral features, and manually extracted fine-grained flat clusterings were compared.Source: §5 · p. 16
• Only 2.7% of SCC clusters were labeled incoherent versus 6.0% for Affinity, while 65.7% of SCC clusters were labeled coherent versus 55.8% for Affinity.Human annotators rated approximately 1200 randomly sampled clusters on a scale from -1 to +1.Source: §5 · p. 16
• For queries containing Green Velvet, SCC produced a considerably more precise and on-topic cluster than Affinity.Additional examples were reported in Table 4.Source: §5 · p. 16, Table 3 · p. 17, Table 4 · p. 17
• SCC discovered meaningful hierarchical relationships at multiple granularities, including jazz subgenres such as bebop, modal jazz, and hard bop.The hierarchy also revealed meaningful relationships among topics such as tennis strategies.Source: §5 · p. 16

• Prior scalable methods use parallel or distributed computation, online or streaming tree construction, graph sparsification, or reduced distance computations.Examples include BIRCH, PERCH, GRINCH [45], approximate minimum spanning trees, and top-down subset clustering.Source: §6 · pp. 17–18
• Balcan et al. [5] also build bottom-up trees with round-specific merger thresholds and recover clusterings under more flexible separation conditions than SCC.Their linkage-function computation is more computationally expensive, and the paper reports an empirical comparison in Appendix §B.Source: §6 · p. 17
• Hierarchical variants of density-based methods, including HDBSCAN∗, correspond to specific linkage functions within a broader family of related approaches.The related literature also includes density- and spanning-tree-based methods [62].Source: §6 · pp. 17–18
• Hierarchical clustering research studies diverse objective functions, including integer linear programming formulations and Dasgupta’s cost function [18].Dasgupta’s objective has been studied in connection with agglomerative clustering [14].Source: §6 · p. 18

7 Conclusion

• SCC uses an agglomerative, round-based procedure with increasing distance thresholds to determine which sub-clusters merge.The method is designed for both hierarchical and flat clustering.Source: §7 · p. 18
• The paper reports proficiency over state-of-the-art clustering algorithms on benchmark datasets and analyzes SCC with respect to the DP-means objective.The conclusion describes both comprehensive empirical analysis and objective-based analysis.Source: §7 · p. 18
• SCC was run on an industrial dataset of 30 billion user queries, where human annotations indicated more coherent clusters than state-of-the-art methods.This demonstrates the method’s reported scalability and web-scale clustering quality.Source: §7 · p. 18

• The ℓ2 proof uses the ordinary triangle inequality rather than the relaxed triangle inequality used in the other case.Source: §A.1 · p. 23
• SCC begins with the shattered partition, assigning each data point to its own cluster.The initial partition is S(0) = {{x}|x ∈ X}.Source: §A.1 · p. 23
• The proof inductively maintains purity: every sub-cluster before the target round is contained in a single ground-truth cluster.The target round r⋆ satisfies S(r⋆) = S⋆.Source: §A.1 · p. 23
• For δ ≥ 30, a geometric threshold exists with 4R ≤ τr ≤ 8R that makes sub-clusters X and X′ form a component without an intervening Y.Because thresholds double geometrically, a threshold in this interval is reached.Source: §A.1 · pp. 23–24
• At the final use of τr, all sub-clusters within each ground-truth cluster merge while sub-clusters from different ground-truth clusters remain unmerged, yielding S(r⋆) = S⋆.The within-cluster separation condition ensures that each ground-truth cluster is formed by that round.Source: §A.1 · p. 24

• SCC can produce the same tree structure as HAC for a suitable sequence of thresholds, so it can recover model-based separated data.Source: §A.2 · p. 24

• Under δ-separation, SCC recovers the target partition and contains an optimal solution to the DP-Facility problem.The facility-opening cost is set to λ = (δ −2) · R.Source: §A.3 · pp. 24–26
• The proof uses a DP-Facility formulation with uniform facility-opening costs λ, squared Euclidean connection costs, and an associated linear-programming dual.The LP uses client-to-facility variables z_ij and facility-opening variables y_i.Source: §A.3 · p. 25
• A feasible dual whose cost matches the constructed clustering establishes optimality through LP duality.The proof invokes COST(α) ≤ OPT(DUAL) = OPT(PRIMAL) ≤ COST(C*) together with COST(α) = COST(C*).Source: §A.3 · pp. 25–26
• The DP-Facility solution supplied by SCC is within a factor of 2 of the optimal DP-Means objective.This follows by combining SCC’s optimal DP-Facility solution under δ-separation with the facility-location-to-DP-Means approximation proposition.Source: §A.3 · p. 26

• SCC produces lower costs than DPMeans++ and achieves higher F1 for particular λ values.Source: B Experiments · p. 27
• LowrankALBCD performs better on CovType, while on other datasets its tested λ values produce unreasonably few clusters despite similar performance in some cases.Source: B Experiments · p. 27
• Running-time comparisons report sparse-graph construction plus algorithm execution for SCC and Affinity, while Grinch and HDBSCAN did not finish on the largest dataset within 10 hours.Source: B Experiments · p. 27
• SCC achieves competitive dendrogram purity against RHC on Iris and Wine despite using a simpler linkage function.Source: B Experiments · p. 28, Table 6 · p. 28