Scalable Hierarchical Clustering with Tree Grafting
  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.
