betaFeedback

WorksComputer Science

Topological Equivalence of Spectral and Density Cluster Hierarchies

Abstract

We compare two canonical ways to recover hierarchical clustering from an underlying density ff: the density cluster tree given by connected components of superlevel sets {f≥λ}\{f\geλ\}, and a spectral hierarchy obtained by applying single linkage to diffusion distances induced by a Laplacian operator. We give conditions under which, at an appropriate diffusion time, the diffusion hierarchy is topologically equivalent to the density cluster tree up to a monotone rescaling of heights. It further shows that a kk-NN graph implementation inherits this equivalence from uniform approximation of diffusion distances, yielding a finite-sample reduction from spectral graph constructions to density-level-set topology.

Introduction

Hierarchical clustering is a basic tool to describe structure in data at many scales. In this paper we study two standard hierarchies that start from an unknown density ff on a compact domain MM. The first one is the density cluster tree TfT_f, defined by the connected components of the superlevel sets of the underlying density function Lλ={x∈M:f(x)≥λ}L_\lambda= \{x \in M : f(x) \ge\lambda\} as λ\lambda decreases [7, 1, 4]. The second one is a diffusion–spectral hierarchy, defined as a reversible Markov operator PP (or a Laplacian) from ff [2, 14]. Both viewpoints share the same idea and define a cluster as a set where the random walk mixes fast inside, but it escapes slowly outside.

The question we ask is simple. The density cluster tree is a canonical topological object, and it comes with a clear statistical target and stability theory [1, 4]. Diffusion distances are very popular because they are algorithmic and robust, and they are connected to spectral gaps and bottlenecks [2, 14]. But it is not always clear what the diffusion hierarchy estimates as a population object. So, when does the diffusion single-linkage hierarchy give the same merge structure as the density cluster tree? This allows to consider the spectral method more than a heuristic, considering it as a certified estimator of a topological object defined by ff.

To make the comparison precise we use merge heights. The density tree can be encoded by the merge-height function

mf(x,y)=sup⁡{λ≥0:x and y are in the same component of Lλ}.m_f(x,y) = \sup\{\lambda\ge0 : x \text{ and } y \text{ are in the same component of } L_\lambda\}.

The diffusion hierarchy at time tt is the single-linkage dendrogram built from (M,dt)(M,d_t), and it has its own merge-height function mt(x,y)m_t(x,y). We say the hierarchies meet if they are the same merge tree up to a monotone rescaling of heights, meaning there exists a strictly increasing map gtg_t such that mt(x,y)=gt(mf(x,y))m_t(x,y) = g_t(m_f(x,y)) for all pairs. This notion matches the idea that the two procedures may use different units on the vertical axis, but they should have the same merge events and the same nesting. We formalize mild Topological Meeting Condition (TMC) implying the meeting happens in an stable diffusive time window. Roughly, for every density level λ\lambda and every component CC of LλL_\lambda, we require two quantitative facts about the chain, it mixes fast inside CC, and also has small probability to exit CC in one step. If there exists a nontrivial time window where mixing has already happened but leakage is still small, and this window is consistent across the levels of the tree, then diffusion single linkage recovers the same hierarchy as density level sets.

Our results connect several lines of work. The density cluster tree goes back to Hartigan [7] and later statistical developments [1, 4]. Diffusion distance and diffusion maps give a spectral geometry view of connectivity and scales [2], and single linkage and MST are classical tools for building hierarchies [14]. On the finite-sample side, we use a modular principle, once diffusion distances are uniformly close, single linkage is stable in merge distortion, so the hard part is reduced to diffusion/Laplacian approximation on graphs [15 GTS20]. The merge-tree viewpoint is also close to stability ideas in topological data analysis [3, 5].

We state the main results in a way that separates the topological argument from the analytic estimates. Single linkage depends only on the order in which connectivity events occur as the threshold increases. Our analytic task is to show that, at a suitable diffusion time, diffusion distance produces the same connectivity events as the density superlevel sets. Hence, agreement at every merge level then implies that the two hierarchies have the same merge tree, up to a monotone rescaling of heights.

We present three results. The first one is a population meeting theorem under an abstract hierarchical metastability condition. The second one is a finite-sample merge-distortion theorem for the standard kk-NN graph algorithm, stated modularly through a uniform diffusion-distance approximation condition. The third one is a geometric theorem that implies metastability, together with a multiscale extension that removes the need for one global diffusion time.

The rest of the paper is organized as follows. Section § 2 fixes notation and reviews preliminaries. Section § 3 states the Topological Meeting Condition and explains how it encodes hierarchical metastability. Section § 4 proves the population meeting theorem by showing within-component contraction and between-component separation of diffusion distance in the metastable window. Section § 5 presents the kk-NN graph algorithm and proves the merge-distortion guarantee using a stability lemma for single linkage. Section § 6 gives geometric conditions that imply the metastability bounds and discusses a multiscale extension that can avoid choosing one global diffusion time. We conclude with discussion and some remaining questions.

Preliminaries and notation

We work on a compact metric space (M,ρ)(M,\rho) with a Borel measure μ\mu. The data distribution is a probability measure π\pi that admits a continuous density f:M→(0,∞)f : M \to(0,\infty) with respect to μ\mu, so dπ=f dμ\mathrm{d}\pi= f\,\mathrm{d}\mu and ∫Mf dμ=1\int_M f\,\mathrm{d}\mu= 1. We observe i.i.d. samples X1,…,Xn∼πX_1,\ldots,X_n \sim\pi. For each level λ≥0\lambda\ge0 we write Lλ={x∈M:f(x)≥λ}L_\lambda= \{x \in M : f(x) \ge\lambda\} and C(λ)\mathcal{C}(\lambda) for the connected components of LλL_\lambda in the topology of MM. The density cluster tree is encoded by the merge-height function mfm_f defined from these components.

We keep regularity assumptions on ff flexible. For the population merge-tree statements, continuity is typically enough. For finite-sample rates and operator approximation, we may assume additional boundedness and smoothness such as Hölder or Lipschitz regularity, and in manifold settings bounded geometry and lower bounds on ff on regions of interest. The important point is that ff plays two roles. It defines the topology of the level sets {f≥λ}\{f \ge\lambda\}, and it also biases the diffusion process that we build from the data.

To define diffusion, we fix a symmetric kernel Kσ:M×M→[0,∞)K_\sigma: M \times M \to[0,\infty). We set

q(x)=∫MKσ(x,y)f(y) dμ(y),p(x,dy)=Kσ(x,y)f(y)q(x) dμ(y),(Pφ)(x)=∫φ(y)p(x,dy).q(x) = \int_M K_\sigma(x,y) f(y)\,\mathrm{d}\mu(y), \qquad p(x,\mathrm{d}y) = \frac{K_\sigma(x,y)f(y)}{q(x)}\,\mathrm{d}\mu(y), \qquad(P\varphi)(x) = \int\varphi(y)p(x,\mathrm{d}y).

The operator PP is a Markov operator with stationary measure πq\pi_q, and we work in L2(πq)L^2(\pi_q). We write p(t)(x,⋅)p^{(t)}(x,\cdot) for the tt-step transition law of the Markov chain (Xt)t≥0(X_t)_{t\ge0} with transition kernel pp. We write dtd_t for diffusion distance at time tt, defined as an L2(πq)L^2(\pi_q) distance between the tt-step transition densities. We write TfT_f for the density cluster tree, and TtdiffT_t^{\mathrm{diff}} for the single-linkage hierarchy built from (M,dt)(M,d_t) with merge-height function mtm_t. For a finite set SS we write dMDd_{\mathrm{MD}} for merge distortion between merge-height functions on SS. We use ∥⋅∥2\lVert\cdot\rVert_2 for L2(πq)L^2(\pi_q) norms, ∥⋅∥op\lVert\cdot\rVert_{\mathrm{op}} for operator norms, and ∥⋅∥TV\lVert\cdot\rVert_{\mathrm{TV}} for total variation norms.

Density cluster tree and merge heights

The density cluster tree is the hierarchy obtained from the superlevel sets

Lλ={x∈M∣f(x)≥λ}L_\lambda= \{x \in M \mid f(x) \ge\lambda\}

when λ\lambda goes from large to small [7, 1]. For a fixed λ\lambda, the set LλL_\lambda can split into several connected components. When λ\lambda decreases, components can only grow and they can merge, but they cannot split. This nesting gives a merge tree.

A convenient way to encode this tree is by a pairwise merge height. It records the highest density level where two points are still connected in the same component.

Definition 1 (Density merge height). For x,y∈Mx,y \in M, define

mf(x,y)=sup⁡{λ≥0∣x and y lie in the same connected component of Lλ}.m_f(x,y)=\sup\left\{\lambda\ge0\mid x\text{ and }y\text{ lie in the same connected component of }L_\lambda\right\}.

The function mfm_f is symmetric, and it is larger when xx and yy stay connected until a higher density level. If ff is continuous, then the superlevel sets change only at special levels. When there are only finitely many such merge levels, the hierarchy is a finite merge tree. We do not use Morse theory. We only use finiteness when we want to choose one diffusion time that works for all merge events.

Diffusion operator, process, and diffusion distance

We now define a Markov process that follows the geometry induced by the density and a kernel. Fix a symmetric kernel Kσ≥0K_\sigma\ge0. We define

q(x)=∫MKσ(x,y)f(y) dμ(y),p(x,dy)=Kσ(x,y)f(y)q(x) dμ(y),(Pφ)(x)=∫φ(y) p(x,dy).q(x)=\int_M K_\sigma(x,y)f(y)\,d\mu(y),\qquad p(x,dy)=\frac{K_\sigma(x,y)f(y)}{q(x)}\,d\mu(y),\qquad(P\varphi)(x)=\int\varphi(y)\,p(x,dy).

Then PP is a Markov operator. It is reversible with respect to a stationary measure πq\pi_q whose density is proportional to qq with respect to μ\mu [2]. The associated random process is the Markov chain (Xt)t≥0(X_t)_{t\ge0} with transition rule Xt+1∣Xt=x∼p(x,⋅)X_{t+1}\mid X_t=x\sim p(x,\cdot).

