Common Failures in Level Set and Tree Guarantees

Why Small Error Does Not Guarantee Every Kind of Stability

A small error in an estimated density is useful, but it is not a universal guarantee. It may control how far the estimated function is from the true function while failing to control the shape of a level set at a particular threshold, the number of its connected components, or the presence of a weak branch in a cluster tree. The missing ingredient is often a condition on the geometry of the true function near the threshold or critical level.

The first task in diagnosing a claim is to identify what is being compared. Function error, set error, boundary error, topology, and tree distance are different quantities. A valid bound for one cannot be silently promoted to a bound for another.

Definition: For a function $f$ on a domain $\mathcal X$ and a level $\lambda$, its upper level set is $L_f(\lambda)=\{x\in\mathcal X:f(x)\geq\lambda\}$. A cluster at level $\lambda$ is a connected component of this set. As $\lambda$ decreases, level sets are nested, and their connected components form a cluster tree.

The following discussion uses uniform error, $\|f-g\|_\infty=\sup_{x\in\mathcal X}|f(x)-g(x)|$, when this quantity is finite. For merge heights, we will use a path-based definition on a compact, path-connected domain $\mathcal X$, with $f$ and $g$ continuous and real-valued. These conditions ensure that the merge heights in the comparison below are finite; without suitable conditions, subtracting extended-real merge heights may not even be defined.

What Uniform Error Actually Gives

If the functions differ by at most $\varepsilon$, points well above or well below a level cannot switch sides of that level. Points close to the level can. This gives a useful set-inclusion result, but it is not a topology theorem.

Theorem: Suppose $\|f-g\|_\infty\leq\varepsilon$, where $\varepsilon\geq0$. For every real $\lambda$, $$ L_f(\lambda+\varepsilon)\subseteq L_g(\lambda)\subseteq L_f(\lambda-\varepsilon). $$ In particular, if $|f(x)-\lambda|>\varepsilon$, then $f(x)$ and $g(x)$ are on the same side of $\lambda$.

Proof. If $x\in L_f(\lambda+\varepsilon)$, then $f(x)\geq\lambda+\varepsilon$. The error bound gives $g(x)\geq f(x)-\varepsilon\geq\lambda$, so $x\in L_g(\lambda)$. Conversely, if $x\in L_g(\lambda)$, then $g(x)\geq\lambda$, and $f(x)\geq g(x)-\varepsilon\geq\lambda-\varepsilon$, so $x\in L_f(\lambda-\varepsilon)$. For the final assertion, if $f(x)>\lambda+\varepsilon$, then $g(x)\geq f(x)-\varepsilon>\lambda$; if $f(x)<\lambda-\varepsilon$, then $g(x)\leq f(x)+\varepsilon<\lambda$. $\square$

The inclusions compare level sets at different levels. They do not say that $L_f(\lambda)$ and $L_g(\lambda)$ have the same topology or even that their boundaries are close. To obtain those stronger conclusions, one needs extra information about the function near the threshold—for example, a margin separating the boundary from nearby values, or a quantitative condition that prevents the function from being too flat there.

Worked Example: A Flat Boundary Can Be Unstable

Take $\mathcal X=[-1,1]$, $f(x)=0$ for every $x$, and level $\lambda=0$. For any $\varepsilon>0$, let $g(x)=-\varepsilon$ for every $x$. Then $\|f-g\|_\infty=\varepsilon$, but

L_f(0)=[-1,1], \qquad L_g(0)=\varnothing.

Thus arbitrarily small uniform error can change a nonempty level set into the empty set. The true function lies exactly on the threshold everywhere, so there is no margin to protect membership. The set-inclusion theorem still holds: its outer set is $L_f(-\varepsilon)=[-1,1]$, and its inner set is $L_f(\varepsilon)=\varnothing$. Those bounds correctly allow both outcomes.

Vanishing Margins and Boundary Rates

Even when a level set changes continuously, its boundary can move much farther than the function error. The key issue is how quickly the function changes as one moves away from the boundary. A flat crossing converts a small vertical error into a larger horizontal displacement.

Worked Example: A Quadratic Boundary Has a Slow Rate

On $\mathcal X=[0,1]$, let $f(x)=x^2$, let $\lambda=0$, and define $g(x)=x^2-\varepsilon$ for $0<\varepsilon<1$. The true level set is $L_f(0)=[0,1]$, while

L_g(0)=\{x:x^2\geq\varepsilon\} =[\sqrt{\varepsilon},1].

The boundary has moved by $\sqrt{\varepsilon}$, although $\|f-g\|_\infty=\varepsilon$. For example, at $\varepsilon=10^{-4}$, the function error is $0.0001$, but the boundary displacement is $0.01$. The displacement is not bounded by a constant times $\varepsilon$ as $\varepsilon$ tends to zero: the ratio is $\sqrt{\varepsilon}/\varepsilon=1/\sqrt{\varepsilon}$, which diverges. A linear boundary-error rate therefore needs a condition stronger than uniform error alone.

