Statistical Inference for Cluster Trees

Introduction

Clustering is a central problem in the analysis and exploration of data. It is a broad topic, with several existing distinct formulations, objectives, and methods. Despite the extensive literature on the topic, a common aspect of the clustering methodologies that has hindered its widespread scientific adoption is the dearth of methods for statistical inference in the context of clustering. Methods for inference broadly allow us to quantify our uncertainty, to discern “true” clusters from finite-sample artifacts, as well as to rigorously test hypotheses related to the estimated cluster structure.

Methods for density clustering fall broadly in the space of hierarchical clustering algorithms, and inherit several of their advantages: they allow for extremely general cluster shapes and sizes, and in general do not require the pre-specification of the number of clusters. Furthermore, unlike flat clustering methods, hierarchical methods are able to provide a multi-resolution summary of the underlying density. The cluster tree, irrespective of the dimensionality of the input random variable, is displayed as a two-dimensional object and this makes it an ideal tool to visualize data. In the context of statistical inference, density clustering has another important advantage over other clustering methods: the object of inference, the cluster tree of the unknown density $p_{0}$, is clearly specified.

In practice, the cluster tree is estimated from a finite sample, $\{X_{1},\ldots,X_{n}\}\sim p_{0}$. In a scientific application, we are often most interested in reliably distinguishing topological features genuinely present in the cluster tree of the unknown $p_{0}$, from topological features that arise due to random fluctuations in the finite sample $\{X_{1},\ldots,X_{n}\}$. In this paper, we focus our inference on the cluster tree of the kernel density estimator, $T_{\widehat{p}_{h}}$, where $\widehat{p}_{h}$ is the kernel density estimator,

where $K$ is a kernel and $h$ is an appropriately chosen bandwidth We address computing the tree $T_{\widehat{p}_{h}}$, and the choice of bandwidth in more detail in what follows..

To develop methods for statistical inference on cluster trees, we construct a confidence set for $T_{p_{0}}$, i.e. a collection of trees that will include $T_{p_{0}}$ with some (pre-specified) probability. A confidence set can be converted to a hypothesis test, and a confidence set shows both statistical and scientific significances while a hypothesis test can only show statistical significances [23, p.155].

To construct and understand the confidence set, we need to solve a few technical and conceptual issues. The first issue is that we need a metric on trees, in order to quantify the collection of trees that are in some sense “close enough” to $T_{\widehat{p}_{h}}$ to be statistically indistinguishable from it. We use the bootstrap to construct tight data-driven confidence sets. However, only some metrics are sufficiently “regular” to be amenable to bootstrap inference, which guides our choice of a suitable metric on trees.

On the basis of a finite sample, the true density is indistinguishable from a density with additional infinitesimal perturbations. This leads to the second technical issue which is that our confidence set invariably contains infinitely complex trees. Inspired by the idea of one-sided inference , we propose a partial ordering on the set of all density trees to define simple trees. To find simple representative trees in the confidence set, we prune the empirical cluster tree by removing statistically insignificant features. These pruned trees are valid with statistical guarantees that are simpler than the empirical cluster tree in the proposed partial ordering.

Our contributions: We begin by considering a variety of metrics on trees, studying their properties and discussing their suitability for inference. We then propose a method of constructing confidence sets and for visualizing trees in this set. This distinguishes aspects of the estimated tree correspond to real features (those present in the cluster tree $T_{p_{0}}$) from noise features. Finally, we apply our methods to several simulations, and a Graft-versus-Host Disease (GvHD) data set to demonstrate the usefulness of our techniques and the role of statistical inference in clustering problems.

Related work: There is a vast literature on density trees (see for instance the book by Klemelä ), and we focus our review on works most closely aligned with our paper. The formal definition of the cluster tree, and notions of consistency in estimation of the cluster tree date back to the work of Hartigan . Hartigan studied the efficacy of single-linkage in estimating the cluster tree and showed that single-linkage is inconsistent when the input dimension $d>1$. Several fixes to single-linkage have since been proposed (see for instance ). The paper of Chaudhuri and Dasgupta provided the first rigorous minimax analysis of the density clustering and provided a computationally tractable, consistent estimator of the cluster tree. The papers propose various modifications and analyses of estimators for the cluster tree. While the question of estimation has been extensively addressed, to our knowledge our paper is the first concerning inference for the cluster tree.

There is a literature on inference for phylogenetic trees (see the papers ), but the object of inference and the hypothesized generative models are typically quite different. Finally, in our paper, we also consider various metrics on trees. There are several recent works, in the computational topology literature, that have considered different metrics on trees. The most relevant to our own work, are the papers that propose the functional distortion metric and the interleaving distance on trees. These metrics, however, are NP-hard to compute in general. In Section 3, we consider a variety of computationally tractable metrics and assess their suitability for inference.

Background and Definitions

As will be clearer in what follows, working only with cluster trees defined via a function $f$ simplifies our search for metrics on trees, allowing us to use metrics specified in terms of the function $f$. With a slight abuse of notation, we will use $T_{f}$ to denote also $\{T_{f}\}$, and write $C\in T_{f}$ to signify $C\in\{T_{f}\}$. The cluster tree $T_{f}$ indeed has a tree structure, since for every pair $C_{1},C_{2}\in T_{f}$, either $C_{1}\subset C_{2}$, $C_{2}\subset C_{1}$, or $C_{1}\cap C_{2}=\emptyset$ holds. See Figure 1 for a graphical illustration of a cluster tree. The formal definition of the tree requires some topological theory; these details are in Appendix B.

In the context of hierarchical clustering, we are often interested in the “height” at which two points or two clusters merge in the clustering. We introduce the merge height from [12, Definition 6]:

For any two points $x,y\in\mathcal{X}$, any $f:\mathcal{X}\mapsto[0,\infty)$, and its tree $T_{f}$, their merge height $m_{f}(x,y)$ is defined as the largest $\lambda$ such that $x$ and $y$ are in the same density cluster at level $\lambda$, i.e.

