Affinity Clustering: Hierarchical Clustering at Scale
Graph clustering is a fundamental task in many data-mining and machine-learning pipelines. In particular, identifying a good hierarchical structure is at the same time a fundamental and challenging problem for several applications. The amount of data to analyze is increasing at an astonishing rate each day. Hence there is a need for new solutions to efficiently compute effective hierarchical clusterings on such huge data. The main focus of this paper is on minimum spanning tree (MST) based clusterings. In particular, we propose affinity, a novel hierarchical clustering based on Borůvka's MST algorithm. We prove certain theoretical guarantees for affinity (as well as some other classic algorithms) and show that in practice it is superior to several other state-of-the-art clustering algorithms. Furthermore, we present two MapReduce implementations for affinity. The first one works for the case where the input graph is dense and takes constant rounds. It is based on a Massively Parallel MST algorithm for dense graphs that improves upon the state-of-the-art algorithm of Lattanzi et al. [34]. Our second algorithm has no assumption on the density of the input graph and finds the affinity clustering in O(log n) rounds using Distributed Hash Tables (DHTs). We show experimentally that our algorithms are scalable for huge data sets, e.g., for graphs with trillions of edges.
The paper focuses on the development of the field of distributed hierarchical clustering. The authors propose a novel class of algorithms tagged 'affinity clustering' that operate on the basis of Boruvka's seminal work on minimal spanning trees and contrast those to linkage clustering algorithms (which are based on Kruskal's work). 
The authors systematically introduce the theoretical underpinnings of affinity clustering, before proposing 'certificates' as a metric to characterise clustering algorithm solutions more generally by assessing the clustered edge weights (cost). 
Following the theoretical analysis and operationalisation of MapReduce variants of affinity clustering for distributed operation, the quality is assessed empirically using standard datasets with variants of linkage- and affinity-based algorithms, as well as k-means. In addition to the Rand index (as metric for clustering accuracy) the quality of algorithms is assessed based on the ratio of the detected clusters (with balanced cluster sizes considered favourable). 
Affinity-based algorithms emerge favourably for nearly all datasets, with in parts significant improvements (with the flat clustering algorithm k-means as closest contestant).
Finally, the scalability of affinity clustering is assessed using private and public corpi, with near-linear scalability for the best performing case.
Overall, the paper proposes a wide range of concepts that extend the field of hierarchical clustering (affinity-based clustering, certificates as QA metric). As far as I could retrace, the contributions are systematically developed and analysed, which warrants visibility.
One (minor) comment includes the experimental evaluation. In cases where the affinity-based algorithms did not perform as well (an example is the cluster size ratio for the Digits dataset), it would have been great to elaborate (or even hypothesise) why this is the case. This would potentially give the reader a better understanding of the applicability of the algorithm and potential limitations.
Minor typos/omissions:
- Page 8, Table 1: "Numbered for ImageGraph are approximate."
- Page 8, Subsection Scalability: Missing reference for public graphs.