Proving a Cluster Tree Stability Theorem

From Density Error to Tree Stability

A small error in a density estimate gives a direct guarantee about its high-density regions: at a given threshold, the estimated excursion set lies between two nearby population excursion sets. But this does not, by itself, say that the estimated tree has exactly the same visible branches. A branch can be too short to distinguish from estimation error, and a small perturbation can change the number or order of nearby merge events.

The proof strategy has two parts. First, uniform error brackets the excursion sets and controls the levels at which pairs of points join. Second, when branches are separated and component labels can be matched across the bracket, this numerical control becomes a statement about corresponding branches. The distinction between these parts is essential: a bound on tree distance need not imply identical branch structure.

Excursion Sets and Their Brackets

Let \(X\) be a compact, connected metric space, and let \(f\) and \(g\) be continuous real-valued functions on \(X\). In density clustering, \(f\) is the population density and \(g\) is an estimated density. For a threshold \(t\), the excursion set of \(f\) is the set of locations where the function reaches at least that level.

Definition: The upper excursion set of \(f\) at level \(t\) is \(C_f(t)=\{x\in X:f(x)\ge t\}\). Its connected components are the clusters at level \(t\). As \(t\) decreases, these sets expand and their components can join.

Assume the uniform error is bounded by \(\varepsilon\ge 0\), so that \(\|f-g\|_\infty=\sup_{x\in X}|f(x)-g(x)|\le\varepsilon\). The pointwise inequalities \(f-\varepsilon\le g\le f+\varepsilon\) imply the following set inclusions.

C_f(t+\varepsilon)\subseteq C_g(t)\subseteq C_f(t-\varepsilon).

These inclusions are the basic bracketing step. A population point that exceeds \(t+\varepsilon\) must exceed \(t\) under \(g\); and a point that exceeds \(t\) under \(g\) must exceed \(t-\varepsilon\) under \(f\). The result applies at every level simultaneously when the error bound is uniform.

Worked Example: Bracketing Excursion Sets of a Density

On \(X=[0,1]\), consider the density \(f(x)=1+0.4\cos(2\pi x)\). It is nonnegative and integrates to one, since \(f(x)\ge0.6\) and \(\int_0^1\cos(2\pi x)\,dx=0\). Let \(g(x)=1+0.4\cos(2\pi x)+0.03\cos(4\pi x)\). This also integrates to one, and \(\|f-g\|_\infty=0.03\).

At threshold \(t=0.8\), the bracket is \(C_f(0.83)\subseteq C_g(0.8)\subseteq C_f(0.77)\). For example, if \(f(x)\ge0.83\), then \(g(x)\ge f(x)-0.03\ge0.8\); if \(g(x)\ge0.8\), then \(f(x)\ge g(x)-0.03\ge0.77\). Thus the estimated excursion set can differ from the population set at level \(0.8\), but it cannot extend beyond the population set at level \(0.77\), or omit points in the population set at level \(0.83\).

The population density has two endpoint peaks, each of height \(1.4\), and a valley at \(x=0.5\) of height \(0.6\). At levels strictly above \(0.6\) and below \(1.4\), its excursion set has two components; at level \(0.6\), those components join. The estimate has \(g(0.5)=0.63\), so its merge level for the two endpoint regions is \(0.63\), a change of \(0.03\), exactly the uniform error bound.

Merge Heights and a Tree-Distance Bound

A cluster tree records how components of excursion sets evolve with the threshold. A convenient way to compare two such trees on the same domain is to compare the levels at which pairs of points first belong to the same component. This yields the merge-distortion distance used here. It controls the tree’s merge information without requiring the two trees to have the same number of branches.

Definition: For \(x,y\in X\), define their merge height under \(f\) by \(m_f(x,y)=\sup\{t:x\text{ and }y\text{ belong to the same connected component of }C_f(t)\}\). For continuous functions on compact connected \(X\), this is finite. Define the merge-distortion distance by \(D_{\mathrm{merge}}(f,g)=\sup_{x,y\in X}|m_f(x,y)-m_g(x,y)|\).