An asymptotic $(1-\alpha)$ confidence set, $C_{\alpha}$, is a collection of trees with the property that

We also provide non-asymptotic upper bounds on the $o(1)$ term in the above definition. Additionally, we provide methods to summarize the confidence set above. In order to summarize the confidence set, we define a partial ordering on trees.

For any $f,g:\mathcal{X}\mapsto[0,\infty)$ and their trees $T_{f}$, $T_{g}$, we say $T_{f}\preceq T_{g}$ if there exists a map $\Phi:\{T_{f}\}\rightarrow\{T_{g}\}$ such that for any $C_{1},C_{2}\in T_{f}$, we have $C_{1}\subset C_{2}$ if and only if $\Phi(C_{1})\subset\Phi(C_{2})$.

With Definition 3 and 4, we describe the confidence set succinctly via some of the simplest trees in the confidence set in Section 4. Intuitively, these are trees without statistically insignificant splits.

It is easy to check that the partial order $\preceq$ in Definition 4 is reflexive (i.e. $T_{f}\preceq T_{f}$) and transitive (i.e. that $T_{f_{1}}\preceq T_{f_{2}}$ and $T_{f_{2}}\preceq T_{f_{3}}$ implies $T_{f_{1}}\preceq T_{f_{3}}$). However, to argue that $\preceq$ is a partial order, we need to show the antisymmetry, i.e. $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ implies that $T_{f}$ and $T_{g}$ are equivalent in some sense. In Appendices A and B, we show an important result: for an appropriate topology on trees, $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ implies that $T_{f}$ and $T_{f}$ are topologically equivalent.

The partial order $\preceq$ in Definition 4 matches intuitive notions of the complexity of the tree for several reasons (see Figure 2). Firstly, $T_{f}\preceq T_{g}$ implies $\text{(number of edges of }T_{f})\leq\text{(number of edges of }T_{g})$ (compare Figure 22(a) and 2(d), and see Lemma 6 in Appendix B). Secondly, if $T_{g}$ is obtained from $T_{f}$ by adding edges, then $T_{f}\preceq T_{g}$ (compare Figure 22(b) and 2(e), and see Lemma 7 in Appendix B). Finally, the existence of a topology preserving embedding from $\{T_{f}\}$ to $\{T_{g}\}$ implies the relationship $T_{f}\preceq T_{g}$ (compare Figure 22(c) and 2(f), and see Lemma 8 in Appendix B).

Tree Metrics

In this section, we introduce some natural metrics on cluster trees and study some of their properties that determine their suitability for statistical inference. We let $p,q:\mathcal{X}\to[0,\infty)$ be nonnegative functions and let $T_{p}$ and $T_{q}$ be the corresponding trees.

Merge distortion metric: The merge distortion metric intuitively measures the discrepancy in the merge height functions of two trees in Definition 2. We consider the merge distortion metric [12, Definition 11] defined by

Modified merge distortion metric: We also consider the modified merge distortion metric given by

where $d_{T_{p}}(x,y)=p(x)+p(y)-2m_{p}(x,y),$ which corresponds to the (pseudo)-distance between $x$ and $y$ along the tree. The metric $d_{\textsc{MM}}$ is used in various proofs in the work of Eldridge et al. . It is sensitive to both distortions of the merge heights in Definition 2, as well as of the underlying densities. Since the metric captures the distortion of distances between points along the tree, it is in some sense most closely aligned with the cluster tree. Finally, it is worth noting that unlike the interleaving distance and the functional distortion metric , the three metrics we consider in this paper are quite simple to approximate to a high-precision.

2 Properties of the Metrics

The following Lemma gives some basic relationships between the three metrics $d_{\infty},d_{\textsc{M}}$ and $d_{\textsc{MM}}$. We define $p_{\inf}=\inf_{x\in\mathcal{X}}p(x)$, and $q_{\inf}$ analogously, and $a=\inf_{x\in\mathcal{X}}\{p(x)+q(x)\}-2\min\{p_{\inf},\,q_{\inf}\}$. Note that when the Lebesgue measure $\mu(\mathcal{X})$ is infinite, then $p_{\inf}=q_{\inf}=a=0$.

For any densities $p$ and $q$, the following relationships hold: (i) When $p$ and $q$ are continuous, then $d_{\infty}(T_{p},T_{q})=d_{\textsc{M}}(T_{p},T_{q}).$ (ii) $d_{\textsc{MM}}(T_{p},T_{q})\leq 4d_{\infty}(T_{p},T_{q}).$ (iii) $d_{\textsc{MM}}(T_{p},T_{q})\geq d_{\infty}(T_{p},T_{q})-a$, where $a$ is defined as above. Additionally when $\mu(\mathcal{X})=\infty$, then $d_{\textsc{MM}}(T_{p},T_{q})\geq d_{\infty}(T_{p},T_{q})$.

The proof is in Appendix F. From Lemma 1, we can see that under a mild assumption (continuity of the densities), $d_{\infty}$ and $d_{\textsc{M}}$ are equivalent. We note again that the work of Eldridge et al. actually defines a family of merge distortion metrics, while we restrict our attention to a canonical one. We can also see from Lemma 1 that while the modified merge metric is not equivalent to $d_{\infty}$, it is usually multiplicatively sandwiched by $d_{\infty}$.

Our next line of investigation is aimed at assessing the suitability of the three metrics for the task of statistical inference. Given the strong equivalence of $d_{\infty}$ and $d_{\textsc{M}}$ we focus our attention on $d_{\infty}$ and $d_{\textsc{MM}}$. Based on prior work (see ), the large sample behavior of $d_{\infty}$ is well understood. In particular, $d_{\infty}(T_{\widehat{p}_{h}},T_{p_{0}})$ converges to the supremum of an appropriate Gaussian process, on the basis of which we can construct confidence intervals for the $d_{\infty}$ metric.

