Scaling hierarchical agglomerative clustering to trillion-edge graphs

In large-scale prediction and information retrieval tasks, we frequently encounter various applications of clustering, a type of unsupervised machine learning that aims to group similar items together. Examples include de-duplication, anomaly detection, privacy, entity matching, compression, and many more (see more examples in our posts on balanced partitioning and hierarchical clustering at scale, scalability and quality in text clustering, and practical differentially private clustering).

A major challenge is clustering extremely large datasets containing hundreds of billions of datapoints. While multiple high-quality clustering algorithms exist, many of them are not easy to run at scale, often due to their high computational costs or not being designed for parallel multicore or distributed environments. The Graph Mining team within Google Research has been working for many years to develop highly scalable clustering algorithms that deliver high quality.

Ten years ago, our colleagues developed a scalable, high-quality algorithm, called affinity clustering, using the simple idea that each datapoint should be in the same cluster as the datapoint it’s most similar to. One can imagine this process as drawing an edge from each point to its nearest neighbor and contracting the connected components. This simple approach was amenable to a scalable MapReduce implementation. However, the guiding principle for the algorithm was not always correct as similarity is not a transitive relation, and the algorithm can erroneously merge clusters due to chaining, i.e., merging long paths of pairwise related concepts to place two unrelated concepts in the same cluster, as illustrated below.

Both affinity clustering and SCC are inspired by the popular hierarchical agglomerative clustering (HAC) algorithm, a greedy clustering algorithm that is well known to deliver very good clustering quality. The HAC algorithm greedily merges the two closest clusters into a new cluster, proceeding until the desired level of dissimilarity between all pairs of remaining clusters is achieved. HAC can be configured using a linkage function that computes the similarity between two clusters; for example, the popular average-linkage measure computes the similarity of (A, B) as the average similarity between the two sets of points. Average-linkage is a good choice of linkage function as it takes into account the sizes of the clusters that are being merged. However, because HAC performs merges greedily, there is no obvious way to parallelize the algorithm. Moreover, the best previous implementations had quadratic complexity, that is the number of operations they performed was proportional to n², where n is the number of input data points. As a result, HAC could only be applied to moderately sized datasets.

The final frontier is to obtain scalable and high-quality HAC algorithms when a graph is so large that it no longer fits within the memory of a single machine. In our most recent paper, we designed a new algorithm, called TeraHAC, that scales approximate HAC to trillion-edge graphs. TeraHAC is based on a new approach to computing approximate HAC that is a natural fit for MapReduce-style algorithms. The algorithm proceeds in rounds. In each round, it partitions the graph into subgraphs and then runs on each subgraph independently to make merges. The tricky question is what merges is the algorithm allowed to make?

The main idea behind TeraHAC is to identify a way to perform merges based solely on information local to the subgraphs, while guaranteeing that the merges can be reordered into an approximate merge sequence. The paradox rests in the fact that a cluster in some subgraph may make a merge that is far from being approximate. However, the merges satisfy a certain condition, which allows us to show that the final result of the algorithm is still the same as what a proper (1+ε)-approximate HAC algorithm would have computed.

TeraHAC uses at most a few dozen rounds on all of the graphs used for evaluation, including the largest inputs; our round-complexity is over 100× lower than the best previous approaches to distributed HAC. Our implementation of TeraHAC can compute a high-quality approximate HAC solution on a graph with several trillion edges in under a day using a modest amount of cluster resources (800 hyper-threads over 100 machines). The quality results on this extremely large dataset are shown in the figure below; we see that TeraHAC achieves the best precision-recall tradeoff compared to other scalable clustering algorithms, and is likely the algorithm of choice for very large-scale graph clustering.

We demonstrate that despite being a classic method, HAC still has many more secrets to reveal. Interesting directions for future work include designing good dynamic algorithms for HAC (some recent work by our colleagues show promising results in this direction) and understanding the complexity of HAC in low-dimensional metric spaces. Aside from theory, we are hopeful that our team’s approach to scalable and sparse algorithms for hierarchical clustering finds wider use in practice.

This blog post reports joint work with our colleagues including MohammadHossein Bateni, David Eisenstat, Rajesh Jayaram, Jason Lee, Vahab Mirrokni and a former intern, Jessica Shi. We also thank our academic collaborators Kishen N Gowda and D Ellis Hershkowitz. Lastly, we thank Tom Small for his valuable help with making the animation in this blog post.