A useful diagnostic is to ask whether the function separates from the level at a known rate near the boundary. In the quadratic example, $f(x)-\lambda=x^2$, so a vertical gap of size $\varepsilon$ corresponds to a horizontal distance of order $\varepsilon^{1/2}$. More generally, if the separation behaves like a distance raised to a power $q>0$, the corresponding displacement is typically of order $\varepsilon^{1/q}$, not automatically order $\varepsilon$. A claimed boundary rate should be checked against this local geometry.

Critical Levels Can Change the Number of Clusters

A level is critical for clustering when the connectivity of its excursion set can change as the level passes through it. At or near such a level, a tiny vertical perturbation can create or remove a connecting bridge. This is not contradicted by a small function error: the topology is sensitive precisely because the connection is determined by values near the critical height.

Worked Example: A Small Shift Splits a Bridge

On $\mathcal X=[-2,2]$, define $f(x)=-(x^2-1)^2$ and consider level $\lambda=-1$. The level set condition is

-(x^2-1)^2\geq-1 \quad\Longleftrightarrow\quad (x^2-1)^2\leq1 \quad\Longleftrightarrow\quad x^2\leq2.

Since $[-\sqrt{2},\sqrt{2}]\subset[-2,2]$, the excursion set is the single interval $[-\sqrt{2},\sqrt{2}]$. Now shift the function down by $0<\varepsilon<1$: set $g=f-\varepsilon$. At the same level, $g(x)\geq-1$ is equivalent to $f(x)\geq-1+\varepsilon$, which gives

(x^2-1)^2\leq1-\varepsilon \quad\Longleftrightarrow\quad 1-\sqrt{1-\varepsilon}\leq x^2\leq1+\sqrt{1-\varepsilon}.

The lower bound on $x^2$ is strictly positive. Thus the level set consists of two disjoint intervals, one on each side of zero. Yet $\|f-g\|_\infty=\varepsilon$, which can be arbitrarily small. A guarantee that cluster counts are unchanged at this fixed level would need to exclude such critical-level behavior or explicitly allow a level shift.

This example also illustrates why a statement about stability across a range of levels is different from a statement at one fixed level. A tree metric may tolerate a small displacement in merge height while the number of components at the exact critical level changes. The metric and the claim must be read together: stability in merge heights is not automatically identical to equality of component counts at every specified level.

Merge-Height Stability Requires Finite Quantities

For points $x,y\in\mathcal X$, define their path-based merge height under $f$ by taking the best bottleneck value over continuous paths joining them:

Definition: If $\Gamma_{xy}$ is the set of continuous paths $\gamma:[0,1]\to\mathcal X$ with $\gamma(0)=x$ and $\gamma(1)=y$, define $$ m_f(x,y)=\sup_{\gamma\in\Gamma_{xy}}\ \inf_{t\in[0,1]} f(\gamma(t)). $$

On a compact path-connected domain, every pair has at least one such path. If $f$ is continuous and real-valued on that compact domain, it is bounded. Consequently every path infimum, and the supremum of those infima, is a finite real number.

Theorem: Let $\mathcal X$ be compact and path-connected, and let $f,g:\mathcal X\to\mathbb R$ be continuous. If $\|f-g\|_\infty\leq\varepsilon$, then for every $x,y\in\mathcal X$, $$ |m_f(x,y)-m_g(x,y)|\leq\varepsilon. $$

Proof. Fix any path $\gamma\in\Gamma_{xy}$. The uniform bound implies $f(\gamma(t))\leq g(\gamma(t))+\varepsilon$ for every $t$. Taking infima over $t$ yields $\inf_t f(\gamma(t))\leq\inf_t g(\gamma(t))+\varepsilon$. Taking suprema over the same path set gives $m_f(x,y)\leq m_g(x,y)+\varepsilon$. Interchanging $f$ and $g$ gives $m_g(x,y)\leq m_f(x,y)+\varepsilon$. The merge heights are finite by the stated assumptions, so these two inequalities combine to give the asserted absolute-value bound. $\square$

The assumptions matter. With merely measurable, real-valued functions on a noncompact domain, a path infimum may be $-\infty$, even though the function takes finite values at every point. Then writing $|m_f-m_g|$ can be undefined if both merge heights equal $-\infty$. Do not apply a real-valued stability bound until finiteness has been established, or a suitable extended-real formulation has been specified.

Coarse Discretization Can Erase a Real Component

A grid or graph can only represent features that its resolution can detect. Uniform approximation at the grid points is not the same as reliable recovery of the continuum excursion set. A narrow high-density component may lie between sampled locations and disappear entirely from the discrete construction.