The situation for the metric $d_{\textsc{MM}}$ is substantially more subtle. One of our eventual goals is to use the non-parametric bootstrap to construct valid estimates of the confidence set. In general, a way to assess the amenability of a functional to the bootstrap is via Hadamard differentiability . Roughly speaking, Hadamard-differentiability is a type of statistical stability, that ensures that the functional under consideration is stable to perturbations in the input distribution. In Appendix C, we formally define Hadamard differentiability and prove that $d_{\textsc{MM}}$ is not point-wise Hadamard differentiable. This does not completely rule out the possibility of finding a way to construct confidence sets based on $d_{\textsc{MM}}$, but doing so would be difficult and so far we know of no way to do it.

In summary, based on computational considerations we eliminate the interleaving distance and the functional distortion metric , we eliminate the $d_{\textsc{MM}}$ metric based on its unsuitability for statistical inference and focus the rest of our paper on the $d_{\infty}$ (or equivalently $d_{\textsc{M}}$) metric which is both computationally tractable and has well understood statistical behavior.

Confidence Sets

In this section, we consider the construction of valid confidence intervals centered around the kernel density estimator, defined in Equation (1). We first observe that a fixed bandwidth for the KDE gives a dimension-free rate of convergence for estimating a cluster tree. For estimating a density in high dimensions, the KDE has a poor rate of convergence, due to a decreasing bandwidth for simultaneously optimizing the bias and the variance of the KDE.

Suppose that the true unknown density $p_{0}$, has no non-degenerate critical points The Hessian of $p_{0}$ at every critical point is non-degenerate. Such functions are known as Morse functions., then there exists a constant $h_{0}>0$ such that for all $0<h\leq h_{0}$, the two cluster trees, $T_{p_{0}}$ and $T_{p_{h}}$ have the same topology in Appendix A.

From Lemma 2, proved in Appendix G, a fixed bandwidth for the KDE can be applied to give a dimension-free rate of convergence for estimating the cluster tree. Instead of decreasing bandwidth $h$ and inferring the cluster tree of the true density $T_{p_{0}}$ at rate $O_{P}(n^{-2/(4+d)})$, Lemma 2 implies that we can fix $h>0$ and infer the cluster tree of the biased density $T_{p_{h}}$ at rate $O_{P}(n^{-1/2})$ independently of the dimension. Hence a fixed bandwidth crucially enhances the convergence rate of the proposed methods in high-dimensional settings.

We recall that we base our inference on the $d_{\infty}$ metric, and we recall the definition of a valid confidence set (see Definition 3). As a conceptual first step, suppose that for a specified value $\alpha$ we could compute the $1-\alpha$ quantile of the distribution of $d_{\infty}(T_{\widehat{p}_{h}},T_{p_{h}})$, and denote this value $t_{\alpha}$. Then a valid confidence set for the unknown $T_{p_{h}}$ is $C_{\alpha}=\{T:d_{\infty}(T,T_{\widehat{p}_{h}})\leq t_{\alpha}\}$. To estimate $t_{\alpha}$, we use the bootstrap. Specifically, we generate $B$ bootstrap samples, $\{\widetilde{X}_{1}^{1},\cdots,\widetilde{X}_{n}^{1}\},\ldots,\{\widetilde{X}_{1}^{B},\cdots,\widetilde{X}_{n}^{B}\},$ by sampling with replacement from the original sample. On each bootstrap sample, we compute the KDE, and the associated cluster tree. We denote the cluster trees $\{\widetilde{T}_{p_{h}}^{1},\ldots,\widetilde{T}_{p_{h}}^{B}\}$. Finally, we estimate $t_{\alpha}$ by

Then the data-driven confidence set is $\widehat{C}_{\alpha}=\{T:d_{\infty}(T,\widehat{T}_{h})\leq\widehat{t}_{\alpha}\}.$ Using techniques from , the following can be shown (proof omitted):

Under mild regularity conditions on the kernelSee Appendix D.1 for details., we have that the constructed confidence set is asymptotically valid and satisfies,

Hence our data-driven confidence set is consistent at dimension independent rate. When $h$ is a fixed small constant, Lemma 2 implies that $T_{p_{0}}$ and $T_{p_{h}}$ have the same topology, and Theorem 3 guarantees that the non-parametric bootstrap is consistent at a dimension independent $O(((\log n)^{7}/n)^{1/6})$ rate. For reasons explained in , this rate is believed to be optimal.

2 Probing the Confidence Set

The confidence set $\widehat{C}_{\alpha}$ is an infinite set with a complex structure. Infinitesimal perturbations of the density estimate are in our confidence set and so this set contains very complex trees. One way to understand the structure of the confidence set is to focus attention on simple trees in the confidence set. Intuitively, these trees only contain topological features (splits and branches) that are sufficiently strongly supported by the data.

We propose two pruning schemes to find trees, that are simpler than the empirical tree $T_{\widehat{p}_{h}}$ that are in the confidence set. Pruning the empirical tree aids visualization as well as de-noises the empirical tree by eliminating some features that arise solely due to the stochastic variability of the finite-sample. The algorithms are (see Figure 3): 1. Pruning only leaves: Remove all leaves of length less than $2\widehat{t}_{\alpha}$ (Figure 33(b)). 2. Pruning leaves and internal branches: In this case, we first prune the leaves as above. This yields a new tree. Now we again prune (using cumulative length) any leaf of length less than $2\widehat{t}_{\alpha}$. We continue iteratively until all remaining leaves are of cumulative length larger than $2\widehat{t}_{\alpha}$ (Figure 33(c)).

