Topological Equivalence of Spectral and Density Cluster Hierarchies

# Topological Equivalence of Spectral and Density Cluster Hierarchies
Source: [https://arxiv.org/html/2610.31909](https://arxiv.org/html/2610.31909)
###### Abstract

We compare two canonical ways to recover hierarchical clustering from an underlying densityff: the*density cluster tree*given by connected components of superlevel sets\{f≥λ\}\\\{f\\geq\\lambda\\\}, 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 akk\-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\.

## 1Introduction

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 densityffon a compact domainMM\. The first one is the*density cluster tree*TfT\_\{f\}, defined by the connected components of the superlevel sets of the underlying density functionLλ=\{x∈M:f⁡\(x\)≥λ\}L\_\{\\lambda\}=\\\{x\\in M:f\(x\)\\geq\\lambda\\\}asλ\\lambdadecreases\[[7](https://arxiv.org/html/2610.31909#bib.bib1),[1](https://arxiv.org/html/2610.31909#bib.bib2),[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\. The second one is a*diffusion–spectral hierarchy*, defined as a reversible Markov operatorPP\(or a Laplacian\) fromff\[[3](https://arxiv.org/html/2610.31909#bib.bib4),[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\. 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](https://arxiv.org/html/2610.31909#bib.bib2),[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\. Diffusion distances are very popular because they are algorithmic and robust, and they are connected to spectral gaps and bottlenecks\[[3](https://arxiv.org/html/2610.31909#bib.bib4),[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\. 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 byff\.

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\\geq 0:\\ x\\text\{ and \}y\\text\{ are in the same component of \}L\_\{\\lambda\}\\\}\.The diffusion hierarchy at timettis the single\-linkage dendrogram built from\(M,dt\)\(M,d\_\{t\}\), and it has its own merge\-height functionmt​\(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 mapgtg\_\{t\}such thatmt​\(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λ\\lambdaand every componentCCofLλL\_\{\\lambda\}, we require two quantitative facts about the chain, it mixes fast insideCC, and also has small probability to exitCCin 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](https://arxiv.org/html/2610.31909#bib.bib1)\]and later statistical developments\[[1](https://arxiv.org/html/2610.31909#bib.bib2),[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\. Diffusion distance and diffusion maps give a spectral geometry view of connectivity and scales\[[3](https://arxiv.org/html/2610.31909#bib.bib4)\], and single linkage and MST are classical tools for building hierarchies\[[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\. 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\[[14](https://arxiv.org/html/2610.31909#bib.bib6),[6](https://arxiv.org/html/2610.31909#bib.bib9)\]\. The merge\-tree viewpoint is also close to stability ideas in topological data analysis\[[2](https://arxiv.org/html/2610.31909#bib.bib8),[4](https://arxiv.org/html/2610.31909#bib.bib7)\]\.

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 standardkk\-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](https://arxiv.org/html/2610.31909#S2)fixes notation and reviews preliminaries\. Section[3](https://arxiv.org/html/2610.31909#S3)states the Topological Meeting Condition and explains how it encodes hierarchical metastability\. Section[4](https://arxiv.org/html/2610.31909#S4)proves the population meeting theorem by showing within\-component contraction and between\-component separation of diffusion distance in the metastable window\. Section[5](https://arxiv.org/html/2610.31909#S5)presents thekk\-NN graph algorithm and proves the merge\-distortion guarantee using a stability lemma for single linkage\. Section[6](https://arxiv.org/html/2610.31909#S6)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\.

## 2Preliminaries and notation

We work on a compact metric space\(M,ρ\)\(M,\\rho\)with a Borel measureμ\\mu\. The data distribution is a probability measureπ\\pithat admits a continuous densityf:M→\(0,∞\)f:M\\to\(0,\\infty\)with respect toμ\\mu, sod​π=f​d​μd\\pi=f\\,d\\muand∫Mf​𝑑μ=1\\int\_\{M\}f\\,d\\mu=1\. We observe i\.i\.d\. samplesX1,…,Xn∼πX\_\{1\},\\dots,X\_\{n\}\\sim\\pi\. For each levelλ≥0\\lambda\\geq 0we writeLλ=\{x∈M:f⁡\(x\)≥λ\}L\_\{\\lambda\}=\\\{x\\in M:f\(x\)\\geq\\lambda\\\}and𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)for the connected components ofLλL\_\{\\lambda\}in the topology ofMM\. The density cluster tree is encoded by the merge\-height functionmfm\_\{f\}defined from these components\.

We keep regularity assumptions onffflexible\. 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 onffon regions of interest\. The important point is thatffplays two roles\. It defines the topology of the level sets\{f≥λ\}\\\{f\\geq\\lambda\\\}, and it also biases the diffusion process that we build from the data\.

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

q⁡\(x\)=∫MKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\),p⁡\(x,𝑑y\)=Kσ​\(x,y\)​f​\(y\)q⁡\(x\)​𝑑μ​\(y\),\(P​φ\)​\(x\)=∫φ⁡\(y\)​p​\(x,𝑑y\)\.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\)\.The operatorPPis a Markov operator with stationary measureπq\\pi\_\{q\}, and we work inL2​\(πq\)L^\{2\}\(\\pi\_\{q\}\)\. We writep\(t\)​\(x,⋅\)p^\{\(t\)\}\(x,\\cdot\)for thett\-step transition law of the Markov chain\(Xt\)t≥0\(X\_\{t\}\)\_\{t\\geq 0\}with transition kernelpp\. We writedtd\_\{t\}for diffusion distance at timett, defined as anL2​\(πq\)L^\{2\}\(\\pi\_\{q\}\)distance between thett\-step transition densities\. We writeTfT\_\{f\}for the density cluster tree, andTtdiffT\_\{t\}^\{\\mathrm\{diff\}\}for the single\-linkage hierarchy built from\(M,dt\)\(M,d\_\{t\}\)with merge\-height functionmtm\_\{t\}\. For a finite setSSwe writedMDd\_\{\\mathrm\{MD\}\}for merge distortion between merge\-height functions onSS\. We use∥⋅∥2\\\|\\cdot\\\|\_\{2\}forL2​\(πq\)L^\{2\}\(\\pi\_\{q\}\)norms,∥⋅∥op\\\|\\cdot\\\|\_\{\\mathrm\{op\}\}for operator norms, and∥⋅∥TV\\\|\\cdot\\\|\_\{\\mathrm\{TV\}\}for total variation norms\.

### 2\.1Density 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\)\\geq\\lambda\\\}whenλ\\lambdagoes from large to small\[[7](https://arxiv.org/html/2610.31909#bib.bib1),[1](https://arxiv.org/html/2610.31909#bib.bib2)\]\. For a fixedλ\\lambda, the setLλL\_\{\\lambda\}can split into several connected components\. Whenλ\\lambdadecreases, 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\)\.

Forx,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\\Big\\\{\\lambda\\geq 0\\,\\Big\|\\,x\\text\{ and \}y\\text\{ lie in the same connected component of \}L\_\{\\lambda\}\\Big\\\}\.

The functionmfm\_\{f\}is symmetric, and it is larger whenxxandyystay connected until a higher density level\. Ifffis 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\.

### 2\.2Diffusion 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 kernelKσ≥0K\_\{\\sigma\}\\geq 0\. We define

q⁡\(x\)=∫MKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\),p⁡\(x,𝑑y\)=Kσ​\(x,y\)​f​\(y\)q⁡\(x\)​𝑑μ​\(y\),\(P​φ\)​\(x\)=∫φ⁡\(y\)​p​\(x,𝑑y\)\.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\)\.ThenPPis a Markov operator\. It is reversible with respect to a stationary measureπq\\pi\_\{q\}whose density is proportional toqqwith respect toμ\\mu\[[3](https://arxiv.org/html/2610.31909#bib.bib4)\]\. The associated random process is the Markov chain\(Xt\)t≥0\(X\_\{t\}\)\_\{t\\geq 0\}with transition ruleXt\+1\|Xt=x∼p⁡\(x,⋅\)X\_\{t\+1\}\\mid X\_\{t\}=x\\sim p\(x,\\cdot\)\.

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

###### Definition 2\(Diffusion distance\[[3](https://arxiv.org/html/2610.31909#bib.bib4)\]\)\.

Letp\(t\)​\(x,⋅\)p^\{\(t\)\}\(x,\\cdot\)be thett\-step transition law fromxx, and assumep\(t\)​\(x,⋅\)p^\{\(t\)\}\(x,\\cdot\)is absolutely continuous with respect toπq\\pi\_\{q\}\. Define

dt​\(x,y\)=‖d​p\(t\)​\(x,⋅\)d​πq−d​p\(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 thatPPis self\-adjoint inL2​\(πq\)L^\{2\}\(\\pi\_\{q\}\)\. Therefore there exists an orthonormal eigenbasis\(ψℓ\)ℓ≥0\(\\psi\_\{\\ell\}\)\_\{\\ell\\geq 0\}with real eigenvalues\(λℓ\)ℓ≥0\(\\lambda\_\{\\ell\}\)\_\{\\ell\\geq 0\}such that

1=λ0\>λ1≥λ2≥⋯≥−1,ψ0≡1\.1=\\lambda\_\{0\}\>\\lambda\_\{1\}\\geq\\lambda\_\{2\}\\geq\\cdots\\geq\-1,\\qquad\\psi\_\{0\}\\equiv 1\.In this setting diffusion distance has a simple spectral form\.

###### Lemma 1\(Spectral formula for diffusion distance\[[3](https://arxiv.org/html/2610.31909#bib.bib4)\]\)\.

For allx,y∈Mx,y\\in Mand all integerst≥1t\\geq 1,

dt​\(x,y\)2=∑ℓ≥1λℓ2​t​\(ψℓ​\(x\)−ψℓ​\(y\)\)2\.d\_\{t\}\(x,y\)^\{2\}=\\sum\_\{\\ell\\geq 1\}\\lambda\_\{\\ell\}^\{2t\}\\big\(\\psi\_\{\\ell\}\(x\)\-\\psi\_\{\\ell\}\(y\)\\big\)^\{2\}\.

###### Proof sketch\.

Write the Radon–Nikodym derivative ofp\(t\)​\(x,⋅\)p^\{\(t\)\}\(x,\\cdot\)with respect toπq\\pi\_\{q\}using the eigenbasis ofPPinL2​\(πq\)L^\{2\}\(\\pi\_\{q\}\)\. ApplyPt​ψℓ=λℓt​ψℓP^\{t\}\\psi\_\{\\ell\}=\\lambda\_\{\\ell\}^\{t\}\\psi\_\{\\ell\}to see how each mode scales withtt\. The squaredL2​\(π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](https://arxiv.org/html/2610.31909#Thmlemma1)shows that largettsuppresses modes with\|λℓ\|<1\|\\lambda\_\{\\ell\}\|<1\. In this sensettcontrols the scale at which the geometry is observed\.

### 2\.3Parzen windows, kernel density estimation, andkk\-NN density estimation

In practiceffis unknown, so level setsLλL\_\{\\lambda\}are not directly available\. A classical way to estimateffis the Parzen window method, also called kernel density estimation\[[10](https://arxiv.org/html/2610.31909#bib.bib11),[11](https://arxiv.org/html/2610.31909#bib.bib10),[13](https://arxiv.org/html/2610.31909#bib.bib12),[16](https://arxiv.org/html/2610.31909#bib.bib13)\]\. In Euclidean spaceℝd\\mathbb\{R\}^\{d\}with Lebesgue measure, the standard KDE has the form

f^h​\(x\)=1n​hd​∑i=1nK⁡\(x−Xih\),\\hat\{f\}\_\{h\}\(x\)=\\frac\{1\}\{nh^\{d\}\}\\sum\_\{i=1\}^\{n\}K\\\!\\left\(\\frac\{x\-X\_\{i\}\}\{h\}\\right\),whereh\>0h\>0is a bandwidth andKKis a nonnegative kernel with∫ℝdK⁡\(u\)​𝑑u=1\\int\_\{\\mathbb\{R\}^\{d\}\}K\(u\)\\,du=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\)​𝑑μ​\(y\)=1\.\\hat\{f\}\_\{h\}\(x\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}K\_\{h\}\(x,X\_\{i\}\),\\qquad K\_\{h\}\(x,y\)\\geq 0,\\qquad\\int\_\{M\}K\_\{h\}\(x,y\)\\,d\\mu\(y\)=1\.A typical choice isKh​\(x,y\)=ch​κ​\(ρ⁡\(x,y\)/h\)K\_\{h\}\(x,y\)=c\_\{h\}\\,\\kappa\(\\rho\(x,y\)/h\)with a radial profileκ\\kappaand a normalizing constantchc\_\{h\}that depends onhhand the geometry of\(M,μ\)\(M,\\mu\)\. Under smoothness assumptions onffand mild conditions onKK, one gets pointwise and uniform convergence off^h\\hat\{f\}\_\{h\}toffwhenh→0h\\to 0andn​hd→∞nh^\{d\}\\to\\infty, with the usual bias and variance tradeoff\[[13](https://arxiv.org/html/2610.31909#bib.bib12),[16](https://arxiv.org/html/2610.31909#bib.bib13)\]\. In density clustering, one can usef^h\\hat\{f\}\_\{h\}to define empirical superlevel sets\{f^h≥λ\}\\\{\\hat\{f\}\_\{h\}\\geq\\lambda\\\}and then build an estimated cluster tree\[[1](https://arxiv.org/html/2610.31909#bib.bib2),[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\.

A different estimator useskknearest neighbors\[[8](https://arxiv.org/html/2610.31909#bib.bib14),[16](https://arxiv.org/html/2610.31909#bib.bib13)\]\. Letrk​\(x\)r\_\{k\}\(x\)be the distance fromxxto itskkth nearest neighbor amongX1,…,XnX\_\{1\},\\dots,X\_\{n\}in the metricρ\\rho\. LetV⁡\(x,r\)=μ⁡\(B⁡\(x,r\)\)V\(x,r\)=\\mu\(B\(x,r\)\)denote theμ\\mu\-volume of the ballB⁡\(x,r\)=\{y∈M:ρ⁡\(x,y\)≤r\}B\(x,r\)=\\\{y\\in M:\\rho\(x,y\)\\leq r\\\}\. A standardkk\-NN density estimator is

f^k​\-NN​\(x\)=kn​V​\(x,rk​\(x\)\)\.\\hat\{f\}\_\{k\\text\{\-NN\}\}\(x\)=\\frac\{k\}\{n\\,V\(x,r\_\{k\}\(x\)\)\}\.This estimator adapts to local sampling density becauserk​\(x\)r\_\{k\}\(x\)shrinks in high\-density regions and grows in low\-density regions\. The parameterkkcontrols smoothing\. Under regularity assumptions onμ\\muandff, consistency holds whenk→∞k\\to\\inftyandk/n→0k/n\\to 0\[[8](https://arxiv.org/html/2610.31909#bib.bib14),[16](https://arxiv.org/html/2610.31909#bib.bib13)\]\. Thekk\-NN idea is also the backbone of the graph constructions in this paper, because thekk\-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 andkk\-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 estimatingffeverywhere\.

### 2\.4Single linkage, MST, and merge distortion

LetSSbe a finite set and letddbe a symmetric dissimilarity onSSwithd⁡\(x,x\)=0d\(x,x\)=0\. Single linkage builds a dendrogram by increasing a thresholdτ\\tauand looking at the graph onSSwith edges

\{\(x,y\)∈S×S∣d⁡\(x,y\)≤τ\}\.\\\{\(x,y\)\\in S\\times S\\mid d\(x,y\)\\leq\\tau\\\}\.Asτ\\tauincreases, connected components merge\. The merge heightmd​\(x,y\)m\_\{d\}\(x,y\)is the smallestτ\\tauwherexxandyybecome connected\.

There is also an equivalent path view\. Consider any path fromxxtoyyin the complete graph onSS\. Look at the largest edge length along that path\. Thenmd​\(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\[[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\.

We compare two dendrograms using merge distortion\[[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\. It measures the largest difference between corresponding merge heights\.

###### Definition 3\(Merge distortion\[[5](https://arxiv.org/html/2610.31909#bib.bib3)\]\)\.

LetSSbe finite and letm,m′:S×S→ℝm,m^\{\\prime\}:S\\times S\\to\\mathbb\{R\}be symmetric merge\-height functions\. Define

dMD​\(m,m′\)=supx,y∈S\|m⁡\(x,y\)−m′​\(x,y\)\|\.d\_\{\\mathrm\{MD\}\}\(m,m^\{\\prime\}\)=\\sup\_\{x,y\\in S\}\\big\|m\(x,y\)\-m^\{\\prime\}\(x,y\)\\big\|\.

### 2\.5Spectral 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\[[12](https://arxiv.org/html/2610.31909#bib.bib15),[9](https://arxiv.org/html/2610.31909#bib.bib16),[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\. Given pointsX1,…,XnX\_\{1\},\\dots,X\_\{n\}, define an affinity matrixWWwith entriesWi​j≥0W\_\{ij\}\\geq 0, often of the formWi​j=Kσ​\(Xi,Xj\)W\_\{ij\}=K\_\{\\sigma\}\(X\_\{i\},X\_\{j\}\)or a sparsified version using akk\-NN graph\. LetDDbe the diagonal degree matrixDi​i=∑j=1nWi​jD\_\{ii\}=\\sum\_\{j=1\}^\{n\}W\_\{ij\}\. The unnormalized graph Laplacian isL=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ℝm\\mathbb\{R\}^\{m\}, then it clusters in that embedding, typically bykk\-means\[[9](https://arxiv.org/html/2610.31909#bib.bib16),[15](https://arxiv.org/html/2610.31909#bib.bib5)\]\. 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

This is exactly the discrete analogue of the Markov operatorPPin the population\. Thett\-step transition matrixPntP\_\{n\}^\{t\}describes how probability mass spreads on the graph afterttsteps\. Diffusion distance is the distance between thesett\-step transition distributions\. In the finite graph setting, ifπn\\pi\_\{n\}is the stationary distribution ofPnP\_\{n\}, then a discrete diffusion distance can be written as

d^t​\(i,j\)=‖Pnt​\(i,⋅\)πn​\(⋅\)−Pnt​\(j,⋅\)πn​\(⋅\)‖ℓ2​\(πn\)\.\\hat\{d\}\_\{t\}\(i,j\)=\\left\\\|\\frac\{P\_\{n\}^\{t\}\(i,\\cdot\)\}\{\\pi\_\{n\}\(\\cdot\)\}\-\\frac\{P\_\{n\}^\{t\}\(j,\\cdot\)\}\{\\pi\_\{n\}\(\\cdot\)\}\\right\\\|\_\{\\ell^\{2\}\(\\pi\_\{n\}\)\}\.This distance has a spectral representation that mirrors Lemma[1](https://arxiv.org/html/2610.31909#Thmlemma1)\. If\(λ^ℓ,ψ^ℓ\)\(\\hat\{\\lambda\}\_\{\\ell\},\\hat\{\\psi\}\_\{\\ell\}\)are eigenpairs ofPnP\_\{n\}inℓ2​\(πn\)\\ell^\{2\}\(\\pi\_\{n\}\), then

d^t​\(i,j\)2=∑ℓ≥1λ^ℓ2​t​\(ψ^ℓ​\(i\)−ψ^ℓ​\(j\)\)2,\\hat\{d\}\_\{t\}\(i,j\)^\{2\}=\\sum\_\{\\ell\\geq 1\}\\hat\{\\lambda\}\_\{\\ell\}^\{2t\}\\big\(\\hat\{\\psi\}\_\{\\ell\}\(i\)\-\\hat\{\\psi\}\_\{\\ell\}\(j\)\\big\)^\{2\},and this is exactly the diffusion map embedding of\[[3](https://arxiv.org/html/2610.31909#bib.bib4)\]\. The factorλ^ℓt\\hat\{\\lambda\}\_\{\\ell\}^\{t\}makestta scale parameter\. Smallttkeeps many modes and sees local structure, while largettkills 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 operatorPPis built from the kernel and the density, and the empirical operatorPnP\_\{n\}is built from the sample\. WhenPnP\_\{n\}approximatesPPin an appropriate sense, the leading eigenvalues and eigenfunctions approximate their population counterparts\[[14](https://arxiv.org/html/2610.31909#bib.bib6),[6](https://arxiv.org/html/2610.31909#bib.bib9)\]\. 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\.

### 2\.6Diffusion hierarchy and meeting

Fixt∈ℕt\\in\\mathbb\{N\}\. Define the diffusion hierarchyTtdiffT\_\{t\}^\{\\mathrm\{diff\}\}as the single\-linkage dendrogram built on\(M,dt\)\(M,d\_\{t\}\)\. Its merge\-height function is denotedmt​\(x,y\)m\_\{t\}\(x,y\)\. It is defined as the smallest thresholdτ\\tauat whichxxandyybecome 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 sayTtdiffT\_\{t\}^\{\\mathrm\{diff\}\}meetsTfT\_\{f\}if there exists a strictly increasing functiongt:\[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\}\(m\_\{f\}\(x,y\)\)\\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 bygtg\_\{t\}\.

## 3Metastability interface

The meeting mechanism is metastability\. For each density levelλ\\lambdaand each componentC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\), we need fast mixing insideCCand slow leakage out ofCC\. Both are measured at diffusion timett\.

We define two quantities\. The leakage is

αout​\(λ\)=supC∈𝒞⁡\(λ\)supx∈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 onCC\. A convenient device is a reflected or dominating chainPCP\_\{C\}that stays inCCand dominates the restriction ofPPtoCC\.

###### Definition 5\(Dominating in\-component chain\)\.

Fix a measurable setCCwithπq​\(C\)\>0\\pi\_\{q\}\(C\)\>0\. A Markov operatorPCP\_\{C\}supported onCCis called dominating if for everyx∈Cx\\in Cand every measurableB⊂CB\\subset Cwe havePC​\(x,B\)≥P⁡\(x,B\)P\_\{C\}\(x,B\)\\geq P\(x,B\), andPCP\_\{C\}is reversible with stationary measureπq\(⋅∣C\)\\pi\_\{q\}\(\\cdot\\mid C\)\.

Dominating chains exist in standard settings by reflecting mass that would exitCCback intoCC\. 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\)\>0andαout​\(⋅\)∈\(0,1\)\\alpha\_\{\\mathrm\{out\}\}\(\\cdot\)\\in\(0,1\)and functionstmin​\(⋅\),tmax​\(⋅\):\[0,∞\)→ℕt\_\{\\min\}\(\\cdot\),t\_\{\\max\}\(\\cdot\):\[0,\\infty\)\\to\\mathbb\{N\}such that for every levelλ\\lambdaand every componentC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)the following hold\.

1. \(TMC1\)There exists a dominating chainPCP\_\{C\}onCCwhose spectral gap inL2\(π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 ofPCP\_\{C\}, then1−λ1​\(C\)≥γin​\(λ\)1\-\\lambda\_\{1\}\(C\)\\geq\\gamma\_\{\\mathrm\{in\}\}\(\\lambda\)\.
2. \(TMC2\)Leakage fromCCunderPPis small and satisfiessupx∈CP⁡\(x,Cc\)≤αout​\(λ\)\\sup\_\{x\\in C\}P\(x,C^\{c\}\)\\leq\\alpha\_\{\\mathrm\{out\}\}\(\\lambda\)\.
3. \(TMC3\)There is a metastable time window\. For everyλ\\lambdawe havetmin​\(λ\)≤tmax​\(λ\)t\_\{\\min\}\(\\lambda\)\\leq t\_\{\\max\}\(\\lambda\)\. For allt∈\[tmin​\(λ\),tmax​\(λ\)\]t\\in\[t\_\{\\min\}\(\\lambda\),t\_\{\\max\}\(\\lambda\)\]one hast​γin​\(λ\)≫1t\\gamma\_\{\\mathrm\{in\}\}\(\\lambda\)\\gg 1andt​αout​\(λ\)≪1t\\alpha\_\{\\mathrm\{out\}\}\(\\lambda\)\\ll 1\. 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\.

## 4Population 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\.

### 4\.1Within and between bounds

We first control diffusion distance inside one component\. The idea is to compare the true chainPPwith a chainPCP\_\{C\}that is forced to stay insideCC\. The chainPCP\_\{C\}mixes quickly, so thett\-step transition densities from any two starting points become close\. The true chain differs fromPCP\_\{C\}only when it exitsCC, and this is controlled by the one\-step leakage\.

###### Lemma 2\(Within\-component contraction\)\.

Fixλ≥0\\lambda\\geq 0and letC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)\. AssumePCP\_\{C\}is a dominating chain onCCwith spectral gap at leastγ=γin​\(λ\)\\gamma=\\gamma\_\{\\mathrm\{in\}\}\(\\lambda\)\. Assumesupx∈CP⁡\(x,Cc\)≤η\\sup\_\{x\\in C\}P\(x,C^\{c\}\)\\leq\\etawithη≤αout​\(λ\)\\eta\\leq\\alpha\_\{\\mathrm\{out\}\}\(\\lambda\)\. Letrt,x=d​p\(t\)​\(x,⋅\)/d​πqr\_\{t,x\}=dp^\{\(t\)\}\(x,\\cdot\)/d\\pi\_\{q\}and letrt,xC=d​pC\(t\)​\(x,⋅\)/d​πqr^\{C\}\_\{t,x\}=dp\_\{C\}^\{\(t\)\}\(x,\\cdot\)/d\\pi\_\{q\}be the correspondingtt\-step densities forPPandPCP\_\{C\}with respect toπq\\pi\_\{q\}, withrt,xCr^\{C\}\_\{t,x\}extended by zero outsideCC\. Then for allt∈ℕt\\in\\mathbb\{N\}and allx,y∈Cx,y\\in C,

dt​\(x,y\)=‖rt,x−rt,y‖L2​\(πq\)≤2​\(1−γ\)tπq​\(C\)\+4​t​ηπq​\(C\)\.d\_\{t\}\(x,y\)=\\\|r\_\{t,x\}\-r\_\{t,y\}\\\|\_\{L^\{2\}\(\\pi\_\{q\}\)\}\\;\\leq\\;\\frac\{2\(1\-\\gamma\)^\{t\}\}\{\\sqrt\{\\pi\_\{q\}\(C\)\}\}\+\\frac\{4t\\eta\}\{\\sqrt\{\\pi\_\{q\}\(C\)\}\}\.

###### 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\.\\\|r\_\{t,x\}\-r\_\{t,y\}\\\|\_\{2\}\\leq\\\|r\_\{t,x\}\-r^\{C\}\_\{t,x\}\\\|\_\{2\}\+\\\|r^\{C\}\_\{t,x\}\-r^\{C\}\_\{t,y\}\\\|\_\{2\}\+\\\|r^\{C\}\_\{t,y\}\-r\_\{t,y\}\\\|\_\{2\}\.We bound the middle term using the spectral gap ofPCP\_\{C\}\. SincePCP\_\{C\}is reversible with stationary measureπq\(⋅∣C\)\\pi\_\{q\}\(\\cdot\\mid C\), it is self\-adjoint onL2\(πq\(⋅∣C\)\)L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\. LetΠC\\Pi\_\{C\}be the averaging operator onCCgiven by\(ΠC​h\)​\(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 standardL2L^\{2\}contraction on mean\-zero functions

∥PCth−ΠCh∥L2\(πq\(⋅∣C\)\)≤\(1−γ\)t∥h−ΠCh∥L2\(πq\(⋅∣C\)\)\.\\\|P\_\{C\}^\{t\}h\-\\Pi\_\{C\}h\\\|\_\{L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\}\\leq\(1\-\\gamma\)^\{t\}\\\|h\-\\Pi\_\{C\}h\\\|\_\{L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\}\.Apply this withh⁡\(⋅\)=r0,xC​\(⋅\)h\(\\cdot\)=r^\{C\}\_\{0,x\}\(\\cdot\)interpreted in the usual way throughtt\-step densities\. A clean way is to work directly withtt\-step densities\. The functionrt,xCr^\{C\}\_\{t,x\}is a density onCCwith respect toπq\(⋅∣C\)\\pi\_\{q\}\(\\cdot\\mid C\)scaled by the factorπq​\(C\)−1\\pi\_\{q\}\(C\)^\{\-1\}\. The differencert,xC−rt,yCr^\{C\}\_\{t,x\}\-r^\{C\}\_\{t,y\}has integral00overCC\. 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\)\)\.\\\|r^\{C\}\_\{t,x\}\-r^\{C\}\_\{t,y\}\\\|\_\{L^\{2\}\(\\pi\_\{q\}\)\}=\\sqrt\{\\pi\_\{q\}\(C\)\}\\,\\\|r^\{C\}\_\{t,x\}\-r^\{C\}\_\{t,y\}\\\|\_\{L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\}\\leq\\sqrt\{\\pi\_\{q\}\(C\)\}\\,\(1\-\\gamma\)^\{t\}\\\|r^\{C\}\_\{0,x\}\-r^\{C\}\_\{0,y\}\\\|\_\{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 densitiesa,ba,bonCCwith 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\)\.\\\|a\-b\\\|\_\{L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\}\\leq\\\|a\\\|\_\{L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\}\+\\\|b\\\|\_\{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\)\.\\\|r^\{C\}\_\{t,x\}\-r^\{C\}\_\{t,y\}\\\|\_\{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\)≤2​t​ηπq​\(C\)\\\|r\_\{t,x\}\-r^\{C\}\_\{t,x\}\\\|\_\{L^\{2\}\(\\pi\_\{q\}\)\}\\leq\\frac\{2t\\eta\}\{\\sqrt\{\\pi\_\{q\}\(C\)\}\}and similarly foryy\. LetA=CA=C\. SincePPcan leaveCCin one step with probability at mostη\\etafrom any point ofCC, 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 insideCC, sopC\(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 most2​t​η2t\\eta\. Writegt,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 functiongt,xg\_\{t,x\}integrates to00and itsL1​\(πq\)L^\{1\}\(\\pi\_\{q\}\)norm equals‖νt,x‖TV≤2​t​η\\\|\\nu\_\{t,x\}\\\|\_\{\\mathrm\{TV\}\}\\leq 2t\\eta\. Also,gt,xg\_\{t,x\}is supported onC∪CcC\\cup C^\{c\}, and we can use the inequality‖g‖2≤‖g‖1/πq​\(C\)\\\|g\\\|\_\{2\}\\leq\\\|g\\\|\_\{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 ofgt,xg\_\{t,x\}insideCCcarries all the mass ofpC\(t\)​\(x,⋅\)p\_\{C\}^\{\(t\)\}\(x,\\cdot\)while the missing mass is at mostt​ηt\\eta\. This yields

‖rt,x−rt,xC‖L2​\(πq\)=‖gt,x‖2≤‖gt,x‖1πq​\(C\)≤2​t​ηπq​\(C\)\.\\\|r\_\{t,x\}\-r^\{C\}\_\{t,x\}\\\|\_\{L^\{2\}\(\\pi\_\{q\}\)\}=\\\|g\_\{t,x\}\\\|\_\{2\}\\leq\\frac\{\\\|g\_\{t,x\}\\\|\_\{1\}\}\{\\sqrt\{\\pi\_\{q\}\(C\)\}\}\\leq\\frac\{2t\\eta\}\{\\sqrt\{\\pi\_\{q\}\(C\)\}\}\.Doing the same foryyand combining the three bounds gives

dt​\(x,y\)≤2​\(1−γ\)tπq​\(C\)\+4​t​ηπ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 setAAthat contains one component and the valley in front of it\. Starting from the component, the chain stays inAAwith high probability forttsteps\. Starting from the other component, the chain entersAAwith small probability forttsteps\. This difference of probabilities gives a lower bound on theL2L^\{2\}distance by Cauchy–Schwarz\.

###### Lemma 3\(Between\-component separation\)\.

Fixλ≥0\\lambda\\geq 0\. LetC,C′∈𝒞⁡\(λ\)C,C^\{\\prime\}\\in\\mathcal\{C\}\(\\lambda\)be distinct components\. Assume there exists a measurable setVVsuch thatA=C∪VA=C\\cup Vis measurable,C′∩A=∅C^\{\\prime\}\\cap A=\\emptyset, and the following two bounds hold for someη∈\(0,1\)\\eta\\in\(0,1\)

supx∈AP⁡\(x,Ac\)≤ηandsupx∈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 thatt​η≤1/4t\\eta\\leq 1/4\. Then for allx∈Cx\\in Cand ally∈C′y\\in C^\{\\prime\},

dt​\(x,y\)≥1−4​t​ηπq​\(A\)\.d\_\{t\}\(x,y\)\\;\\geq\\;\\frac\{1\-4t\\eta\}\{\\sqrt\{\\pi\_\{q\}\(A\)\}\}\.

###### Proof\.

Fixx∈C⊆Ax\\in C\\subseteq Aandy∈C′⊆Acy\\in C^\{\\prime\}\\subseteq A^\{c\}\. We first boundp\(t\)​\(x,A\)p^\{\(t\)\}\(x,A\)from below\. Consider the event that the chain starting fromxxleavesAAat some step in\{1,…,t\}\\\{1,\\dots,t\\\}\. By a union bound and the first assumption,

ℙx​\(∃s≤t​with​Xs∈Ac\)≤∑s=0t−1supz∈AP⁡\(z,Ac\)≤t​η\.\\mathbb\{P\}\_\{x\}\\\!\\big\(\\exists s\\leq t\\text\{ with \}X\_\{s\}\\in A^\{c\}\\big\)\\leq\\sum\_\{s=0\}^\{t\-1\}\\sup\_\{z\\in A\}P\(z,A^\{c\}\)\\leq t\\eta\.Therefore

p\(t\)​\(x,A\)=ℙx​\(Xt∈A\)≥1−t​η\.p^\{\(t\)\}\(x,A\)=\\mathbb\{P\}\_\{x\}\(X\_\{t\}\\in A\)\\geq 1\-t\\eta\.Next we boundp\(t\)​\(y,A\)p^\{\(t\)\}\(y,A\)from above\. For the chain to be inAAat timett, it must enterAAat some steps∈\{1,…,t\}s\\in\\\{1,\\dots,t\\\}\. By another union bound and the second assumption,

p\(t\)​\(y,A\)=ℙy​\(Xt∈A\)≤ℙy​\(∃s≤t​with​Xs∈A\)≤∑s=0t−1supz∈AcP⁡\(z,A\)≤t​η\.p^\{\(t\)\}\(y,A\)=\\mathbb\{P\}\_\{y\}\(X\_\{t\}\\in A\)\\leq\\mathbb\{P\}\_\{y\}\\\!\\big\(\\exists s\\leq t\\text\{ with \}X\_\{s\}\\in A\\big\)\\leq\\sum\_\{s=0\}^\{t\-1\}\\sup\_\{z\\in A^\{c\}\}P\(z,A\)\\leq t\\eta\.Subtracting the bounds gives

p\(t\)​\(x,A\)−p\(t\)​\(y,A\)≥1−2​t​η\.p^\{\(t\)\}\(x,A\)\-p^\{\(t\)\}\(y,A\)\\geq 1\-2t\\eta\.Now writert,x=d​p\(t\)​\(x,⋅\)/d​πqr\_\{t,x\}=dp^\{\(t\)\}\(x,\\cdot\)/d\\pi\_\{q\}andrt,y=d​p\(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 onAA

∫A\(rt,x−rt,y\)​d​πq≤‖rt,x−rt,y‖L2​\(πq\)⋅‖𝟏A‖L2​\(πq\)=dt​\(x,y\)​πq​\(A\)\.\\int\_\{A\}\(r\_\{t,x\}\-r\_\{t,y\}\)\\,d\\pi\_\{q\}\\leq\\\|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−2​t​ηπq​\(A\)\.d\_\{t\}\(x,y\)\\geq\\frac\{1\-2t\\eta\}\{\\sqrt\{\\pi\_\{q\}\(A\)\}\}\.Finally we replace1−2​t​η1\-2t\\etaby1−4​t​η1\-4t\\etawhich is weaker but convenient in later uniform arguments, sincet​η≤1/4t\\eta\\leq 1/4implies1−2​t​η≥\(1−4​t​η\)1\-2t\\eta\\geq\(1\-4t\\eta\)\. ∎

This lemma gives the outside part\. It says that if there is a regionAAaround one component that is hard to exit and also hard to enter, then diffusion distance separates that component from the other components at timett\. In the full meeting theorem we use this withAAbuilt 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](https://arxiv.org/html/2610.31909#Thmlemma2)\.

### 4\.2Meeting 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 numberU⁡\(λ,t\)U\(\\lambda,t\)\. All between\-component diffusion distances are above a numberV⁡\(λ,t\)V\(\\lambda,t\)\. IfU⁡\(λ,t\)<V⁡\(λ,t\)U\(\\lambda,t\)<V\(\\lambda,t\), then any thresholdτ\\tauin 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 onettthat 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 timettsuch that for all critical levelsλ\\lambdaone hast∈\[tmin​\(λ\),tmax​\(λ\)\]t\\in\[t\_\{\\min\}\(\\lambda\),t\_\{\\max\}\(\\lambda\)\]\. For thisttthere exists a strictly increasing functiongtg\_\{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\.HenceTtdiffT\_\{t\}^\{\\mathrm\{diff\}\}andTfT\_\{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 intervalIk=\[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 thisttfor 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 onLλL\_\{\\lambda\}\. Consider the collection of components𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)\. For eachC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\), Lemma[2](https://arxiv.org/html/2610.31909#Thmlemma2)gives a uniform bound

supx,y∈Cdt​\(x,y\)≤UC​\(λ,t\)withUC​\(λ,t\)=2​\(1−γin​\(λ\)\)tπq​\(C\)\+4​t​αout​\(λ\)πq​\(C\)\.\\sup\_\{x,y\\in C\}d\_\{t\}\(x,y\)\\leq 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\)=supC∈𝒞⁡\(λ\)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 componentsC,C′∈𝒞⁡\(λ\)C,C^\{\\prime\}\\in\\mathcal\{C\}\(\\lambda\)\. SinceCCandC′C^\{\\prime\}are distinct connected components ofLλL\_\{\\lambda\}, any path fromCCtoC′C^\{\\prime\}must leaveLλL\_\{\\lambda\}\. This gives a natural valley region inMMbetween them\. In the TMC interface we encode this by assuming that for each componentCCthere exists a measurable setVC​\(λ\)V\_\{C\}\(\\lambda\)such thatAC​\(λ\)=C∪VC​\(λ\)A\_\{C\}\(\\lambda\)=C\\cup V\_\{C\}\(\\lambda\)satisfies the two\-sided bottleneck condition in Lemma[3](https://arxiv.org/html/2610.31909#Thmlemma3)with parameterη=αout​\(λ\)\\eta=\\alpha\_\{\\mathrm\{out\}\}\(\\lambda\)\. Applying Lemma[3](https://arxiv.org/html/2610.31909#Thmlemma3)gives, for allx∈Cx\\in Candy∈C′y\\in C^\{\\prime\},

dt​\(x,y\)≥VC​\(λ,t\)withVC​\(λ,t\)=1−4​t​αout​\(λ\)πq​\(AC​\(λ\)\)\.d\_\{t\}\(x,y\)\\geq 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\)=infC∈𝒞⁡\(λ\)VC​\(λ,t\)\.V\(\\lambda,t\)=\\inf\_\{C\\in\\mathcal\{C\}\(\\lambda\)\}V\_\{C\}\(\\lambda,t\)\.Becauset​γin​\(λ\)≫1t\\gamma\_\{\\mathrm\{in\}\}\(\\lambda\)\\gg 1andt​αout​\(λ\)≪1t\\alpha\_\{\\mathrm\{out\}\}\(\\lambda\)\\ll 1for 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 onLλL\_\{\\lambda\}with edges\{\(u,v\)∈Lλ2∣dt​\(u,v\)≤τ⁡\(λ\)\}\\\{\(u,v\)\\in L\_\{\\lambda\}^\{2\}\\mid d\_\{t\}\(u,v\)\\leq\\tau\(\\lambda\)\\\}\. The inequalitydt​\(u,v\)≤U⁡\(λ,t\)d\_\{t\}\(u,v\)\\leq U\(\\lambda,t\)foru,vu,vin the same component implies that each density componentC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)becomes connected inside this graph\. The inequalitydt​\(u,v\)≥V⁡\(λ,t\)d\_\{t\}\(u,v\)\\geq V\(\\lambda,t\)foru,vu,vin different components implies that there are no edges between different components\. Therefore the connected components of this threshold graph are exactly𝒞⁡\(λ\)\\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, definegtg\_\{t\}on critical levels bygt​\(λ\)=τ​\(λ\)g\_\{t\}\(\\lambda\)=\\tau\(\\lambda\)\. Extendgtg\_\{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 anyx,y∈Mx,y\\in Mand letλ⋆=mf​\(x,y\)\\lambda^\{\\star\}=m\_\{f\}\(x,y\)\. By definition, for everyλ<λ⋆\\lambda<\\lambda^\{\\star\}the points are connected insideLλL\_\{\\lambda\}, and for everyλ\>λ⋆\\lambda\>\\lambda^\{\\star\}they are not connected insideLλL\_\{\\lambda\}\. Since connectivity agrees at all critical levels and changes only at critical levels, the same statement holds when we restrictλ\\lambdatoΛ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 wherexxandyyare connected in the diffusion hierarchy is exactlygt​\(λ⋆\)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 calibrationgtg\_\{t\}is necessary\. Even when the two trees have the same shape, the heights live in different units\. Density heights are values offf, while diffusion heights are thresholds ondtd\_\{t\}\. The theorem says that after a monotone change of units, the two merge\-height functions coincide\.

## 5Finite\-sample theory

We now turn to data\. The algorithm is standard\. We build akk\-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\.

### 5\.1Estimator

LetX1,…,Xn∼fX\_\{1\},\\dots,X\_\{n\}\\sim fi\.i\.d\. Build the symmetrizedkk\-NN graph on\{Xi\}i=1n\\\{X\_\{i\}\\\}\_\{i=1\}^\{n\}\. Define weightsWi​j=Kσ​\(Xi,Xj\)W\_\{ij\}=K\_\{\\sigma\}\(X\_\{i\},X\_\{j\}\)if\(i,j\)\(i,j\)is an edge andWi​j=0W\_\{ij\}=0otherwise\. Define degreesDi​i=∑jWi​jD\_\{ii\}=\\sum\_\{j\}W\_\{ij\}and the random walk matrixPn=D−1​WP\_\{n\}=D^\{\-1\}W\. Let\(λ^ℓ,ψ^ℓ\)ℓ≥0\(\\hat\{\\lambda\}\_\{\\ell\},\\hat\{\\psi\}\_\{\\ell\}\)\_\{\\ell\\geq 0\}be eigenpairs ofPnP\_\{n\}withλ^0=1\\hat\{\\lambda\}\_\{0\}=1andψ^0≡1\\hat\{\\psi\}\_\{0\}\\equiv 1\. For a truncation dimensionmm, define the diffusion embedding

Φt​\(i\)=\(λ^1t​ψ^1​\(i\),…,λ^mt​ψ^m​\(i\)\)∈ℝm,d^t​\(i,j\)=‖Φt​\(i\)−Φt​\(j\)‖2\.\\Phi\_\{t\}\(i\)=\\big\(\\hat\{\\lambda\}\_\{1\}^\{t\}\\hat\{\\psi\}\_\{1\}\(i\),\\dots,\\hat\{\\lambda\}\_\{m\}^\{t\}\\hat\{\\psi\}\_\{m\}\(i\)\\big\)\\in\\mathbb\{R\}^\{m\},\\qquad\\hat\{d\}\_\{t\}\(i,j\)=\\\|\\Phi\_\{t\}\(i\)\-\\Phi\_\{t\}\(j\)\\\|\_\{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 bym^t\\hat\{m\}\_\{t\}\.

### 5\.2Stability 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\)\.

LetSSbe finite and letd,d′d,d^\{\\prime\}be symmetric dissimilarities onSSwithd⁡\(x,x\)=d′​\(x,x\)=0d\(x,x\)=d^\{\\prime\}\(x,x\)=0\. If

supx,y∈S\|d⁡\(x,y\)−d′​\(x,y\)\|≤η,\\sup\_\{x,y\\in S\}\|d\(x,y\)\-d^\{\\prime\}\(x,y\)\|\\leq\\eta,then the single\-linkage merge\-height functionsmdm\_\{d\}andmd′m\_\{d^\{\\prime\}\}satisfy

dMD​\(md,md′\)≤η\.d\_\{\\mathrm\{MD\}\}\(m\_\{d\},m\_\{d^\{\\prime\}\}\)\\leq\\eta\.

###### Proof\.

Fixx,y∈Sx,y\\in S\. For a pathπ=\(v0=x,v1,…,vk=y\)\\pi=\(v\_\{0\}=x,v\_\{1\},\\dots,v\_\{k\}=y\)define its bottleneck underddby

Bd​\(π\)=max0≤j<k⁡d⁡\(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\\leadsto y\}B\_\{d\}\(\\pi\),where the infimum is over all finite paths in the complete graph onSS\.

Assumesupu,v\|d⁡\(u,v\)−d′​\(u,v\)\|≤η\\sup\_\{u,v\}\|d\(u,v\)\-d^\{\\prime\}\(u,v\)\|\\leq\\eta\. Then for every pathπ\\pi,

\|Bd​\(π\)−Bd′​\(π\)\|≤maxj⁡\|d⁡\(vj,vj\+1\)−d′​\(vj,vj\+1\)\|≤η\.\|B\_\{d\}\(\\pi\)\-B\_\{d^\{\\prime\}\}\(\\pi\)\|\\leq\\max\_\{j\}\|d\(v\_\{j\},v\_\{j\+1\}\)\-d^\{\\prime\}\(v\_\{j\},v\_\{j\+1\}\)\|\\leq\\eta\.In particular,Bd′​\(π\)≤Bd​\(π\)\+ηB\_\{d^\{\\prime\}\}\(\\pi\)\\leq B\_\{d\}\(\\pi\)\+\\etafor allπ\\pi\. Taking infimum overπ\\pigives

md′​\(x,y\)≤md​\(x,y\)\+η\.m\_\{d^\{\\prime\}\}\(x,y\)\\leq m\_\{d\}\(x,y\)\+\\eta\.By symmetry, swappingddandd′d^\{\\prime\}givesmd​\(x,y\)≤md′​\(x,y\)\+ηm\_\{d\}\(x,y\)\\leq m\_\{d^\{\\prime\}\}\(x,y\)\+\\eta\. Therefore

\|md​\(x,y\)−md′​\(x,y\)\|≤η\.\|m\_\{d\}\(x,y\)\-m\_\{d^\{\\prime\}\}\(x,y\)\|\\leq\\eta\.Taking the supremum overx,yx,yyieldsdMD​\(md,md′\)≤ηd\_\{\\mathrm\{MD\}\}\(m\_\{d\},m\_\{d^\{\\prime\}\}\)\\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 saysmt=gt∘mfm\_\{t\}=g\_\{t\}\\circ m\_\{f\}\. The stability lemma says that ifd^t\\hat\{d\}\_\{t\}is close todtd\_\{t\}, thenm^t\\hat\{m\}\_\{t\}is close tomtm\_\{t\}\. Combining them gives a direct path from graph spectral approximation to topological recovery\.

### 5\.3Merge\-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\[[14](https://arxiv.org/html/2610.31909#bib.bib6),[6](https://arxiv.org/html/2610.31909#bib.bib9)\]\. Once we have it, the dendrogram guarantee is immediate by Lemma[4](https://arxiv.org/html/2610.31909#Thmlemma4)\.

###### Theorem 2\(Finite\-sample merge distortion\)\.

Fix a timettand assume the population meeting theorem \(Theorem[1](https://arxiv.org/html/2610.31909#Thmtheorem1)\) holds at thisttwith calibrationgtg\_\{t\}\. Assume that with probability at least1−δ1\-\\delta,

supi,j∈\[n\]\|d^t​\(i,j\)−dt​\(Xi,Xj\)\|≤ηn\.\\sup\_\{i,j\\in\[n\]\}\\big\|\\hat\{d\}\_\{t\}\(i,j\)\-d\_\{t\}\(X\_\{i\},X\_\{j\}\)\\big\|\\leq\\eta\_\{n\}\.Letmt\(n\)m\_\{t\}^\{\(n\)\}be the restriction of the population diffusion merge heightsmtm\_\{t\}toSn=\{X1,…,Xn\}S\_\{n\}=\\\{X\_\{1\},\\dots,X\_\{n\}\\\}\. Then on the same event,

dMD​\(m^t,mt\(n\)\)≤ηn\.d\_\{\\mathrm\{MD\}\}\(\\hat\{m\}\_\{t\},m\_\{t\}^\{\(n\)\}\)\\leq\\eta\_\{n\}\.In addition, ifgt−1g\_\{t\}^\{\-1\}is Lipschitz on the relevant image interval with constantLtL\_\{t\}, then

dMD​\(gt−1∘m^t,mf\(n\)\)≤Lt​ηn,d\_\{\\mathrm\{MD\}\}\(g\_\{t\}^\{\-1\}\\circ\\hat\{m\}\_\{t\},\\ m\_\{f\}^\{\(n\)\}\)\\leq L\_\{t\}\\,\\eta\_\{n\},wheremf\(n\)m\_\{f\}^\{\(n\)\}ismfm\_\{f\}restricted toSnS\_\{n\}\.

###### Proof\.

Work on the event

ℰ=\{supi,j∈\[n\]\|d^t\(i,j\)−dt\(Xi,Xj\)\|≤ηn\}\.\\mathcal\{E\}=\\Big\\\{\\sup\_\{i,j\\in\[n\]\}\|\\hat\{d\}\_\{t\}\(i,j\)\-d\_\{t\}\(X\_\{i\},X\_\{j\}\)\|\\leq\\eta\_\{n\}\\Big\\\}\.Onℰ\\mathcal\{E\}, apply Lemma[4](https://arxiv.org/html/2610.31909#Thmlemma4)with the finite setS=\[n\]S=\[n\], the dissimilarityd⁡\(i,j\)=dt​\(Xi,Xj\)d\(i,j\)=d\_\{t\}\(X\_\{i\},X\_\{j\}\), andd′​\(i,j\)=d^t​\(i,j\)d^\{\\prime\}\(i,j\)=\\hat\{d\}\_\{t\}\(i,j\)\. This gives

dMD​\(m^t,md\)≤ηn,d\_\{\\mathrm\{MD\}\}\(\\hat\{m\}\_\{t\},m\_\{d\}\)\\leq\\eta\_\{n\},wheremdm\_\{d\}is the single\-linkage merge\-height function built fromd⁡\(i,j\)=dt​\(Xi,Xj\)d\(i,j\)=d\_\{t\}\(X\_\{i\},X\_\{j\}\)\. By definition,mdm\_\{d\}is exactlymtm\_\{t\}restricted to the sample\. Thereforemd=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\)\}\)\\leq\\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\)\}\.Applygt−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\)\}=\\big\(g\_\{t\}^\{\-1\}\\circ\\hat\{m\}\_\{t\}\-g\_\{t\}^\{\-1\}\\circ m\_\{t\}^\{\(n\)\}\\big\)\+\\big\(g\_\{t\}^\{\-1\}\\circ m\_\{t\}^\{\(n\)\}\-m\_\{f\}^\{\(n\)\}\\big\)\.The second term is zero\. The first term is controlled by the Lipschitz property ofgt−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\)\|\.\\big\|g\_\{t\}^\{\-1\}\(\\hat\{m\}\_\{t\}\(i,j\)\)\-g\_\{t\}^\{\-1\}\(m\_\{t\}^\{\(n\)\}\(i,j\)\)\\big\|\\leq L\_\{t\}\\,\|\\hat\{m\}\_\{t\}\(i,j\)\-m\_\{t\}^\{\(n\)\}\(i,j\)\|\.Taking the supremum over pairs yields

dMD​\(gt−1∘m^t,mf\(n\)\)≤Lt​dMD​\(m^t,mt\(n\)\)≤Lt​ηn\.d\_\{\\mathrm\{MD\}\}\(g\_\{t\}^\{\-1\}\\circ\\hat\{m\}\_\{t\},\\ m\_\{f\}^\{\(n\)\}\)\\leq L\_\{t\}\\,d\_\{\\mathrm\{MD\}\}\(\\hat\{m\}\_\{t\},m\_\{t\}^\{\(n\)\}\)\\leq 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\.

## 6Geometry 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\.

### 6\.1Geometric meeting condition

We assume now thatMMis a compactdd\-dimensionalC2C^\{2\}Riemannian manifold with geodesic distanceρ\\rhoand volume measureμ\\mu\. We fix a localized kernelKσ​\(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Λ\\Lambdabe a finite set of levels that contains all critical merge levels of the density cluster tree\. We sayffsatisfies GMC onΛ\\Lambdaif there exist functionsf¯​\(λ\)\>0\\underline\{f\}\(\\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\)\>0such that for everyλ∈Λ\\lambda\\in\\Lambdaand everyC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)the following hold\.

1. \(GMC1\)f​\(x\)≥f¯​\(λ\)f\(x\)\\geq\\underline\{f\}\(\\lambda\)for allx∈Cx\\in C\.
2. \(GMC2\)CChas reach at leastrreach​\(λ\)r\_\{\\mathrm\{reach\}\}\(\\lambda\), meaning the tubular neighborhood projection is well\-defined up to radiusrreach​\(λ\)r\_\{\\mathrm\{reach\}\}\(\\lambda\)\. In particular,CChas no arbitrarily thin necks at scales belowrreach​\(λ\)r\_\{\\mathrm\{reach\}\}\(\\lambda\)\.
3. \(GMC3\)for everyx∈Cx\\in Cand every0<r≤rreach​\(λ\)0<r\\leq r\_\{\\mathrm\{reach\}\}\(\\lambda\), the local volume satisfies vmin​\(λ\)​rd≤μ⁡\(B⁡\(x,r\)∩C\)≤vmax​\(λ\)​rd\.v\_\{\\min\}\(\\lambda\)\\,r^\{d\}\\leq\\mu\(B\(x,r\)\\cap C\)\\leq v\_\{\\max\}\(\\lambda\)\\,r^\{d\}\.
4. \(GMC4\)ifC≠C′C\\neq C^\{\\prime\}are distinct components in𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\), then every continuous path fromCCtoC′C^\{\\prime\}must pass through a pointzzwithf⁡\(z\)≤λ−Δvalley​\(λ\)f\(z\)\\leq\\lambda\-\\Delta\_\{\\mathrm\{valley\}\}\(\\lambda\)\.

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

### 6\.2Geometry implies metastability

The next theorem turns GMC into the two quantitative bounds required by TMC\. The core idea is that a local kernel walk at scaleσ\\sigmabehaves 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\}/\\mathrm\{diam\}\(C\)^\{2\}up to geometry factors\. For leakage, the transition probability across the boundary is suppressed because the kernel multiplies byf⁡\(y\)f\(y\), and the valley forcesffto be much smaller outside\.

###### Theorem 3\(GMC implies levelwise metastability\)\.

Assume GMC onΛ\\Lambdaand assumeσ\\sigmais small enough thatKσ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\\Lambdaand everyC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)there exists a dominating reflected chainPCP\_\{C\}with spectral gap at leastγin​\(λ\)\\gamma\_\{\\mathrm\{in\}\}\(\\lambda\), and the leakage satisfiessupx∈CP⁡\(x,Cc\)≤αout​\(λ\)\\sup\_\{x\\in C\}P\(x,C^\{c\}\)\\leq\\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\}\}\{\\mathrm\{diam\}\(C\)^\{2\}\}\\cdot\\frac\{v\_\{\\min\}\(\\lambda\)\}\{v\_\{\\max\}\(\\lambda\)\}\\cdot\\underline\{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 ofMM\.

###### 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\\LambdaandC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)\. Define the kernel mass

q⁡\(x\)=∫MKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\),qC​\(x\)=∫CKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\)\.q\(x\)=\\int\_\{M\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\),\\qquad q\_\{C\}\(x\)=\\int\_\{C\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\)\.The original transition isp⁡\(x,d​y\)=Kσ​\(x,y\)​f​\(y\)​q​\(x\)−1​d​μ​\(y\)p\(x,dy\)=K\_\{\\sigma\}\(x,y\)f\(y\)q\(x\)^\{\-1\}d\\mu\(y\)\. We define a reflected transition supported onCCby

pC​\(x,d​y\)=Kσ​\(x,y\)​f​\(y\)qC​\(x\)​1y∈C​d​μ​\(y\)\.p\_\{C\}\(x,dy\)=\\frac\{K\_\{\\sigma\}\(x,y\)f\(y\)\}\{q\_\{C\}\(x\)\}\\,\\mathbf\{1\}\_\{y\\in C\}\\,d\\mu\(y\)\.This stays insideCCby 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 ofpptoCCbecauseqC​\(x\)≤q​\(x\)q\_\{C\}\(x\)\\leq q\(x\)implies

pC​\(x,B\)=1qC​\(x\)​∫BKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\)≥1q⁡\(x\)​∫BKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\)=p⁡\(x,B\)p\_\{C\}\(x,B\)=\\frac\{1\}\{q\_\{C\}\(x\)\}\\int\_\{B\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\)\\geq\\frac\{1\}\{q\(x\)\}\\int\_\{B\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\)=p\(x,B\)for every measurableB⊂CB\\subset Cand everyx∈Cx\\in C\. This gives a dominating chain in the sense of Definition[6](https://arxiv.org/html/2610.31909#Thmdefinition6)\.

*Step 2\. Leakage bound\.*Forx∈Cx\\in Cwe have

P⁡\(x,Cc\)=∫CcKσ​\(x,y\)​f​\(y\)q⁡\(x\)​𝑑μ​\(y\)=∫CcKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\)∫MKσ​\(x,y\)​f​\(y\)​𝑑μ​\(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\. Fixr≍σr\\asymp\\sigmasmall enough so thatB⁡\(x,r\)⊆CB\(x,r\)\\subseteq Cfor pointsxxthat are at distance at leastrrfrom∂C\\partial C\. For boundary points we use reach to say thatB⁡\(x,r\)∩CB\(x,r\)\\cap Cstill has volume at least a constant fraction ofrdr^\{d\}\. By GMC, onCCwe havef≥f¯​\(λ\)f\\geq\\underline\{f\}\(\\lambda\)\. AlsoKσ​\(x,y\)≥exp\(−r2/σ2\)K\_\{\\sigma\}\(x,y\)\\geq\\exp\(\-r^2/\\sigma^2\)onρ⁡\(x,y\)≤r\\rho\(x,y\)\\leq r\. Therefore

q⁡\(x\)≥∫B⁡\(x,r\)∩CKσ​\(x,y\)​f​\(y\)​𝑑μ​\(y\)≥exp\(−r2/σ2\)​f¯​\(λ\)​μ​\(B⁡\(x,r\)∩C\)≳f¯​\(λ\)​vmin​\(λ\)​rd\.q\(x\)\\geq\\int\_\{B\(x,r\)\\cap C\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\)\\geq\\exp\(\-r^2/\\sigma^2\)\\,\\underline\{f\}\(\\lambda\)\\,\\mu\(B\(x,r\)\\cap C\)\\gtrsim\\underline\{f\}\(\\lambda\)\\,v\_\{\\min\}\(\\lambda\)\\,r^\{d\}\.We upper bound the numerator using the valley depth\. Any pointyythat contributes to leavingCCmust be in a region that is connected to another component only through values offfat mostλ−Δvalley​\(λ\)\\lambda\-\\Delta\_\{\\mathrm\{valley\}\}\(\\lambda\)\. In particular, outsideCCnear the boundary ofCCthere exist regions whereffis 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\)​𝑑μ​\(y\)≤\(λ−Δvalley​\(λ\)\)​∫CcKσ​\(x,y\)​𝑑μ​\(y\)\.\\int\_\{C^\{c\}\}K\_\{\\sigma\}\(x,y\)f\(y\)\\,d\\mu\(y\)\\leq\(\\lambda\-\\Delta\_\{\\mathrm\{valley\}\}\(\\lambda\)\)\\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\)​𝑑μ​\(y\)\\int\_\{\\rho\(x,y\)\\geq r\}K\_\{\\sigma\}\(x,y\)\\,d\\mu\(y\)is at mostexp\(−cr2/σ2\)\\exp\(\-c r^2/\\sigma^2\)times a polynomial factor\. Choosingr≍σr\\asymp\\sigmagives 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\)\}\{\\underline\{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\)=infh∈L2\(πq\(⋅∣C\)\)∫hdπq\(⋅∣C\)=0ℰC​\(h,h\)Varπq\(⋅∣C\)\(h\),\\gamma\(P\_\{C\}\)=\\inf\_\{\\begin\{subarray\}\{c\}h\\in L^\{2\}\(\\pi\_\{q\}\(\\cdot\\mid C\)\)\\\\ \\int h\\,d\\pi\_\{q\}\(\\cdot\\mid C\)=0\\end\{subarray\}\}\\frac\{\\mathcal\{E\}\_\{C\}\(h,h\)\}\{\\mathrm\{Var\}\_\{\\pi\_\{q\}\(\\cdot\\mid C\)\}\(h\)\},where the Dirichlet form is

ℰC​\(h,h\)=12​∫C∫C\(h⁡\(x\)−h⁡\(y\)\)2​pC​\(x,𝑑y\)​d​πq​\(x∣C\)\.\\mathcal\{E\}\_\{C\}\(h,h\)=\\frac\{1\}\{2\}\\int\_\{C\}\\int\_\{C\}\(h\(x\)\-h\(y\)\)^\{2\}\\,p\_\{C\}\(x,dy\)\\,d\\pi\_\{q\}\(x\\mid C\)\.For the localized Gaussian kernel and smallσ\\sigma, the chainPCP\_\{C\}behaves like a local averaging operator at scaleσ\\sigma\. Standard kernel calculations on manifolds show thatℰC​\(h,h\)\\mathcal\{E\}\_\{C\}\(h,h\)controls an energy of the formσ2∫C∥∇h∥2dπq\(⋅∣C\)\\sigma^\{2\}\\int\_\{C\}\\\|\\nabla h\\\|^\{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 onCCat scale comparable todiam⁡\(C\)\\mathrm\{diam\}\(C\)\. In its simplest form it says

Varπq\(⋅∣C\)\(h\)≲diam\(C\)2⋅vmax​\(λ\)vmin​\(λ\)⋅1f¯​\(λ\)∫C∥∇h∥2dπq\(⋅∣C\),\\mathrm\{Var\}\_\{\\pi\_\{q\}\(\\cdot\\mid C\)\}\(h\)\\lesssim\\mathrm\{diam\}\(C\)^\{2\}\\cdot\\frac\{v\_\{\\max\}\(\\lambda\)\}\{v\_\{\\min\}\(\\lambda\)\}\\cdot\\frac\{1\}\{\\underline\{f\}\(\\lambda\)\}\\int\_\{C\}\\\|\\nabla h\\\|^\{2\}\\,d\\pi\_\{q\}\(\\cdot\\mid C\),where the volume growth constants and the lower bound onffensure the measureπq\(⋅∣C\)\\pi\_\{q\}\(\\cdot\\mid C\)is comparable toμ\\muonCCup to factors\. Combining the two displays gives

ℰC​\(h,h\)Varπq\(⋅∣C\)\(h\)≳σ2diam​\(C\)2⋅vmin​\(λ\)vmax​\(λ\)⋅f¯​\(λ\),\\frac\{\\mathcal\{E\}\_\{C\}\(h,h\)\}\{\\mathrm\{Var\}\_\{\\pi\_\{q\}\(\\cdot\\mid C\)\}\(h\)\}\\gtrsim\\frac\{\\sigma^\{2\}\}\{\\mathrm\{diam\}\(C\)^\{2\}\}\\cdot\\frac\{v\_\{\\min\}\(\\lambda\)\}\{v\_\{\\max\}\(\\lambda\)\}\\cdot\\underline\{f\}\(\\lambda\),uniformly over mean\-zerohh\. 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\.

### 6\.3Multiscale 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 schedulet⁡\(λ\)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\. Lett⁡\(λ\)t\(\\lambda\)be a schedule defined onΛ\\Lambdasuch that for eachλ\\lambdait lies inside the levelwise metastable window, andt⁡\(λ\)t\(\\lambda\)is nonincreasing inλ\\lambda\.

###### Definition 8\(Multiscale diffusion dissimilarity\)\.

Fix a scheduleλ↦t⁡\(λ\)\\lambda\\mapsto t\(\\lambda\)defined onΛ\\Lambda\. Forx,y∈Mx,y\\in M, define

dMS\(x,y\)=inf\{dt⁡\(λ\)\(x,y\)\|λ∈Λ,λ≤mf\(x,y\)\}\.d\_\{\\mathrm\{MS\}\}\(x,y\)=\\inf\\Big\\\{d\_\{t\(\\lambda\)\}\(x,y\)\\,\\Big\|\\,\\lambda\\in\\Lambda,\\ \\lambda\\leq m\_\{f\}\(x,y\)\\Big\\\}\.LetTMST^\{\\mathrm\{MS\}\}be the single\-linkage dendrogram built from\(M,dMS\)\(M,d\_\{\\mathrm\{MS\}\}\), with merge\-height functionmMSm\_\{\\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λ\\lambdacomes from diffusion timet⁡\(λ\)t\(\\lambda\)\.

###### Theorem 4\(Multiscale meeting theorem\)\.

Assume GMC onΛ\\Lambdaand lett⁡\(λ\)t\(\\lambda\)be any schedule such that for everyλ∈Λ\\lambda\\in\\Lambdathe timet⁡\(λ\)t\(\\lambda\)lies in the corresponding levelwise metastable window given by Theorem[3](https://arxiv.org/html/2610.31909#Thmtheorem3)\. Then there exists a strictly increasing functiongMSg\_\{\\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\.HenceTMST^\{\\mathrm\{MS\}\}is isomorphic toTfT\_\{f\}as a merge tree\.

###### Proof\.

Fixλ∈Λ\\lambda\\in\\Lambda\. Consider the diffusion distance at timet⁡\(λ\)t\(\\lambda\)\. By Theorem[3](https://arxiv.org/html/2610.31909#Thmtheorem3), the pair\(f,P\)\(f,P\)satisfies the levelwise metastability bounds at this time\. Therefore, by applying Lemma[2](https://arxiv.org/html/2610.31909#Thmlemma2)and Lemma[3](https://arxiv.org/html/2610.31909#Thmlemma3)at timet⁡\(λ\)t\(\\lambda\), we obtain two numbersU⁡\(λ\)U\(\\lambda\)andV⁡\(λ\)V\(\\lambda\)such that

supC∈𝒞⁡\(λ\)supx,y∈Cdt⁡\(λ\)​\(x,y\)≤U⁡\(λ\),infC≠C′C,C′∈𝒞⁡\(λ\)infx∈C,y∈C′dt⁡\(λ\)​\(x,y\)≥V⁡\(λ\),\\sup\_\{C\\in\\mathcal\{C\}\(\\lambda\)\}\\sup\_\{x,y\\in C\}d\_\{t\(\\lambda\)\}\(x,y\)\\leq U\(\\lambda\),\\qquad\\inf\_\{\\begin\{subarray\}\{c\}C\\neq C^\{\\prime\}\\\\ C,C^\{\\prime\}\\in\\mathcal\{C\}\(\\lambda\)\\end\{subarray\}\}\\inf\_\{x\\in C,y\\in C^\{\\prime\}\}d\_\{t\(\\lambda\)\}\(x,y\)\\geq V\(\\lambda\),and moreoverU⁡\(λ\)<V⁡\(λ\)U\(\\lambda\)<V\(\\lambda\)becauset⁡\(λ\)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 onLλL\_\{\\lambda\}with edges\{dt⁡\(λ\)≤τ\(λ\)\}\\\{d\_\{t\(\\lambda\)\}\\leq\\tau\(\\lambda\)\\\}has connected components exactly𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)\.

Now we transfer this property to the multiscale dissimilaritydMSd\_\{\\mathrm\{MS\}\}\. First takex,yx,yin the same componentC∈𝒞⁡\(λ\)C\\in\\mathcal\{C\}\(\\lambda\)\. Thenmf​\(x,y\)≥λm\_\{f\}\(x,y\)\\geq\\lambda\. By definition ofdMSd\_\{\\mathrm\{MS\}\}, the infimum is taken over allλ′∈Λ\\lambda^\{\\prime\}\\in\\Lambdawithλ′≤mf​\(x,y\)\\lambda^\{\\prime\}\\leq m\_\{f\}\(x,y\), in particular it includesλ\\lambdaitself\. Therefore

dMS​\(x,y\)≤dt⁡\(λ\)​\(x,y\)≤U⁡\(λ\)<τ⁡\(λ\)\.d\_\{\\mathrm\{MS\}\}\(x,y\)\\leq d\_\{t\(\\lambda\)\}\(x,y\)\\leq U\(\\lambda\)<\\tau\(\\lambda\)\.So all pairs inside eachCChavedMSd\_\{\\mathrm\{MS\}\}belowτ⁡\(λ\)\\tau\(\\lambda\)and thus eachCCis connected in the threshold graph built fromdMSd\_\{\\mathrm\{MS\}\}\.

Next takex∈Cx\\in Candy∈C′y\\in C^\{\\prime\}for two distinct componentsC≠C′C\\neq C^\{\\prime\}in𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)\. Thenmf​\(x,y\)<λm\_\{f\}\(x,y\)<\\lambda\. This means that for everyλ′∈Λ\\lambda^\{\\prime\}\\in\\Lambdawithλ′≤mf​\(x,y\)\\lambda^\{\\prime\}\\leq m\_\{f\}\(x,y\), we haveλ′<λ\\lambda^\{\\prime\}<\\lambda\. In particular, at levelλ\\lambdathe points lie in different components, so the separating valley at levelλ\\lambdais present\. The definition ofτ⁡\(λ\)\\tau\(\\lambda\)and the separation bound at timet⁡\(λ\)t\(\\lambda\)imply that for any such pair,

dt⁡\(λ\)​\(x,y\)≥V⁡\(λ\)\>τ⁡\(λ\)\.d\_\{t\(\\lambda\)\}\(x,y\)\\geq V\(\\lambda\)\>\\tau\(\\lambda\)\.SincedMS​\(x,y\)d\_\{\\mathrm\{MS\}\}\(x,y\)is an infimum over diffusion distances at levelsλ′≤mf​\(x,y\)\\lambda^\{\\prime\}\\leq 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\-λ\\lambdabottleneck\. Indeed, ifdMS​\(x,y\)≤τ⁡\(λ\)d\_\{\\mathrm\{MS\}\}\(x,y\)\\leq\\tau\(\\lambda\)then there would exist someλ′≤mf​\(x,y\)\\lambda^\{\\prime\}\\leq m\_\{f\}\(x,y\)withdt⁡\(λ′\)​\(x,y\)≤τ⁡\(λ\)d\_\{t\(\\lambda^\{\\prime\}\)\}\(x,y\)\\leq\\tau\(\\lambda\)\. Butλ′≤mf​\(x,y\)<λ\\lambda^\{\\prime\}\\leq m\_\{f\}\(x,y\)<\\lambdaimplies thatxxandyyare already separated before levelλ\\lambda, hence the valley that separatesCCandC′C^\{\\prime\}is still present, and the same between\-component argument applies to show thatdt⁡\(λ′\)​\(x,y\)d\_\{t\(\\lambda^\{\\prime\}\)\}\(x,y\)cannot be as small asτ⁡\(λ\)\\tau\(\\lambda\)\. ThereforedMS​\(x,y\)\>τ⁡\(λ\)d\_\{\\mathrm\{MS\}\}\(x,y\)\>\\tau\(\\lambda\)for pairs in different components of𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)\.

We have shown that for eachλ∈Λ\\lambda\\in\\Lambda, the connected components of the threshold graph onLλL\_\{\\lambda\}with edges\{dMS≤τ\(λ\)\}\\\{d\_\{\\mathrm\{MS\}\}\\leq\\tau\(\\lambda\)\\\}are exactly𝒞⁡\(λ\)\\mathcal\{C\}\(\\lambda\)\. This is the same connectivity agreement used in the proof of Theorem[1](https://arxiv.org/html/2610.31909#Thmtheorem1)\. DefinegMS​\(λ\)=τ​\(λ\)g\_\{\\mathrm\{MS\}\}\(\\lambda\)=\\tau\(\\lambda\)onΛ\\Lambdaand 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 allx,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 dissimilaritydMSd\_\{\\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\.

## 7Discussion

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 onkk\-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 onkk\-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

- \[CD10\]K\. Chaudhuri and S\. Dasgupta\(2010\)Rates of convergence for the cluster tree\.InAdvances in Neural Information Processing Systems \(NeurIPS\),Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p1.1),[§1](https://arxiv.org/html/2610.31909#S1.p2.1),[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.1](https://arxiv.org/html/2610.31909#S2.SS1.p1.2),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.3)\.
- \[CEH07\]D\. Cohen\-Steiner, H\. Edelsbrunner, and J\. Harer\(2007\)Stability of persistence diagrams\.Discrete & Computational Geometry37\(1\),pp\. 103–120\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p5.1)\.
- \[CL06\]R\. R\. Coifman and S\. Lafon\(2006\)Diffusion maps\.Applied and Computational Harmonic Analysis21\(1\),pp\. 5–30\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p1.1),[§1](https://arxiv.org/html/2610.31909#S1.p2.1),[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.2](https://arxiv.org/html/2610.31909#S2.SS2.p1.2),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p2.4),[Definition 2](https://arxiv.org/html/2610.31909#Thmdefinition2),[Lemma 1](https://arxiv.org/html/2610.31909#Thmlemma1)\.
- \[EH10\]H\. Edelsbrunner and J\. Harer\(2010\)Computational topology: an introduction\.American Mathematical Society\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p5.1)\.
- \[EBW15\]J\. Eldridge, M\. Belkin, and Y\. Wang\(2015\)Beyond hartigan consistency: merge distortion metric for hierarchical clustering\.Journal of Machine Learning Research16,pp\. 2817–2844\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p1.1),[§1](https://arxiv.org/html/2610.31909#S1.p2.1),[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.3),[§2\.4](https://arxiv.org/html/2610.31909#S2.SS4.p3.1),[Definition 3](https://arxiv.org/html/2610.31909#Thmdefinition3)\.
- \[GS20\]N\. García Trillos and D\. Slepčev\(2020\)A variational approach to the consistency of spectral clustering\.Applied and Computational Harmonic Analysis45\(2\),pp\. 239–281\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p3.1),[§5\.3](https://arxiv.org/html/2610.31909#S5.SS3.p1.1)\.
- \[HAR81\]J\. A\. Hartigan\(1981\)Consistency of single linkage for high\-density clusters\.Journal of the American Statistical Association76\(374\),pp\. 388–394\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p1.1),[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.1](https://arxiv.org/html/2610.31909#S2.SS1.p1.2)\.
- \[LQ65\]D\. O\. Loftsgaarden and C\. P\. Quesenberry\(1965\)A nonparametric estimate of a multivariate density function\.The Annals of Mathematical Statistics36\(3\),pp\. 1049–1051\.Cited by:[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p2.2)\.
- \[NJW02\]A\. Y\. Ng, M\. I\. Jordan, and Y\. Weiss\(2002\)On spectral clustering: analysis and an algorithm\.InAdvances in Neural Information Processing Systems,Vol\.14\.Cited by:[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p1.1),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p1.2)\.
- \[PAR62\]E\. Parzen\(1962\)On estimation of a probability density function and mode\.The Annals of Mathematical Statistics33\(3\),pp\. 1065–1076\.Cited by:[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.1)\.
- \[ROS56\]M\. Rosenblatt\(1956\)Remarks on some nonparametric estimates of a density function\.The Annals of Mathematical Statistics27\(3\),pp\. 832–837\.Cited by:[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.1)\.
- \[SM00\]J\. Shi and J\. Malik\(2000\)Normalized cuts and image segmentation\.InProceedings of the IEEE Conference on Computer Vision and Pattern Recognition,pp\. 731–737\.Cited by:[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p1.1)\.
- \[SIL86\]B\. W\. Silverman\(1986\)Density estimation for statistics and data analysis\.Chapman and Hall\.Cited by:[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.3)\.
- \[vBB08\]U\. von Luxburg, M\. Belkin, and O\. Bousquet\(2008\)Consistency of spectral clustering\.The Annals of Statistics36\(2\),pp\. 555–586\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p3.1),[§5\.3](https://arxiv.org/html/2610.31909#S5.SS3.p1.1)\.
- \[VON07\]U\. von Luxburg\(2007\)A tutorial on spectral clustering\.Statistics and Computing17\(4\),pp\. 395–416\.Cited by:[§1](https://arxiv.org/html/2610.31909#S1.p1.1),[§1](https://arxiv.org/html/2610.31909#S1.p2.1),[§1](https://arxiv.org/html/2610.31909#S1.p5.1),[§2\.4](https://arxiv.org/html/2610.31909#S2.SS4.p2.1),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p1.1),[§2\.5](https://arxiv.org/html/2610.31909#S2.SS5.p1.2)\.
- \[WAS06\]L\. Wasserman\(2006\)All of nonparametric statistics\.Springer\.Cited by:[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.1),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p1.3),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p2.1),[§2\.3](https://arxiv.org/html/2610.31909#S2.SS3.p2.2)\.