The definition uses component membership, not merely whether both points lie in an excursion set: two points can both be above a threshold and still lie in different components. The connectedness of \(X\) ensures that at every level no higher than \(\min_X f\), the excursion set is all of \(X\); compactness and continuity ensure that \(f\) is bounded.

Theorem: If \(f,g:X\to\mathbb R\) are continuous on compact connected \(X\) and \(\|f-g\|_\infty\le\varepsilon\), then \(D_{\mathrm{merge}}(f,g)\le\varepsilon\).

Proof. Fix \(x,y\in X\). If \(x\) and \(y\) are in the same component of \(C_f(t)\), the bracket gives \(C_f(t)\subseteq C_g(t-\varepsilon)\). Thus they are in the same component of \(C_g(t-\varepsilon)\), and \(m_g(x,y)\ge t-\varepsilon\). For every \(t<m_f(x,y)\), there is a level \(s>t\) at which they are in the same component: this follows from the definition of supremum. Applying the preceding implication at \(s\) gives \(m_g(x,y)\ge s-\varepsilon>t-\varepsilon\). Letting \(t\) increase to \(m_f(x,y)\) yields \(m_g(x,y)\ge m_f(x,y)-\varepsilon\). Interchanging \(f\) and \(g\) gives \(m_f(x,y)\ge m_g(x,y)-\varepsilon\). Hence \(|m_f(x,y)-m_g(x,y)|\le\varepsilon\). Taking the supremum over \(x,y\) proves the theorem. \(\square\)

Worked Example: Comparing Merge Heights for Two Regions

For the density pair in the previous example, take \(x=0\) and \(y=1\). Every path in \([0,1]\) joining these points must pass through \(0.5\). Under \(f\), the highest threshold at which the endpoints are in the same excursion-set component is therefore \(f(0.5)=0.6\): below this valley level the interval between the endpoints is included, while above it the two endpoint regions are disconnected.

Under \(g\), the corresponding valley is at \(0.5\), where \(g(0.5)=1-0.4+0.03=0.63\). To check it is a minimum, write \(u=\cos(2\pi x)\). Then \(g(x)=1+0.4u+0.03(2u^2-1)\). Its derivative with respect to \(u\) is \(0.4+0.12u\), which is positive for \(-1\le u\le1\). The minimum occurs at \(u=-1\), or \(x=0.5\). Therefore \(m_f(0,1)=0.60\), \(m_g(0,1)=0.63\), and their absolute difference is \(0.03\).

The same theorem applies to every pair of points, not just the endpoints. The calculation illustrates how a small uniform density error controls the height information represented by the tree.

When Merge-Height Control Identifies Branches

A merge-distortion bound is meaningful even when the estimated tree has extra or missing short branches. To conclude that corresponding branches are actually preserved, more is needed. The following finite-tree version makes the needed conditions explicit. A branch-label certificate means that component bracketing across the relevant levels supplies a one-to-one correspondence between the population and estimated leaves, and therefore identifies the same pairs of leaves at each merge event. This is a structural matching assumption, not a consequence of the error bound alone.

Theorem: Suppose the population cluster tree is a finite binary tree with a branch-label certificate for the estimated tree. Assume its distinct internal merge heights are separated by at least \(\gamma>0\), and \(\|f-g\|_\infty\le\varepsilon\) with \(2\varepsilon<\gamma\). Then the matched merge events have the same order, and each matched merge height differs by at most \(\varepsilon\). In particular, their merge-height tree distance is at most \(\varepsilon\).

Proof. For each matched pair of leaves, the branch-label certificate identifies the same pair in both trees. The preceding theorem bounds the difference between the corresponding merge heights by \(\varepsilon\). Consider two distinct population merge heights \(h_1<h_2\), with \(h_2-h_1\ge\gamma\), and their estimated heights \(\hat h_1,\hat h_2\). Then \(\hat h_1\le h_1+\varepsilon\) and \(\hat h_2\ge h_2-\varepsilon\). Therefore \(\hat h_2-\hat h_1\ge(h_2-h_1)-2\varepsilon\ge\gamma-2\varepsilon>0\). Their order is preserved. Applying this argument to every pair of distinct merge events preserves their order throughout the finite tree. The pairwise merge-height bound gives the stated distance bound. \(\square\)

