PaperlayerView exact revision on arXiv

Source-linked AI summary

Scalable Hierarchical Clustering with Tree Grafting

Nicholas Monath, Ari Kobren, Akshay Krishnamurthy, Michael Glass, Andrew McCallum

arXiv:2001.00076v1cs.LGcs.DSstat.ML

TL;DR

General-linkage HAC requires O(n2 log n) computation, making it infeasible for datasets of even moderate size. Grinch incrementally builds a hierarchy using rotate and graft rearrangements and introduces model-based separation for arbitrary linkage functions. Grinch achieves perfect dendrogram purity (1.0) in the synthetic experiment, compared with 0.872 for Rotate and 0.854 for Online.

  • Problem

    General-linkage HAC requires O(n2 log n) computation, making it infeasible for datasets of even moderate size.

    Source: §1 · p. 1

  • Method

    Grinch incrementally builds a hierarchy using rotate and graft rearrangements and introduces model-based separation for arbitrary linkage functions.

    Source: §1 · p. 2

  • Results

    Grinch achieves perfect dendrogram purity (1.0) in the synthetic experiment, compared with 0.872 for Rotate and 0.854 for Online.

    Source: §4.1 · p. 9

  • Takeaways & Limitations

    Grinch provides a scalable hierarchical-clustering approach for complex cluster structures, with higher accuracy than scalable baselines and greater scalability than HAC.

    Source: §1 · p. 2, §6 · p. 15

    Rotate cannot reliably recover chain-structured connected components because local rotations cannot globally rearrange the hierarchy.

    Source: §3.1 · p. 5

Abstract

from arXiv · show

We introduce Grinch, a new algorithm for large-scale, non-greedy hierarchical clustering with general linkage functions that compute arbitrary similarity between two point sets. The key components of Grinch are its rotate and graft subroutines that efficiently reconfigure the hierarchy as new points arrive, supporting discovery of clusters with complex structure. Grinch is motivated by a new notion of separability for clustering with linkage functions: we prove that when the model is consistent with a ground-truth clustering, Grinch is guaranteed to produce a cluster tree containing the ground-truth, independent of data arrival order. Our empirical results on benchmark and author coreference datasets (with standard and learned linkage functions) show that Grinch is more accurate than other scalable methods, and orders of magnitude faster than hierarchical agglomerative clustering.

1 Introduction

HAC supports arbitrary linkage functions and broad applications, but its computational cost and greedy online variants limit scalability and robustness; Grinch addresses these issues with non-greedy tree rearrangements and theoretical guarantees.

Motivation

  • HAC supports diverse applications and cluster-level scoring functions, including learned functions needed for entity resolution.Its flexibility comes from evaluating similarities between sets of points rather than only individual pairs.Source: §1 · p. 1
  • O(n2 log n) computation makes general-linkage HAC infeasible on even moderately sized datasets.Online and mini-batch alternatives avoid some computation but make greedy, irreversible merges that depend on data arrival order.Source: §1 · pp. 1–2
  • Existing incremental methods can revisit earlier decisions but remain limited to local reconsideration and do not support arbitrary linkage functions.These limitations motivate a method that combines incremental processing with broader hierarchy rearrangements.Source: §1 · p. 2

Contributions

  • Grinch is an incremental hierarchical clustering algorithm supporting arbitrary linkage functions through rotate and graft operations.Rotate performs local child–aunt swaps, while graft can move and merge distant subtrees to discover complex cluster structures.Source: §1 · p. 2
  • Model-based separation yields a ground-truth tree-consistency guarantee, while experiments report higher accuracy and efficiency than baseline scalable methods.The evaluation includes average, centroid-cosine, and learned linkage functions on benchmark and author-coreference datasets.Source: §1 · p. 2

2 Linkage Functions for Clustering

This section defines set-wise linkage functions and model-based separation, then connects the resulting graph view to cluster trees and HAC’s correctness under separation.

2 Linkage Functions for Clustering

  • Linkage functions score two sets of points, capturing relationships that pairwise similarities cannot represent.They are functions f : 2X × 2X → R and support applications including image segmentation, document coreference, and entity resolution.Source: §2 · p. 2
  • The paper seeks an algorithm as flexible as HAC for arbitrary linkage functions but dramatically faster.This goal motivates replacing HAC’s O(n2 log n) general-linkage computation with scalable alternatives.Source: §2.1 · p. 3, §2 · p. 3