In Appendix D.2 we formally define the pruning operation and show the following. The remaining tree $\widetilde{T}$ after either of the above pruning operations satisfies: (i) $\widetilde{T}\preceq T_{\widehat{p}_{h}}$, (ii) there exists a function $f$ whose tree is $\widetilde{T}$, and (iii) $\widetilde{T}\in\widehat{C}_{\alpha}$ (see Lemma 10 in Appendix D.2). In other words, we identified a valid tree with a statistical guarantee that is simpler than the original estimate $T_{\widehat{p}_{h}}$. Intuitively, some of the statistically insignificant features have been removed from $T_{\widehat{p}_{h}}$. We should point out, however, that there may exist other trees that are simpler than $T_{\widehat{p}_{h}}$ that are in $\widehat{C}_{\alpha}$. Ideally, we would like to have an algorithm that identifies all trees in the confidence set that are minimal with respect to the partial order $\preceq$ in Definition 4. This is an open question that we will address in future work.

Experiments

In this section, we demonstrate the techniques we have developed for inference on synthetic data, as well as on a real dataset.

We consider three simulations: the ring data (Figure 44(a) and 4(d)), the Mickey Mouse data (Figure 44(b) and 4(e)), and the yingyang data (Figure 44(c) and 4(f)). The smoothing bandwidth is chosen by the Silverman reference rule and we pick the significance level $\alpha=0.05$.

Example 1: The ring data. (Figure 44(a) and 4(d)) The ring data consists of two structures: an outer ring and a center node. The outer circle consists of $1000$ points and the central node contains $200$ points. To construct the tree, we used $h=0.202$.

Example 2: The Mickey Mouse data. (Figure 44(b) and 4(e)) The Mickey Mouse data has three components: the top left and right uniform circle ($400$ points each) and the center circle ($1200$ points). In this case, we select $h=0.200$.

Example 3: The yingyang data. (Figure 44(c) and 4(f)) This data has $5$ connected components: outer ring ($2000$ points), the two moon-shape regions ($400$ points each), and the two nodes ($200$ points each). We choose $h=0.385$.

Figure 4 shows those data (4(a), 4(b), and 4(c)) along with the pruned density trees (solid parts in 4(d), 4(e), and 4(f)). Before pruning the tree (both solid and dashed parts), there are more leaves than the actual number of connected components. But after pruning (only the solid parts), every leaf corresponds to an actual connected component. This demonstrates the power of a good pruning procedure.

2 GvHD dataset

Now we apply our method to the GvHD (Graft-versus-Host Disease) dataset . GvHD is a complication that may occur when transplanting bone marrow or stem cells from one subject to another . We obtained the GvHD dataset from R package ‘mclust’. There are two subsamples: the control sample and the positive (treatment) sample. The control sample consists of $9083$ observations and the positive sample contains $6809$ observations on $4$ biomarker measurements ($d=4$). By the normal reference rule , we pick $h=39.1$ for the positive sample and $h=42.2$ for the control sample. We set the significance level $\alpha=0.05$.

Figure 5 shows the density trees in both samples. The solid brown parts are the remaining components of density trees after pruning and the dashed blue parts are the branches removed by pruning. As can be seen, the pruned density tree of the positive sample (Figure 55(a)) is quite different from the pruned tree of the control sample (Figure 55(b)). The density function of the positive sample has fewer bumps ($2$ significant leaves) than the control sample ($3$ significant leaves). By comparing the pruned trees, we can see how the two distributions differ from each other.

Discussion

There are several open questions that we will address in future work. First, it would be useful to have an algorithm that can find all trees in the confidence set that are minimal with respect to the partial order $\preceq$. These are the simplest trees consistent with the data. Second, we would like to find a way to derive valid confidence sets using the metric $d_{\textsc{MM}}$ which we view as an appealing metric for tree inference. Finally, we have used the Silverman reference rule for choosing the bandwidth but we would like to find a bandwidth selection method that is more targeted to tree inference.

References

Appendix A Topological Preliminaries

The goal of this section is to define an appropriate topology on the cluster tree $T_{f}$ in Definition 1. Defining an appropriate topology for the cluster tree $T_{f}$ is important in this paper for several reasons: (1) the topology gives geometric insight for the cluster tree, (2) homeomorphism (topological equivalence) is connected to equivalence in the partial order $\preceq$ in Definition 4, and (3) the topology gives a justification for using a fixed bandwidth $h$ for constructing confidence set $\widehat{C}_{\alpha}$ as in Lemma 2 to obtain faster rates of convergence.

We construct the topology of the cluster tree $T_{f}$ by imposing a topology on the corresponding collection of connected components $\{T_{f}\}$ in Definition 1. For defining a topology on $\{T_{f}\}$, we define the tree distance function $d_{T_{f}}$ in Definition 5, and impose the metric topology induced from the tree distance function. Using a distance function for topology not only eases formulating topology but also enables us to inherit all the good properties of the metric topology.

The desired tree distance function $d_{T_{f}}:\{T_{f}\}\times\{T_{f}\}\to[0,\infty)$ is based on the merge height function $m_{f}$ in Definition 2. For later use in the proof, we define the tree distance function $d_{T_{f}}$ on both $\mathcal{X}$ and $\{T_{f}\}$ as follows:

Let $f:\mathcal{X}\to[0,\infty)$ be a function, and $T_{f}$ be its cluster tree in Definition 1. For any two points $x,y\in\mathcal{X}$, the tree distance function $d_{T_{f}}:\mathcal{X}\times\mathcal{X}\to[0,\infty)$ of $T_{f}$ on $\mathcal{X}$ is defined as

Similarly, for any two clusters $C_{1},C_{2}\in\{T_{f}\}$, we first define $\lambda_{1}=\sup\{\lambda:C_{1}\in T_{f}(\lambda)\}$, and $\lambda_{2}$ analogously. We then define the tree distance function $d_{T_{f}}:\{T_{f}\}\times\{T_{f}\}\to[0,\infty)$ of $T_{f}$ on $\mathcal{X}$ as:

