Intrinsic Bottleneck Distance for Merge Trees
David Beers, Gillian Grindstaff · 2025
Read Intrinsic Bottleneck Distance for Merge Trees by David Beers, Gillian Grindstaff (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-02755.txt.
Introduction
David Beers and Gillian Grindstaff wrote a 2025 topology paper on merge trees, structures that record how connected components of a filtered space merge over time. Two distances compete: a fast bottleneck distance on barcodes, and a richer interleaving distance that is hard to compute.
As raw maps, the two distances differ, because many merge trees share one barcode. The authors instead compare the intrinsic metrics, distances measured by shortest path length inside merge tree space itself. They prove those intrinsic versions coincide, settling a conjecture. Both distances therefore induce the same length geometry. In practice, where a path between trees is known, the cheap bottleneck distance can stand in for the interleaving distance, which is generally hard even to approximate.
Catalog record
| CREATOR | David Beers, Gillian Grindstaff |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 48 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-02755
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Intrinsic Bottleneck Distance for Merge Trees David Beers, Gillian Grindstaff Abstract Merge trees are a topological descriptor of a filtered space that enriches the degree zero barcode with its merge structure. The space of merge trees comes equipped with an interleaving distance d I d_{I} , which prompts a naive question: is the interleaving distance between two merge trees equal to the bottleneck distance between their corresponding barcodes? As the map from merge trees to barcodes is not injective, the answer as posed is no, but (as conjectured in Gasparovic et al.) we prove that it is true for the intrinsic metrics d ^ I \widehat{d}_{I} and d ^ B \widehat{d}_{B} realized by infinitesimal path length in merge tree space. This result suggests that in some special cases the bottleneck distance (which can be computed quickly) can be substituted for the interleaving distance (in general, NP-hard). 1 Introduction One central topic in applied topology is the multiscale study of shape. Beginning with a family of nested topological spaces \{X_{t}\}_{t\in\mathbb{R}} , the dimension-0 persistence barcode , or simply the barcode , captures the path components of the family as t evolves. The barcode is a multiset of intervals [t_{b},t_{d}) on which individual components “persist”: the birth value t_{b} at which the component first appears, and the death value t_{d} at which it merges with an older component [ ZC04 ] . From this summary, the number of path components in X_{t} can be recovered as the number of intervals containing t . Crucially, when merging of path components occurs, the barcode marks the death of the later-born component, but retains no information about the component it has merged with. When this information is retained, the components of \{X_{t}\} can be summarized by a sharper descriptor called a merge tree . More precisely defined in Section 2 , a merge tree is a tree-like shape is obtained from the barcode assigned to \{X_{t}\}_{t\in\mathbb{R}} by gluing together intervals corresponding to path components at the moment they are merged. The interplay between dimension-0 persistence barcodes and merge trees has been explored extensively [ Cur18 , KGH20 , CDG+24 ] , and used in applications such as neuronal morphology [ KH+18 , LWA+17 , KRS+19 , BGH+23 ] . Barcodes come equipped with a metric 1 1 1 Technically speaking, the bottleneck distance is an extended pseudometric. On the kinds of barcodes that appear in this paper, those in which each interval has a closed left endpoint and open right endpoint, it is a metric. d_{B} , called the bottleneck distance . The consistency of barcodes in analyzing real data sets depends on foundational stability results; for certain domains of data (including point clouds in \mathbb{R}^{n} under Gromov-Hausdorff distance and height maps under \ell_{\infty} distance), distance-based maps to the metric space of barcodes are Lipschitz [ CSEH07 ] . Beyond stability, the geometry of the space of barcodes itself is complex and not fully understood - among other properties, it is infinite-dimensional and non-Riemannian, with multiple Fréchet means arising from regions of positive curvature [ CGGGMS24 ] . Nevertheless, the distance between two points can be computed efficiently [ KMN17 ] ; it is largely through this metric, and its properties, that statistics can be built on persistence barcodes [ TMMH14 ] . Canonical algebraic and mass-transport distances are known to coincide between 1-parameter persistence modules and their barcodes [ BL14 ] , a key result enabling quick computation of these statistics. A natural variation of the space of barcodes is the space of all merge trees (referred to throughout as \mathrm{MT} ) with interleaving distance d_{I} . Pointwise, \mathrm{MT} differs from the space of barcodes only by the additional combinatorial data of which components merge, so that the forgetful map detaching branches from trees following the Elder Rule ( [ CKMW21 , Cur18 , EH10 ] , see also Figure 2 ) recovers the original barcode. Through this forgetful map we may define the bottleneck distance d_{B} on merge trees as well. We have good reason to hope for tractable geometry: in addition to its natural correspondence with the space of barcodes, many metric spaces of trees have been defined and studied in other applications, such as phylogenetics and data structures. Although phylogenetic analysis focuses on labeled, fixed taxa, metrics based on Euclidean [ BHV01 ] , tropical [ MLYK22 ] and probabilistic metrics [ GNLH21 ] can induce a geometry on unlabeled trees as quotients of labeled tree space (as outlined in [ FN20 ] ). Additionally, when one restricts to rooted trees, the cophenetic metric uses the height of merge events/least common ancestor to encode point pairs in a correlation matrix, and then takes an L^{p} norm on the matrices. Munch and Stefanou [ MS19 ] have observed that this locally represents the interleaving on merge trees measured by d_{I} . Gasparovic et al. [ GMO+25 ] show that the intrinsic interleaving distance \widehat{d}_{I} , as defined by infinitesimal path length in \mathrm{MT} , coincides with d_{I} on the space of merge trees (stated here as Theorem 18 ). That is, every interleaving distance on merge trees can be realized by a geodesic. This is critical for defining Fréchet means and further statistics. Morozov et al. [ MBW13 ] established that d_{I} dominates d_{B} in the merge-tree setting, meaning d_{B}\leq d_{I} , but strict equality does not hold, as d_{B} is a pseudometric on merge trees that cannot distinguish between different trees associated to the same barcode. In their conclusion, Gasparovic et al. mention (informally) a conjecture: that on the space \mathrm{MT} , the intrinsic versions of bottleneck and interleaving distances actually agree. Intuitively, this would follow from a branched covering structure in which generic neighborhoods in \mathrm{MT} with interleaving distance are isometric with their projection to the space of barcodes with interleaving distance, which is in turn isometric to the same set equipped with bottleneck distance. The intrinsic interleaving geodesics, then, are locally isometric lifts of bottleneck geodesics, and induce the same length-space structure on \mathrm{MT} . In Theorem 19 we prove this conjecture: \widehat{d}_{B}=\widehat{d}_{I}. This result extends the computational advantages of bottleneck distance from the space of barcodes to merge trees with known geodesics, and elucidates the relationship between the two geometries. 2 Background 2.1 Merge Trees A tree is a finite acyclic graph. A geometric tree is any topological space X obtained from a tree G by viewing each edge of G as a copy of the unit interval [0,1] and identifying endpoints corresponding to the same vertex of G . Branch points (resp. leaves) in X are the points in x corresponding to branch points (resp. leaves) under this identification. Definition 1 . A merge tree (T,f) is a pair consisting of 1. A topological space T=X\sqcup[0,1)/\sim , where X is a geometric tree and \sim is the relation x_{0}\sim 0 , for some particular x_{0}\in X (called the root ). 2. A continuous function f:T\to\mathbb{R} such that: • f is strictly increasing on its restriction to the copy of [0,1) in the definition of T and f(y)\to\infty as y\to 1 on this interval. • f is strictly increasing on any injective path \gamma:[0,1]\to X with \gamma(1)=x_{0} .