2.1 Model-based Separation

  • Model-based separation requires higher linkage scores when two sets form a connected subgraph than when they do not.The graph treats data points as vertices, connected components as ground-truth clusters, and f as the set-wise similarity function.Source: §2.1 · p. 3
  • Clique components recover strict separation, whereas chain components may contain nonadjacent points that are dissimilar despite separation.Adjacent chain segments remain similar, making chain structure challenging for local incremental algorithms.Source: §2.1 · p. 3
  • Figure 1 illustrates that separation guarantees connected-set comparisons without requiring every within-component pair to outrank every cross-component pair.In the chain example, f(s0, s1) can be below f(s1, s2), while f(s1, s2) remains below f(s2, s3).Source: Figure 1 · p. 4

2.2 Cluster Trees

  • A cluster tree compactly represents multiple valid clusterings through tree-consistent partitions whose disjoint subtrees cover the data.This representation supports later selection of a clustering and groups similar points hierarchically.Source: §2.2 · p. 4
  • If f separates G, HAC returns a cluster tree containing the graph’s connected components as a tree-consistent partition.At each step, connected-subgraph mergers receive higher scores than disconnected mergers, but general-linkage HAC still costs O(n2 log n).Source: §2.2 · p. 4

3 Rotations, Grafting and Grinch

Grinch incrementally builds hierarchical cluster trees with local rotations, non-local grafts, and restructuring to handle unfavorable arrival order and complex connected components. Under model-based separation, it recovers a tree containing the ground-truth clustering regardless of input order.

3.1 Online HAC and Rotations

  • Online HAC can permanently violate the ground-truth partition, while rotations correct local errors but cannot reliably recover chain-structured connected components.Rotations swap a node's sibling and aunt when the aunt scores higher, but their local scope limits provable recovery to clique-structured components.Source: §3.1 · p. 5

3.2 Subtree Grafting

  • Grafting searches for a similar leaf that prefers the target node over its current sibling, then recursively tests and merges the pair when the linkage condition succeeds.The procedure supports discovery of chain-structured connected components through non-local tree rearrangement.Source: §3.2 · p. 6

3.3 Tree Restructuring

  • Restructuring follows successful grafts by swapping nodes along ancestor paths so descendant subtrees remain connected and spurious grafts are resisted.Poorly structured trees can otherwise disconnect previously discovered ground-truth clusters after a graft.Source: §3.3 · pp. 6–7

3 Rotations, Grafting and Grinch

  • Grinch combines rotations, grafts, and restructuring while incrementally inserting each point into a cluster tree.Each new point joins its nearest-neighbor leaf, rotations correct local score violations, grafts are attempted from ancestors, and successful grafts trigger restructuring.Source: §3.4 · p. 7

3.4 Grinch

  • When the linkage function separates the graph and its components define the ground truth, Grinch recovers a tree-consistent ground-truth partition regardless of input order.The theorem applies the rotate, graft, and restruct routines to Grinch's incremental construction.Source: §3.4 · p. 7

4 Experiments

The experiments evaluate Grinch’s clustering quality, scalability, linkage flexibility, grafting behavior, and robustness to arrival order across synthetic, large-scale, author-coreference, and ALOI datasets.

4.1 Synthetic Data Experiment

  • 1.0 dendrogram purity: Grinch is perfect on the synthetic dataset, versus 0.872 for Rotate and 0.854 for Online.The competing incremental methods cannot globally rearrange the hierarchy.Source: §4.1 · p. 9

4.2 Approximations

  • Each of the first four approximations reduces computational cost without affecting dendrogram purity, while removing grafts lowers DP by 3% on ALOI and 12% on synthetic data.Removing rotate causes additional DP drops of 6% on ALOI and 2% on the synthetic dataset.Source: §4.2 · p. 10, Table 1 · p. 10

4.3 Large Scale Clustering

  • Across large-scale datasets, Grinch outperforms Rotate and Online under both linkage functions except on CovType, where methods perform similarly.Approximate-neighbor Grinch also surpasses Perch on ALOI, while HAC is best on Speaker but cannot scale to ALOI.Source: §4.3 · p. 11, Table 2 · p. 11

4.4 Author Coreference

  • On both author-coreference datasets, Grinch outperforms other scalable methods and even HAC on DBLP using learned linkage functions.The authors suggest Grinch’s approximation of HAC may regularize against overfitting in the learned linkage function.Source: §4.4 · p. 12, Table 3 · p. 12

4.5 Significance of Grafting

  • By 1000 inserted ALOI points, Grinch dominates Rotate, although individual grafts change dendrogram purity by only about 0.001.The cumulative graft-related change remains below 0.005 after 5000 points, versus a 0.03 final purity gap, suggesting small early rearrangements have long-term effects.Source: §4.5 · pp. 12–13, Figure 4 · p. 13

