Nonidentifiability of Weak Cluster Branches

Why Weak Branches Are Hard to Distinguish

A cluster tree records how connected components of density superlevel sets join as the density threshold decreases. A branch that merges at a saddle height very close to a competing height can be fragile: a small change in the density may shift its merge level, and data may not contain enough information to tell the alternatives apart. This is not just a limitation of a particular estimator. If two distributions are sufficiently close, no procedure can reliably distinguish their cluster trees.

We make that point precise with a finite example and a confidence-set lower bound. The finite model is a probability density with respect to counting measure on a three-vertex path. It isolates the merge-height issue without requiring geometric or smoothness assumptions. The same testing argument applies in a continuous model whenever two admissible densities have small statistical divergence but separated cluster trees.

Merge Heights and Tree Distance

For a density $f$ on a space with a specified notion of connectedness, its superlevel set at threshold $\lambda$ is $\{x:f(x)\geq\lambda\}$. The cluster tree describes the connected components of these sets across thresholds. For points $x,y$, their merge height is the highest threshold at which they belong to the same component. In the finite graph used below, this height has a direct path formula.

Definition: Let $G=(V,E)$ be a connected finite graph and let $f:V\to(0,\infty)$. For vertices $x,y\in V$, define their merge height by $$ m_f(x,y)=\max_{\pi:x\leadsto y}\ \min_{v\in\pi} f(v), $$ where the maximum is over paths from $x$ to $y$. It is the largest threshold at which $x$ and $y$ remain connected in the induced graph on $\{v:f(v)\geq\lambda\}$. For two densities $f,g$ on the same graph, define their merge-height distance by $$ d_{\mathrm{merge}}(f,g)=\max_{x,y\in V}|m_f(x,y)-m_g(x,y)|. $$

This distance compares the merge heights encoded by the trees. If a convention also includes equal-point pairs, $m_f(x,x)=f(x)$; we will check those pairs explicitly. Merge-height distance is the relevant resolution for the example, rather than a claim that every possible cluster-tree metric behaves identically.

Worked Example: A Three-Vertex Cluster Tree

Take the path $L-S-R$, with edges $(L,S)$ and $(S,R)$. Consider the probability mass functions $$ p_A=(0.39,\,0.22,\,0.39),\qquad p_B=(0.41,\,0.18,\,0.41), $$ in the order $L,S,R$. Each vector sums to one. Under either distribution, the two endpoint masses exceed the mass at $S$. For $p_A$, the endpoint-minus-center difference is $0.39-0.22=0.17$; for $p_B$, it is $0.41-0.18=0.23$.

Every path between distinct vertices contains $S$, and $S$ is the lowest-mass vertex on each such path. Thus $m_{p_A}(L,S)=m_{p_A}(S,R)=m_{p_A}(L,R)=0.22$, while all three corresponding merge heights under $p_B$ equal $0.18$. Each changes by $0.04$, so $d_{\mathrm{merge}}(p_A,p_B)=0.04$. If equal-point pairs are included, the endpoint heights change by $0.02$ each and the center height changes by $0.04$; the supremum remains $0.04$.

The distinct pairs all matter: it would be incorrect to say that only the pair $(L,R)$ has a changed merge height. The shared center vertex is the bottleneck for each of the three paths.

Close Densities Can Encode Separated Merge Heights

Here is a parameterized version of the example. Let $0<e\leq 1/23$, and define distributions on $L-S-R$ by $$ p_A=(0.4-e/2,\,0.2+e,\,0.4-e/2),\qquad p_B=(0.4+e/2,\,0.2-e,\,0.4+e/2). $$ Both vectors sum to one. All entries are positive: in particular, $0.2-e\geq 0.2-1/23>0.15$. Under $p_A$, each endpoint exceeds the center by $0.2-1.5e>0$; under $p_B$, each exceeds it by $0.2+1.5e>0$. Consequently the center is the bottleneck for all paths between distinct vertices. All three distinct-pair merge heights equal $0.2+e$ under $p_A$, and $0.2-e$ under $p_B$. Each changes by $2e$. Equal-point merge heights, if included, change by $e$ at the endpoints and $2e$ at the center. In either convention, $$ d_{\mathrm{merge}}(p_A,p_B)=2e. $$

Worked Example: Bounding the Divergence of the Two Models