Diffusion distance compares two starting points by comparing their tt-step transition laws. If two points are in the same well connected region, their tt-step distributions become similar. If they are separated by a bottleneck, their tt-step distributions stay different.

Definition 2 (Diffusion distance [2]). Let p(t)(x,⋅)p^{(t)}(x,\cdot) be the tt-step transition law from xx, and assume p(t)(x,⋅)p^{(t)}(x,\cdot) is absolutely continuous with respect to πq\pi_q. Define

dt(x,y)=∥dp(t)(x,⋅)dπq−dp(t)(y,⋅)dπq∥L2(πq).d_t(x,y)=\left\|\frac{dp^{(t)}(x,\cdot)}{d\pi_q}-\frac{dp^{(t)}(y,\cdot)}{d\pi_q}\right\|_{L^2(\pi_q)}.

Reversibility implies that PP is self-adjoint in L2(πq)L^2(\pi_q). Therefore there exists an orthonormal eigenbasis (ψℓ)ℓ≥0(\psi_\ell)_{\ell\ge0} with real eigenvalues (λℓ)ℓ≥0(\lambda_\ell)_{\ell\ge0} such that

1=λ0>λ1≥λ2≥⋯≥−1,ψ0≡1.1=\lambda_0>\lambda_1\ge\lambda_2\ge\cdots\ge-1,\qquad\psi_0\equiv1.

In this setting diffusion distance has a simple spectral form.

Lemma 1 (Spectral formula for diffusion distance [2]). For all x,y∈Mx,y\in M and all integers t≥1t\ge1,

dt(x,y)2=∑ℓ≥1λℓ2t(ψℓ(x)−ψℓ(y))2.d_t(x,y)^2=\sum_{\ell\ge1}\lambda_\ell^{2t}\left(\psi_\ell(x)-\psi_\ell(y)\right)^2.

Proof sketch. Write the Radon–Nikodym derivative of p(t)(x,⋅)p^{(t)}(x,\cdot) with respect to πq\pi_q using the eigenbasis of PP in L2(πq)L^2(\pi_q). Apply Ptψℓ=λℓtψℓP^t\psi_\ell=\lambda_\ell^t\psi_\ell to see how each mode scales with tt. The squared L2(πq)L^2(\pi_q) distance between the two expansions is the sum of squared coefficients, because the eigenfunctions are orthonormal. This gives the claimed formula.

Lemma 1 shows that large tt suppresses modes with ∣λℓ∣<1|\lambda_\ell|<1. In this sense tt controls the scale at which the geometry is observed.

Parzen windows, kernel density estimation, and kk-NN density estimation

In practice ff is unknown, so level sets LλL_\lambda are not directly available. A classical way to estimate ff is the Parzen window method, also called kernel density estimation [10, 11, 12, 16]. In Euclidean space Rd\mathbb{R}^d with Lebesgue measure, the standard KDE has the form

f^h(x)=1nhd∑i=1nK(x−Xih).\widehat{f}_h(x)=\frac{1}{nh^d}\sum_{i=1}^{n}K\left(\frac{x-X_i}{h}\right).

where h>0h > 0 is a bandwidth and KK is a nonnegative kernel with ∫RdK(u) du=1\int_{\mathbb{R}^d} K(u)\,\mathrm{d}u = 1. On a general metric measure space (M,ρ,μ)(M,\rho,\mu) one can write the same idea using a pairwise kernel

f^h(x)=1n∑i=1nKh(x,Xi),Kh(x,y)≥0,∫MKh(x,y) dμ(y)=1.\hat{f}_h(x) = \frac{1}{n}\sum_{i=1}^{n} K_h(x,X_i), \qquad K_h(x,y) \ge0, \qquad\int_M K_h(x,y)\,\mathrm{d}\mu(y) = 1.

A typical choice is Kh(x,y)=chκ(ρ(x,y)/h)K_h(x,y) = c_h\kappa(\rho(x,y)/h) with a radial profile κ\kappa and a normalizing constant chc_h that depends on hh and the geometry of (M,μ)(M,\mu). Under smoothness assumptions on ff and mild conditions on KK, one gets pointwise and uniform convergence of f^h\hat{f}_h to ff when h→0h \to0 and nhd→∞nh^d \to\infty, with the usual bias and variance tradeoff [12, 16]. In density clustering, one can use f^h\hat{f}_h to define empirical superlevel sets {f^h≥λ}\{\hat{f}_h \ge\lambda\} and then build an estimated cluster tree [1, 4].

A different estimator uses kk nearest neighbors [8, 16]. Let rk(x)r_k(x) be the distance from xx to its kkth nearest neighbor among X1,…,XnX_1,\ldots,X_n in the metric ρ\rho. Let V(x,r)=μ(B(x,r))V(x,r) = \mu(B(x,r)) denote the μ\mu-volume of the ball B(x,r)={y∈M:ρ(x,y)≤r}B(x,r) = \{y \in M : \rho(x,y) \le r\}. A standard kk-NN density estimator is

f^k-NN(x)=knV(x,rk(x)).\hat{f}_{k\text{-NN}}(x) = \frac{k}{nV(x,r_k(x))}.

This estimator adapts to local sampling density because rk(x)r_k(x) shrinks in high-density regions and grows in low-density regions. The parameter kk controls smoothing. Under regularity assumptions on μ\mu and ff, consistency holds when k→∞k \to\infty and k/n→0k/n \to0 [8, 16]. The kk-NN idea is also the backbone of the graph constructions in this paper, because the kk-NN graph provides a data-driven neighborhood structure that adapts to the sampling distribution.

In our setting, these estimators appear in two roles. First, they are direct estimators of level sets and the density cluster tree. Second, they indirectly define diffusion operators and graph Laplacians through kernels and kk-NN graphs. The meeting results then say that, at the right diffusion time, the diffusion hierarchy can recover the same merge tree as the population level-set hierarchy without explicitly estimating ff everywhere.

Single linkage, MST, and merge distortion

Let SS be a finite set and let dd be a symmetric dissimilarity on SS with d(x,x)=0d(x,x) = 0. Single linkage builds a dendrogram by increasing a threshold τ\tau and looking at the graph on SS with edges

{(x,y)∈S×S∣d(x,y)≤τ}.\{(x,y) \in S \times S \mid d(x,y) \le\tau\}.

As τ\tau increases, connected components merge. The merge height md(x,y)m_d(x,y) is the smallest τ\tau where xx and yy become connected.

There is also an equivalent path view. Consider any path from xx to yy in the complete graph on SS. Look at the largest edge length along that path. Then md(x,y)m_d(x,y) is the minimum possible value of this maximum over all paths. This bottleneck value is realized on a minimum spanning tree, so single linkage can be computed from an MST [14].

We compare two dendrograms using merge distortion [4]. It measures the largest difference between corresponding merge heights.

Definition 3 (Merge distortion [4]). Let SS be finite and let m,m′:S×S→Rm,m' : S \times S \to\mathbb{R} be symmetric merge-height functions. Define

