Uniform Error and Cluster Tree Consistency

Why Uniform Error Matters for Cluster Trees

A density cluster tree records how connected high-density regions grow and merge as the density threshold is lowered. Estimating the density uniformly is useful because it controls every threshold set at once. But a small vertical error in a density estimate does not automatically mean that its tree has exactly the same branches: small perturbations can create short-lived branches or split a merge that was tied in the population tree.

The right first guarantee is quantitative: uniform density error bounds the error in every pairwise merge height. A further condition, separation between distinct population merge levels, can protect the ordering of a finite, identifiable tree structure. We will state carefully which conclusions follow from which conditions.

Because \(X\) is connected and \(f\) is continuous on a compact space, thresholds below \(\min_{x\in X}f(x)\) give \(L_f(\lambda)=X\). Thus the set defining \(m_f(x,y)\) is nonempty and the merge height is finite. For \(x=y\), the merge height is \(f(x)\). For distinct points, it records the highest density threshold at which they are still connected in a single superlevel component.

If \(\hat f\) is another continuous function on the same domain, the uniform error is \(\|\hat f-f\|_\infty=\sup_{x\in X}|\hat f(x)-f(x)|\). The merge-distortion between their trees is the largest discrepancy between corresponding pairwise merge heights: \(\sup_{x,y\in X}|m_{\hat f}(x,y)-m_f(x,y)|\). This compares merge structure without asserting that the two trees have exactly the same branches.

The Superlevel-Set Sandwich

The basic fact is that a uniform error of at most \(\varepsilon\) can shift a density threshold by at most \(\varepsilon\). This set inclusion is the starting point for the tree guarantee.

Proof. If \(x\in L_f(\lambda+\varepsilon)\), then \(f(x)\geq\lambda+\varepsilon\). Since \(\hat f(x)\geq f(x)-\varepsilon\), we have \(\hat f(x)\geq\lambda\), so \(x\in L_{\hat f}(\lambda)\). Conversely, if \(x\in L_{\hat f}(\lambda)\), then \(f(x)\geq\hat f(x)-\varepsilon\geq\lambda-\varepsilon\), so \(x\in L_f(\lambda-\varepsilon)\). This proves both inclusions. \(\square\)

Uniform Error Bounds Every Merge Height

The sandwich has a direct consequence for the tree. A connected set in an estimated superlevel set remains connected when viewed inside the larger true superlevel set supplied by the sandwich. Applying this reasoning in both directions gives a two-sided error bound.

Proof. Fix \(x,y\). Suppose \(x\) and \(y\) lie in one connected component of \(L_{\hat f}(\lambda)\). That component is a connected subset of \(L_f(\lambda-\varepsilon)\), by the sandwich lemma. Any connected subset of a space lies within a single connected component of that space, so \(x\) and \(y\) are in one component of \(L_f(\lambda-\varepsilon)\). It follows that \(m_f(x,y)\geq\lambda-\varepsilon\) for every such \(\lambda\). Taking the supremum over those \(\lambda\) gives \(m_f(x,y)\geq m_{\hat f}(x,y)-\varepsilon\).

For the other direction, if \(x\) and \(y\) lie in one component of \(L_f(\lambda)\), that component is a connected subset of \(L_{\hat f}(\lambda-\varepsilon)\), again by the sandwich lemma. Hence \(m_{\hat f}(x,y)\geq m_f(x,y)-\varepsilon\), by taking the supremum over such \(\lambda\). Combining the two inequalities yields \(|m_{\hat f}(x,y)-m_f(x,y)|\leq\varepsilon\). Since \(x,y\) were arbitrary, the same bound holds for the supremum over all pairs. \(\square\)

When Do Merge Levels Protect Tree Structure?

Merge-height consistency is unconditional under the theorem’s assumptions, but exact topology requires more care. Uniform closeness alone does not exclude new tiny branches, nor does it determine how a population merge involving three or more branches will split under perturbation. A useful stronger conclusion is available for a finite, anchored tree with identifiable branches.

The anchor and binary assumptions matter. Anchors specify which branches are being compared, so the claim concerns the tree induced by those anchors, not every possible branch at every location in \(X\). Binary merges are identifiable from the pattern of which pairs merge above which other pairs. A multifurcation does not have a unique binary refinement, so it cannot be promised that a small perturbation preserves its exact branching pattern.

Proof. For any two distinct population critical levels \(\gamma>\gamma'\), their estimated counterparts, say \(\hat\gamma\) and \(\hat\gamma'\), each differ from the population value by at most \(\varepsilon\), by the merge-height theorem. Therefore \(\hat\gamma\geq\gamma-\varepsilon\) and \(\hat\gamma'\leq\gamma'+\varepsilon\). Since \(\gamma-\gamma'\geq\Delta>2\varepsilon\), we have \(\hat\gamma-\hat\gamma'\geq\Delta-2\varepsilon>0\). Thus every strict ordering between distinct population levels is preserved.

To see why this preserves the anchored binary structure, consider an internal node and its two child branches. Every pair of anchors from opposite children has merge height equal to that node’s level. Pairs within a child that merge at a higher internal level remain above that node after perturbation: the population levels differ by at least \(\Delta\), and the preceding inequality preserves their order. Hence the two child groups are still separate above the node’s merge, and join at that merge rather than at a different internal level. Applying this argument at each internal node reconstructs the same binary hierarchy on the anchors. The conclusion does not rule out additional branches that contain no anchor. \(\square\)

What Uniform Convergence Does—and Does Not—Guarantee

For a sequence of density estimates \(\hat f_n\), if \(\|\hat f_n-f\|_\infty\xrightarrow{p}0\), the merge-distortion also converges to zero in probability. Indeed, the theorem gives \(\sup_{x,y}|m_{\hat f_n}(x,y)-m_f(x,y)|\leq\|\hat f_n-f\|_\infty\) for every \(n\). For any \(\eta>0\), the probability that the left side exceeds \(\eta\) is therefore no greater than the probability that the uniform error exceeds \(\eta\), which tends to zero. The same implication holds for almost-sure uniform convergence.

If the population has a finite anchored binary structure with a fixed positive separation \(\Delta\), then uniform consistency also gives eventual structure recovery in probability. The event \(\|\hat f_n-f\|_\infty<\Delta/2\) has probability tending to one, and on that event the proposition applies. This is a statement about the specified anchored structure; it is not a guarantee that an unpruned estimated tree has no extra short branches.

A common mistake is to argue, “The density estimate is uniformly close, so its cluster tree must have the same topology.” The merge-height theorem supports a precise but narrower conclusion: every pairwise merge height is close. Exact topology can still fail to be identifiable if a population merge is tied among several branches, if critical levels are too close to order reliably, or if the estimate creates branches that are not represented by the chosen anchors. Keeping these conclusions separate is essential when interpreting a consistency claim.