Reviews: Graphons, mergeons, and so on!

Hierarchical clustering is commonly applied to two types of objects: 1. sets of points 2. graphs (in which case it is usually called hierarchical graph partitioning) What can be said about the statistical properties of hierarchical clustering? In case (1), we can look at the underlying density from which the points are sampled, define a suitable (infinite) "cluster tree" for this density and then assert that a particular hierarchical clustering procedure returns finite trees that converge to this cluster tree in some suitable sense. Recent work by Eldridge et al has used a criterion called "merge distortion" to assess the discrepancy between the target (infinite) tree and the tree estimated from a finite sample. Specific algorithms have been found to be consistent in the sense of having the right limit, and their rates of convergence have been determined. The present paper is interested in extending this methodology to case (2).