WorksComputer Science
Topological Equivalence of Spectral and Density Cluster Hierarchies
Abstract
We compare two canonical ways to recover hierarchical clustering from an underlying density : the density cluster tree given by connected components of superlevel sets , 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 -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 on a compact domain . The first one is the density cluster tree , defined by the connected components of the superlevel sets of the underlying density function as decreases [7, 1, 4]. The second one is a diffusion–spectral hierarchy, defined as a reversible Markov operator (or a Laplacian) from [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 .
To make the comparison precise we use merge heights. The density tree can be encoded by the merge-height function
The diffusion hierarchy at time is the single-linkage dendrogram built from , and it has its own merge-height function . 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 such that 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 and every component of , we require two quantitative facts about the chain, it mixes fast inside , and also has small probability to exit 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 -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 -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 with a Borel measure . The data distribution is a probability measure that admits a continuous density with respect to , so and . We observe i.i.d. samples . For each level we write and for the connected components of in the topology of . The density cluster tree is encoded by the merge-height function defined from these components.
We keep regularity assumptions on 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 on regions of interest. The important point is that plays two roles. It defines the topology of the level sets , and it also biases the diffusion process that we build from the data.
To define diffusion, we fix a symmetric kernel . We set
The operator is a Markov operator with stationary measure , and we work in . We write for the -step transition law of the Markov chain with transition kernel . We write for diffusion distance at time , defined as an distance between the -step transition densities. We write for the density cluster tree, and for the single-linkage hierarchy built from with merge-height function . For a finite set we write for merge distortion between merge-height functions on . We use for norms, for operator norms, and for total variation norms.
Density cluster tree and merge heights
The density cluster tree is the hierarchy obtained from the superlevel sets
when goes from large to small [7, 1]. For a fixed , the set can split into several connected components. When 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 , define
The function is symmetric, and it is larger when and stay connected until a higher density level. If 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 . We define
Then is a Markov operator. It is reversible with respect to a stationary measure whose density is proportional to with respect to [2]. The associated random process is the Markov chain with transition rule .
Diffusion distance compares two starting points by comparing their -step transition laws. If two points are in the same well connected region, their -step distributions become similar. If they are separated by a bottleneck, their -step distributions stay different.
Definition 2 (Diffusion distance [2]). Let be the -step transition law from , and assume is absolutely continuous with respect to . Define
Reversibility implies that is self-adjoint in . Therefore there exists an orthonormal eigenbasis with real eigenvalues such that
In this setting diffusion distance has a simple spectral form.
Lemma 1 (Spectral formula for diffusion distance [2]). For all and all integers ,
Proof sketch. Write the Radon–Nikodym derivative of with respect to using the eigenbasis of in . Apply to see how each mode scales with . The squared 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 suppresses modes with . In this sense controls the scale at which the geometry is observed.
Parzen windows, kernel density estimation, and -NN density estimation
In practice is unknown, so level sets are not directly available. A classical way to estimate is the Parzen window method, also called kernel density estimation [10, 11, 12, 16]. In Euclidean space with Lebesgue measure, the standard KDE has the form
where is a bandwidth and is a nonnegative kernel with . On a general metric measure space one can write the same idea using a pairwise kernel
A typical choice is with a radial profile and a normalizing constant that depends on and the geometry of . Under smoothness assumptions on and mild conditions on , one gets pointwise and uniform convergence of to when and , with the usual bias and variance tradeoff [12, 16]. In density clustering, one can use to define empirical superlevel sets and then build an estimated cluster tree [1, 4].
A different estimator uses nearest neighbors [8, 16]. Let be the distance from to its th nearest neighbor among in the metric . Let denote the -volume of the ball . A standard -NN density estimator is
This estimator adapts to local sampling density because shrinks in high-density regions and grows in low-density regions. The parameter controls smoothing. Under regularity assumptions on and , consistency holds when and [8, 16]. The -NN idea is also the backbone of the graph constructions in this paper, because the -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 -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 everywhere.
Single linkage, MST, and merge distortion
Let be a finite set and let be a symmetric dissimilarity on with . Single linkage builds a dendrogram by increasing a threshold and looking at the graph on with edges
As increases, connected components merge. The merge height is the smallest where and become connected.
There is also an equivalent path view. Consider any path from to in the complete graph on . Look at the largest edge length along that path. Then 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 be finite and let be symmetric merge-height functions. Define
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 , define an affinity matrix with entries , often of the form or a sparsified version using a -NN graph. Let be the diagonal degree matrix . The unnormalized graph Laplacian is , and common normalized versions are
Spectral clustering uses the leading eigenvectors of one of these Laplacians to embed the data into , then it clusters in that embedding, typically by -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
This is exactly the discrete analogue of the Markov operator in the population. The -step transition matrix describes how probability mass spreads on the graph after steps. Diffusion distance is the distance between these -step transition distributions. In the finite graph setting, if is the stationary distribution of , then a discrete diffusion distance can be written as
This distance has a spectral representation that mirrors Lemma 1. If are eigenpairs of in , then
and this is exactly the diffusion map embedding of [2]. The factor makes a scale parameter. Small keeps many modes and sees local structure, while large 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 is built from the kernel and the density, and the empirical operator is built from the sample. When approximates 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 . Define the diffusion hierarchy as the single-linkage dendrogram built on . Its merge-height function is denoted . It is defined as the smallest threshold at which and become connected in the graph with edges . One can implement this on an -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 meets if there exists a strictly increasing function such that
This definition is strong. It says the two merge trees are isomorphic. Only the height scale changes by .
Metastability interface
The meeting mechanism is metastability. For each density level and each component , we need fast mixing inside and slow leakage out of . Both are measured at diffusion time . We define two quantities. The leakage is
The mixing rate is defined using a comparison chain supported on . A convenient device is a reflected or dominating chain that stays in and dominates the restriction of to .
Definition 5 (Dominating in-component chain). Fix a measurable set with . A Markov operator supported on is called dominating if for every and every measurable we have , and is reversible with stationary measure .
Dominating chains exist in standard settings by reflecting mass that would exit back into . In this paper we treat existence as part of the assumption interface.
Definition 6 (Topological Meeting Condition). We say satisfies TMC if there exist functions and and functions such that for every level and every component the following hold.
(TMC1) There exists a dominating chain on whose spectral gap in is at least .
Equivalently, if is the second-largest eigenvalue of , then .
(TMC2) Leakage from under is small and satisfies .
(TMC3) There is a metastable time window. For every we have . For all one has and . Also, along the tree order, higher density levels should not require larger times. The map is nonincreasing and the map 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 with a chain that is forced to stay inside . The chain mixes quickly, so the -step transition densities from any two starting points become close. The true chain differs from only when it exits , and this is controlled by the one-step leakage.
Lemma 2 (Within-component contraction). Fix and let . Assume is a dominating chain on with spectral gap at least . Assume with . Let and let be the corresponding -step transition densities for and with respect to , with extended by zero outside . Then for all and all ,
Proof. We split the difference into an in-component mixing part and two exit-error parts
We bound the middle term using the spectral gap of . Since is reversible with stationary measure , it is self-adjoint on . Let be the averaging operator on given by . The spectral gap assumption implies the standard contraction on mean-zero functions
Apply this with interpreted in the usual way through -step densities. A clean way is to work directly with -step densities. The function is a density on with respect to scaled by the factor . The difference has integral over . Therefore
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 on with respect to , one has
This bound holds when the one-step kernel has bounded density relative to , which is the case in the standard compact kernel setting that we use later in the geometric section. With this bound we get
It remains to bound the exit-error terms. We show that and similarly for .
Let . Since can leave in one step with probability at most from any point of , a union bound gives
The dominating chain stays inside , so . Therefore the signed measure has total variation at most . Write , which is the Radon–Nikodym derivative of with respect to . The function integrates to and its norm equals . Also, is supported on , and we can use the inequality for functions supported on a set of -mass at least , which here is enough because the part of inside carries all the mass of while the missing mass is at most . This yields
Doing the same for and combining the three bounds gives
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 that contains one component and the valley in front of it. Starting from the component, the chain stays in with high probability for steps. Starting from the other component, the chain enters with small probability for steps. This difference of probabilities gives a lower bound on the distance by Cauchy–Schwarz.
Lemma 3 (Between-component separation). Fix . Let be distinct components. Assume there exists a measurable set such that is measurable, , and the following two bounds hold for some
*Assume also that . Then for all and all ,
Proof. Fix and . We first bound from below. Consider the event that the chain starting from leaves at some step in . By a union bound and the first assumption,
Therefore
Next we bound from above. For the chain to be in at time , it must enter at some step . By another union bound and the second assumption,
Subtracting the bounds gives
Now write and . Then
Apply Cauchy–Schwarz on
Therefore
Finally we replace by which is weaker but convenient in later uniform arguments, since implies .
This lemma gives the outside part. It says that if there is a region 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 . In the full meeting theorem we use this with 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 , all within-component diffusion distances are below a number . All between-component diffusion distances are above a number . If , then any threshold in between recovers exactly the connected components at level . If this holds at every merge level and the tree has only finitely many merge levels, we can choose one that works for all of them.
Theorem 1 (Population meeting under TMC). Assume *satisfies TMC. Assume also that the density cluster tree has finitely many critical merge levels. Then there exists an integer time such that for all critical levels one has . For this there exists a strictly increasing function such that
Hence and are isomorphic as merge trees.
Proof. Let be the finite set of critical merge levels of the density cluster tree. By TMC3, for each there is a nonempty integer interval where mixing dominates leakage at level . 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 is finite and the windows are nonempty, we can pick a single integer time
Fix this for the rest of the proof.
For each critical level , we construct a threshold that makes diffusion connectivity match density connectivity on . Consider the collection of components . For each , Lemma 2 gives a uniform bound
Let
Next we lower bound diffusion distances between distinct components. Fix two distinct components . Since and are distinct connected components of , any path from to must leave . This gives a natural valley region in between them. In the TMC interface we encode this by assuming that for each component there exists a measurable set such that satisfies the two-sided bottleneck condition in Lemma 3 with parameter . Applying Lemma 3 gives, for all and ,
Let
Because and for all and because the constants depend only on , we can ensure that for every critical level
This is the quantitative separation needed for topology. Now fix a critical level . Choose any threshold such that
Consider the graph on with edges . The inequality for in the same component implies that each density component becomes connected inside this graph. The inequality for in different components implies that there are no edges between different components. Therefore the connected components of this threshold graph are exactly .
We have proved that for each critical level , diffusion thresholding at recovers exactly the same component partition as the density superlevel set at level . This implies that the merge trees are the same, up to a monotone rescaling of heights. To formalize this, define on critical levels by . Extend to all of as a strictly increasing function, for example by linear interpolation between consecutive critical levels and any strictly increasing continuation below .
Finally fix any and let . By definition, for every the points are connected inside , and for every they are not connected inside . Since connectivity agrees at all critical levels and changes only at critical levels, the same statement holds when we restrict to . The diffusion threshold graphs at thresholds have exactly the same connectivity at these critical levels. Therefore the largest height where and are connected in the diffusion hierarchy is exactly . This is the identity
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 is necessary. Even when the two trees have the same shape, the heights live in different units. Density heights are values of , while diffusion heights are thresholds on . 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 -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 i.i.d. Build the symmetrized -NN graph on . Define weights if is an edge and otherwise. Define degrees and the random walk matrix . Let be eigenpairs of with and . For a truncation dimension , define the diffusion embedding
Run single linkage on the dissimilarity matrix and denote the resulting merge heights by .
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 , then every path bottleneck changes by at most , and taking the best path cannot increase this. So the entire merge-height function changes by at most .
Lemma 4 (Single-linkage stability in merge distortion). Let be finite and let be symmetric dissimilarities on with . If
then the single-linkage merge-height functions and satisfy
Proof. Fix . For a path define its bottleneck under by
A standard characterization of single linkage is
where the infimum is over all finite paths in the complete graph on . Assume . Then for every path ,
In particular, for all . Taking infimum over gives
By symmetry, swapping and gives . Therefore
Taking the supremum over yields .
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 . The stability lemma says that if is close to , then is close to . 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 and assume the population meeting theorem (Theorem 1) holds at this with calibration . Assume that with probability at least ,
Let be the restriction of the population diffusion merge heights to . Then on the same event,
In addition, if is Lipschitz on the relevant image interval with constant , then
where is restricted to .
Proof. Work on the event
On , apply Lemma 4 with the finite set , the dissimilarity , and . This gives
where is the single-linkage merge-height function built from . By definition, is exactly restricted to the sample. Therefore and we obtain
For the second claim, use the population meeting identity restricted to the sample
Apply to both sides and write
The second term is zero. The first term is controlled by the Lipschitz property of . For every pair ,
Taking the supremum over pairs yields
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, -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 such that any two distinct merge events in differ by at least , then whenever , the dendrogram defined by has exactly the same merge-tree topology as . The reason is that the merge-tree topology depends only on the ordering of merge heights, and a merge distortion smaller than 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 is a compact -dimensional Riemannian manifold with geodesic distance and volume measure . We fix a localized kernel for small . We state a condition on superlevel components.
Definition 7 (Geometric Meeting Condition). Let be a finite set of levels that contains all critical merge levels of the density cluster tree. We say satisfies GMC on if there exist functions , , , , and such that for every and every the following hold.
(GMC1) for all .
(GMC2) has reach at least , meaning the tubular neighborhood projection is well-defined up to radius . In particular, has no arbitrarily thin necks at scales below .
(GMC3) for every and every , the local volume satisfies
(GMC4) if are distinct components in , then every continuous path from to must pass through a point with .
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 behaves like a reflected diffusion at scale . Inside a regular set, such a diffusion has spectral gap of order up to geometry factors. For leakage, the transition probability across the boundary is suppressed because the kernel multiplies by , and the valley forces to be much smaller outside.
Theorem 3 (GMC implies levelwise metastability). Assume GMC on and assume is small enough that is effectively supported on . Then there exist functions and such that for every and every there exists a dominating reflected chain with spectral gap at least , and the leakage satisfies . Moreover one can take bounds of the form
where constants depend only on kernel regularity and bounded geometry of .
Proof. We construct a reflected chain and then bound its spectral gap and the leakage.
Step 1. Construction of a reflected dominating chain. Fix and . Define the kernel mass
The original transition is . We define a reflected transition supported on by
This stays inside by construction. It is reversible with respect to up to a normalization because it is a standard restriction and renormalization of a symmetric kernel. It also dominates the restriction of to because implies
for every measurable and every . This gives a dominating chain in the sense of Definition 6.
Step 2. Leakage bound. For we have
We lower bound the denominator using the mass inside a local ball. Fix small enough so that for points that are at distance at least from . For boundary points we use reach to say that still has volume at least a constant fraction of . By GMC, on we have . Also on . Therefore
We upper bound the numerator using the valley depth. Any point that contributes to leaving must be in a region that is connected to another component only through values of at most . In particular, outside near the boundary of there exist regions where is at most , and the kernel is localized at scale , so the main contribution to the numerator comes from such nearby points. Thus
For a Gaussian kernel on a manifold of bounded geometry, the tail mass is at most times a polynomial factor. Choosing gives a constant bound on the kernel mass outside the local ball. Combining with the denominator lower bound yields
Absorbing the bounded prefactor into constants gives the claimed exponential-type leakage bound
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
where the Dirichlet form is
For the localized Gaussian kernel and small , the chain behaves like a local averaging operator at scale . Standard kernel calculations on manifolds show that controls an energy of the form up to constants depending on kernel regularity and geometry. On the other hand, GMC gives a Poincaré inequality on at scale comparable to . In its simplest form it says
where the volume growth constants and the lower bound on ensure the measure is comparable to on up to factors. Combining the two displays gives
uniformly over mean-zero . This yields the claimed lower bound on the spectral gap . 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 rather than one global time. The main idea is to define a new dissimilarity that, for a pair , 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 be a schedule defined on such that for each it lies inside the levelwise metastable window, and is nonincreasing in .
Definition 8 (Multiscale diffusion dissimilarity). Fix a schedule defined on . For , define
Let be the single-linkage dendrogram built from , with merge-height function .
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 comes from diffusion time .
Theorem 4 (Multiscale meeting theorem). Assume on and let be any schedule such that for every the time lies in the corresponding levelwise metastable window given by Theorem 3. Then there exists a strictly increasing function such that
Hence is isomorphic to as a merge tree.
Proof. Fix . Consider the diffusion distance at time . By Theorem 3, the pair satisfies the levelwise metastability bounds at this time. Therefore, by applying Lemma 2 and Lemma 3 at time , we obtain two numbers and such that
and moreover because is inside the metastable window. Choose a threshold such that
Then the threshold graph on with edges has connected components exactly . Now we transfer this property to the multiscale dissimilarity . First take in the same component . Then . By definition of , the infimum is taken over all with , in particular it includes itself. Therefore
So all pairs inside each have below and thus each is connected in the threshold graph built from .
Next take and for two distinct components in . Then . This means that for every with , we have . In particular, at level the points lie in different components, so the separating valley at level is present. The definition of and the separation bound at time imply that for any such pair,
Since is an infimum over diffusion distances at levels and these levels are below , the key point is that taking the infimum cannot create an artificial short edge that would cross the level- bottleneck. Indeed, if then there would exist some with . But implies that and are already separated before level , hence the valley that separates and is still present, and the same between-component argument applies to show that cannot be as small as . Therefore for pairs in different components of .
We have shown that for each , the connected components of the threshold graph on with edges are exactly . This is the same connectivity agreement used in the proof of Theorem 1. Define on and extend strictly increasing. Then the same nesting argument implies
for all .
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 .
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 -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 -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]Kamalika Chaudhuri and Sanjoy Dasgupta. Rates of convergence for the cluster tree. In Advances in Neural Information Processing Systems (NeurIPS), 2010.
- [2]Ronald R. Coifman and Stéphane Lafon. Diffusion maps. Applied and Computational Harmonic Analysis, 21(1):5–30, 2006.DOI
- [3]David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete & Computational Geometry, 37(1):103–120, 2007.
- [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]Herbert Edelsbrunner and John Harer. Computational Topology: An Introduction. American Mathematical Society, 2010.
- [7]John A. Hartigan. Consistency of single linkage for high-density clusters. Journal of the American Statistical Association, 76(374):388–394, 1981.DOI
- [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
- [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.
- [10]Emanuel Parzen. On estimation of a probability density function and mode. The Annals of Mathematical Statistics, 33(3):1065–1076, 1962.DOI
- [11]Murray Rosenblatt. Remarks on some nonparametric estimates of a density function. The Annals of Mathematical Statistics, 27(3):832–837, 1956.DOI
- [12]Bernard W. Silverman. Density Estimation for Statistics and Data Analysis. Chapman and Hall, 1986.
- [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.
- [14]Ulrike von Luxburg. A tutorial on spectral clustering. Statistics and Computing, 17(4):395–416, 2007.arxiv.org/abs/0711.0189
- [15]Ulrike von Luxburg, Mikhail Belkin, and Olivier Bousquet. Consistency of spectral clustering. The Annals of Statistics, 36(2):555–586, 2008.DOI
- [16]Larry Wasserman. All of Nonparametric Statistics. Springer, 2006.DOI