dMD(m,m′)=sup⁡x,y∈S∣m(x,y)−m′(x,y)∣.d_{\mathrm{MD}}(m,m') = \sup_{x,y\in S} \left|m(x,y)-m'(x,y)\right|.

Spectral clustering and diffusion

Spectral clustering starts from the same basic object as diffusion geometry, namely a weighted graph or a kernel affinity built from the data [13, 9, 14]. Given points X1,…,XnX_1,\ldots,X_n, define an affinity matrix WW with entries Wij≥0W_{ij} \ge0, often of the form Wij=Kσ(Xi,Xj)W_{ij} = K_\sigma(X_i,X_j) or a sparsified version using a kk-NN graph. Let DD be the diagonal degree matrix Dii=∑j=1nWijD_{ii} = \sum_{j=1}^{n} W_{ij}. The unnormalized graph Laplacian is L=D−WL = D-W, and common normalized versions are

Lrw=I−D−1WandLsym=I−D−1/2WD−1/2.L_{\mathrm{rw}} = I-D^{-1}W \qquad\text{and} \qquad L_{\mathrm{sym}} = I-D^{-1/2}WD^{-1/2}.

Spectral clustering uses the leading eigenvectors of one of these Laplacians to embed the data into Rm\mathbb{R}^m, then it clusters in that embedding, typically by kk-means [9, 14]. The reason this works is that eigenvectors of the Laplacian capture low-frequency structure on the graph, and low-frequency structure is shaped by bottlenecks and almost-disconnected regions.

Diffusion enters because the normalized adjacency defines a random walk. The random-walk transition matrix is

Pn=D−1W.P_n = D^{-1}W.

This is exactly the discrete analogue of the Markov operator PP in the population. The tt-step transition matrix PntP_n^t describes how probability mass spreads on the graph after tt steps. Diffusion distance is the distance between these tt-step transition distributions. In the finite graph setting, if πn\pi_n is the stationary distribution of PnP_n, then a discrete diffusion distance can be written as

d^t(i,j)=∥Pnt(i,⋅)πn(⋅)−Pnt(j,⋅)πn(⋅)∥ℓ2(πn).\widehat{d}_t(i,j) = \left\lVert\frac{P_n^t(i,\cdot)}{\pi_n(\cdot)}-\frac{P_n^t(j,\cdot)}{\pi_n(\cdot)} \right\rVert_{\ell^2(\pi_n)}.

This distance has a spectral representation that mirrors Lemma 1. If (λ^ℓ,ψ^ℓ)(\widehat{\lambda}_\ell,\widehat{\psi}_\ell) are eigenpairs of PnP_n in ℓ2(πn)\ell^2(\pi_n), then

d^t(i,j)2=∑ℓ≥1λ^ℓ2t(ψ^ℓ(i)−ψ^ℓ(j))2.\widehat{d}_t(i,j)^2 = \sum_{\ell\geq1}\widehat{\lambda}_\ell^{2t}\left(\widehat{\psi}_\ell(i)-\widehat{\psi}_\ell(j)\right)^2.

and this is exactly the diffusion map embedding of [2]. The factor λ^ℓt\widehat{\lambda}_\ell^t makes tt a scale parameter. Small tt keeps many modes and sees local structure, while large tt kills higher modes and collapses the geometry toward the stationary distribution.

From a statistical viewpoint, spectral clustering and diffusion maps are two faces of the same operator approximation problem. The population operator PP is built from the kernel and the density, and the empirical operator PnP_n is built from the sample. When PnP_n approximates PP in an appropriate sense, the leading eigenvalues and eigenfunctions approximate their population counterparts [15 GTS20]. This implies stability of diffusion embeddings and of spectral clustering objectives. In our paper we use this pipeline differently. We do not aim to recover a partition at one scale. We instead run single linkage on diffusion distance and we recover a full hierarchy, and we connect its topology to the density cluster tree through metastability.

Diffusion hierarchy and meeting

Fix t∈Nt \in\mathbb{N}. Define the diffusion hierarchy TtdiffT_t^{\mathrm{diff}} as the single-linkage dendrogram built on (M,dt)(M,d_t). Its merge-height function is denoted mt(x,y)m_t(x,y). It is defined as the smallest threshold τ\tau at which xx and yy become connected in the graph with edges {(u,v):dt(u,v)≤τ}\{(u,v):d_t(u,v)\leq\tau\}. One can implement this on an ε\varepsilon-net or on a sample. In the population statements we only need the induced ordering of connectivity events as the threshold increases.

We say two trees meet if one merge-height function is a strictly increasing transform of the other.

Definition 4 (Meeting by monotone calibration). We say TtdiffT_t^{\mathrm{diff}} meets TfT_f if there exists a strictly increasing function gt:[0,∞)→[0,∞)g_t:[0,\infty)\to[0,\infty) such that

mt(x,y)=gt(mf(x,y))for all x,y∈M.m_t(x,y)=g_t\left(m_f(x,y)\right) \qquad\text{for all }x,y\in M.

This definition is strong. It says the two merge trees are isomorphic. Only the height scale changes by gtg_t.

Metastability interface

The meeting mechanism is metastability. For each density level λ\lambda and each component C∈C(λ)C\in\mathcal{C}(\lambda), we need fast mixing inside CC and slow leakage out of CC. Both are measured at diffusion time tt. We define two quantities. The leakage is

αout(λ)=sup⁡C∈C(λ)sup⁡x∈CP(x,Cc).\alpha_{\mathrm{out}}(\lambda)=\sup_{C\in\mathcal{C}(\lambda)}\sup_{x\in C}P(x,C^c).

The mixing rate is defined using a comparison chain supported on CC. A convenient device is a reflected or dominating chain PCP_C that stays in CC and dominates the restriction of PP to CC.

Definition 5 (Dominating in-component chain). Fix a measurable set CC with πq(C)>0\pi_q(C) > 0. A Markov operator PCP_C supported on CC is called dominating if for every x∈Cx \in C and every measurable B⊂CB \subset C we have PC(x,B)≥P(x,B)P_C(x, B) \ge P(x, B), and PCP_C is reversible with stationary measure πq(⋅∣C)\pi_q(\cdot\mid C).

Dominating chains exist in standard settings by reflecting mass that would exit CC back into CC. In this paper we treat existence as part of the assumption interface.

Definition 6 (Topological Meeting Condition). We say (f,P)(f, P) satisfies TMC if there exist functions γin(⋅)>0\gamma_{\mathrm{in}}(\cdot) > 0 and αout(⋅)∈(0,1)\alpha_{\mathrm{out}}(\cdot) \in(0, 1) and functions tmin⁡(⋅),tmax⁡(⋅):[0,∞)→Nt_{\min}(\cdot), t_{\max}(\cdot) : [0, \infty) \to\mathbb{N} such that for every level λ\lambda and every component C∈C(λ)C \in\mathcal{C}(\lambda) the following hold.

(TMC1) There exists a dominating chain PCP_C on CC whose spectral gap in L2(πq(⋅∣C))L^2(\pi_q(\cdot\mid C)) is at least γin(λ)\gamma_{\mathrm{in}}(\lambda).

Equivalently, if λ1(C)\lambda_1(C) is the second-largest eigenvalue of PCP_C, then 1−λ1(C)≥γin(λ)1 - \lambda_1(C) \ge\gamma_{\mathrm{in}}(\lambda).

(TMC2) Leakage from CC under PP is small and satisfies sup⁡x∈CP(x,Cc)≤αout(λ)\sup_{x \in C} P(x, C^c) \le\alpha_{\mathrm{out}}(\lambda).

(TMC3) There is a metastable time window. For every λ\lambda we have tmin⁡(λ)≤tmax⁡(λ)t_{\min}(\lambda) \le t_{\max}(\lambda). For all t∈[tmin⁡(λ),tmax⁡(λ)]t \in[t_{\min}(\lambda), t_{\max}(\lambda)] one has tγin(λ)≫1t\gamma_{\mathrm{in}}(\lambda) \gg1 and tαout(λ)≪1t\alpha_{\mathrm{out}}(\lambda) \ll1. Also, along the tree order, higher density levels should not require larger times. The map λ↦tmin⁡(λ)\lambda\mapsto t_{\min}(\lambda) is nonincreasing and the map λ↦tmax⁡(λ)\lambda\mapsto t_{\max}(\lambda) is nondecreasing.

Condition (TMC3) formalizes the slogan mix before you leak, uniformly along the hierarchy.

Population meeting

The population meeting theorem is proved by turning metastability into two metric inequalities. Inside each density component, diffusion distance becomes small because the chain mixes fast. Across different components, diffusion distance stays large because the chain has trouble crossing the low-density valley. If these two regimes are separated by a gap, then a single linkage threshold can recover the correct connected components at each merge level.

Within and between bounds

We first control diffusion distance inside one component. The idea is to compare the true chain PP with a chain PCP_C that is forced to stay inside CC. The chain PCP_C mixes quickly, so the tt-step transition densities from any two starting points become close. The true chain differs from PCP_C only when it exits CC, and this is controlled by the one-step leakage.

Lemma 2 (Within-component contraction). Fix λ≥0\lambda\ge0 and let C∈C(λ)C \in\mathcal{C}(\lambda). Assume PCP_C is a dominating chain on CC with spectral gap at least γ=γin(λ)\gamma= \gamma_{\mathrm{in}}(\lambda). Assume sup⁡x∈CP(x,Cc)≤η\sup_{x \in C} P(x, C^c) \le\eta with η≤αout(λ)\eta\le\alpha_{\mathrm{out}}(\lambda). Let rt,x=dp(t)(x,⋅)dπqr_{t,x} = \frac{d p^{(t)}(x, \cdot)}{d\pi_q} and let rt,xC=dpC(t)(x,⋅)dπqr^C_{t,x} = \frac{d p_C^{(t)}(x, \cdot)}{d\pi_q} be the corresponding tt-step transition densities for PP and PCP_C with respect to πq\pi_q, with rt,xCr^C_{t,x} extended by zero outside CC. Then for all t∈Nt \in\mathbb{N} and all x,y∈Cx,y \in C,

dt(x,y)=∥rt,x−rt,y∥L2(πq)≤2(1−γ)tπq(C)+4tηπq(C).(1)d_t(x,y) = \lVert r_{t,x} - r_{t,y} \rVert_{L^2(\pi_q)} \le\frac{2(1-\gamma)^t}{\sqrt{\pi_q(C)}} + \frac{4t\eta}{\sqrt{\pi_q(C)}}. \tag*{(1)}

Proof. We split the difference into an in-component mixing part and two exit-error parts

∥rt,x−rt,y∥2≤∥rt,x−rt,xC∥2+∥rt,xC−rt,yC∥2+∥rt,yC−rt,y∥2.\lVert r_{t,x} - r_{t,y} \rVert_2 \le\lVert r_{t,x} - r^C_{t,x} \rVert_2 + \lVert r^C_{t,x} - r^C_{t,y} \rVert_2 + \lVert r^C_{t,y} - r_{t,y} \rVert_2.

We bound the middle term using the spectral gap of PCP_C. Since PCP_C is reversible with stationary measure πq(⋅∣C)\pi_q(\cdot\mid C), it is self-adjoint on L2(πq(⋅∣C))L^2(\pi_q(\cdot\mid C)). Let ΠC\Pi_C be the averaging operator on CC given by (ΠCh)(z)=∫Ch(u) dπq(u∣C)(\Pi_C h)(z) = \int_C h(u)\,d\pi_q(u \mid C). The spectral gap assumption implies the standard L2L^2 contraction on mean-zero functions

∥PCth−ΠCh∥L2(πq(⋅∣C))≤(1−γ)t∥h−ΠCh∥L2(πq(⋅∣C)).\lVert P_C^t h - \Pi_C h \rVert_{L^2(\pi_q(\cdot\mid C))} \le(1-\gamma)^t \lVert h - \Pi_C h \rVert_{L^2(\pi_q(\cdot\mid C))}.

Apply this with h(⋅)=r0,xC(⋅)h(\cdot) = r^C_{0,x}(\cdot) interpreted in the usual way through tt-step densities. A clean way is to work directly with tt-step densities. The function rt,xCr^C_{t,x} is a density on CC with respect to πq(⋅∣C)\pi_q(\cdot\mid C) scaled by the factor πq(C)−1\pi_q(C)^{-1}. The difference rt,xC−rt,yCr^C_{t,x} - r^C_{t,y} has integral 00 over CC. Therefore

∥rt,xC−rt,yC∥L2(πq)=πq(C)∥rt,xC−rt,yC∥L2(πq(⋅∣C))≤πq(C)(1−γ)t∥r0,xC−r0,yC∥L2(πq(⋅∣C)).\lVert r^C_{t,x} - r^C_{t,y} \rVert_{L^2(\pi_q)} = \sqrt{\pi_q(C)} \lVert r^C_{t,x} - r^C_{t,y} \rVert_{L^2(\pi_q(\cdot\mid C))} \le\sqrt{\pi_q(C)}(1-\gamma)^t \lVert r^C_{0,x} - r^C_{0,y} \rVert_{L^2(\pi_q(\cdot\mid C))}.

For the last norm we use a crude bound that is sufficient for our goal and matches the scaling in the statement. For two probability densities a,ba,b on CC with respect to πq(⋅∣C)\pi_q(\cdot\mid C), one has

∥a−b∥L2(πq(⋅∣C))≤∥a∥L2(πq(⋅∣C))+∥b∥L2(πq(⋅∣C))≤2πq(C).\lVert a-b\rVert_{L^2(\pi_q(\cdot\mid C))}\leq\lVert a\rVert_{L^2(\pi_q(\cdot\mid C))}+\lVert b\rVert_{L^2(\pi_q(\cdot\mid C))}\leq\frac{2}{\sqrt{\pi_q(C)}}.

This bound holds when the one-step kernel has bounded density relative to πq(⋅∣C)\pi_q(\cdot\mid C), which is the case in the standard compact kernel setting that we use later in the geometric section. With this bound we get

∥rt,xC−rt,yC∥L2(πq)≤2(1−γ)tπq(C).\lVert r^C_{t,x}-r^C_{t,y}\rVert_{L^2(\pi_q)}\leq\frac{2(1-\gamma)^t}{\sqrt{\pi_q(C)}}.

It remains to bound the exit-error terms. We show that ∥rt,x−rt,xC∥L2(πq)≤2tηπq(C)\lVert r_{t,x}-r^C_{t,x}\rVert_{L^2(\pi_q)}\leq\frac{2t\eta}{\sqrt{\pi_q(C)}} and similarly for yy.

Let A=CA=C. Since PP can leave CC in one step with probability at most η\eta from any point of CC, a union bound gives

p(t)(x,Cc)≤tηfor all x∈C.p^{(t)}(x,C^c)\leq t\eta\qquad\text{for all }x\in C.

The dominating chain stays inside CC, so pC(t)(x,Cc)=0p_C^{(t)}(x,C^c)=0. Therefore the signed measure νt,x=p(t)(x,⋅)−pC(t)(x,⋅)\nu_{t,x}=p^{(t)}(x,\cdot)-p_C^{(t)}(x,\cdot) has total variation at most 2tη2t\eta. Write gt,x=rt,x−rt,xCg_{t,x}=r_{t,x}-r^C_{t,x}, which is the Radon–Nikodym derivative of νt,x\nu_{t,x} with respect to πq\pi_q. The function gt,xg_{t,x} integrates to 00 and its L1(πq)L^1(\pi_q) norm equals ∥νt,x∥TV≤2tη\lVert\nu_{t,x}\rVert_{\mathrm{TV}}\leq2t\eta. Also, gt,xg_{t,x} is supported on C∪CcC\cup C^c, and we can use the inequality ∥g∥2≤∥g∥1/πq(C)\lVert g\rVert_2\leq\lVert g\rVert_1/\sqrt{\pi_q(C)} for functions supported on a set of πq\pi_q-mass at least πq(C)\pi_q(C), which here is enough because the part of gt,xg_{t,x} inside CC carries all the mass of pC(t)(x,⋅)p^{(t)}_C(x,\cdot) while the missing mass is at most tηt\eta. This yields

∥rt,x−rt,xC∥L2(πq)=∥gt,x∥2≤∥gt,x∥1πq(C)≤2tηπq(C).\lVert r_{t,x}-r^C_{t,x}\rVert_{L^2(\pi_q)}=\lVert g_{t,x}\rVert_2\leq\frac{\lVert g_{t,x}\rVert_1}{\sqrt{\pi_q(C)}}\leq\frac{2t\eta}{\sqrt{\pi_q(C)}}.

Doing the same for yy and combining the three bounds gives

dt(x,y)≤2(1−γ)tπq(C)+4tηπq(C).d_t(x,y)\leq\frac{2(1-\gamma)^t}{\sqrt{\pi_q(C)}}+\frac{4t\eta}{\sqrt{\pi_q(C)}}.

This lemma is the inside part of the story. It tells us that, in a metastable time window, diffusion distance collapses each density component into a small metric cluster. This is exactly what single linkage needs, because it will connect points inside a component at a small threshold that can be chosen uniformly over the component.

We now control diffusion distance across two different components. The idea is to use one test set AA that contains one component and the valley in front of it. Starting from the component, the chain stays in AA with high probability for tt steps. Starting from the other component, the chain enters AA with small probability for tt steps. This difference of probabilities gives a lower bound on the L2L^2 distance by Cauchy–Schwarz.

Lemma 3 (Between-component separation). Fix λ≥0\lambda\geq0. Let C,C′∈C(λ)C,C'\in\mathcal{C}(\lambda) be distinct components. Assume there exists a measurable set VV such that A=C∪VA=C\cup V is measurable, C′∩A=∅C'\cap A=\varnothing, and the following two bounds hold for some η∈(0,1)\eta\in(0,1)

sup⁡x∈AP(x,Ac)≤ηandsup⁡x∈AcP(x,A)≤η.\sup_{x\in A}P(x,A^c)\leq\eta\qquad\text{and}\qquad\sup_{x\in A^c}P(x,A)\leq\eta.

*Assume also that tη≤1/4t\eta\leq1/4. Then for all x∈Cx\in C and all y∈C′y\in C',

dt(x,y)≥1−4tηπq(A).d_t(x,y)\geq\frac{1-4t\eta}{\sqrt{\pi_q(A)}}.

Proof. Fix x∈C⊆Ax\in C\subseteq A and y∈C′⊆Acy\in C'\subseteq A^c. We first bound p(t)(x,A)p^{(t)}(x,A) from below. Consider the event that the chain starting from xx leaves AA at some step in {1,…,t}\{1,\ldots,t\}. By a union bound and the first assumption,

Px(∃s≤t with Xs∈Ac)≤∑s=0t−1sup⁡z∈AP(z,Ac)≤tη.\mathbb{P}_x(\exists s\leq t\text{ with }X_s\in A^c)\leq\sum_{s=0}^{t-1}\sup_{z\in A}P(z,A^c)\leq t\eta.

Therefore

p(t)(x,A)=Px(Xt∈A)≥1−tη.p^{(t)}(x,A)=\mathbb{P}_{x}(X_t\in A)\ge1-t\eta.

Next we bound p(t)(y,A)p^{(t)}(y,A) from above. For the chain to be in AA at time tt, it must enter AA at some step s∈{1,…,t}s\in\{1,\ldots,t\}. By another union bound and the second assumption,

p(t)(y,A)=Py(Xt∈A)≤Py(∃s≤t with Xs∈A)≤∑s=0t−1sup⁡z∈AcP(z,A)≤tη.p^{(t)}(y,A)=\mathbb{P}_{y}(X_t\in A)\le\mathbb{P}_{y}(\exists s\le t\text{ with }X_s\in A)\le\sum_{s=0}^{t-1}\sup_{z\in A^c}P(z,A)\le t\eta.

Subtracting the bounds gives

p(t)(x,A)−p(t)(y,A)≥1−2tη.p^{(t)}(x,A)-p^{(t)}(y,A)\ge1-2t\eta.

Now write rt,x=dp(t)(x,⋅)/dπqr_{t,x}=dp^{(t)}(x,\cdot)/d\pi_q and rt,y=dp(t)(y,⋅)/dπqr_{t,y}=dp^{(t)}(y,\cdot)/d\pi_q. Then

p(t)(x,A)−p(t)(y,A)=∫A(rt,x−rt,y) dπq.p^{(t)}(x,A)-p^{(t)}(y,A)=\int_A(r_{t,x}-r_{t,y})\,d\pi_q.

Apply Cauchy–Schwarz on AA

∫A(rt,x−rt,y) dπq≤∥rt,x−rt,y∥L2(πq)⋅∥1A∥L2(πq)=dt(x,y)πq(A).\int_A(r_{t,x}-r_{t,y})\,d\pi_q\le\|r_{t,x}-r_{t,y}\|_{L^2(\pi_q)}\cdot\|\mathbf{1}_A\|_{L^2(\pi_q)}=d_t(x,y)\sqrt{\pi_q(A)}.

Therefore

dt(x,y)≥1−2tηπq(A).d_t(x,y)\ge\frac{1-2t\eta}{\sqrt{\pi_q(A)}}.

Finally we replace 1−2tη1-2t\eta by 1−4tη1-4t\eta which is weaker but convenient in later uniform arguments, since tη≤1/4t\eta\le1/4 implies 1−2tη≥(1−4tη)1-2t\eta\ge(1-4t\eta).

This lemma gives the outside part. It says that if there is a region AA around one component that is hard to exit and also hard to enter, then diffusion distance separates that component from the other components at time tt. In the full meeting theorem we use this with AA built from one density component plus its valley. The main role of the lemma is to give a uniform lower bound that can beat the uniform upper bound from Lemma 2.

Meeting theorem

We now combine the two inequalities into the population meeting theorem. The high-level picture is a threshold sandwich. At each relevant level λ\lambda, all within-component diffusion distances are below a number U(λ,t)U(\lambda,t). All between-component diffusion distances are above a number V(λ,t)V(\lambda,t). If U(λ,t)<V(λ,t)U(\lambda,t)<V(\lambda,t), then any threshold τ\tau in between recovers exactly the connected components at level λ\lambda. If this holds at every merge level and the tree has only finitely many merge levels, we can choose one tt that works for all of them.

Theorem 1 (Population meeting under TMC). Assume (f,P)(f,P) *satisfies TMC. Assume also that the density cluster tree has finitely many critical merge levels. Then there exists an integer time tt such that for all critical levels λ\lambda one has t∈[tmin⁡(λ),tmax⁡(λ)]t\in[t_{\min}(\lambda),t_{\max}(\lambda)]. For this tt there exists a strictly increasing function gtg_t such that

mt(x,y)=gt(mf(x,y))for all x,y∈M.m_t(x,y)=g_t(m_f(x,y))\qquad\text{for all }x,y\in M.

Hence TtdiffT_t^{\mathrm{diff}} and TfT_f are isomorphic as merge trees.

Proof. Let Λcrit={λ1>λ2>⋯>λK}\Lambda_{\mathrm{crit}}=\{\lambda_1>\lambda_2>\cdots>\lambda_K\} be the finite set of critical merge levels of the density cluster tree. By TMC3, for each λk\lambda_k there is a nonempty integer interval Ik=[tmin⁡(λk),tmax⁡(λk)]I_k=[t_{\min}(\lambda_k),t_{\max}(\lambda_k)] where mixing dominates leakage at level λk\lambda_k. The monotonicity in TMC3 implies that these intervals are nested in the sense that higher levels do not shift the window to larger times. Since Λcrit\Lambda_{\mathrm{crit}} is finite and the windows are nonempty, we can pick a single integer time

t∈⋂k=1KIk.t\in\bigcap_{k=1}^{K}I_k.

Fix this tt for the rest of the proof.

For each critical level λ=λk\lambda=\lambda_k, we construct a threshold τ(λ)\tau(\lambda) that makes diffusion connectivity match density connectivity on LλL_\lambda. Consider the collection of components C(λ)\mathcal{C}(\lambda). For each C∈C(λ)C\in\mathcal{C}(\lambda), Lemma 2 gives a uniform bound

sup⁡x,y∈Cdt(x,y)≤UC(λ,t)withUC(λ,t)=2(1−γin(λ))tπq(C)+4tαout(λ)πq(C).\sup_{x,y\in C}d_t(x,y)\le U_C(\lambda,t)\quad\text{with}\quad U_C(\lambda,t)=\frac{2(1-\gamma_{\mathrm{in}}(\lambda))^t}{\sqrt{\pi_q(C)}}+\frac{4t\alpha_{\mathrm{out}}(\lambda)}{\sqrt{\pi_q(C)}}.

Let

U(λ,t)=sup⁡C∈C(λ)UC(λ,t).U(\lambda,t)=\sup_{C\in\mathcal{C}(\lambda)}U_C(\lambda,t).

Next we lower bound diffusion distances between distinct components. Fix two distinct components C,C′∈C(λ)C,C'\in\mathcal{C}(\lambda). Since CC and C′C' are distinct connected components of LλL_\lambda, any path from CC to C′C' must leave LλL_\lambda. This gives a natural valley region in MM between them. In the TMC interface we encode this by assuming that for each component CC there exists a measurable set VC(λ)V_C(\lambda) such that AC(λ)=C∪VC(λ)A_C(\lambda)=C\cup V_C(\lambda) satisfies the two-sided bottleneck condition in Lemma 3 with parameter η=αout(λ)\eta=\alpha_{\mathrm{out}}(\lambda). Applying Lemma 3 gives, for all x∈Cx\in C and y∈C′y\in C',

dt(x,y)≥VC(λ,t)withVC(λ,t)=1−4tαout(λ)πq(AC(λ)).d_t(x,y)\ge V_C(\lambda,t)\quad\text{with}\quad V_C(\lambda,t)=\frac{1-4t\alpha_{\mathrm{out}}(\lambda)}{\sqrt{\pi_q(A_C(\lambda))}}.

Let

V(λ,t)=inf⁡C∈C(λ)VC(λ,t).V(\lambda,t)=\inf_{C\in\mathcal{C}(\lambda)}V_C(\lambda,t).

Because tγin(λ)≫1t\gamma_{\mathrm{in}}(\lambda)\gg1 and tαout(λ)≪1t\alpha_{\mathrm{out}}(\lambda)\ll1 for all λ∈Λcrit\lambda\in\Lambda_{\mathrm{crit}} and because the constants depend only on λ\lambda, we can ensure that for every critical level

U(λ,t)<V(λ,t).U(\lambda,t)<V(\lambda,t).

This is the quantitative separation needed for topology. Now fix a critical level λ\lambda. Choose any threshold τ(λ)\tau(\lambda) such that

U(λ,t)<τ(λ)<V(λ,t).U(\lambda,t)<\tau(\lambda)<V(\lambda,t).

Consider the graph on LλL_\lambda with edges {(u,v)∈Lλ2∣dt(u,v)≤τ(λ)}\{(u,v)\in L_\lambda^2\mid d_t(u,v)\le\tau(\lambda)\}. The inequality dt(u,v)≤U(λ,t)d_t(u,v)\le U(\lambda,t) for u,vu,v in the same component implies that each density component C∈C(λ)C\in\mathcal{C}(\lambda) becomes connected inside this graph. The inequality dt(u,v)≥V(λ,t)d_t(u,v)\ge V(\lambda,t) for u,vu,v in different components implies that there are no edges between different components. Therefore the connected components of this threshold graph are exactly C(λ)\mathcal{C}(\lambda).

We have proved that for each critical level λ\lambda, diffusion thresholding at τ(λ)\tau(\lambda) recovers exactly the same component partition as the density superlevel set at level λ\lambda. This implies that the merge trees are the same, up to a monotone rescaling of heights. To formalize this, define gtg_t on critical levels by gt(λ)=τ(λ)g_t(\lambda)=\tau(\lambda). Extend gtg_t to all of [0,∞)[0,\infty) as a strictly increasing function, for example by linear interpolation between consecutive critical levels and any strictly increasing continuation below λK\lambda_K.

Finally fix any x,y∈Mx,y\in M and let λ⋆=mf(x,y)\lambda^\star=m_f(x,y). By definition, for every λ<λ⋆\lambda<\lambda^\star the points are connected inside LλL_\lambda, and for every λ>λ⋆\lambda>\lambda^\star they are not connected inside LλL_\lambda. Since connectivity agrees at all critical levels and changes only at critical levels, the same statement holds when we restrict λ\lambda to Λcrit\Lambda_{\mathrm{crit}}. The diffusion threshold graphs at thresholds τ(λ)=gt(λ)\tau(\lambda)=g_t(\lambda) have exactly the same connectivity at these critical levels. Therefore the largest height where xx and yy are connected in the diffusion hierarchy is exactly gt(λ⋆)g_t(\lambda^\star). This is the identity

mt(x,y)=gt(mf(x,y)).m_t(x,y)=g_t(m_f(x,y)).

This theorem is the main conceptual result at population level. It tells us that diffusion time is not only a scale parameter for geometry. In a metastable window it becomes a topological scale parameter, because it preserves the merge tree of density level sets. This is the bridge that lets us interpret a spectral construction as an estimator of a topological object.

The proof also shows why the calibration gtg_t is necessary. Even when the two trees have the same shape, the heights live in different units. Density heights are values of ff, while diffusion heights are thresholds on dtd_t. The theorem says that after a monotone change of units, the two merge-height functions coincide.

Finite-sample theory

We now turn to data. The algorithm is standard. We build a kk-NN graph, define a random walk, compute diffusion embeddings using the leading eigenvectors, compute pairwise diffusion distances, and then run single linkage which is equivalent to an MST computation. The main statistical point is modular. If empirical diffusion distances are uniformly close to population diffusion distances on the sample, then the full dendrogram is uniformly close in merge distortion.

Estimator

Let X1,…,Xn∼fX_1,\ldots,X_n \sim f i.i.d. Build the symmetrized kk-NN graph on {Xi}i=1n\{X_i\}_{i=1}^n. Define weights Wij=Kσ(Xi,Xj)W_{ij}=K_\sigma(X_i,X_j) if (i,j)(i,j) is an edge and Wij=0W_{ij}=0 otherwise. Define degrees Dii=∑jWijD_{ii}=\sum_j W_{ij} and the random walk matrix Pn=D−1WP_n=D^{-1}W. Let (λ^ℓ,ψ^ℓ)ℓ≥0(\hat{\lambda}_\ell,\hat{\psi}_\ell)_{\ell\geq0} be eigenpairs of PnP_n with λ^0=1\hat{\lambda}_0=1 and ψ^0≡1\hat{\psi}_0\equiv1. For a truncation dimension mm, define the diffusion embedding

Φt(i)=(λ^1tψ^1(i),…,λ^mtψ^m(i))∈Rm,d^t(i,j)=∥Φt(i)−Φt(j)∥2.\Phi_t(i)=\left(\hat{\lambda}_1^t\hat{\psi}_1(i),\ldots,\hat{\lambda}_m^t\hat{\psi}_m(i)\right)\in\mathbb{R}^m,\qquad\hat{d}_t(i,j)=\lVert\Phi_t(i)-\Phi_t(j)\rVert_2.

Run single linkage on the dissimilarity matrix (d^t(i,j))i,j(\hat{d}_t(i,j))_{i,j} and denote the resulting merge heights by m^t\hat{m}_t.

Stability of single linkage

The next lemma is purely algorithmic and it is the reason merge distortion is the right metric here. Single linkage merge heights are bottleneck values along best paths. If we perturb each edge length by at most η\eta, then every path bottleneck changes by at most η\eta, and taking the best path cannot increase this. So the entire merge-height function changes by at most η\eta.

Lemma 4 (Single-linkage stability in merge distortion). Let SS be finite and let d,d′d,d' be symmetric dissimilarities on SS with d(x,x)=d′(x,x)=0d(x,x)=d'(x,x)=0. If

sup⁡x,y∈S∣d(x,y)−d′(x,y)∣≤η,\sup_{x,y\in S}\lvert d(x,y)-d'(x,y)\rvert\leq\eta,

then the single-linkage merge-height functions mdm_d and md′m_{d'} satisfy

dMD(md,md′)≤η.d_{\mathrm{MD}}(m_d,m_{d'})\leq\eta.

Proof. Fix x,y∈Sx,y\in S. For a path π=(v0=x,v1,…,vk=y)\pi=(v_0=x,v_1,\ldots,v_k=y) define its bottleneck under dd by

Bd(π)=max⁡0≤j<kd(vj,vj+1).B_d(\pi)=\max_{0\leq j<k}d(v_j,v_{j+1}).

A standard characterization of single linkage is

md(x,y)=inf⁡π:x⇝yBd(π),m_d(x,y)=\inf_{\pi:x\rightsquigarrow y}B_d(\pi),

where the infimum is over all finite paths in the complete graph on SS. Assume sup⁡u,v∣d(u,v)−d′(u,v)∣≤η\sup_{u,v}\lvert d(u,v)-d'(u,v)\rvert\leq\eta. Then for every path π\pi,

∣Bd(π)−Bd′(π)∣≤max⁡j∣d(vj,vj+1)−d′(vj,vj+1)∣≤η.\lvert B_d(\pi)-B_{d'}(\pi)\rvert\leq\max_j\lvert d(v_j,v_{j+1})-d'(v_j,v_{j+1})\rvert\leq\eta.

In particular, Bd′(π)≤Bd(π)+ηB_{d'}(\pi)\leq B_d(\pi)+\eta for all π\pi. Taking infimum over π\pi gives

md′(x,y)≤md(x,y)+η.m_{d'}(x,y)\leq m_d(x,y)+\eta.

By symmetry, swapping dd and d′d' gives md(x,y)≤md′(x,y)+ηm_d(x,y)\leq m_{d'}(x,y)+\eta. Therefore

∣md(x,y)−md′(x,y)∣≤η.\lvert m_d(x,y)-m_{d'}(x,y)\rvert\leq\eta.

Taking the supremum over x,yx,y yields dMD(md,md′)≤ηd_{\mathrm{MD}}(m_d,m_{d'})\leq\eta.

This lemma turns a hard hierarchical object into a simple uniform bound on pairwise distances. It is the core reduction used in the finite-sample theorem. We do not need to control the MST directly. We only need to control the diffusion distance matrix uniformly. It also matches our bigger goal. The population theorem says mt=gt∘mfm_t=g_t\circ m_f. The stability lemma says that if d^t\hat{d}_t is close to dtd_t, then m^t\hat{m}_t is close to mtm_t. Combining them gives a direct path from graph spectral approximation to topological recovery.

Merge-distortion theorem

We now state the statistical result. It is modular on purpose. The theorem assumes a high-probability uniform approximation of diffusion distances. Many existing graph Laplacian results can be used to prove such a bound under geometric assumptions [15 GTS20]. Once we have it, the dendrogram guarantee is immediate by Lemma 4.

Theorem 2 (Finite-sample merge distortion). Fix a time tt and assume the population meeting theorem (Theorem 1) holds at this tt with calibration gtg_t. Assume that with probability at least 1−δ1-\delta,

sup⁡i,j∈[n]∣d^t(i,j)−dt(Xi,Xj)∣≤ηn.\sup_{i,j\in[n]} \left|\hat{d}_t(i,j)-d_t(X_i,X_j)\right| \le\eta_n.

Let mt(n)m_t^{(n)} be the restriction of the population diffusion merge heights mtm_t to Sn={X1,…,Xn}S_n=\{X_1,\ldots,X_n\}. Then on the same event,

dMD(m^t,mt(n))≤ηn.d_{\mathrm{MD}}(\hat{m}_t,m_t^{(n)})\le\eta_n.

In addition, if gt−1g_t^{-1} is Lipschitz on the relevant image interval with constant LtL_t, then

dMD(gt−1∘m^t,mf(n))≤Ltηn,d_{\mathrm{MD}}(g_t^{-1}\circ\hat{m}_t,m_f^{(n)})\le L_t\eta_n,

where mf(n)m_f^{(n)} is mfm_f restricted to SnS_n.

Proof. Work on the event

E={sup⁡i,j∈[n]∣d^t(i,j)−dt(Xi,Xj)∣≤ηn}.\mathcal{E}=\left\{\sup_{i,j\in[n]}\left|\hat{d}_t(i,j)-d_t(X_i,X_j)\right|\le\eta_n\right\}.

On E\mathcal{E}, apply Lemma 4 with the finite set S=[n]S=[n], the dissimilarity d(i,j)=dt(Xi,Xj)d(i,j)=d_t(X_i,X_j), and d′(i,j)=d^t(i,j)d'(i,j)=\hat{d}_t(i,j). This gives

dMD(m^t,md)≤ηn,d_{\mathrm{MD}}(\hat{m}_t,m_d)\le\eta_n,

where mdm_d is the single-linkage merge-height function built from d(i,j)=dt(Xi,Xj)d(i,j)=d_t(X_i,X_j). By definition, mdm_d is exactly mtm_t restricted to the sample. Therefore md=mt(n)m_d=m_t^{(n)} and we obtain

dMD(m^t,mt(n))≤ηn.d_{\mathrm{MD}}(\hat{m}_t,m_t^{(n)})\le\eta_n.

For the second claim, use the population meeting identity restricted to the sample

mt(n)=gt∘mf(n).m_t^{(n)}=g_t\circ m_f^{(n)}.

Apply gt−1g_t^{-1} to both sides and write

gt−1∘m^t−mf(n)=(gt−1∘m^t−gt−1∘mt(n))+(gt−1∘mt(n)−mf(n)).g_t^{-1}\circ\hat{m}_t-m_f^{(n)} = \left(g_t^{-1}\circ\hat{m}_t-g_t^{-1}\circ m_t^{(n)}\right) + \left(g_t^{-1}\circ m_t^{(n)}-m_f^{(n)}\right).

The second term is zero. The first term is controlled by the Lipschitz property of gt−1g_t^{-1}. For every pair (i,j)(i,j),

∣gt−1(m^t(i,j))−gt−1(mt(n)(i,j))∣≤Lt∣m^t(i,j)−mt(n)(i,j)∣.\left|g_t^{-1}(\hat{m}_t(i,j))-g_t^{-1}(m_t^{(n)}(i,j))\right| \le L_t\left|\hat{m}_t(i,j)-m_t^{(n)}(i,j)\right|.

Taking the supremum over pairs yields

dMD(gt−1∘m^t,mf(n))≤LtdMD(m^t,mt(n))≤Ltηn.d_{\mathrm{MD}}(g_t^{-1}\circ\hat{m}_t,m_f^{(n)}) \le L_t d_{\mathrm{MD}}(\hat{m}_t,m_t^{(n)}) \le L_t\eta_n.

This theorem is the statistical wrapper around the population meeting theorem. It says that the only genuinely analytic part for data is the approximation of diffusion distances. Once this approximation holds uniformly, the dendrogram converges automatically in merge distortion. It also explains why we prefer to state the result in this modular way. Graph Laplacian approximation has many technical variants, depending on kernel choice, kk-NN graphs, manifolds, and noise models. The hierarchical conclusion does not depend on those details. It only depends on the uniform diffusion-distance error.

Remark 1 (Exact topology under a height margin). If there exists Γ>0\Gamma>0 such that any two distinct merge events in mf(n)m_f^{(n)} differ by at least Γ\Gamma, then whenever Ltηn<Γ/2L_t\eta_n<\Gamma/2, the dendrogram defined by gt−1∘m^tg_t^{-1}\circ\hat{m}_t has exactly the same merge-tree topology as mf(n)m_f^{(n)}. The reason is that the merge-tree topology depends only on the ordering of merge heights, and a merge distortion smaller than Γ/2\Gamma/2 cannot change that ordering.

Geometry and multiscale meeting

TMC is a clean interface but it is abstract. We now give geometric conditions that imply the two needed quantitative ingredients. One ingredient is a lower bound on the spectral gap of an in-component reflected chain. The other ingredient is an upper bound on leakage across the boundary of a component. Both are controlled by regularity of the component and the depth of the density valley separating components.

Geometric meeting condition

We assume now that MM is a compact dd-dimensional C2C^2 Riemannian manifold with geodesic distance ρ\rho and volume measure μ\mu. We fix a localized kernel Kσ(x,y)=exp⁡(−ρ(x,y)2/σ2)K_\sigma(x,y) = \exp(-\rho(x,y)^2/\sigma^2) for small σ\sigma. We state a condition on superlevel components.

Definition 7 (Geometric Meeting Condition). Let Λ\Lambda be a finite set of levels that contains all critical merge levels of the density cluster tree. We say ff satisfies GMC on Λ\Lambda if there exist functions f(λ)>0f(\lambda) > 0, rreach(λ)>0r_{\mathrm{reach}}(\lambda) > 0, vmin⁡(λ)>0v_{\min}(\lambda) > 0, vmax⁡(λ)<∞v_{\max}(\lambda) < \infty, and Δvalley(λ)>0\Delta_{\mathrm{valley}}(\lambda) > 0 such that for every λ∈Λ\lambda\in\Lambda and every C∈C(λ)C \in\mathcal{C}(\lambda) the following hold.

(GMC1) f(x)≥f(λ)f(x) \ge f(\lambda) for all x∈Cx \in C.

(GMC2) CC has reach at least rreach(λ)r_{\mathrm{reach}}(\lambda), meaning the tubular neighborhood projection is well-defined up to radius rreach(λ)r_{\mathrm{reach}}(\lambda). In particular, CC has no arbitrarily thin necks at scales below rreach(λ)r_{\mathrm{reach}}(\lambda).

(GMC3) for every x∈Cx \in C and every 0<r≤rreach(λ)0 < r \le r_{\mathrm{reach}}(\lambda), the local volume satisfies

vmin⁡(λ)rd≤μ(B(x,r)∩C)≤vmax⁡(λ)rd.v_{\min}(\lambda)r^d \le\mu(B(x,r) \cap C) \le v_{\max}(\lambda)r^d.

(GMC4) if C≠C′C \ne C' are distinct components in C(λ)\mathcal{C}(\lambda), then every continuous path from CC to C′C' must pass through a point zz with f(z)≤λ−Δvalley(λ)f(z) \le\lambda- \Delta_{\mathrm{valley}}(\lambda).

GMC says components are thick and regular, and they are separated by real density valleys.

Geometry implies metastability

The next theorem turns GMC into the two quantitative bounds required for TMC. The core idea is that a local kernel walk at scale σ\sigma behaves like a reflected diffusion at scale σ\sigma. Inside a regular set, such a diffusion has spectral gap of order σ2/diam⁡(C)2\sigma^2/\operatorname{diam}(C)^2 up to geometry factors. For leakage, the transition probability across the boundary is suppressed because the kernel multiplies by f(y)f(y), and the valley forces ff to be much smaller outside.

Theorem 3 (GMC implies levelwise metastability). Assume GMC on Λ\Lambda and assume σ\sigma is small enough that KσK_\sigma is effectively supported on ρ(x,y)≲σ\rho(x,y) \lesssim\sigma. Then there exist functions γin(λ)\gamma_{\mathrm{in}}(\lambda) and αout(λ)\alpha_{\mathrm{out}}(\lambda) such that for every λ∈Λ\lambda\in\Lambda and every C∈C(λ)C \in\mathcal{C}(\lambda) there exists a dominating reflected chain PCP_C with spectral gap at least γin(λ)\gamma_{\mathrm{in}}(\lambda), and the leakage satisfies sup⁡x∈CP(x,Cc)≤αout(λ)\sup_{x \in C} P(x,C^c) \le\alpha_{\mathrm{out}}(\lambda). Moreover one can take bounds of the form

γin(λ)≳σ2diam⁡(C)2⋅vmin⁡(λ)vmax⁡(λ)⋅f(λ),αout(λ)≲exp⁡(−cΔvalley(λ)σ2),\gamma_{\mathrm{in}}(\lambda) \gtrsim\frac{\sigma^2}{\operatorname{diam}(C)^2} \cdot\frac{v_{\min}(\lambda)}{v_{\max}(\lambda)} \cdot f(\lambda), \qquad\alpha_{\mathrm{out}}(\lambda) \lesssim\exp\left(-c\frac{\Delta_{\mathrm{valley}}(\lambda)}{\sigma^2}\right),

where constants depend only on kernel regularity and bounded geometry of MM.

Proof. We construct a reflected chain and then bound its spectral gap and the leakage.

Step 1. Construction of a reflected dominating chain. Fix λ∈Λ\lambda\in\Lambda and C∈C(λ)C \in\mathcal{C}(\lambda). Define the kernel mass

q(x)=∫MKσ(x,y)f(y) dμ(y),qC(x)=∫CKσ(x,y)f(y) dμ(y).q(x) = \int_M K_\sigma(x,y)f(y)\,\mathrm{d}\mu(y), \qquad q_C(x) = \int_C K_\sigma(x,y)f(y)\,\mathrm{d}\mu(y).

The original transition is p(x,dy)=Kσ(x,y)f(y)q(x)−1dμ(y)p(x,\mathrm{d}y) = K_\sigma(x,y)f(y)q(x)^{-1}\mathrm{d}\mu(y). We define a reflected transition supported on CC by

pC(x,dy)=Kσ(x,y)f(y)qC(x)1y∈C dμ(y).p_C(x,\mathrm{d}y) = \frac{K_\sigma(x,y)f(y)}{q_C(x)}\mathbf{1}_{y \in C}\,\mathrm{d}\mu(y).

This stays inside CC by construction. It is reversible with respect to πq(⋅∣C)\pi_q(\cdot\mid C) up to a normalization because it is a standard restriction and renormalization of a symmetric kernel. It also dominates the restriction of pp to CC because qC(x)≤q(x)q_C(x) \le q(x) implies

pC(x,B)=1qC(x)∫BKσ(x,y)f(y) dμ(y)≥1q(x)∫BKσ(x,y)f(y) dμ(y)=p(x,B)p_C(x,B) = \frac{1}{q_C(x)} \int_B K_\sigma(x,y)f(y)\,d\mu(y) \ge\frac{1}{q(x)} \int_B K_\sigma(x,y)f(y)\,d\mu(y) = p(x,B)

for every measurable B⊂CB \subset C and every x∈Cx \in C. This gives a dominating chain in the sense of Definition 6.

Step 2. Leakage bound. For x∈Cx \in C we have

P(x,Cc)=∫CcKσ(x,y)f(y)q(x) dμ(y)=∫CcKσ(x,y)f(y) dμ(y)∫MKσ(x,y)f(y) dμ(y).P(x,C^c) = \int_{C^c} \frac{K_\sigma(x,y)f(y)}{q(x)}\,d\mu(y) = \frac{\int_{C^c} K_\sigma(x,y)f(y)\,d\mu(y)}{\int_M K_\sigma(x,y)f(y)\,d\mu(y)}.

We lower bound the denominator using the mass inside a local ball. Fix r≍σr \asymp\sigma small enough so that B(x,r)⊆CB(x,r) \subseteq C for points xx that are at distance at least rr from ∂C\partial C. For boundary points we use reach to say that B(x,r)∩CB(x,r) \cap C still has volume at least a constant fraction of rdr^d. By GMC, on CC we have f≥f(λ)f \ge f(\lambda). Also Kσ(x,y)≥exp⁡(−r2/σ2)K_\sigma(x,y) \ge\exp(-r^2/\sigma^2) on ρ(x,y)≤r\rho(x,y) \le r. Therefore

q(x)≥∫B(x,r)∩CKσ(x,y)f(y) dμ(y)≥exp⁡(−r2/σ2)f(λ)μ(B(x,r)∩C)≳f(λ)vmin⁡(λ)rd.q(x) \ge\int_{B(x,r)\cap C} K_\sigma(x,y)f(y)\,d\mu(y) \ge\exp(-r^2/\sigma^2)f(\lambda)\mu(B(x,r)\cap C) \gtrsim f(\lambda)v_{\min}(\lambda)r^d.

We upper bound the numerator using the valley depth. Any point yy that contributes to leaving CC must be in a region that is connected to another component only through values of ff at most λ−Δvalley(λ)\lambda-\Delta_{\mathrm{valley}}(\lambda). In particular, outside CC near the boundary of CC there exist regions where ff is at most λ−Δvalley(λ)\lambda-\Delta_{\mathrm{valley}}(\lambda), and the kernel is localized at scale σ\sigma, so the main contribution to the numerator comes from such nearby points. Thus

∫CcKσ(x,y)f(y) dμ(y)≤(λ−Δvalley(λ))∫CcKσ(x,y) dμ(y).\int_{C^c} K_\sigma(x,y)f(y)\,d\mu(y) \le\bigl(\lambda-\Delta_{\mathrm{valley}}(\lambda)\bigr)\int_{C^c} K_\sigma(x,y)\,d\mu(y).

For a Gaussian kernel on a manifold of bounded geometry, the tail mass ∫ρ(x,y)≥rKσ(x,y) dμ(y)\int_{\rho(x,y)\ge r} K_\sigma(x,y)\,d\mu(y) is at most exp⁡(−cr2/σ2)\exp(-cr^2/\sigma^2) times a polynomial factor. Choosing r≍σr \asymp\sigma gives a constant bound on the kernel mass outside the local ball. Combining with the denominator lower bound yields

P(x,Cc)≲λ−Δvalley(λ)f(λ)⋅exp⁡(−cΔvalley(λ)σ2).P(x,C^c) \lesssim\frac{\lambda-\Delta_{\mathrm{valley}}(\lambda)}{f(\lambda)}\cdot\exp\left(-c\frac{\Delta_{\mathrm{valley}}(\lambda)}{\sigma^2}\right).

Absorbing the bounded prefactor into constants gives the claimed exponential-type leakage bound

αout(λ)≲exp⁡(−cΔvalley(λ)σ2).\alpha_{\mathrm{out}}(\lambda) \lesssim\exp\left(-c\frac{\Delta_{\mathrm{valley}}(\lambda)}{\sigma^2}\right).

Step 3. Spectral gap lower bound for the reflected chain. For a reversible Markov operator, the spectral gap can be written using the Rayleigh quotient

γ(PC)=inf⁡h∈L2(πq(⋅∣C))∫hdπq(⋅∣C)=0EC(h,h)Var⁡πq(⋅∣C)(h).\gamma(P_C) = \inf_{\substack{h\in L^2(\pi_q(\cdot\mid C))\\ \int h\,d\pi_q(\cdot\mid C)=0}} \frac{\mathcal{E}_C(h,h)}{\operatorname{Var}_{\pi_q(\cdot\mid C)}(h)}.

where the Dirichlet form is

EC(h,h)=12∫C∫C(h(x)−h(y))2pC(x,dy) dπq(x∣C).\mathcal{E}_C(h,h) = \frac{1}{2}\int_C\int_C (h(x)-h(y))^2p_C(x,dy)\,d\pi_q(x\mid C).

For the localized Gaussian kernel and small σ\sigma, the chain PCP_C behaves like a local averaging operator at scale σ\sigma. Standard kernel calculations on manifolds show that EC(h,h)\mathcal{E}_C(h,h) controls an energy of the form σ2∫C∥∇h∥2 dπq(⋅∣C)\sigma^2\int_C \lVert\nabla h\rVert^2\,d\pi_q(\cdot\mid C) up to constants depending on kernel regularity and geometry. On the other hand, GMC gives a Poincaré inequality on CC at scale comparable to diam⁡(C)\operatorname{diam}(C). In its simplest form it says

Var⁡πq(⋅∣C)(h)≲diam⁡(C)2⋅vmax⁡(λ)vmin⁡(λ)⋅1f(λ)∫C∥∇h∥2 dπq(⋅∣C),(2)\operatorname{Var}_{\pi_q(\cdot\mid C)}(h) \lesssim\operatorname{diam}(C)^2\cdot\frac{v_{\max}(\lambda)}{v_{\min}(\lambda)}\cdot\frac{1}{f(\lambda)}\int_C \lVert\nabla h\rVert^2\,d\pi_q(\cdot\mid C), \tag*{(2)}

where the volume growth constants and the lower bound on ff ensure the measure πq(⋅∣C)\pi_q(\cdot\mid C) is comparable to μ\mu on CC up to factors. Combining the two displays gives

EC(h,h)Var⁡πq(⋅∣C)(h)≳σ2diam⁡(C)2⋅vmin⁡(λ)vmax⁡(λ)⋅f(λ),\frac{\mathcal{E}_C(h,h)}{\operatorname{Var}_{\pi_q(\cdot\mid C)}(h)} \gtrsim\frac{\sigma^2}{\operatorname{diam}(C)^2}\cdot\frac{v_{\min}(\lambda)}{v_{\max}(\lambda)}\cdot f(\lambda),

uniformly over mean-zero hh. This yields the claimed lower bound on the spectral gap γin(λ)\gamma_{\mathrm{in}}(\lambda). Putting Steps 1 to 3 together, we have constructed a dominating reflected chain with the desired gap and we have bounded leakage, which proves the theorem.

This theorem is the geometric engine behind the abstract TMC interface. It explains where the two time scales come from. Mixing is controlled by a spectral gap, which is controlled by a Poincaré inequality and therefore by diameter and regularity. Leakage is controlled by an energy barrier, here a density valley, which appears exponentially through the Gaussian kernel. It also shapes the global goal. Once we can guarantee such bounds level by level, we can apply the population meeting theorem to conclude that diffusion single linkage recovers the density merge tree. If one diffusion time cannot work for all levels, we can still build a multiscale diffusion dissimilarity that adapts the time to the level.

Multiscale diffusion and meeting without a global time

Different density levels can have different metastable windows. This is natural because small high-density components can mix faster than large low-density components. The next construction allows us to use a time schedule t(λ)t(\lambda) rather than one global time. The main idea is to define a new dissimilarity that, for a pair (x,y)(x,y), looks at the diffusion time that corresponds to the density level where they should be connected.

We allow diffusion time to depend on the density level. Let t(λ)t(\lambda) be a schedule defined on Λ\Lambda such that for each λ\lambda it lies inside the levelwise metastable window, and t(λ)t(\lambda) is nonincreasing in λ\lambda.

Definition 8 (Multiscale diffusion dissimilarity). Fix a schedule λ↦t(λ)\lambda\mapsto t(\lambda) defined on Λ\Lambda. For x,y∈Mx,y \in M, define

dMS(x,y)=inf⁡{dt(λ)(x,y)∣λ∈Λ, λ≤mf(x,y)}.d_{\mathrm{MS}}(x,y)=\inf\left\{d_{t(\lambda)}(x,y)\mid\lambda\in\Lambda,\ \lambda\le m_f(x,y)\right\}.

Let TMST^{\mathrm{MS}} be the single-linkage dendrogram built from (M,dMS)(M,d_{\mathrm{MS}}), with merge-height function mMSm_{\mathrm{MS}}.

The next theorem says that this multiscale dissimilarity still produces the same merge tree as the density cluster tree. The proof follows the same threshold sandwich idea, but now the threshold used at level λ\lambda comes from diffusion time t(λ)t(\lambda).

Theorem 4 (Multiscale meeting theorem). Assume GMCGMC on Λ\Lambda and let t(λ)t(\lambda) be any schedule such that for every λ∈Λ\lambda\in\Lambda the time t(λ)t(\lambda) lies in the corresponding levelwise metastable window given by Theorem 3. Then there exists a strictly increasing function gMSg_{\mathrm{MS}} such that

mMS(x,y)=gMS(mf(x,y))for all x,y∈M.m_{\mathrm{MS}}(x,y)=g_{\mathrm{MS}}(m_f(x,y))\qquad\text{for all }x,y\in M.

Hence TMST^{\mathrm{MS}} is isomorphic to TfT_f as a merge tree.

Proof. Fix λ∈Λ\lambda\in\Lambda. Consider the diffusion distance at time t(λ)t(\lambda). By Theorem 3, the pair (f,P)(f,P) satisfies the levelwise metastability bounds at this time. Therefore, by applying Lemma 2 and Lemma 3 at time t(λ)t(\lambda), we obtain two numbers U(λ)U(\lambda) and V(λ)V(\lambda) such that

sup⁡C∈C(λ) sup⁡x,y∈Cdt(λ)(x,y)≤U(λ),inf⁡C≠C′C,C′∈C(λ) inf⁡x∈C,y∈C′dt(λ)(x,y)≥V(λ),\sup_{C\in\mathcal{C}(\lambda)}\ \sup_{x,y\in C}d_{t(\lambda)}(x,y)\le U(\lambda),\qquad \inf_{\substack{C\ne C'\\ C,C'\in\mathcal{C}(\lambda)}}\ \inf_{\substack{x\in C,y\in C'}}d_{t(\lambda)}(x,y)\ge V(\lambda),

and moreover U(λ)<V(λ)U(\lambda)<V(\lambda) because t(λ)t(\lambda) is inside the metastable window. Choose a threshold τ(λ)\tau(\lambda) such that

U(λ)<τ(λ)<V(λ).U(\lambda)<\tau(\lambda)<V(\lambda).

Then the threshold graph on LλL_\lambda with edges {dt(λ)≤τ(λ)}\{d_{t(\lambda)}\le\tau(\lambda)\} has connected components exactly C(λ)\mathcal{C}(\lambda). Now we transfer this property to the multiscale dissimilarity dMSd_{\mathrm{MS}}. First take x,yx,y in the same component C∈C(λ)C \in\mathcal{C}(\lambda). Then mf(x,y)≥λm_f(x,y) \ge\lambda. By definition of dMSd_{\mathrm{MS}}, the infimum is taken over all λ′∈Λ\lambda' \in\Lambda with λ′≤mf(x,y)\lambda' \le m_f(x,y), in particular it includes λ\lambda itself. Therefore

dMS(x,y)≤dt(λ)(x,y)≤U(λ)<τ(λ).d_{\mathrm{MS}}(x,y) \le d_{t(\lambda)}(x,y) \le U(\lambda) < \tau(\lambda).

So all pairs inside each CC have dMSd_{\mathrm{MS}} below τ(λ)\tau(\lambda) and thus each CC is connected in the threshold graph built from dMSd_{\mathrm{MS}}.

Next take x∈Cx \in C and y∈C′y \in C' for two distinct components C≠C′C \ne C' in C(λ)\mathcal{C}(\lambda). Then mf(x,y)<λm_f(x,y) < \lambda. This means that for every λ′∈Λ\lambda' \in\Lambda with λ′≤mf(x,y)\lambda' \le m_f(x,y), we have λ′<λ\lambda' < \lambda. In particular, at level λ\lambda the points lie in different components, so the separating valley at level λ\lambda is present. The definition of τ(λ)\tau(\lambda) and the separation bound at time t(λ)t(\lambda) imply that for any such pair,

dt(λ)(x,y)≥V(λ)>τ(λ).d_{t(\lambda)}(x,y) \ge V(\lambda) > \tau(\lambda).

Since dMS(x,y)d_{\mathrm{MS}}(x,y) is an infimum over diffusion distances at levels λ′≤mf(x,y)\lambda' \le m_f(x,y) and these levels are below λ\lambda, the key point is that taking the infimum cannot create an artificial short edge that would cross the level-λ\lambda bottleneck. Indeed, if dMS(x,y)≤τ(λ)d_{\mathrm{MS}}(x,y) \le\tau(\lambda) then there would exist some λ′≤mf(x,y)\lambda' \le m_f(x,y) with dt(λ′)(x,y)≤τ(λ)d_{t(\lambda')}(x,y) \le\tau(\lambda). But λ′≤mf(x,y)<λ\lambda' \le m_f(x,y) < \lambda implies that xx and yy are already separated before level λ\lambda, hence the valley that separates CC and C′C' is still present, and the same between-component argument applies to show that dt(λ′)(x,y)d_{t(\lambda')}(x,y) cannot be as small as τ(λ)\tau(\lambda). Therefore dMS(x,y)>τ(λ)d_{\mathrm{MS}}(x,y) > \tau(\lambda) for pairs in different components of C(λ)C(\lambda).

We have shown that for each λ∈Λ\lambda\in\Lambda, the connected components of the threshold graph on LλL_\lambda with edges {dMS≤τ(λ)}\{d_{\mathrm{MS}} \le\tau(\lambda)\} are exactly C(λ)\mathcal{C}(\lambda). This is the same connectivity agreement used in the proof of Theorem 1. Define gMS(λ)=τ(λ)g_{\mathrm{MS}}(\lambda) = \tau(\lambda) on Λ\Lambda and extend strictly increasing. Then the same nesting argument implies

mMS(x,y)=gMS(mf(x,y))m_{\mathrm{MS}}(x,y) = g_{\mathrm{MS}}(m_f(x,y))

for all x,y∈Mx,y \in M.

This multiscale theorem removes the main practical weakness of choosing one diffusion time. It says we can recover the same density merge tree even if different levels require different diffusion times. In the final dendrogram, single linkage is applied only once, on the combined dissimilarity dMSd_{\mathrm{MS}}.

For our bigger goal, this is important because it makes the topological guarantee compatible with realistic data. In data, metastability is rarely uniform across scales. The multiscale construction keeps the same theoretical target, the density cluster tree, while allowing time to vary with level in a controlled way.

Discussion

This work gives a precise meaning to a common spectral clustering workflow. So a diffusion hierarchy is not only a geometric summary. It can be interpreted as an estimator of density level-set topology. This has practical value because density level sets are hard to compute in high dimension, while diffusion distances on kk-NN graphs are scalable. The multiscale extension is also useful since different density levels can need different diffusion times.

Future work is mostly about making the theorem operational. One direction is data-driven choice of time, using stability of the MST or of merge heights as a diagnostic for the metastable window. Another direction is sharper finite-sample rates for uniform diffusion-distance approximation on kk-NN graphs, including the effect of truncation and eigenvector error. A last direction is computation, designing faster multiscale diffusion hierarchies without running many full eigen decompositions.

References

  1. [1]Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for the cluster tree. In Advances in Neural Information Processing Systems (NeurIPS), 2010.
  2. [2]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
  3. [3]David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007.
  4. [4]Justin Eldridge, Mikhail Belkin, and Yusu Wang. Beyond hartigan consistency: Merge distortion metric for hierarchical clustering. Journal of Machine Learning Research, 16:2817–2844, 2015.arxiv.org/abs/1506.06422
  5. [5]Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. American Mathematical Society, 2010.
  6. [7]John A. Hartigan. Consistency of single linkage for high-density clusters. Journal of the American Statistical Association, 76(374):388–394, 1981.DOI
  7. [8]Donald O. Loftsgaarden and Charles P. Quesenberry. A nonparametric estimate of a multivariate density function. The Annals of Mathematical Statistics, 36(3):1049–1051, 1965.DOI
  8. [9]Andrew Y. Ng, Michael I. Jordan, and Yair Weiss. On spectral clustering: Analysis and an algorithm. In Advances in Neural Information Processing Systems, volume 14, 2002.
  9. [10]Emanuel Parzen. On estimation of a probability density function and mode. The Annals of Mathematical Statistics, 33(3):1065–1076, 1962.DOI
  10. [11]Murray Rosenblatt. Remarks on some nonparametric estimates of a density function. The Annals of Mathematical Statistics, 27(3):832–837, 1956.DOI
  11. [12]Bernard W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
  12. [13]Jianbo Shi and Jitendra Malik. Normalized cuts and image segmentation. In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition, pages 731–737, 2000.
  13. [14]Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.arxiv.org/abs/0711.0189
  14. [15]Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2):555–586, 2008.DOI
  15. [16]Larry Wasserman. All of Nonparametric Statistics. Springer, 2006.DOI

Paper details

vlnc:W_vdkkmrmh
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Computer Science

Not recorded for this paper

View statement
Looking for related papers…
Contents