4.6 Robustness

  • On adversarial ALOI arrival orders, Grinch achieves higher DP than Perch and mini-batch HAC under Round-Robin ordering and remains competitive with mini-batch HAC under Sorted ordering.Mini-batch HAC performs poorly under Round-Robin ordering, whereas Sorted ordering is easier for it.Source: §4.6 · p. 14, Table 4 · p. 14

5 Related Work

Prior scalable clustering methods either optimize particular linkage functions or rely on sampling, while model-based separation generalizes perfect hierarchical structure to arbitrary set-level linkage functions.

Online and incremental clustering

  • Online and incremental methods are diverse, but each optimizes a specific linkage function, limiting their generality.Examples include complete-linkage-like rearrangements, k-center objectives, and k-means cost.Source: §5 · p. 14

Probabilistic alternatives

  • Split-merge MCMC escapes local minima through sampling, but accepted mergers or splits become rapidly less likely as the dataset grows.This contrasts with Grinch, which uses deterministic tree rearrangements rather than sampling.Source: §5 · pp. 14–15

Probabilistic hierarchical models

  • HAC remains central to probabilistic hierarchical models and learned entity-resolution systems, but its inefficiency motivates randomized fitting on data subsets.BHC fitting uses HAC directly, while randomized approaches still invoke HAC on small subsets.Source: §5 · p. 15

Theoretical relation

  • Model-based separation strictly generalizes perfect hierarchical clustering by allowing arbitrary similarities between point sets rather than only pairwise-derived linkage functions.Single-, average-, and complete-linkage settings are special cases of this broader formulation.Source: §5 · p. 15

6 Conclusion

The paper presents Grinch as an incremental hierarchical clustering algorithm that combines rotate and graft to handle complex structure regardless of arrival order. It proves perfect dendrogram purity under model-based separation and reports improved accuracy and scalability over baselines.

Conclusion

  • Grinch uses rotate and graft to discover complex cluster structure regardless of data arrival order.The algorithm is designed for hierarchical clustering under any linkage function.Source: §6 · p. 15
  • Under the separated setting, Grinch always returns a tree with perfect dendrogram purity.The guarantee is tied to the paper’s model-based separation condition.Source: §6 · p. 15
  • The empirical evaluation finds Grinch more accurate than baseline approaches and more scalable than hierarchical agglomerative clustering.The paper positions Grinch for large clustering problems with complicated relationships and learned linkage functions.Source: §6 · p. 15
  • Source code for Grinch is publicly available.The paper provides the repository URL for implementation access.Source: §6 · p. 15

A Proof of Theorem 1

The proof establishes that Grinch preserves strong connectivity and completeness as points arrive by combining rotations, grafting, and restructuring under a separating linkage model. These invariants imply that connected components remain a tree-consistent partition of the hierarchy.

Definitions and theorem strategy

  • Strong connectivity means every descendant of a connected node is connected, while completeness means a node’s leaves form an entire connected component.The theorem requires both properties to hold for the constructed tree.Source: A Proof of Theorem 1 · p. 19

Rotation Lemma

  • The Rotation Lemma shows that adding a point and applying rotations preserves all nodes that were previously strongly connected.Rotations alone do not guarantee completeness, so they are insufficient for the full theorem.Source: A Proof of Theorem 1 · p. 19

Rotation proof

  • When the new point connects to existing leaves, nearest-neighbor placement and separation preserve strong connectivity through rotations; when it does not, rotations move it out of affected subtrees.The proof handles the two cases according to whether the point has an edge to a leaf under its initial parent.Source: A Proof of Theorem 1 · p. 19

Grafting Lemmas

  • Grafting preserves strong connectivity and completeness when initiated from a maximal strongly connected or non-strongly-connected node.The argument excludes harmful merges with nonmaximal nodes and shows maximal-node grafts do not disconnect strongly connected subtrees.Source: A Proof of Theorem 1 · p. 20

Grafting Lemma 2

  • If a strongly connected node is a strict subset of a graph component, grafting returns a larger strongly connected node, recursively enlarging the leaf set toward that component.The constrained nearest-neighbor search identifies a leaf connected to the current subtree, and successful merges satisfy the displayed linkage comparison.Source: A Proof of Theorem 1 · p. 21

Restructuring Lemma

  • Restructuring converts a connected but non-strongly-connected ancestor into a strongly connected node through swaps with connected descendants.The swaps preserve the ancestor’s leaf set and terminate when the target ancestor becomes strongly connected.Source: A Proof of Theorem 1 · pp. 22–23

Theorem 1

  • Inductively, rotations, grafts, and restructuring restore both invariants after every point insertion, yielding a tree-consistent partition of the graph’s connected components.Successive grafts strictly enlarge strongly connected leaf sets until they become connected components.Source: A Proof of Theorem 1 · p. 23
Loading 2001.00076v1…