The tree distance function $d_{T_{f}}$ in Definition 2 is a pseudometric on $\mathcal{X}$ and is a metric on $\{T_{f}\}$ as desired, proven in Lemma 4. The proof is given later in Appendix E.

Let $f:\mathcal{X}\to[0,\infty)$ be a function, $T_{f}$ be its cluster tree in Definition 1, and $d_{T_{f}}$ be its tree distance function in Definition 5. Then $d_{T_{f}}$ on $\mathcal{X}$ is a pseudometric and $d_{T_{f}}$ on $\{T_{f}\}$ is a metric.

From the metric $d_{T_{f}}$ on $\{T_{f}\}$ in Definition 5, we impose the induced metric topology on $\{T_{f}\}$. We say $T_{f}$ is homeomorphic to $T_{g}$, or $T_{f}\cong T_{g}$, when their corresponding collection of connected components are homeomorphic, i.e. $\{T_{f}\}\cong\{T_{g}\}$. (Two spaces are homeomorphic if there exists a bijective continuous function between them, with a continuous inverse.)

To get some geometric understanding of the cluster tree in Definition 1, we identify edges that constitute the cluster tree. Intuitively, edges correspond to either leaves or internal branches. An edge is roughly defined as a set of clusters whose inclusion relationship with respect to clusters outside an edge are equivalent, so that when the collection of connected components is divided into edges, we observe the same inclusion relationship between representative clusters whenever any cluster is selected as a representative for each edge.

For formally defining edges, we define an interval in the cluster tree and the equivalence relation in the cluster tree. For any two clusters $A,B\in\{T_{f}\}$, the interval $[A,B]\subset\{T_{f}\}$ is defined as a set clusters that contain $A$ and are contained in $B$, i.e.

The equivalence relation $\sim$ is defined as $A\sim B$ if and only if their inclusion relationship with respect to clusters outside $[A,B]$ and $[B,A]$, i.e.

Then it is easy to see that the relation $\sim$ is reflexive($A\sim A$), symmetric$(A\sim B$ implies $B\sim A$), and transitive ($A\sim B$ and $B\sim C$ implies $A\sim C$). Hence the relation $\sim$ is indeed an equivalence relation, and we can consider the set of equivalence classes $\{T_{f}\}/_{\sim}$. We define the edge set $E(T_{f})$ as $E(T_{f}):=\{T_{f}\}/_{\sim}$.

For later use, we define the partial order on the edge set $E(T_{f}))$ as follows: $[C_{1}]\leq[C_{2}]$ if and only if for all $A\in[C_{1}]$ and $B\in[C_{2}]$, $A\subset B$. We say that a tree $T_{f}$ is finite if its edge $E(T_{f})$ is a finite set.

Appendix B The Partial Order

As discussed in Section 2, to see that the partial order $\preceq$ in Definition 4 is indeed a partial order, we need to check the reflexivity, the transitivity, and the antisymmetry. The reflexivity and the transitivity are easier to check, but to show antisymmetric, we need to show that if two trees $T_{f}$ and $T_{g}$ satisfies $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$, then $T_{f}$ and $T_{g}$ are equivalent in some sense. And we give the equivalence relation as the topology on the cluster tree defined in Appendix A. The argument is formally stated in Lemma 5. The proof is done later in Appendix E.

Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. Then if $f,g$ are continuous and $T_{f},T_{g}$ are finite, $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ implies that there exists a homeomorphism $\Phi:\{T_{f}\}\rightarrow\{T_{g}\}$ that preserves the root, i.e. $\Phi(\mathcal{X})=\mathcal{X}$. Conversely, if there exists a homeomorphism $\Phi:\{T_{f}\}\rightarrow\{T_{g}\}$ that preserves the root, $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ hold.

The partial order $\preceq$ in Definition 4 gives a formal definition of simplicity of trees, and it is used to justify pruning schemes in Section 4.2. Hence it is important to match the partial order $\preceq$ with the intuitive notions of the complexity of the tree. We provided three arguments in Section 2: (1) if $T_{f}\preceq T_{g}$ holds then it must be the case that $\text{(number of edges of }T_{f})\leq\text{(number of edges of }T_{g})$, (2) if $T_{g}$ can be obtained from $T_{f}$ by adding edges, then $T_{f}\preceq T_{g}$ holds, and (3) the existence of a topology preserving embedding from $\{T_{f}\}$ to $\{T_{g}\}$ implies the relationship $T_{f}\preceq T_{g}$. We formally state each item in Lemma 6, 7, and 8. Proofs of these lemmas are done later in Appendix E.

Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. Suppose $T_{f}\preceq T_{g}$ via $\Phi:\{T_{f}\}\to\{T_{g}\}$. Define $\bar{\Phi}:E(T_{f})\to E(T_{g})$ by for $[C]\in E(T_{f})$ choosing any $C\in[C]$ and defining as $\bar{\Phi}([C])=[\Phi(C)]$. Then $\bar{\Phi}$ is injective, and as a consequence, $|E(T_{f})|\leq|E(T_{g})|$.

Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. If $T_{g}$ can be obtained from $T_{f}$ by adding edges, then $T_{f}\preceq T_{g}$ holds.

Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. If there exists a one-to-one map $\Phi:\{T_{f}\}\to\{T_{g}\}$ that is a homeomorphism between $\{T_{f}\}$ and $\Phi(\{T_{f}\})$ and preserves the root, i.e. $\Phi(\mathcal{X})=\mathcal{X}$, then $T_{f}\preceq T_{g}$ holds.

Appendix C Hadamard Differentiability

Let $B(x)$ be the smallest set $B\in T_{p}$ such that $x\in B$. $d_{T_{p}}(x,y)$ is not Hadamard differentiable for $x\neq y$ when one of the following two scenarios occurs:

$\min\{p(x),p(y)\}=p(c)$ for some critical point $c$.

The merge distortion metric $d_{\textsc{M}}$ is also not Hadamard differentiable.