The separation condition protects the order of events once their correspondence is established. It does not, by itself, establish the branch-label certificate. Component bracketing at selected levels, together with a valid component-matching condition, is what supplies that structural link.

Worked Example: Separation Preserves Merge Order

Suppose a certified three-leaf tree has population merge heights \(h_1=0.50\) and \(h_2=0.70\). Their separation is \(\gamma=0.20\). Let the uniform error be \(\varepsilon=0.04\). Since \(2\varepsilon=0.08<0.20\), the theorem applies.

The estimated merge heights must satisfy \(\hat h_1\in[0.46,0.54]\) and \(\hat h_2\in[0.66,0.74]\). Even in the least favorable case, \(\hat h_2-\hat h_1\ge0.66-0.54=0.12>0\). Thus the first event remains below the second, and each event has height error at most \(0.04\). This conclusion uses the stated certification; the numerical gap alone would not tell us which estimated branches correspond to the population branches.

Why Branch Separation Matters

A branch born and merged within a narrow range of density levels can be difficult to distinguish from perturbation. If its characteristic height difference is comparable to \(\varepsilon\), the excursion-set brackets may cover both its appearance and disappearance. The merge-distortion theorem still bounds pairwise merge-height errors, but it does not guarantee that a short branch survives as a separate branch in the estimate.

This is why a stability proof should report its conclusions at the right level. Uniform error alone gives a deterministic merge-height bound. A conclusion about the same number of branches, the same branch ordering, or recovery of particular components requires additional separation and matching assumptions. In applications, those assumptions must be justified for the density and the resolution at which the tree is being interpreted.

Worked Example: A Gap Too Small for Order Recovery

Consider two distinct population merge heights, \(h_1=0.50\) and \(h_2=0.55\), and an error bound \(\varepsilon=0.03\). Each estimated height can differ from its population value by as much as \(0.03\). The permissible ranges are \([0.47,0.53]\) and \([0.52,0.58]\), which overlap.

The merge-height bound remains valid for each matched event, but the ranges do not certify their order: the first estimate could be \(0.53\) while the second is \(0.52\). Here the population gap is \(0.05\), less than \(2\varepsilon=0.06\). Without stronger information, one cannot infer that the estimated tree orders these events as the population tree does.

Common Pitfall

Wrong reasoning: “The estimated density is uniformly close to the true density, so the estimated cluster tree has exactly the same branches.” This skips the structural step. Uniform error proves the excursion-set inclusions and the merge-height bound, but it does not rule out unresolved short branches or establish a branch-by-branch correspondence.

Correction: State separately what the error bound proves and what the branch assumptions prove. Use uniform error for the level and merge-height inequalities. To claim stable branch identity or ordering, also specify a component-matching certificate and a separation margin large enough relative to the error; for merge heights with error at most \(\varepsilon\), the strict ordering condition is a gap greater than \(2\varepsilon\).

Key takeaway: Bracketing controls where estimated excursion sets can lie; merge-height stability converts that control into a tree-distance bound. Branch separation and component matching are additional ingredients for claims about the tree’s branch structure.

Check Your Understanding

Work through these questions using the definitions and proof strategy above.

If \(\|f-g\|_\infty\le\varepsilon\), write the two excursion-set inclusions at a general level \(t\).
Why does membership of \(x\) and \(y\) in the same component matter in the definition of merge height?
Which step in the merge-distortion proof uses the excursion-set bracket?
Two merge heights are separated by \(0.12\), and the uniform error bound is \(0.05\). Does the stated order-preservation condition hold? Explain.
Why does a merge-distortion bound alone not establish that the estimated and population trees have the same number of branches?