Worked Example: A Grid Misses a Narrow Excursion

On $[0,1]$, take grid points $G=\{0,0.25,0.5,0.75,1\}$ and define the triangular bump

f(x)=\max\left(0,1-\frac{|x-0.375|}{0.04}\right).

At level $\lambda=0.5$, the continuum excursion set is found by solving $1-|x-0.375|/0.04\geq0.5$, or $|x-0.375|\leq0.02$. Hence $L_f(0.5)=[0.355,0.395]$, a nonempty interval. The grid points closest to the bump center are $0.25$ and $0.5$, each at distance $0.125$. Its function value is $\max(0,1-0.125/0.04)=0$, and every other grid point is at least as far from the center, so its value is also zero. Thresholding the grid values at $0.5$ therefore produces no vertices at all, even though the true excursion set is nonempty.

A resolution guarantee needs a link between grid spacing and feature width, and often a regularity bound as well. For example, if $f$ is $L$-Lipschitz and every point of the domain is within distance $h$ of a grid point, then any $x$ satisfying $f(x)\geq\lambda+Lh$ has a grid point $z$ with $f(z)\geq f(x)-Lh\geq\lambda$. This guarantees detection of points with that extra vertical margin; it does not by itself guarantee that the graph’s connected components match those of the continuum set.

Set Convergence Is Not Topology or Tree Convergence

Even convergence of sets in a strong geometric sense need not preserve the number of connected components. Consider the compact sets $A_n=[-1,-1/n]\cup[1/n,1]$ for $n\geq2$, and $A=[-1,1]$. Every point of $A$ is within distance at most $1/n$ of $A_n$, and $A_n\subset A$. Thus their Hausdorff distance is at most $1/n$, which tends to zero. But every $A_n$ has two connected components, whereas $A$ has one. A gap can vanish in set distance while changing topology at the limit.

Tree convergence has further structure: it concerns nested components and their merge relationships, not just the locations of points in individual level sets. A uniform function bound can control merge heights under suitable assumptions, as shown above, but a claim about branch recovery, component identity, or a particular tree metric requires the corresponding definitions and conditions. In particular, a branch whose height or spatial separation vanishes may be difficult to distinguish from no branch at all. Weak-branch nonidentifiability is not repaired merely by proving convergence of estimated functions or excursion sets.

Common Mistakes and a Practical Audit

Claiming topology from uniform error alone. The level-set inclusions control sets at shifted thresholds; they do not rule out splits or mergers at a fixed critical level.
Assuming every boundary rate is linear. The quadratic example has displacement $\sqrt{\varepsilon}$, not order $\varepsilon$. Check the local margin or separation condition before asserting a rate.
Using a grid as if it were the continuum. A sampled graph can miss a component narrower than its resolution. State how the grid spacing relates to feature size and function regularity.
Equating set convergence with topological convergence. A shrinking gap can disappear in Hausdorff distance while the component count changes.
Subtracting possibly infinite merge heights. The wrong reasoning is “uniform error is at most $\varepsilon$, so the absolute difference of merge heights is at most $\varepsilon$” without checking that the heights are finite. The correction is to impose conditions such as continuity on a compact path-connected domain, or formulate an appropriate extended-real comparison that does not subtract two values of $-\infty$.

Identify the target.
Is the claim about function error, a level set, its boundary, its topology, or a cluster-tree metric?

Check the relevant assumptions.
For a fixed-level claim, inspect margins and critical levels; for discretization, inspect resolution; for merge heights, verify finiteness and the path assumptions.

Match the conclusion to the guarantee.
Do not turn function or set convergence into topology or tree convergence without a result that explicitly supports that implication.

Key takeaway: A guarantee is only as strong as its target and assumptions. Uniform error gives useful level-set inclusions and, under suitable finite-height conditions, merge-height control. Flat boundaries, critical levels, weak branches, and coarse grids can still defeat stronger conclusions.

Check Your Understanding

For each question, identify what is guaranteed and what additional condition would be needed for a stronger claim.

If $\|f-g\|_\infty\leq\varepsilon$, write the two level-set inclusions at level $\lambda$.
In the quadratic-boundary example, what is the boundary displacement as a function of $\varepsilon$, and why is it not a linear error rate?
For the function $f(x)=-(x^2-1)^2$, what happens to the number of components at level $-1$ after replacing $f$ by $f-\varepsilon$, where $0<\varepsilon<1$?
Why does a grid whose sampled values are all below a threshold not prove that the continuum excursion set is empty?
Can Hausdorff convergence alone guarantee that connected-component counts eventually agree? Explain using the shrinking-gap construction.
What assumptions in the merge-height stability theorem ensure that the absolute difference of merge heights is defined?