Appendix D Confidence Sets Constructions

To apply the results in which imply that the bootstrap confidence set is consistent, we consider the following two assumptions.

The kernel function $K$ has the bounded second derivative and is symmetric, non-negative, and

Assumption (K1) is to ensure that the variance of the KDE is bounded and $p_{h}$ has the bounded second derivative. This assumption is very common in statistical literature, see e.g. . Assumption (K2) is to regularize the complexity of the kernel function so that the supremum norm for kernel functions and their derivatives can be bounded in probability. A similar assumption appears in and . The Gaussian kernel and most compactly supported kernels satisfy both assumptions.

D.2 Pruning

$\widetilde{p}$ in (ii) satisfies $\widetilde{p}\in\widehat{C}_{\alpha}$.

Remark: It can be shown that complete pruning — simultaneously removing all leaves and branches with length less than $2\widehat{t}_{\alpha}$ — can in general yield a tree that is outside the confidence set. For example, see Figure 3. If we do complete pruning to this tree, we will get the trivial tree.

Appendix E Proofs for Appendix A and B

Lemma 4. Let $f:\mathcal{X}\to[0,\infty)$ be a function, $T_{f}$ be its cluster tree in Definition 1, and $d_{T_{f}}$ be its tree distance function in Definition 5. Then $d_{T_{f}}$ on $\mathcal{X}$ is a pseudometric and $d_{T_{f}}$ on $\{T_{f}\}$ is a metric.

First, we show that $d_{T_{f}}$ on $\mathcal{X}$ is a pseudometric. To do this, we need to show non-negativity($d_{T_{f}}(x,y)\geq 0$), $x=y$ implying $d_{T_{f}}(x,y)=0$, symmetry($d_{T_{f}}(x,y)=d_{T_{f}}(y,x)$), and subadditivity($d_{T_{f}}(x,y)+d_{T_{f}}(y,z)\leq d_{T_{f}}(x,z)$).

For non-negativity, note that for all $x,y\in\mathcal{X}$, $m_{f}(x,y)\leq\min\left\{f(x),f(y)\right\}$, so

For $x=y$ implying $d_{T_{f}}(x,y)=0$, $x=y$ implies $m_{f}(x,y)=f(x)=f(y)$, so

For symmetry, since $m_{f}(x,y)=m_{f}(y,x)$,

For subadditivity, note first that $m_{f}(x,y)\leq f(y)$ and $m_{f}(y,z)\leq f(y)$ holds, so

And also note that there exists $C_{xy},C_{yz}\in T_{f}\left(\min\left\{m_{f}(x,y),\,m_{f}(y,z)\right\}\right)$ that satisfies $x,y\in C_{xy}$ and $y,z\subset C_{yz}$. Then $y\in C_{xy}\cap C_{yz}\neq\emptyset$, so $x,z\in C_{xy}=C_{yz}$. Then from definition of $m_{f}(x,z)$, this implies that

And by applying (7) and (8), $d_{T_{f}}(x,y)+d_{T_{f}}(y,z)$ is upper bounded by $d_{T_{f}}(x,z)$ as

Hence (4), (5), (6), and (E.1) implies that $d_{T_{f}}$ on $\mathcal{X}$ is a pseudometric.

Second, we show that $d_{T_{f}}$ on $\{T_{f}\}$ is a metric. To do this, we need to show non-negativity($d_{T_{f}}(x,y)\geq 0$), identity of indiscernibles($x=y\iff d_{T_{f}}(x,y)=0$), symmetry($d_{T_{f}}(x,y)=d_{T_{f}}(y,x)$), and subadditivity($d_{T_{f}}(x,y)+d_{T_{f}}(y,z)\leq d_{T_{f}}(x,z)$).

For nonnegativity, note that if $C_{1}\in T_{f}(\lambda_{1})$ and $C_{2}\in T_{f}(\lambda_{2})$, then $m_{f}(C_{1},C_{2})\leq\min\{\lambda_{1},\lambda_{2}\}$, so

For identity of indiscernibles, $C_{1}=C_{2}$ implies $m_{f}(C_{1},C_{2})=\lambda_{1}=\lambda_{2}$, so

And conversely, $d_{T_{f}}(C_{1},C_{2})=0$ implies $\lambda_{1}=\lambda_{2}=m_{f}(C_{1},C_{2})$, so there exists $C\in T_{f}(\lambda_{1})$ such that $C_{1}\subset C$ and $C_{2}\subset C$. Then since $C_{1},C_{2},C\in T_{f}(\lambda_{1})$, so $C_{1}\cap C\neq\emptyset$ implies $C_{1}=C$ and similarly $C_{2}=C$, so

Hence (11) and (12) implies identity of indiscernibles as

For symmetry, since $m_{f}(C_{1},C_{2})=m_{f}(C_{2},C_{1})$,

For subadditivity, note that $m_{f}(C_{1},C_{2})\leq\lambda_{2}$ and $m_{f}(C_{2},C_{3})\leq\lambda_{2}$ holds, so

And also note that there exists $C_{12},C_{23}\in T_{f}\left(\min\left\{m_{f}(C_{1},C_{2}),\,m_{f}(C_{2},C_{3})\right\}\right)$ that satisfies $C_{1},C_{2}\subset C_{12}$ and $C_{2},C_{3}\subset C_{23}$. Then $C_{2}\subset C_{12}\cap C_{23}\neq\emptyset$, so $C_{1},C_{3}\in C_{12}=C_{23}$. Then from definition of $m_{f}(C_{1},C_{3})$, this implies that

And by applying (15) and (16), $d_{T_{f}}(C_{1},C_{2})+d_{T_{f}}(C_{2},C_{3})$ is upper bounded by $d_{T_{f}}(C_{1},C_{3})$ as

Hence (10), (13), (14), and (E.1) $d_{T_{f}}$ on $\{T_{f}\}$ is a metric.

