Persistent Homology for Density Cluster Trees

From Density Thresholds to a Filtration

A density cluster tree records how high-density regions split into separate components as the density threshold rises, or merge as it falls. Persistent homology gives a concise way to represent that changing component structure: each branch becomes an interval whose endpoints are its birth height and its merge height. Comparing those intervals makes it possible to ask not only whether a component appears, but whether it persists across a substantial range of density levels.

Let \(D\) be a compact triangulable domain and let \(f:D\to\mathbb{R}\) be a continuous density function. At threshold \(\lambda\), its superlevel set is \(L_f(\lambda)=\{x\in D:f(x)\geq\lambda\}\). As \(\lambda\) decreases, these sets grow and are nested: if \(\lambda_1\geq\lambda_2\), then \(L_f(\lambda_1)\subseteq L_f(\lambda_2)\). The resulting nested family is a filtration.

For clarity, assume the filtration is tame: for example, \(f\) may be piecewise linear on a finite triangulation. Then only finitely many component births and mergers occur, and the degree-zero persistence diagram consists of finitely many points, with multiplicity. The component that remains after all finite branches merge is essential; it is represented by \((b,-\infty)\) in density-height coordinates. Equivalently, under the usual sublevel-set convention for \(-f\), its death coordinate is \(+\infty\).

When multiple components merge at the same level, the elder rule pairs the merging component with the largest birth height as the one that continues, while the other component or components die at that merge height. This makes the finite intervals correspond to branches that end in a merger. Persistent homology in degree zero is therefore a numerical description of merge features, not a new clustering rule.

Worked Examples of Component Persistence

Uniform Error and Bottleneck Stability

The bottleneck distance compares two persistence diagrams by matching their points. For finite points \((b,d)\) and \((b',d')\), the matching cost is \(\max\{|b-b'|,|d-d'|\}\). A point may instead be matched to the diagonal \(b=d\); its cost is its distance to that diagonal in the maximum norm, namely \((b-d)/2\). The bottleneck distance is the smallest possible largest cost over all matchings. Essential points must be matched to essential points.

The key stability fact is that small uniform function error yields small bottleneck distance for the diagrams. The hypotheses matter: the functions are defined on the same domain, the filtrations are tame (or, more generally, q-tame), and the uniform error is finite. Write \(Dgm_0(f)\) for the degree-zero diagram of the superlevel filtration, using density-height coordinates.

The theorem is the superlevel-set version of the classical bottleneck stability theorem. Its connection to density estimation begins with a direct inclusion argument. For every threshold \(\lambda\), uniform error gives

Indeed, if \(f(x)\geq\lambda+\varepsilon\), then \(g(x)\geq f(x)-\varepsilon\geq\lambda\). If \(g(x)\geq\lambda\), then \(f(x)\geq g(x)-\varepsilon\geq\lambda-\varepsilon\). These inclusions say that the two filtrations are shifted versions of one another by at most \(\varepsilon\). To express this using the standard increasing-parameter convention, set \(h=-f\) and \(k=-g\): their sublevel sets obey the corresponding inclusions after shifting the parameter by \(\varepsilon\). The algebraic stability theorem for tame persistence modules turns this interleaving into the stated bottleneck bound.

There is also a direct bound for pairwise merge heights. Suppose \(D\) is path-connected, and define the path merge height for \(x,y\in D\) by

where the supremum is over continuous paths from \(x\) to \(y\). For continuous \(f\) on compact \(D\), the minimum along each such path exists. This quantity is the highest threshold at which some path connects \(x\) to \(y\). It agrees with their component merge level when the superlevel sets have the usual path-connected component structure, as in a finite piecewise-linear filtration.

Proof. Fix any path \(\gamma\) from \(x\) to \(y\). At every point on the path, \(g\geq f-\varepsilon\), so \(\min_t g(\gamma(t))\geq\min_t f(\gamma(t))-\varepsilon\). Taking the supremum over paths gives \(m_g(x,y)\geq m_f(x,y)-\varepsilon\). Interchanging \(f\) and \(g\) gives \(m_f(x,y)\geq m_g(x,y)-\varepsilon\). Together these inequalities imply the claim. \(\square\)

What Stability Does—and Does Not—Say

Bottleneck stability is useful when a density is estimated rather than known. If an estimate \(\hat f\) satisfies \(\|\hat f-f\|_\infty\leq\varepsilon\), the theorem guarantees that the estimated degree-zero diagram is within bottleneck distance \(\varepsilon\) of the population diagram. Large-persistence branches cannot be erased by an arbitrarily small uniform perturbation: a bar longer than \(2\varepsilon\) cannot be matched to the diagonal at cost at most \(\varepsilon\). The theorem does not, by itself, identify which matched branch is scientifically meaningful; that interpretation depends on the application and the feature’s scale.

A common mistake is to infer that every estimated branch corresponds to a true branch. The matching definition allows short finite bars to be paired with the diagonal, and the theorem’s bound says that any unmatched finite bar must have persistence at most \(2\varepsilon\). Thus the correction is not “all branches are recovered,” but “branches that are too short relative to the error may be indistinguishable from perturbation.” A second mistake is to treat a small error in an integrated metric as if it were a uniform error. The stated bottleneck guarantee requires a bound on the largest pointwise discrepancy; an \(L^1\) or \(L^2\) error alone does not supply that hypothesis.