For positive probability mass functions $p,q$ on a finite set, the Kullback–Leibler divergence is $D_{\mathrm{KL}}(p\|q)=\sum_x p(x)\log\{p(x)/q(x)\}$. The inequality $\log u\leq u-1$, for $u>0$, gives $$ D_{\mathrm{KL}}(p\|q) \leq \sum_x p(x)\left(\frac{p(x)}{q(x)}-1\right) =\sum_x\frac{(p(x)-q(x))^2}{q(x)}. $$ For the last equality, expand the square and use $\sum_xp(x)=\sum_xq(x)=1$.

Apply this bound to $D_{\mathrm{KL}}(p_A\|p_B)$. The coordinate differences $p_A-p_B$ are $(-e,2e,-e)$, so their squares are $e^2,4e^2,e^2$. The endpoint denominators from $p_B$ are $0.4+e/2\geq0.4$; its center denominator is $0.2-e>0.15$. Therefore $$ D_{\mathrm{KL}}(p_A\|p_B) \leq \left(\frac{2}{0.4}+\frac{4}{0.15}\right)e^2 <32e^2. $$ Indeed, $2/0.4=5$, $4/0.15=26.\overline{6}$, and their sum is $31.\overline{6}<32$. This calculation uses the sharper center-denominator bound; replacing it with $0.1$ would give a coefficient of $45$, not a coefficient small enough for the sample-size bound below.

From a Two-Point Test to a Confidence-Set Bound

For distributions $P,Q$, write $\operatorname{TV}(P,Q)=\sup_A|P(A)-Q(A)|$ for total variation distance. We use Pinsker’s inequality, $\operatorname{TV}(P,Q)\leq\sqrt{D_{\mathrm{KL}}(P\|Q)/2}$, when $P$ is absolutely continuous with respect to $Q$. For finite distributions, the inequality follows by taking an event attaining the supremum, applying the log-sum inequality to reduce divergence to the two event probabilities, and using binary divergence $d(a\|b)\geq2(a-b)^2$. The latter follows from its second derivative in $a$, $1/[a(1-a)]\geq4$, and its value and first derivative being zero at $a=b$.

For independent samples, divergence adds: $D_{\mathrm{KL}}(P^n\|Q^n)=nD_{\mathrm{KL}}(P\|Q)$. This follows by writing the log likelihood ratio of the product distributions as a sum of $n$ single-observation log ratios and taking its expectation. Thus a small one-observation divergence can still make the two sample laws difficult to distinguish when $n$ observations are collected.

Theorem: Let $P_0,P_1$ be two sampling distributions with target cluster trees $T_0,T_1$ in a metric $d$, and put $\Delta=d(T_0,T_1)>0$. Suppose a random confidence set $C_n$ has coverage at least $1-\alpha$ under both models: $$ P_i^n\{T_i\in C_n\}\geq 1-\alpha,\qquad i=0,1. $$ If the events in this display and $\operatorname{diam}_d(C_n)$ are measurable, with the convention $\operatorname{diam}_d(\varnothing)=0$, then $$ E_{P_0^n}\!\left[\operatorname{diam}_d(C_n)\right] \geq \Delta\left(1-2\alpha-\operatorname{TV}(P_0^n,P_1^n)\right), $$ whenever the right-hand side is positive. Here $\operatorname{diam}_d(C)=\sup_{S,T\in C}d(S,T)$.

Proof. Under $P_0^n$, the event $T_0\in C_n$ has probability at least $1-\alpha$. Coverage under $P_1^n$ gives $P_1^n\{T_1\in C_n\}\geq1-\alpha$; by the definition of total variation, $P_0^n\{T_1\in C_n\}\geq1-\alpha-\operatorname{TV}(P_0^n,P_1^n)$. The probability that both trees belong to $C_n$, under $P_0^n$, is at least the sum of these two probabilities minus one. It is therefore at least $1-2\alpha-\operatorname{TV}(P_0^n,P_1^n)$. On that intersection, the diameter is at least $d(T_0,T_1)=\Delta$; elsewhere it is nonnegative. Taking expectations proves the bound. $\square$