E.2 Proof of Lemma 5

Lemma 5. Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. Then if $f,g$ are continuous and $T_{f},T_{g}$ are finite, $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ implies that there exists a homeomorphism $\Phi:\{T_{f}\}\rightarrow\{T_{g}\}$ that preserves the root, i.e. $\Phi(\mathcal{X})=\mathcal{X}$. Conversely, if there exists a homeomorphism $\Phi:\{T_{f}\}\rightarrow\{T_{g}\}$ that preserves the root, $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ hold.

First, we show that $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ implies homeomorphism. Let $\Phi:\{T_{f}\}\to\{T_{g}\}$ be the map that gives the partial order $T_{f}\preceq T_{g}$ in Definition 4. Then from Lemma 6, $\bar{\Phi}:E(T_{f})\to E(T_{g})$ is injective and $|E(T_{f})|\leq|E(T_{g})|$. With a similar argument, $|E(T_{g})|\leq|E(T_{f})|$ holds, so

Since we assumed that $T_{f}$ and $T_{g}$ are finite, i.e. $|E(T_{f})|$ and $|E(T_{g})|$ are finite, $\bar{\Phi}$ becomes a bijection.

Now, let $[C_{1}]$ and $[C_{2}]$ be adjacent edges in $E(T_{f})$, and without loss of generality, assume $C_{1}\subset C_{2}$. We argue below that $\bar{\Phi}([C_{1}])$ and $\bar{\Phi}([C_{2}])$ are also adjacent edges. Then $\Phi(C_{1})\subset\Phi(C_{2})$ holds from Definition 4, and since $\bar{\Phi}$ is bijective, $[\Phi(C_{1})]=\bar{\Phi}([C_{1}])$ and $[\Phi(C_{2})]=\bar{\Phi}([C_{2}])$ holds. Suppose there exists $\widetilde{C}_{3}\in\{T_{g}\}$ such that $[\widetilde{C}_{3}]\notin\{\bar{\Phi}([C_{1}]),\,\bar{\Phi}([C_{2}])\}$ and $\Phi(C_{1})\subset\widetilde{C}_{3}\subset\Phi(C_{2})$. Then since $\bar{\Phi}$ is bijective, there exists $C_{3}\in\{T_{f}\}$ such that $[\Phi(C_{3})]=[\widetilde{C}_{3}]$. Then $\Phi(C_{1})\subset\widetilde{C}_{3}\subset\Phi(C_{2})$ implies that $C_{1}\subset C_{3}\subset C_{2}$, and $\bar{\Phi}$ being a bijection implies that $[C_{3}]\notin\{[C_{1}],\,[C_{3}]\}$. This is a contradiction since $[C_{1}]$ and $[C_{2}]$ are adjacent edges. Hence there is no such $\widetilde{C}_{3}$, and $\bar{\Phi}([C_{1}])$ and $\bar{\Phi}([C_{2}])$ are adjacent edges. Therefore, $\bar{\Phi}:E(T_{f})\to E(T_{g})$ is a bijective map that sends adjacent edges to adjacent edges, and also sends root edge to root edge.

Then combining $\bar{\Phi}:E(T_{f})\to E(T_{g})$ being bijective sending adjacent edges to adjacent edges and root edge to root edge, and $f,g$ being continuous, the map $\bar{\Phi}:E(T_{f})\to E(T_{g})$ can be extended to a homeomorphism $\{T_{g}\}\to\{T_{f}\}$ that preserves the root.

Second, the part that homeomorphism implies $T_{f}\preceq T_{g}$ and $T_{g}\preceq T_{f}$ follows by Lemma 8. $\Box$

E.3 Proof of Lemma 6

Lemma 6. Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. Suppose $T_{f}\preceq T_{g}$ via $\Phi:\{T_{f}\}\to\{T_{g}\}$. Define $\bar{\Phi}:E(T_{f})\to E(T_{g})$ by for $[C]\in E(T_{f})$ choosing any $C\in[C]$ and defining as $\bar{\Phi}([C])=[\Phi(C)]$. Then $\bar{\Phi}$ is injective, and as a consequence, $|E(T_{f})|\leq|E(T_{g})|$.

We will first show that equivalence relation on $\{T_{g}\}$ implies equivalence relation on $\{T_{f}\}$, i.e.

Suppose $\Phi(C_{1})\sim\Phi(C_{2})$ in $\{T_{g}\}$. Then from Definition 4 of $\Phi$, for any $C\in\{T_{f}\}$ such that $C\notin[C_{1},C_{2}]\cup[C_{2},C_{1}]$, $\Phi(C)\notin[\Phi(C_{1}),\Phi(C_{2})]\cup[\Phi(C_{2}),\Phi(C_{1})]$ holds. Then from definition of $\Phi(C_{1})\sim\Phi(C_{2})$,

Then again from Definition 4 of $\Phi$, equivalence relation holds for $C_{1}$ and $C_{2}$ holds as well, i.e.

Hence (18) is shown, and this implies that

E.4 Proof of Lemma 7

Lemma 7. Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. If $T_{g}$ can be obtained from $T_{f}$ by adding edges, then $T_{f}\preceq T_{g}$ holds.

Proof. Since $T_{g}$ can be obtained from $T_{f}$ by adding edges, there is a map $\Phi:T_{f}\to T_{g}$ which preserves order, i.e. $C_{1}\subset C_{2}$ if and only if $\Phi(C_{1})\subset\Phi(C_{2})$. Hence $T_{f}\preceq T_{g}$ holds. $\Box$

E.5 Proof of Lemma 8

Lemma 8. Let $f,g:\mathcal{X}\rightarrow[0,\infty)$ be functions, and $T_{f},T_{g}$ be their cluster trees in Definition 1. If there exists a one-to-one map $\Phi:\{T_{f}\}\to\{T_{g}\}$ that is a homeomorphism between $\{T_{f}\}$ and $\Phi(\{T_{f}\})$ and preserves root, i.e. $\Phi(\mathcal{X})=\mathcal{X}$, then $T_{f}\preceq T_{g}$ holds.

