Graphons, mergeons, and so on!
In this work we develop a theory of hierarchical clustering for graphs. Our modeling assumption is that graphs are sampled from a graphon, which is a powerful and general model for generating graphs and analyzing large networks. Graphons are a far richer class of graph models than stochastic blockmodels, the primary setting for recent progress in the statistical theory of graph clustering. We define what it means for an algorithm to produce the "correct" clustering, give sufficient conditions in which a method is statistically consistent, and provide an explicit algorithm satisfying these properties.
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).  The starting point is, necessarily, to specify some kind of underlying  distribution over graphs. The authors make a very general choice: the  underlying distribution is a "graphon". Briefly, this is a generative process over (infinite) graphs specified by a function W: [0,1]^2 --> [0,1]. To sample a graph with n nodes: -- Pick n values x1, .., xn at random from [0,1]. Here, xi is a latent feature associated with node i. -- Put an edge between nodes i and j with probability W(xi, xj). There has recently been quite a lot of interest in this generative process, motivated by the kinds of large graphs that are central to computational  social science.  The authors define a natural hierarchical clustering associated with a  graphon: this is the obvious one, whose clusters are obtained by picking a threshold t, considering points x and x' "connected" if W(x,x') > t, and then identifying clusters with the resulting connected components. One  technical complication is to state this definition in a way that is not derailed by sets of measure zero, and the authors do so by setting up an equivalence relation in which measurable sets are considered equivalent if their set difference has measure zero.  With the limit object thus defined, the authors proceed to develop a notion of consistency. One complication is the latent variables: in any given graph, the latent variables associated with nodes are not specified in advance; thus they need to be marginalized out. This is the one key difficulty of case (2) (see above) that does not arise in case (1).  The authors then use a notion of merge distortion (as in earlier work) to define consistency.  Finally, they give an algorithm for estimating the graphon cluster tree that is provably consistent. It is based on first estimating the edge probabilities and then applying single linkage. 
(See summary for main strengths of the paper)  There is some related work that the authors should reference carefully: the  paper of Steinwart on "Adaptive density level set clustering". Like the present  paper, Steinwart takes great pains to define connectedness in a way that is  resistant to sets of measure zero. Can the authors comment on how their approach  differs?  All in all, this is important, exciting, and novel work.