In the finite construction, the target trees are the trees induced by $p_A,p_B$, and their distance is $2e$. The preceding divergence calculation and Pinsker’s inequality give $$ \operatorname{TV}(p_A^n,p_B^n) \leq \sqrt{\frac{nD_{\mathrm{KL}}(p_A\|p_B)}{2}} <\sqrt{16ne^2}. $$ Choosing $e=1/(23\sqrt n)$ ensures $e\leq1/23$ and yields $nD_{\mathrm{KL}}(p_A\|p_B)<32/529<1/12$. Hence the sample total variation is less than $\sqrt{1/24}$, even though the two target merge-height trees are separated by $2/(23\sqrt n)$. For any uniformly honest confidence set, the theorem therefore implies $$ E_{p_A^n}\!\left[\operatorname{diam}_{d_{\mathrm{merge}}}(C_n)\right] \geq \frac{2}{23\sqrt n}\left(1-2\alpha-\sqrt{\frac{1}{24}}\right), $$ provided the parenthetical quantity is positive. This is a lower bound on the uncertainty that remains even for a confidence set with correct coverage under both alternatives.

Worked Example: A Numerical Confidence-Set Bound

Take $n=100$, $e=1/(23\sqrt{100})=1/230$, and confidence level $95\%$, so $\alpha=0.05$. The tree separation is $\Delta=2e=1/115\approx0.00870$. The divergence bound gives $$ nD_{\mathrm{KL}}(p_A\|p_B)<32\frac{100}{230^2} =\frac{32}{529}<0.0605. $$ Pinsker’s inequality then gives $\operatorname{TV}(p_A^{100},p_B^{100})<\sqrt{16/529}=4/23\approx0.174$.

The probability, under $p_A^{100}$, that a $95\%$-honest confidence set contains both trees is at least $1-2(0.05)-4/23=0.9-4/23\approx0.726$. Whenever it contains both, its diameter is at least $1/115$. Thus $$ E_{p_A^{100}}\!\left[\operatorname{diam}_{d_{\mathrm{merge}}}(C_{100})\right] \geq \frac{1}{115}\left(0.9-\frac{4}{23}\right) \approx0.00631. $$ The lower bound is smaller than the tree separation because the confidence set need not contain both trees on every sample; it must, however, contain both with probability bounded away from zero under this pair of close models.

What the Lower Bound Says About Weak Branches

The construction has merge-height separation proportional to $e$, while the one-observation divergence is at most a constant times $e^2$. With $e$ of order $n^{-1/2}$, the two sample distributions remain close, and an honest confidence set cannot generally have diameter smaller than that order over a model class containing both alternatives. In particular, a small estimated difference between candidate saddle heights should not be read as decisive evidence about which merge level is correct.

The argument is a two-point lower bound, not an estimator-specific failure. If two admissible models have cluster trees separated by $\Delta$ but sample distributions with small total variation, the confidence-set conclusion follows regardless of how the set was constructed. This clarifies the role of separation assumptions: stronger assumptions that rule out near ties may permit sharper guarantees, while near-tied alternatives limit what can be certified from the data.

A common mistake is to infer that a weak branch is impossible to recover merely because its saddle height is close to another. The bound does not establish that claim. In this three-vertex example the component structure is the same under both distributions; the demonstrated uncertainty concerns the merge heights. More generally, a testing lower bound for a particular tree metric establishes uncertainty at that metric’s resolution, not necessarily failure of every qualitative topological decision. To claim nonrecovery of a particular branch, one must specify competing models with different branch structure and verify both their tree separation and their statistical closeness.

Key takeaway: Close sampling distributions can encode cluster trees whose merge heights differ by a meaningful amount at the statistical resolution. A uniformly honest confidence set must reflect that ambiguity; small estimated saddle-height gaps alone do not justify precise branch claims.

Check Your Understanding

Check that you can connect the tree geometry to the testing argument.

On the path $L-S-R$, why is $S$ the bottleneck for every path between distinct vertices when its density value is below both endpoint values?
For the pair $p_A,p_B$, calculate the difference in each coordinate and explain why all three distinct-pair merge heights change by $2e$.
Why is $0.2-e>0.15$ under the stated restriction $e\leq1/23$, and how does that bound affect the divergence calculation?
In the confidence-set theorem, why does coverage under $P_1^n$ imply a lower bound on $P_0^n\{T_1\in C_n\}$?
What does the two-point lower bound establish about weak branches, and what additional evidence would be needed to claim that a branch’s qualitative topology cannot be recovered?