Proof. For any $C\in\{T_{f}\}$, note that $[C,\mathcal{X}]\subset\{T_{f}\}$ is homeomorphic to an interval, hence $\Phi([C,\mathcal{X}])\subset\{T_{g}\}$ is also homeomorphic to an interval. Since $\{T_{g}\}$ is topologically a tree, an interval in a tree with fixed boundary points is uniquely determined, i.e.

For showing $T_{f}\preceq T_{g}$, we need to argue that for all $C_{1},C_{2}\in\{T_{f}\}$, $C_{1}\subset C_{2}$ holds if and only if $\Phi(C_{1})\subset\Phi(C_{2})$. For only if direction, suppose $C_{1}\subset C_{2}$. Then $C_{2}\in[C_{1},\mathcal{X}]$, so Definition 4 and (19) implies

For if direction, suppose $\Phi(C_{1})\subset\Phi(C_{2})$. Then since $\Phi^{-1}:\Phi(\{T_{f}\})\to\{T_{f}\}$ is also an homeomorphism with $\Phi^{-1}(\mathcal{X})=\mathcal{X}$, hence by repeating above argument, we have

Hence (20) and (21) implies $T_{f}\preceq T_{g}$. $\Box$

Appendix F Proofs for Section 3 and Appendix C

Lemma 1. For any densities $p$ and $q$, the following relationships hold:

When $p$ and $q$ are continuous, then $d_{\infty}(T_{p},T_{q})=d_{\textsc{M}}(T_{p},T_{q})$.

$d_{\textsc{MM}}(T_{p},T_{q})\leq 4d_{\infty}(T_{p},T_{q}).$

$d_{\textsc{MM}}(T_{p},T_{q})\geq d_{\infty}(T_{p},T_{q})-a$, where $a$ is defined as above. Additionally when $\mu(\mathcal{X})=\infty$, then $d_{\textsc{MM}}(T_{p},T_{q})\geq d_{\infty}(T_{p},T_{q})$.

First, we show $d_{M}(T_{p},\,T_{q})\leq d_{\infty}(T_{p},\,T_{q})$. Note that this part is implicitly shown in Eldridge et al. [12, Proof of Theorem 6]. For all $\epsilon>0$ and for any $x,y\in\mathcal{X}$, let $C_{0}\in T_{p}(m_{p}(x,y)-\epsilon)$ with $x,y\in C_{0}$. Then for all $z\in C_{0}$, $q(z)$ is lower bounded as

so $C_{0}\subset q^{-1}\left(m_{p}(x,y)-\epsilon-d_{\infty}(T_{p},T_{q}),\,\infty\right)$ and $C_{0}$ is connected, so $x$ and $y$ are in the same connected component of $q^{-1}\left(m_{p}(x,y)-\epsilon-d_{\infty}(T_{p},T_{q}),\,\infty\right)$, which implies

A similar argument holds for other direction as

so (22) and (23) being held for all $\epsilon>0$ implies

And taking $\sup$ over all $x,y\in\mathcal{X}$ in (24) $d_{M}(T_{p},\,T_{q})$ is upper bounded by $d_{\infty}(T_{p},\,T_{q})$, i.e.

Second, we show $d_{M}(T_{p},\,T_{q})\geq d_{\infty}(T_{p},\,T_{q})$. For all $\epsilon>0$, Let $x$ be such that $|p(x)-q(x)|>d_{\infty}(T_{p},T_{q})-\frac{\epsilon}{2}$. Then since $p$ and $q$ are continuous, there exists $\delta>0$ such that

Then for any $y\in B(x,\,\delta)$, since $B(x,\,\delta)$ is connected, $p(x)-\frac{\epsilon}{2}\leq m_{p}(x,y)\leq p(x)$ holds and $q(x)-\frac{\epsilon}{2}\leq m_{q}(x,y)\leq q(x)$, so

Since this holds for any $\epsilon>0$, $d_{M}(T_{p},\,T_{q})$ is lower bounded by $d_{\infty}(T_{p},\,T_{q})$, i.e.

(25) and (26) implies $d_{\infty}(T_{p},T_{q})=d_{\textsc{M}}(T_{p},T_{q})$.

We have already seen that for all $x,y\in\mathcal{X}$, $|m_{p}(x,y)-m_{q}(x,y)|\leq d_{\infty}(T_{p},T_{q})$ in (24). Hence for all $x,y\in\mathcal{X}$,

Since this holds for all $x,y\in\mathcal{X}$, so

For all $\epsilon>0$, Let $x$ be such that $|p(x)-q(x)|>d_{\infty}(T_{p},T_{q})-\frac{\epsilon}{2}$, and without loss of generality assume that $p(x)>q(x)$. Let $y$ be such that $p(y)+q(y)<\underset{x}{\inf}(p(x)+q(x))+\frac{\epsilon}{2}$. Then $m_{p}(x,y)\leq p(y)$ holds, and since $\mathcal{X}$ is connected, $q_{\inf}\leq m_{q}(x,y)$ holds. Hence

where $a=\underset{x\in\mathcal{X}}{\inf}(p(x)+q(x))-2\min\left\{p_{\inf},\,q_{\inf}\right\}$. Since this holds for all $\epsilon>0$, we have

Hence $0\leq d_{\textsc{MM}}(T_{p},T_{q})\leq 4d_{\infty}(T_{p},T_{q})$ holds. And both extreme cases can happen, i.e. $d_{\textsc{MM}}(T_{p},T_{q})=4d_{\infty}(T_{p},T_{q})>0$ and $d_{\textsc{MM}}(T_{p},T_{q})=0,\,d_{\infty}(T_{p},T_{q})>0$ can happens.