Two scalar field ensembles (illustrated by nine representatives each) with
clustermap distance matrices using branch mappings (top) and classic edit
mappings (center and bottom). In both ensembles, false clusters are identified
by previous approaches, which prevent detection of an outlier in the right
ensemble (which is visible but not detectable without previous knowledge of
the domain, i.e. its existence). Our new distance does not find the false
clusters and is therefore able to identify the outlier clearly in the right
example.

# Branch Decomposition-Independent Edit Distances for Merge Trees

Florian Wetzels0000-0002-5526-7138, Heike Leitte0000-0002-7112-2190, and
Christoph Garth0000-0003-1669-8549
Technische Universität Kaiserslautern

###### Abstract

Edit distances between merge trees of scalar fields have many applications in
scientific visualization, such as ensemble analysis, feature tracking or
symmetry detection. In this paper, we propose branch mappings, a novel
approach to the construction of edit mappings for merge trees. Classic edit
mappings match nodes or edges of two trees onto each other, and therefore have
to either rely on branch decompositions of both trees or have to use auxiliary
node properties to determine a matching. In contrast, branch mappings employ
branch properties instead of node similarity information, and are independent
of predetermined branch decompositions. Especially for topological features,
which are typically based on branch properties, this allows a more intuitive
distance measure which is also less susceptible to instabilities from small-
scale perturbations. For trees with $\mathcal{O}(n)$ nodes, we describe an
$\mathcal{O}(n^{4})$ algorithm for computing optimal branch mappings, which is
faster than the only other branch decomposition-independent method in the
literature by more than a linear factor. Furthermore, we compare the results
of our method on synthetic and real-world examples to demonstrate its
practicality and utility.

<ccs2012> <concept>
<concept_id>10010147.10010371.10010352.10010381</concept_id>
<concept_desc>Computing methodologies Collision detection</concept_desc>
<concept_significance>300</concept_significance> </concept> <concept>
<concept_id>10010583.10010588.10010559</concept_id> <concept_desc>Hardware
Sensors and actuators</concept_desc>
<concept_significance>300</concept_significance> </concept> <concept>
<concept_id>10010583.10010584.10010587</concept_id> <concept_desc>Hardware PCB
design and layout</concept_desc>
<concept_significance>100</concept_significance> </concept> </ccs2012>

[300]Computing methodologies Collision detection [300]Hardware Sensors and
actuators [100]Hardware PCB design and layout

††volume: 41††issue: 3

##  1 Introduction

The study or visualization of scalar fields, either acquired through
simulation or real-world experiments, is a major avenue of research within
scientific visualization. As computational power increases, so does the size
and complexity of scalar fields. Furthermore, modeling of uncertainty is
rapidly becoming increasingly popular as ensemble simulation is becoming more
accessible. Due to this development, efficient measures for the similarity of
scalar fields are of high interest, e.g in clustering tasks or outlier
detection in scalar field ensembles, pattern or periodicity recognition in the
analysis of time-dependent scalar fields, and symmetry or self-similarity
detection within complex scalar fields of high dimension. Furthermore, the
problem of finding mappings between substructures of two given objects is
closely related to distance measures, as many algorithms such as edit
distances compute both concurrently. Uses for such algorithms include feature
tracking in time-varying scalar fields and identifying common structures or
features in ensemble data, which are of importance in many visualization
scenarios.

Since working directly on a scalar field becomes computationally infeasible
rather quickly, these tasks are often executed on abstract representations.
One prominent example for those is the _contour tree_ or a slightly simpler
variant of it, the _merge tree_[EH10]. Both concepts originate in the fields
of Topological Data Analysis, more specifically Persistent Homology[EH10].
They have a variety of applications (see [HLH∗16]), either used directly as a
(abstract) visualization of the represented scalar field, for generating
visualizations, for improving interaction, or simply as a representation
amenable to other methods, e.g. distance functions.

In this paper, we present a novel distance measure for scalar fields and merge
trees that is based on the tree edit distance. While edit distances and
related methods on topological structures have been used before to measure the
distance between scalar fields (e.g. [SMKN20, PVDT21]), our method generalizes
previous approaches to overcome restrictions that prevent these methods from
capturing certain semantic properties of the data in the distance.

More precisely, tree edit distances work on mappings between nodes or edges of
trees, which are local features, whereas the topological features of interest
are global ones such as branches. Recent methods usually overcome this problem
by working on branch decomposition trees or labeling the nodes with properties
of their corresponding branch. Both approaches make the distance depend on a
fixed branch decomposition, typically derived by the elder rule[EH10]. These
are, however, not stable under small-scale perturbations, leading to
semantically imprecise labels of the mapped features and therefore poor
mappings. In this paper, we present a novel method that works on mappings
between branches of arbitrary decompositions, making it therefore robust
against such instabilities. We call them _branch mappings_. Figure Branch
Decomposition-Independent Edit Distances for Merge Trees illustrates two
example applications where branch mappings show better results than previous
approaches. Furthermore, our method generalizes the notion of tree edit
distances as a whole, and we aim to provide an entry point for further
research into this field and its application in scientific visualization and
computational topology, for which it was developed. In detail, our
contributions are the following:

  * •

We collect prior work on edit distances in topology-based visualization, and
provide a novel categorization based on the desired characteristics discussed
above. An overview is given in Table 1.

  * •

We describe a _branch decomposition-independent_ edit distance that focuses on
paths and branches instead of nodes and edges; this stands in contrast to
previous methods that are either branch decomposition-dependent or focus on
edges.

  * •

We illustrate the benefits of this distance in visualization applications by
showcasing several synthetic and real-world examples.

After discussing related work in Section 2, we provide basic definitions, an
introduction into tree edit distances and the categorization in Section 3.1.
In Section 3, we define the concept of _branch mappings_ , which are the core
of our new distance measure and study it formally in detail. Application
examples and practical comparisons with previous methods can be found in
Section 5, before we conclude in Section 6 and give an outlook on future work.

##  2 Related Work

Similarity or dissimilarity measures based on topological abstractions of
scalar fields, or more generally topological descriptors, have been studied in
various ways and a variety of techniques have been proposed in increasing
frequency. A recent survey by Yan et al. [YMS∗21] gives a good overview over
these methods. An introduction into topology based visualization methods in
general can be found in the survey by Heine et al. [HLH∗16].

Out of these methods, the works of Sridharamurthy et al. [SMKN20, SN21], Pont
el al. [PVDT21], Saikia et al. [SSW14], Lohfink et al. [LWL∗20] and Beketayev
et al. [BYM∗14] are most related to ours, as they are all based on edit
mappings or similar mappings between contour or merge trees and their branch
decomposition trees. In Section 3.2, we discuss these methods in detail in
context together with the classification.

Furthermore, our work can be seen as a generalization of tree edit distances
without the context of merge trees. An overview over various versions of tree
edit distances and related problems was given by Bille in 2005 [Bil05].
Closely related techniques are the _constrained edit distance_ [Zha96] and the
_tree alignment distance_ [JWZ94] on unordered rooted trees, or the _one-
degree edit distance_ on ordered trees [Sel77]. We provide a more detailed
discussion of these methods in Section 3.3.

#### Topology-based Similarity Measures.

Apart from edit distances on merge trees or contour trees, other distance
measures based in topological descriptors have been used; among these, the
persistence diagram is frequently used. Mapping persistence pairs of two
scalar fields based on some metric between them is, in principle, largely
equivalent to computing edit distances on branch decomposition trees; the only
difference is that persistence diagrams do not take into account the nesting
of the persistence pairs. Prominent examples of such distances / mapping
methods are the _Wasserstein distance_ [CSEHM10] and the _bottleneck distance_
[CEH07]. Pont et al. [PVDT21] explicitly compare their edit distance method to
these distance measures. An example for a more advanced method based on
persistence diagrams is the work by Rieck et al. [RSL20].

Other graph-based distance measures work, for example, on Reeb Graphs [BDFL16,
BGW13, CO17, SMP15], extremum graphs [NTN15], or also on merge and contour
trees without specifically using an edit distance [MBW13, TN11, YWM∗20].

#### Topology-based Feature Tracking.

Edit mappings between topological descriptors can be used to track and
visualize features in time-varying scalar fields. Here, they are typically
applied to determine correspondence between topologically-characterized
features e.g. across time. The distance measures discussed above can therefore
all be used for this task (e.g. [LGW∗21] or [PVDT21]). Furthermore, a further
set of tracking techniques is based on topological descriptors directly
without relying on edit distance (e.g.[OHW∗17, EHMP04, BWP∗10]). Finally, a
last class of methods relies on topological descriptors only for feature
_identification_ , while the actual tracking is then done by other means, e.g.
a measure of spatial overlap [LWM∗17, SW17, SGL∗16, SHD∗20].

#### Topology-based Ensemble Visualization.

Another area where often methods similar to edit distances are used for
comparative analysis or similarity assessment is uncertainty visualization via
ensembles, specifically the task of finding a representative for the topology
of an ensemble of scalar fields. Lohfink et al. [LWL∗20] and Pont et al.
[PVDT21] derive a representative tree structure for the ensemble from the
induced edit mappings. Other examples for contour tree based visualizations of
ensemble or uncertain data can be found, for example, in the works of Wu and
Zhang [WZ13], Kraus [Kra10] and Günther et al. [GST14]. An example that does
not work on contour trees but persistence diagrams can be found in [TMMH14].

##  3 Merge Trees and Tree Edit Distances

In this section, we start with basic definitions of merge trees and notation
for paths and branches in the Subsection 3.1. Then, we will give an overview
over edit distances on general trees that are relevant for edit distances on
merge trees in 3.2. After that, we will review previous approaches for mapping
based merge tree distances and categorize them in 3.3. An overview is given in
Table 1.

###  3.1 Merge Trees

A detailed introduction into persistent homology and a definition of merge
trees can be found in [ELZ00] or [MW13]. For this paper, we restrict to an
abstract model that captures merge trees of scalar fields of dimension $>1$.

#### Abstract Merge Trees.

We now define the abstract model for merge trees, to which we will refer as
_abstract_ merge trees. These should just be the class of trees, which can be
interpreted as merge trees for some domain of dimension at least $2$.

###### Definition 1

An unordered, rooted tree $T$ of (in general) arbitrary degree (i.e. number of
children) with node labels $f:V(T)\rightarrow\mathbb{R}$ is an _Abstract Merge
Tree_ if the following properties hold:

  * •

The root node has degree one, $\deg(\operatorname{root}(T))=1$

  * •

All inner nodes have a degree of at least two,
$\deg(v)\neq 1$ for all $v\in V(T)$ with $v\neq\operatorname{root}(T)$

  * •

All nodes have a larger scalar value than their parent node, $f(c)>f(p)$ for
all $(c,p)\in E(T)$

(Abstract) Merge trees can have arbitrary further edge- or vertex-labels, e.g.
persistence, volume or the actual segment of an arc.

Since the root of an abstract merge tree always has degree one and inner nodes
do not, subtrees rooted in an inner node are not abstract merge trees
themselves. Therefore, we identify subtrees by root edges, rather than root
nodes: Formally, for a node $p$ with children $c_{1},...,c_{k}$, the subtree
rooted in $(c_{1},p)$ is the “classic” subtree rooted in $p$ where the
subtrees rooted in $c_{2},...,c_{k}$ are removed. Given an abstract merge tree
$T$ with subtree $T^{\prime}$ rooted in the edge $(c,p)$, we define
$T-T^{\prime}$ to be the tree $T^{\prime\prime}$, which we obtain by removing
all edges and all vertices of $T^{\prime}$ from $T$ except the root $p$. If
$p$ has degree two in $T$, then we also remove it from $T^{\prime\prime}$, as
otherwise $p$ would be an inner node of degree one in $T^{\prime\prime}$. With
this definition, it holds that $T^{\prime}$ and $T^{\prime\prime}$ are
abstract merge trees as well.

From now on, we will often just use the term _merge tree_ and it should be
clear from the context if this refers to an abstract merge tree or an actual
merge tree corresponding to a given scalar field.

#### Paths and Branches.

As for general graphs, a _path_ of length $k$ in a merge tree $T$ is a
sequence of vertices $p=v_{1}...v_{k}\in V(T)^{k}$ with $(v_{i},v_{i-1})\in
E(T)$ for all $2\leq i\leq k$ (note the strict root-to-leaf direction). We
denote the edges within a path $p$ by
$\operatorname{edges}(p)\coloneqq\\{(v_{i},v_{i-1})\bigm{|}2\leq i\leq k\\}$.
A _branch_ of $T$ is a path that ends in a leaf. A branch $b=b_{1}...b_{k}$ is
a parent branch of another branch $a=a_{1}...a_{\ell}$ if $a_{1}=b_{i}$ for
some $1<i<k$. We also say $a$ is a child branch of $b$.

A set of branches $B=\\{B_{1},...,B_{k}\\}$ of a merge tree $T$ is called a
_Branch Decomposition_ of $T$ if
$\\{\operatorname{edges}(B_{1}),...,\operatorname{edges}(B_{k})\\}$ is a
partition of $E(T)$. By $B(T)$ we denote the set of all branch decompositions
of $T$. Every branch decomposition $B\in B(T)$ of an abstract merge tree
contains exactly one branch $b\in B$ with $\operatorname{root}(T)\in b$. We
call this branch the _main branch_ of $B$.

The parent-child relations of the branches in a branch decomposition $B\in
B(T)$ form a tree structure by themselves. The tree build from the vertex set
$V=B$ and edge set

$E=\\{(a,b)\bigm{|}a,b\in B,\ b\text{ is a parent branch of }a\\}$

is called the _Branch Decomposition Tree_ (BDT) of $B$.

Let $T$ be a merge tree with $B\in B(T)$, $T^{\prime}$ a subtree of $T$ rooted
in $(c,p)$ and $T^{\prime\prime}=T-T^{\prime}$. If there is a branch
$b=b_{1}...b_{k}$ in $B$ that starts in $(c,p)$, i.e. $p=b_{1},c=b_{2}$, then
$B$ induces branch decompositions $B^{\prime}\in B(T^{\prime})$ and
$B^{\prime\prime}\in B(T^{\prime\prime})$. $B^{\prime}$ and $B^{\prime\prime}$
can be obtained in the obvious way: let $a=a_{1}...a_{\ell}$ with
$b_{1}=a_{i}$ be the parent branch of $b$. We put $b$ into $B^{\prime}$ and we
put the branch $a_{1}...a_{i-1}a_{i+1}...a_{\ell}$ into $B^{\prime\prime}$ if
$p$ has degree two and $a$ otherwise. All other branches from $B$ are put into
$B^{\prime}$ if they are descendants of $b$ and into $B^{\prime\prime}$
otherwise. We denote the branch decompositions $B^{\prime}$ and
$B^{\prime\prime}$ by $B[T^{\prime}]$ and $B[T^{\prime\prime}]$.

###  3.2 Distance Measures for Trees

Various distance measures for rooted unordered trees have been proposed and
investigated in the last decades. In contrast to the ordered case, they differ
significantly in computational complexity, ranging from quadratic algorithms
of running time $\mathcal{O}(n\cdot m)$ to NP-hard or even MAX SNP-hard
problems. We now provide a short overview over often-used methods to provide
insight into the framework of tree edit distances in which we aim to place our
new method. Furthermore, this elucidates the relation between the various
other edit distances that have been applied to merge trees.

The classic edit distance for rooted, ordered, node-labeled trees was
introduced by Tai [Tai79] and is defined to be the cost-optimal sequence of
the following edit operations:

  * •

node-deletion, where all children of the deleted node are appended to its
parent,

  * •

node-insertion, where a new child is inserted for some node and a subset of
its children is made the children of the new node, and

  * •

node-relabel, where the label of a node is changed.

The cost of the single operations is defined by some cost function
$c:((L\cup\\{\bot\\})\times(L\cup\\{\bot\\}))\rightarrow\mathbb{R}_{\geq 0}$
where $L$ is the set of node labels and $\bot$ stands for the null node needed
to represent deletions and insertions. If the basic cost function defines a
metric on the set $L\cup\\{\bot\\}$, then the edit distance between two trees
defines a metric on the set of all rooted, unordered, $L$-labeled
trees[Tai79].

Edit sequences induce a mapping between the vertices of the trees, called
_edit mappings_ or _Tai mappings_ [Tai79]. These are ancestor-preserving, one-
to-one mappings between the two vertex sets. Their cost is defined as the sum
of the relabel costs for all pairs in the relation representing the mapping
together with the sum of all insertion/deletion costs for all vertices from
both trees that are not present in the relation. These mappings are induced as
all nodes in the first tree that are not changed within an edit sequence as
well as those relabeled can be matched to one unique node in the second tree.
Due to this correspondence between edit sequences and mappings, it can be
shown that the cost of the optimal sequence and the optimal mapping is equal.
Typical algorithms for edit distances therefore compute the induced mappings
and their cost, not the actual edit sequence (which can of course be derived
from it).

In contrast to the ordered case, where the general edit distance can be
computed in cubic time [DMRW07, DG18], the problem of computing the edit
distance for unordered trees (which we will call $\mathbf{d_{e}}$) is NP-hard
[ZSS92] and even MAX SNP-hard [ZJ94], and therefore not arbitrarily close to
approximate by a tractable algorithm unless P=NP. This has led to the
development of many simplified versions of the edit distance. Two very popular
approaches are tree alignments [JWZ94] and the constrained edit distance
[Zha96].

An _alignment_ of two trees is a supertree of both that is obtained by
inserting in both trees until they are isomorphic. An alignment induces a
mapping and corresponding costs in a similar fashion as before. The cost of
the optimal alignment is equivalent to an edit distance where all insertions
have to occur before all deletions. We denote this distance in the case for
general trees as $\mathbf{d_{a}}$.

An edit mapping between two trees is called _constrained_ , if it also
fulfills the property that disjoint subtrees are strictly mapped to disjoint
subtrees [Zha96]. The _constrained edit distance_ is defined to be the cost of
an optimal constrained edit mapping between two trees. We denote this distance
in the case for general trees as $\mathbf{d_{c}}$.

Pont et al. [PVDT21] further restricted the constrained edit mappings
specifically for the usecase of BDTs of merge trees. They introduced the
constraint that if a node is deleted, i.e. mapped to null, the entire subtree
rooted in this node has to be deleted, too. This distance is an unordered
version of the 1-degree edit distance which has been proposed by Stanley
Selkow [Sel77] for ordered trees. However, we do not provide a formal proof
for this equivalence. We denote the distance on unordered trees by
$\mathbf{d_{1}}$.

All three versions discussed can be computed more efficiently than the general
edit distance. The alignment distance is still NP-hard [JWZ94] for trees of
arbitrary degree, but can be computed in quadratic time if the trees have
bounded degree [JWZ94], which is a reasonable assumption for merge trees
(however, not true in general). Constrained and 1-degree edit distances are
computable in polynomial time for both bounded degree trees and arbitrary
degree trees, specifically quadratic time for bounded degree [Zha96, PVDT21],
and in time $\mathcal{O}(n_{1}\cdot
n_{2}\cdot(\deg_{1}+\deg_{2})\cdot\log(\deg_{1}+\deg_{2})$ for arbitrary
degree. Furthermore, all three distances form a hierarchy in terms of how
restrictive they are for the allowed mappings and therefore also their search
spaces form a hierarchy of inclusions. For the four distances and arbitrary
trees $T_{1},T_{2}$ the following holds if they are applied using the same
base metric (derived from a clear hierarchy of the recursions in [JWZ94,
Zha96, Sel77]):

$d_{e}(T_{1},T_{2})\leq d_{a}(T_{1},T_{2})\leq d_{c}(T_{1},T_{2})\leq
d_{1}(T_{1},T_{2}).$

###  3.3 Edit Distances for Contour Trees and Merge Trees

Distance metrics between contour trees or merge trees have been used as
similarity measures for scalar fields in many varieties, especially through
the use of tree edit distances and their corresponding edit mappings. We will
now go through those previous approaches that are most similar to ours, which
are those that either explicitly compute structure-preserving mappings between
certain parts of the trees or at least internally use them to compute the
distance based on a base metric for the mapped objects.

| Edit Dist. | BDI | Global Prop. | Time
---|---|---|---|---
$d_{C}$ [SMKN20] | ✓ ($d_{c}$) | – | ✓ | $\Theta(n^{2})$
$W_{2}^{T}$ [PVDT21] | ✓ ($d_{1}$) | – | ✓ | $\Theta(n^{2})$
$d_{S}$ [SSW14] | ✓ ($d_{1}$) | – | ✓ | $\Theta(n^{2})$
$d_{A}$ [LWL∗20] | ✓ ($d_{a}$) | ✓ | – | $\Theta(n^{2})$
$d_{M}$ [BYM∗14] | – | ✓ | ✓ | $\omega(n^{5})$
$d_{C}$ (This paper) | ✓ ($d_{B}$) | ✓ | ✓ | $\mathcal{O}(n^{4})$

Table 1: The categorization of mapping based merge tree distances. A distance
should be a true edit distance (Edit Distance), should be branch
decomposition-independent (BDI) and should use global properties (Global
Prop.). The runtimes refer to bounded degree.

#### Categorization.

To give a better intuition for the differences between these methods and our
method, we categorize them in the following by two further properties (apart
from the distinction whether they are explicitly edit distances or not). The
first one is the type of the input objects. These can be actual contour trees
or merge trees or branch decompositions of these. Then, we distinguish the
type of labels or properties of these features that are used by the base
metric to compute distances of mapped pairs. Here we distinguish local and
global properties as labels of the mapped objects. Examples could be edge
persistence for a local property and branch persistence for a global property.

Sridharamurthy et al. [SMKN20] used the constrained edit distance
$\mathbf{d_{c}}$ to measure the distance between merge trees. As a base metric
for the merge tree nodes, they used $L_{\infty}$ and overhang costs between
the corresponding branches. In [SN21] they adapted this distance to also work
on subtrees (similar to eBDGs in [SSW14]). Pont et al. [PVDT21] used a very
similar distance to compute geodesics between merge trees and barycenter merge
trees as a representative of an ensemble of scalar fields. They applied the
1-degree edit distance $\mathbf{d_{1}}$ to _unordered_ (see Section 4.3 and
App. A in the supp. material) branch decomposition trees using the Wasserstein
metric to compare branches. Another closely related approach is the one by
Saikia et al. [SSW14]. They also compute the one-degree edit distance
$\mathbf{d_{1}}$ between branch decomposition graphs of two merge trees to
find self-similarities within the scalar fields. In contrast to Pont et al.
they considered _ordered_ BDTs (see App. A in the supp. material). As for the
categorization, these three methods fall into the same category: they use
fixed branch decompositions as an input (Pont et al. and Saikia et al. even do
so explicitly by working on BDTs) while using global properties (i.e.
persistence, birth, death, etc. of branches) as labels. We will refer to these
distances as $d_{C}$, $W_{2}^{T}$ and $d_{S}$ and by this mean the mapping
method independent on the used base metric (which means we do use the notation
$W_{2}^{T}$ also for distances that do not use the Wasserstein metric for
single branches). We should note that Pont et al. use a normalization step as
preprocessing to adapt the edit distance for geodesics and barycenters that
modifies the branch labels according to the branch decomposition. To obtain a
meaningful comparison, we only consider their metric without the normalization
step, as it then fits better into the hierarchy of different edit distances.

Lohfink et al. [LWL∗20] used tree alignments to represent the topology of a
scalar field ensemble and to obtain a joint layout of all the contour trees in
the ensemble. The underlying distance is the tree alignment distance
$\mathbf{d_{a}}$. In contrast to labeling the nodes with their corresponding
branches and using a base metric on branches, they labeled the nodes with
their unique parent edge and used euclidean distances for different arc
properties as the base metric. This approach gets actual contour trees as an
input and uses local properties (edge properties) as labels. We will refer to
this distance as $d_{A}$, again independent of the used base metric.

A branch decomposition-independent approach that does not fit into the concept
of edit distances was introduced by Beketayev et al. [BYM∗14] ($d_{M}$). They
also compute a cost-optimal mapping between two branch decompositions of two
given merge trees. However, in contrast to the edit distances, the total cost
of such a mapping is not the sum of the mapped branches, but the value of the
highest cost pair in the mapping. Furthermore, they also compute the optimal
pair of branch decompositions that minimizes the costs. This falls into the
category of methods that get contour trees as inputs (although their core
method compares branch decompositions, they actually find the optimal one) and
also use global properties (branch persistence etc.) for the base metric.

#### Advantages of using a true edit distance.

Almost all approaches from the last section use an actual edit distance. A
very useful property of edit distances is that they always come with a mapping
of different features of the compared objects. In our case they induce a
mapping between the nodes, edges or branches of the two input trees. In fact,
given a cost function for matching two such features or deleting them, the
edit distance value is equal to sum of all mapped or deleted features in the
optimal mapping. We usually compute the distance and the mapping
simultaneously.

An outlier in the list above is the method of Beketayev et al. [BYM∗14]. They
also consider underlying mappings, but since the value of the mapping is only
the value of the worst match or largest deletion, the correspondence between
mappings and distances is weaker. Moreover, their distance does not correspond
to the cost of an edit sequence between the two input trees.

#### Using local properties only.

The alignment distance used in [LWL∗20] uses arc properties for the base
metric. While independent of a specific branch decomposition, this approach
has a substantial downside, which we will discuss in the following example. If
one scalar field has two nested maxima of similar scalar value with the saddle
connecting them close to the extreme points, and the other one only has one of
the maxima, then the distance between the two trees should be small, as there
is only a small split of the maximum from the second tree, which can also be
seen as an insertion of one very small maximum branch. However, the
persistence of the two arcs corresponding to the leaf nodes are both very
small whereas the persistence of the arc leading to the single maximum in the
other tree is large. Therefore the edit costs are high, contradicting the
(intuitively) desired behaviour. Figure 1(a) shows two example trees where
this problem appears. A practical example could be two trees where we apply a
simplification by persistence to both of them and in one tree the second
maximum stays whereas it is removed in the other tree.

031212911031212

(a)

041312………041213………

(b)

Figure 1: Examples for matching problems. For local properties, in (a) we see
two merge trees with the optimal alignment matching in green. Intuitively, the
cost should be $2$, as only one arc of persistence $2$ is removed. However,
the actual cost is $8$ since mapping the right maximum in the left tree
(persistence $3$) to the left maximum in the right tree (persistence $9$) has
cost of $6$. For a fixed branch decompostion, in (b) two merge trees with two
different branch decompositions are shown. The two best matching options are
shown in violet and green. Both yield non-optimal results in comparison to the
desired distance.

#### Using fixed branch decompositions.

The problem stated in the last section can be fixed by using branch
persistences instead of arc persistences. Most methods that we listed above
make use of this approach. However, such a metric would depend on a fixed
branch decomposition, but these are not unique and two badly chosen branch
decompositions of two very similar trees can lead to huge distances. Usually,
a very specific branch decomposition is used, namely the one derived by the
elder rule, preferring the most persistent branches over small ones. But also
this specific decomposition can have crucial instabilities which we will again
see in an example. Consider a merge tree with two very persistent branches,
one of which is feature-rich and one so simple that it does not have any child
branches. Now consider another tree with the same properties. Then, for a low
distance, we need to match the feature-rich branches in both trees onto each
other as well as the simple branches. If, however, the two branches have
similar persistence, the order of the branches can flip between the two trees.
Then a good matching between the two branch decompositions has only the
following options: either map the child branches of the two feature-rich
branches onto each other and take the cost of the persistence difference of
the main branches or match the main branches according to their persistence
and take the cost of not matching the smaller branches. Figure 1(b)
illustrates this example.

This problem can be illustrated on the following practical example. Consider a
scalar field ensemble consisting of 20 scalar fields as illustrated in Figure
Branch Decomposition-Independent Edit Distances for Merge Trees (all members
shown in Figure 2, supp. material). All fields have four large peaks of
similar size with five smaller peaks arising from one of them. The height,
size and exact position of all peaks are chosen randomly within small ranges.
This leads to the following scenario: Which of the four main peaks (the one
with smaller peaks or one of those without) represents the global maximum
differs across the ensemble, and hence also the main branch of the branch
decomposition derived by the elder rule differs. All fields are otherwise
highly similar, as are their merge trees. There are no significant differences
between the fields apart from small-scale, noise-like instabilities. However,
the merge trees resemble those in Figure 1(b) and therefore cannot be mapped
properly by branch decomposition-dependent distances.

On this dataset, we observe that $d_{C}$ [SMKN20] and $W_{2}^{T}$ [PVDT21],
using the Wasserstein base metric proposed in [PVDT21], distinguish four
clusters within the members, which does not convey an intuitive understanding
of the data. A clustermap visualization of the edit distances can be seen in
Figure Branch Decomposition-Independent Edit Distances for Merge Trees. In
contrast to that, our new distance function, which we define in the next
section, does not find these false clusters and therefore resembles an
intuitive understanding of the dataset much closer.

##  4 Branch Mappings

All of the methods listed above have one of the mentioned shortcomings. They
either use branch properties to overcome the problem of local properties at
the expense of the need of a fixed branch decomposition or they are
independent of branch decompositions but only use local properties or they
combine the positive aspects of both but do not offer the benefits of a true
edit distance.

Here, we present a new approach that can be seen as a combination of the ones
from [PVDT21], [SMKN20] and [BYM∗14]. We modify the constrained tree edit
distance so that it maps branches of two given merge trees onto each other and
determine the total cost of such a mapping by taking the sum of distances of
all mapped structures while computing the optimal branch decompositions for
these costs at the same time. By staying within the notion of edit distances,
we keep their global characteristics (in contrast to the more local concept of
taking the cost of the worst matched feature pair) and the induced mappings,
while still doing the optimization over all possible branch decompositions and
mapping the actual features of interest (namely branches, not nodes or edges).

The distance we will introduce is based on the new concept of _branch
mappings_ that are similar to edit mappings and can be seen as an adaptation
of those to branches of trees instead of nodes. Branch mappings can be applied
to merge trees with arbitrary branch decompositions as well as merge trees
with a fixed, given branch decomposition. They can be computed in
$\mathcal{O}(n^{2}\cdot m^{2})$, which is faster than the only other branch
decomposition-independent method (from [BYM∗14]) by more than a linear factor.
We achieve this by intertwining the dynamic programming that iterates all
branch decompositions with the dynamic programming for the classic edit
distance. However, this method of course also has its downsides. We will show
that the branch mapping distance, while being a metric on the domain of branch
decompositions of merge trees, it is not a metric on the set of merge trees.
Furthermore, the computation cost is higher than for the typical tractable
edit distances, which usually can be computed in around $\mathcal{O}(n\cdot
m)$.

We start with the core concept underlying our distance, _branch mappings_.
Similar to edit mappings, constrained edit mappings, or alignments, which are
mappings between the vertex sets of two given trees with different
restrictions to keep certain structures, branch mappings map branches of one
tree to branches of another tree while keeping the ancestor relations of the
mapped branches.

###### Definition 2

Given two abstract merge trees $T_{1},T_{2}$, a branch mapping between $T_{1}$
and $T_{2}$ is a mapping $M\subseteq B_{1}\times B_{2}$ with branch
decompositions $B_{1}\in B(T_{1}),B_{2}\in B(T_{2})$ such that

  1. 1.

If $(a,b),(a^{\prime},b^{\prime})\in M$ then $a=a^{\prime}\Leftrightarrow
b=b^{\prime}$,

  2. 2.

$(m,m^{\prime})\in M$, where $m$ and $m^{\prime}$ are the main branches of
$B_{1}$ and $B_{2}$,

  3. 3.

If $a$ and $b$ are parent branches of $a^{\prime}$, $b^{\prime}$ and
$(a^{\prime},b^{\prime})\in M$, then $(a,b)\in M$,

  4. 4.

If $(a,b),(a^{\prime},b^{\prime})\in M$ and $a_{1}$ is a descendant of
$a^{\prime}_{1}$ then $b_{1}$ is a descendant of $b^{\prime}_{1}$,

where $a=a_{1}...a_{k},a^{\prime}=a^{\prime}_{1}...a^{\prime}_{k^{\prime}}\in
B_{1}$ and
$b=b_{1}...b_{\ell},b^{\prime}=b^{\prime}_{1}...b^{\prime}_{\ell^{\prime}}\in
B_{2}$ are arbitrary branches of the two trees.

Similar to branch decompositions, we define induced mappings as follows: let
$T_{1}^{\prime},T_{2}^{\prime}$ be subtrees of $T_{1},T_{2}$, $B_{1}\in
B(T_{1}),B_{2}\in B(T_{2})$,
$T_{1}^{\prime\prime}=T_{1}-T_{1}^{\prime},T_{2}^{\prime\prime}=T_{2}-T_{2}^{\prime}$
and $M$ be a branch mapping between $B_{1}$ and $B_{2}$. Then we define
$M[B_{1}^{\prime}]$ to be the map

$\\{(a,b)\in M\bigm{|}a\text{ is a descendant of }m^{\prime}\\}$

where $B_{1}^{\prime}=B_{1}[T_{1}^{\prime}]$ and $m^{\prime}$ is the main
branch of $B_{1}^{\prime}$. For
$B_{1}^{\prime\prime}=B_{1}[T_{1}^{\prime\prime}]$ we define
$M[B_{1}^{\prime\prime}]$ to be the map

$\\{(a,b)\in M\bigm{|}a\notin M[B_{1}^{\prime}]\text{ and }a\neq
p\\}\cup\\{(p^{\prime\prime},M(p)\\}$

where $B_{1}^{\prime}$ and $m^{\prime}$ are defined as before, $p$ is the
parent branch of $m^{\prime}$ in $B_{1}$ and $p^{\prime\prime}$ the
corresponding branch in $B_{1}^{\prime\prime}$. We define $M[B_{2}^{\prime}]$
and $M[B_{2}^{\prime\prime}]$ analogously.

###  4.1 Branch Mapping Distance

In analogy to basing tree edit distances on their corresponding mappings, we
now define a distance function on merge trees and their branch decompositions.
For ease of notation, we define for a branch mapping $M$ the set of all edit
operations as

$\overline{M}=M\cup\\{(a,\bot)\bigm{|}\nexists(a,b)\in
M\\}\cup\\{(\bot,b)\bigm{|}\nexists(a,b)\in M\\}.$

Given a cost function on branches of two merge trees $T_{1},T_{2}$,

$\operatorname{c}:((\bigcup_{B_{1}\in
B(T_{1})}B_{1}\cup\\{\bot\\})\times(\bigcup_{B_{2}\in
B(T_{2})}B_{2}\cup\\{\bot\\}))\rightarrow\mathbb{R},$

we define the cost of a branch mapping $M$ to be

$\operatorname{c}(M)=\sum_{(a,b)\in\overline{M}}\operatorname{c}(a,b).$

For a branch decomposition $B\in B(T)$ of some merge tree, we define an empty
mapping $M_{\bot}(B)=\\{(b,\bot)\bigm{|}b\in B\\}$ to be the mapping that
corresponds to deleting the whole tree $T$. We can now define the distance
functions based on the branch mappings.

###### Definition 3

Given two abstract merge trees $T_{1},T_{2}$ with branch decompositions
$B_{1}\in B(T_{1}),B_{2}\in B(T_{2})$, define the distance function

$d_{B}(B_{1},B_{2})=\min\\{\operatorname{c}(M)\bigm{|}M\text{ is a branch
mapping between }B_{1},B_{2}\\}.$

Analogously, for two abstract merge trees $T_{1},T_{2}$, we define

$d_{B}(T_{1},T_{2})=\min\\{d_{B}(B_{1},B_{2})\bigm{|}B_{1}\in
B(T_{1}),B_{2}\in B(T_{2})\\}.$

Furthermore, we also include empty trees into the definition of the branch
mapping distance:

$\displaystyle d_{B}(B_{1},\bot)$ $\displaystyle=$
$\displaystyle\operatorname{c}(M_{\bot}(B_{1})),d_{B}(\bot,B_{2})=\operatorname{c}(M_{\bot}(B_{2})),$
$\displaystyle d_{B}(T_{1},\bot)$ $\displaystyle=$
$\displaystyle\min\\{d_{B}(B_{1},\bot)\bigm{|}B_{1}\in B(T_{1})\\}$

and $d_{B}(\bot,T_{2})$ symmetrically.

For practical purposes, we want to restrict the base metric for single
branches or the branch labels to semantically meaningful ones. In our case,
this means that those properties captured by the labels or costs are actually
_branch_ properties. Formally, we want a cost function
$\operatorname{c}(a_{1}...a_{k},b_{1}...b_{\ell})$ between two branches to
only depend on the start and end points of the branches, i.e. $a_{1}$,
$a_{k}$, $b_{1}$ and $b_{\ell}$. The number and position of child branches
should be irrelevant. We then call it a _pure_ branch distance.

###  4.2 Important Properties

#### Metric properties of the branch mapping distance

We now show that $d_{B}$ is a metric on the set of all branch decompositions
of abstract merge trees but not on the set of all abstract merge trees.

###### Theorem 1

$d_{B}$ is a metric on the set

$\\{(T,B)\bigm{|}T\text{ is an abstract merge tree, }B\in B(T)\\},$

as long as the cost function $c$ on the branch labels is a metric.

######  Proof 4.2.

See supplementary material, App. B.

######  Theorem 4.3.

$d_{B}$ is not a metric on the set

$\\{T\bigm{|}T\text{ is an abstract merge tree}\\}.$

######  Proof 4.4.

If we consider the distance function $d_{B}$ applied to merge trees with
arbitrary branch decompositions, the triangle inequality does (in contrast to
the previous result) no longer hold. The previous argument is not possible in
this case since the optimal mapping between $T_{1},T_{2}$ and $T_{2},T_{3}$
can use a different branch decompositions which leads to mapping costs that
are not possible with a single branch mapping. A counterexample can be found
in Figure 2.

031060510806118$\text{cost}(a,b)=2$$\text{cost}(b,c)=1$$\text{cost}(a,c)=5$(a)(b)(c)

Figure 2: Branch mapping distances for three merge trees using
$|b_{1}-b_{2}|+|p_{1}-p_{2}|$ as base metric for branches with birth values
$b_{1},b_{2}$ and persistences $p_{1},p_{2}$. The optimal map between (a) and
(b) uses branches $(0,10)$, $(3,6)$ and $(5,8)$, whereas the one for (b) and
(c) uses $(0,8)$, $(5,10)$ and $(6,11)$. These maps yield branch mapping
distances of $2$ and $1$. The optimal map between (a) and (c) uses branches
$(0,10)$, $(3,6)$, $(0,11)$ and $(6,8)$ which yields a total distance of $5$.
This violates the metric property as the direct distance between (a) and (c)
is greater than the way over (b).

#### Recursive Structure

A core property of the branch mapping distance is the following: as long as
the base metric is a pure branch metric, we can decompose a branch mapping
into the different subtrees of the given branch decompositions and if we do
so, we can do it in the same way for the cost of the mapping.

######  Lemma 4.5.

Given two merge trees $T_{1},T_{2}$ with branch decompositions $B_{1},B_{2}$
and a branch mapping $M\subseteq B_{1}\times B_{2}$, for any subtrees
$T_{1}^{\prime}$ and $T_{2}^{\prime}$ of $T_{1}$ and $T_{2}$ for which
$B_{1}[T_{1}^{\prime}]$ and $B_{2}[T_{2}^{\prime}]$ exist, and any pure branch
distance $c$, it holds that:

  * •

$\operatorname{c}(M)=\operatorname{c}(M[B[T_{1}^{\prime}]])+\operatorname{c}(M[B[T_{1}-T_{1}^{\prime}]])$,

  * •

$\operatorname{c}(M)=\operatorname{c}(M[B[T_{2}^{\prime}]])+\operatorname{c}(M[B[T_{2}-T_{2}^{\prime}]])$.

######  Proof 4.6.

Follows directly from the pureness of $\operatorname{c}$.

######  Lemma 4.7.

Given two merge trees $T_{1},T_{2}$ with roots $v_{1},u_{1}$, let
$v_{2},u_{2}$ be the unique children of the two roots and let those have
children $v_{3},v_{4}$ and $u_{3},u_{4}$. Let $T_{1}^{\prime}$ be the subtree
rooted in $(v_{2},v_{3})$, $T_{1}^{\prime\prime}$ rooted in $(v_{2},v_{4})$,
$T_{2}^{\prime}$ rooted in $(u_{2},u_{3})$ and $T_{2}^{\prime\prime}$ in
$(u_{2},u_{4})$. Let $M$ be an optimal branch mapping for $T_{1}$ and $T_{2}$.
Then, for the optimal cost of $M$ it holds that:

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime},\bot)+d_{B}(T_{1}-T_{1}^{\prime},T_{2})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(\bot,T_{2}^{\prime})+d_{B}(T_{1},T_{2}-T_{2}^{\prime})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime\prime},\bot)+d_{B}(T_{1}-T_{1}^{\prime\prime},T_{2})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(\bot,T_{2}^{\prime\prime})+d_{B}(T_{1},T_{2}-T_{2}^{\prime\prime})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime},T_{2}^{\prime})+d_{B}(T_{1}-T_{1}^{\prime},T_{2}-T_{2}^{\prime})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime\prime},T_{2}^{\prime\prime})+d_{B}(T_{1}-T_{1}^{\prime\prime},T_{2}-T_{2}^{\prime\prime})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime},T_{2}^{\prime\prime})+d_{B}(T_{1}-T_{1}^{\prime},T_{2}-T_{2}^{\prime\prime})$
or

  * •

$d_{B}(T_{1},T_{2})=d_{B}(T_{1}^{\prime\prime},T_{2}^{\prime})+d_{B}(T_{1}-T_{1}^{\prime\prime},T_{2}-T_{2}^{\prime})$

######  Proof 4.8.

See supplementary material, App. C.

If one of the trees only consists of two nodes, i.e. it only has one possible
branch decomposition with one branch, we can just omit the corresponding
recursions. Next, we consider the recursion for the case where one tree is
empty.

######  Lemma 4.9.

Given a merge tree $T_{1}$ with root $v_{1}$, let $v_{2}$ be the unique
children of the root and let it have children $v_{3},v_{4}$. Let
$T_{1}^{\prime}$ be the subtree rooted in $(v_{2},v_{3})$ and
$T_{1}^{\prime\prime}$ rooted in $(v_{2},v_{4})$. Then, for the optimal cost
of $M_{\bot}(T_{1})$ it holds that:

  * •

$d_{B}(T_{1},\bot)=d_{B}(T_{1}^{\prime},\bot)+d_{B}(T_{1}-T_{1}^{\prime},\bot)$
or

  * •

$d_{B}(T_{1},\bot)=d_{B}(T_{1}^{\prime\prime},\bot)+d_{B}(T_{1}-T_{1}^{\prime\prime},\bot)$,

and $d_{B}(\bot,T_{2})$ decomposes symmetrically.

See Appendix D.

We should note that the previous lemmas only consider binary merge trees.
However, it is easy to adapt for trees of arbitrary degree and we therefore
omit this proof for better readability. We continue with the base cases of the
recursion.

######  Lemma 4.10.

Given two merge trees $T_{1}=(\\{v_{1},v_{2}\\},\\{(v_{2},v_{1})\\})$,
$T_{2}=(\\{u_{1},u_{2}\\},\\{(u_{2},u_{1})\\})$ that only have one branch, the
following holds for $d_{B}$:

  * •

$d_{B}(T_{1},\bot)=\operatorname{c}(v_{1}v_{2},\bot)$,

  * •

$d_{B}(\bot,T_{2})=\operatorname{c}(\bot,u_{1}u_{2})$ and

  * •

$d_{B}(T_{1},T_{2})=\operatorname{c}(v_{1}v_{2},u_{1}u_{2})$.

######  Proof 4.11.

See supplementary material, App. E.

We can use these lemmas to derive a recursive formula for $d_{B}(T_{1},T_{2})$
by taking the minimum of the different terms in each case. This gives a
recursion very similar to the ones for the classic edit distances that can be
computed with a dynamic programming approach. In the Section 4.4 we will
discuss this algorithm.

###  4.3 Search Space Comparison to other Methods

We now want to illustrate more precisely how the branch mapping distance
relates to other known distance measures. Since the contour tree alignments
from [LWL∗20] form some kind of outlier by only considering local properties,
we will only look at those methods that use actual branch properties. We
therefore try to fit the new method into a hierarchy of branch based methods
that we extracted from the papers describing the two closest methods on merge
trees [SSW14, SMKN20, PVDT21]. We do this by illustrating the relationship in
a schematic drawing of the considered search spaces for mappings between
branches/features shown in Figure 3.

$W_{2}^{D}$$d_{C}$$W_{2}^{T}$$d_{B}$$d_{S}$ Figure 3: A schematic illustration
of the search spaces of branch based distance measures for merge trees or
scalar fields. $W_{2}^{D}$ (Wasserstein Distance between Persistence Diagrams,
compare [PVDT21]) maps the branches of a fixed branch decomposition without
any structural constraints. $d_{C}$ and $W_{2}^{T}$ restrict the search space
by introducing structural constraints based on the merge trees. Since $d_{C}$
allows for gaps in the mapping and $W_{2}^{T}$ is not order preserving, the
two models can be seen as orthogonal to each other. $d_{S}$ also works on a
fixed branch decomposition and is strictly more restrictive than the other
two. For details, see App. A (supp. material). $d_{B}$ then takes the
structural constraints from $d_{S}$ but lifts them to the space of arbitrary
branch decompositions, thereby defining a model that is orthogonal to both
$d_{C}$ and $W_{2}^{T}$.

###  4.4 Algorithm

In this section, we will use the recursive structure of optimal branch
mappings shown in Lemmas 4.7-4.10 to derive a recursive algorithm that
computes the branch mapping distance.

First, consider all subtrees $T_{1}^{\prime}$, $T_{1}^{\prime\prime}$,
$T_{2}^{\prime}$, $T_{2}^{\prime\prime}$, $T_{1}-T_{1}^{\prime}$,
$T_{1}-T_{1}^{\prime\prime}$, $T_{2}-T_{2}^{\prime}$ and
$T_{2}-T_{2}^{\prime\prime}$ from Lemma 4.7. All of them (in all recursive
steps) are abstract merge trees with a root of degree one. We can identify the
trees appearing in this recursion by two nodes: the root node of the subtree
and its unique child (which does not have to be a child in the original tree
$T_{1}$/$T_{2}$). Therefore, we generally switch to identifying trees in this
manner in contrast to identifying them just by one node like in the recursions
for classic tree edit distances and define an algorithm computing
$d_{B}(n_{1},p_{1},n_{2},p_{2})$ where $n_{1},n_{2}$ stand for the current
nodes and $p_{1},p_{2}$ stand for the parent nodes of the considered subtrees.
For example, $d_{B}(T_{1},T_{2})$ is represented by
$d_{B}(v_{1},v_{2},u_{1},u_{2})$, whereas
$d_{B}(T_{1}-T_{1}^{\prime},T_{2}-T_{2}^{\prime\prime})$ is represented by
$d_{B}(v_{4},v_{1},u_{3},u1)$. Intuitively, $p_{1},p_{2}$ can be considered as
the last matched nodes in the currently tracked branch, which is illustrated
in Figure 4. In App. F (supp. material), we present pseudo code showing the
algorithm for binary trees and discuss how to adapt the algorithm for non-
binary trees.

$p_{1}$$n_{1}$$c_{1,1}$$c_{1,2}$$p_{2}$$n_{2}$$c_{2,1}$$c_{2,2}$(a)

$d_{B}(c_{1,1},p_{1},c_{2,1},p_{2})+d_{B}(c_{1,2},n_{1},c_{2,2},n_{2})$

$p_{1}$$n_{1}$$c_{1,1}$$c_{1,2}$$p_{2}$$n_{2}$$c_{2,1}$$c_{2,2}$(b)

$d_{B}(c_{1,1},p_{1},c_{2,2},p_{2})+d_{B}(c_{1,2},n_{1},c_{2,1},n_{2})$

$p_{1}$$n_{1}$$c_{1,1}$$c_{1,2}$$p_{2}$$n_{2}$$c_{2,1}$$c_{2,2}$(c)

$d_{B}(c_{1,1},p_{1},n_{1},p_{2})+d_{B}(c_{1,2},n_{1},\bot,\bot)$

$p_{1}$$n_{1}$$c_{1,1}$$c_{1,2}$$p_{2}$$n_{2}$$c_{2,1}$$c_{2,2}$(d)

$d_{B}(c_{1,2},p_{1},n_{1},p_{2})+d_{B}(c_{1,1},n_{1},\bot,\bot)$

Figure 4: Exemplary illustration of recursive structure of
$d_{B}(n_{1},p_{1},n_{2},p_{2})$ in Algorithm 1 in App. F (supp. material). In
(a) we continue main branch tracking with the left subtree in both trees and
match the right subtrees onto each other, whereas in (b) we continue main
branch tracking with the left subtree in $T_{1}$ and the right subtree in
$T_{2}$ and match the other two subtrees onto each other. In (c), we continue
main branch tracking with the left subtree in $T_{1}$ and delete the right
subtree. In $T_{2}$, we do nothing. In (d), we continue main branch tracking
with the right subtree in $T_{1}$, delete the left subtree and do nothing in
$T_{2}$.

#### Running time.

An obvious bound on the running time of Algorithm 1 in App. F (supp. material)
using memoization is $\mathcal{O}(|T_{1}|^{2}\cdot|T_{2}|^{2})$, since the
number of subproblems is constant, they are always smaller than the current
one and there are only $|T_{1}|^{2}\cdot|T_{2}|^{2}$ many 4-tuples of nodes.
However, this can be tightened to
$\mathcal{O}(|T_{1}|\cdot\operatorname{depth}(T_{1})\cdot|T_{2}|\cdot\operatorname{depth}(T_{2}))$,
since we know that $p_{1},p_{2}$ are always ancestors of $n_{1},n_{2}$. A
short discussion on the runtime for non-bounded degree can be found in App. F
(supp. material).

These bounds of course only hold if the base metric is computable in constant
time. Typical metrics like difference in persistence or bottleneck,
Wasserstein and $L_{\infty}$-distances are all constant time operations. For
branch mappings, it is also important that these are pure branch metrics,
since then they only depend on the start and end point of a branch, which are
always available when evaluating the base metric (through $n_{1},p_{1}$ or
$n_{2},p_{2}$).

#### Variants.

There are a few adaptations that can be applied and should be noted here.
First, saddle swap instabilities are a key problem of all tractable edit
distances on merge trees and are of course still present in the branch mapping
distance. To handle such instabilities, [SMKN20] and [PVDT21] use a
preprocessing step to collapse small edges (through an $\epsilon$-parameter)
such that branches in a parent-child relation that are probable to be
influenced by such instabilities become siblings instead. Of course, this
preprocessing is also applicable to our method and should yield the same
improvements, however, we did not implement or test it. Furthermore, it is
possible to adapt our algorithm to not try all branch decompositions and use a
fixed one instead. The computed distance and mapping then becomes equivalent
to the one from [SSW14].

It is also possible to not just sum up the costs of all pairs in the optimal
matchings but to sum up the squared pair costs and then take the square root
of the sum. This approach was used in [PVDT21] and makes the resulting
distance directly comparable to the classic Wasserstein distance for
persistence diagrams. This is of course also possible with our method or
$d_{C}$ and we used this variant for the motivational examples in Section
Branch Decomposition-Independent Edit Distances for Merge Trees.

Another property to note is that branch mappings induce vertex mappings in the
sense of constrained (or even 1-degree) edit mappings. Therefore, it is
possible to construct an alignment of two trees by computing the optimal
branch mapping. This alignment is a supertree of the two input trees and can
therefore again be aligned. This gives us the possibility to use an iterated
heuristic for an alignment of a set of merge trees (based on the branch
mapping distance) as it has been done for contour trees in [LWL∗20]. We plan
to implement such a method in future work.

##  5 Experiments

In the following, we demonstrate the utility of our technique as a basis for
typical tasks in visualization, and compare it against other, similar
techniques. The basis for these experiments is a straightforward Python
implementation of the algorithm given in Section 4.4 and the constrained edit
distance. Merge trees are computed using TTK [TFL∗18], and ParaView [SAL∗07]
is used for result visualization. The three experiments described in the
following correspond to three different uses of distance functions between
scalar fields as found in many visualization applications: outlier
identification, periodicity detection, and feature tracking. App. H (supp.
material) discusses the results on noisy versions of the same data.

For benchmarks, we use a C++ implementation which is publicly available on
Github as well as the easier to read Python version [WLG21]. Computation of
individual distances for the here used trees with up to 80 vertices took only
a few milliseconds. On noisier trees with sizes between 100 and 400, times
went up to the range of seconds. For more details, see App. G (supp.
material).

###  5.1 Outlier Detection

Outlier detection is a major concern in ensemble analysis, and the distance
between merge trees of two scalar ensemble members can be used towards this.
We consider a synthetic example dataset shown in Figure Branch Decomposition-
Independent Edit Distances for Merge Trees. This dataset is based on the
example ensemble from Section 3.3, with one modification: we add a fifth peak
in the middle of the four large peaks, but create an outlier by omitting this
peak in a single ensemble member. Outlier detection then proceeds by computing
the pairwise merge tree distances for all pairs of trees, using the squared
sum of the mapping costs.

Using clustermaps to visualize the distance matrices, it is easy to see that
the branch mapping distance ($d_{B}$) distinguishes the outlier clearly,
whereas the constrained edit distance $d_{C}$ and the Wasserstein distance
$W_{2}^{T}$ do not. For the latter two, the cost of the missing branch in the
outlier ensemble member is concealed by the cluster effects when working with
fixed branch decompositions. A visualization of the entire ensemble and
further results obtained using additional parameter choice can be found in the
supplementary material (App. H). Note that this dataset was constructed
specifically to illustrate the problem of fixed branch decompositions, as
discussed in Section 3.3. We make both datasets available publicly with our
implementation [WLG21].

###  5.2 Periodicity Detection

Periodicity detection is an often encountered problem in time-varying data; we
here consider a time-varying dataset consisting of 1001 time steps of a
$400\times 50$ grid representing the scalar velocity magnitude of the flow
around a cylinder that forms a periodic Kármán vortex street. It was simulated
by Weinkauf [WT10] using the _GerrisFlowSolver_ [Pop04].

Reproducing the experiment of Sridharamurthy et al. [SMKN20] with our distance
measure, we compute the merge tree distance matrix for all pairs of time steps
and visualize this as a heatmap (cf. Figure 6). Here, the branch mapping
distance matrix exhibits exactly the same periodicity pattern as the
constrained edit distance matrix (Fig. 13 in [SMKN20]), giving a period/half-
period of 75/37 time steps, respectively (see App. H (supp. material) for a
direct comparison).

Figure 5: Feature Tracking for the Heated Cylinder (top) and ion density
(bottom) datasets. We rendered all maxima matched by the optimal branch
mapping in consistent colors over all time points. The matching for the heated
cylinder shows how the rising plume splits up over time into two and then
three distinct maxima while the two peaks around the pole stay constant. The
rendering for the ion density dataset shows that the branch mapping represents
the intuitively correct mapping of the corresponding peaks, which is for
example not true for a mapping obtained by Wasserstein distances on
persistence diagrams according to [PVDT21].

###  5.3 Feature Tracking over Time

As a last experiment, we utilize our distance metric for feature tracking
within a time series of scalar fields. Here, we consider two different time
series. The SciVis contest 2008 dataset [WN08] describes development of ion
density during universe formation, and was also used as in a tracking case
study in prior work [PVDT21]. Second, the heated cylinder dataset describes an
ensemble of flows around a heated pole in a fluid. This dataset was also used
in prior work on ensemble analysis [LWL∗20], and we make it available publicly
[WLG21]. We again consider velocity magnitude as the variable of interest for
tracking.

For both datasets, we provide a proof-of-concept for the proposed branch
mapping distance by replicating previous results. We are able to extract
semantically meaningful matchings of features, comparable to those found
earlier [LWL∗20, PVDT21] from the branch mappings for both datasets (see App.
H (supp. material) for a direct comparison). Visualizations of the matched
features are shown in Figure 5, indicating that our distance measure is useful
for tracking applications in topology-based visualization.

##  6 Conclusion and Outlook

In this paper, we presented a novel variant of edit distances that is tailored
specifically to matching branches of merge trees. We provided a formal
definition and analysis of metric properties as well as an algorithm and
implementation. We showed that it is as expressive as previous approaches on
practical datasets and that it can improve the quality of the matching and
distance measure significantly on datasets containing specific structures. We
also discussed limitations of the new method, them being its higher complexity
and the fact that it is not a metric on merge trees, which does, however, not
influence its utility for the provided tasks. In the context of our
classification, we have described an edit distance-based method that works on
merge trees and uses global properties. However, this method does so in a very
specific and restricted way, which we now discuss together with options for
less restrictive methods and future work.

Figure 6: A heatmap of the distance matrix for all pairs of the first 225 time
steps of the vortex street dataset (full matrix cf. supp. material, App. H),
clearly indicating a period/half-period 75/37.

#### Other Branch Decomposition-Independent Methods.

A restriction we used was to only map _branches_. We could generalize this to
arbitrary _paths_ of a merge tree. As branches are paths, this would just
extend the concept of branch mappings by again increasing the search space.
Such _path mappings_ would actually be computable in the same time and space
bounds. In future work, we want to investigate the formal foundations of path
mappings.

Another restriction is that the new distance corresponds to the 1-degree edit
distance in the classic setting. We also want to consider adaptions of
constrained edit mappings, alignments, the general edit distance or even
unrooted versions of those. For these options, we have to find suitable
definitions and study their complexity to see which of these options are
applicable in practice.

#### Other Applications.

Furthermore, as hinted in Section 4.4, we plan to integrate branch mappings
(and maybe path mappings) into the alignment framework introduced in [LWL∗20]
(which is definitely possible) and investigate the possibility of combining it
with the geodesic/barycenter methods introduced in [PVDT21]. The latter seems
more likely to be possible for certain variants of path mappings which we
believe to be a metric, since the normalization step from [PVDT21] seems hard
to apply to non-fixed branch decompositions and barycenter computation could
be hindered by the missing triangle inequality. A very typical application of
distance measures for scalar fields that we have not studied in this paper is
symmetry or self-similarity detection. As the memoization table computed by
the algorithm includes distances for all subtrees of both input trees, it is
possible to use it to find substructures of high similarity by applying
methods similar to those from [SSW14]. We aim to implement them in future
work, too. Furthermore, we plan to investigate if similar distances can be
defined for contour trees instead of merge trees. Hurdles to overcome here
would be, for example, that paths in contour trees are not necessarily
monotone, and by restricting to monotone branches, the impact of saddle-swap
instabilities increase significantly.

#### Parallel Implementation.

For a more efficient implementation, we want to look deeper into optimization
options and also develop a parallel implementation of our algorithm. This
could lead to a significantly improved performance, as the branching factor in
the $\mathcal{O}(n^{4})$-sized search space is high, which (intuitively)
should lead to high parallelization potential.

## References

  * [BDFL16] Bauer U., Di Fabio B., Landi C.:  An edit distance for Reeb graphs.  In _Proceedings of the Eurographics 2016 Workshop on 3D Object Retrieval_ (Goslar Germany, Germany, 2016), 3DOR ’16, Eurographics Association, pp. 27–34.  doi:10.2312/3dor.20161084.
  * [BGW13] Bauer U., Ge X., Wang Y.:  Measuring distance between Reeb graphs.  _Proceedings of the Annual Symposium on Computational Geometry_ (07 2013).  doi:10.1145/2582112.2582169.
  * [Bil05] Bille P.:  A survey on tree edit distance and related problems.  _Theoretical Computer Science 337_ , 1-3 (2005), 217–239.  doi:10.1016/j.tcs.2004.12.030.
  * [BWP∗10] Bremer P.-T., Weber G., Pascucci V., Day M., Bell J.:  Analyzing and tracking burning structures in lean premixed hydrogen flames.  _IEEE Transactions on Visualization and Computer Graphics 16_ , 2 (Mar. 2010), 248–260.  doi:10.1109/tvcg.2009.69.
  * [BYM∗14] Beketayev K., Yeliussizov D., Morozov D., Weber G. H., Hamann B.:  Measuring the distance between merge trees.  In _Topological Methods in Data Analysis and Visualization III, Theory, Algorithms, and Applications_ , Bremer P., Hotz I., Pascucci V., Peikert R., (Eds.). Springer, 2014, pp. 151–165.  doi:10.1007/978-3-319-04099-8_10.
  * [CEH07] Cohen-Steiner D., Edelsbrunner H., Harer J.:  Stability of persistence diagrams.  _Discret. Comput. Geom. 37_ , 1 (2007), 103–120.  doi:10.1007/s00454-006-1276-5.
  * [CO17] Carrière M., Oudot S.:  Local equivalence and intrinsic metrics between reeb graphs.  In _33rd International Symposium on Computational Geometry, SoCG 2017, July 4-7, 2017, Brisbane, Australia_ (2017), Aronov B., Katz M. J., (Eds.), vol. 77 of _LIPIcs_ , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 25:1–25:15.  doi:10.4230/LIPIcs.SoCG.2017.25.
  * [CSEHM10] Cohen-Steiner D., Edelsbrunner H., Harer J., Mileyko Y.:  Lipschitz functions have lp-stable persistence.  _Foundations of Computational Mathematics 10_ , 2 (2010), 127–139.  doi:10.1007/s10208-010-9060-6.
  * [DG18] Dudek B., Gawrychowski P.:  Edit distance between unrooted trees in cubic time.  In _45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic_ (2018), Chatzigiannakis I., Kaklamanis C., Marx D., Sannella D., (Eds.), vol. 107 of _LIPIcs_ , Schloss Dagstuhl - Leibniz-Zentrum für Informatik, pp. 45:1–45:14.  doi:10.4230/LIPIcs.ICALP.2018.45.
  * [DMRW07] Demaine E. D., Mozes S., Rossman B., Weimann O.:  An optimal decomposition algorithm for tree edit distance.  In _Automata, Languages and Programming, 34th International Colloquium, ICALP 2007, Wroclaw, Poland, July 9-13, 2007, Proceedings_ (2007), Arge L., Cachin C., Jurdzinski T., Tarlecki A., (Eds.), vol. 4596 of _Lecture Notes in Computer Science_ , Springer, pp. 146–157.  doi:10.1007/978-3-540-73420-8\\_15.
  * [EH10] Edelsbrunner H., Harer J.:  _Computational Topology - an Introduction_.  American Mathematical Society, 2010.  URL: http://www.ams.org/bookstore-getitem/item=MBK-69.
  * [EHMP04] Edelsbrunner H., Harer J., Mascarenhas A., Pascucci V.:  Time-varying reeb graphs for continuous space-time data.  In _Proceedings of the Twentieth Annual Symposium on Computational Geometry_ (New York, NY, USA, 2004), SCG ’04, Association for Computing Machinery, p. 366–372.  doi:10.1145/997817.997872.
  * [ELZ00] Edelsbrunner H., Letscher D., Zomorodian A.:  Topological persistence and simplification.  In _41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12-14 November 2000, Redondo Beach, California, USA_ (2000), IEEE Computer Society, pp. 454–463.  doi:10.1109/SFCS.2000.892133.
  * [GST14] Günther D., Salmon J., Tierny J.:  Mandatory critical points of 2d uncertain scalar fields.  _Comput. Graph. Forum 33_ , 3 (2014), 31–40.  doi:10.1111/cgf.12359.
  * [HLH∗16] Heine C., Leitte H., Hlawitschka M., Iuricich F., De Floriani L., Scheuermann G., Garth C.:  A survey of topology-based methods in visualization.  _Computer Graphics Forum 35_ (06 2016), 643–667.  doi:10.1111/cgf.12933.
  * [JWZ94] Jiang T., Wang L., Zhang K.:  Alignment of trees - an alternative to tree edit.  In _Combinatorial Pattern Matching, 5th Annual Symposium, CPM 94, Asilomar, California, USA, June 5-8, 1994, Proceedings_ (1994), Crochemore M., Gusfield D., (Eds.), vol. 807 of _Lecture Notes in Computer Science_ , Springer, pp. 75–86.  doi:10.1007/3-540-58094-8\\_7.
  * [Kra10] Kraus M.:  Visualization of uncertain contour trees.  In _IMAGAPP 2010 - Proceedings of the International Conference on Imaging Theory and Applications and IVAPP 2010 - Proceedings of the International Conference on Information Visualization Theory and Applications, Angers, France, May 17 - 21, 2010_ (2010), Richard P., Braz J., (Eds.), INSTICC Press, pp. 132–139.  doi:https://doi.org/10.5220/0002817201320139.
  * [LGW∗21] Lohfink A. P., Gartzky F., Wetzels F., Vollmer L., Garth C.:  Time-varying fuzzy contour trees.  In _2021 IEEE Visualization Conference, IEEE VIS 2021 - Short Papers, New Orleans, LA, USA, October 24-29, 2021_ (2021), IEEE, pp. 86–90.  doi:10.1109/VIS49827.2021.9623286.
  * [LWL∗20] Lohfink A. P., Wetzels F., Lukasczyk J., Weber G. H., Garth C.:  Fuzzy contour trees: Alignment and joint layout of multiple contour trees.  _Comput. Graph. Forum 39_ , 3 (2020), 343–355.  doi:10.1111/cgf.13985.
  * [LWM∗17] Lukasczyk J., Weber G., Maciejewski R., Garth C., Leitte H.:  Dynamic nested tracking graphs.  _Computer Graphics Forum 36_ , 3 (2017), 12–22.  doi:10.1111/cgf.13164.
  * [MBW13] Morozov D., Beketayev K., Weber G.:  Interleaving distance between merge trees.  _Discrete and Computational Geometry 49_ , 22-45 (2013), 52.
  * [MW13] Morozov D., Weber G. H.:  Distributed merge trees.  In _ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming, PPoPP ’13, Shenzhen, China, February 23-27, 2013_ (2013), Nicolau A., Shen X., Amarasinghe S. P., Vuduc R. W., (Eds.), ACM, pp. 93–102.  doi:10.1145/2442516.2442526.
  * [NTN15] Narayanan V., Thomas D. M., Natarajan V.:  Distance between extremum graphs.  In _2015 IEEE Pacific Visualization Symposium, PacificVis 2015, Hangzhou, China, April 14-17, 2015_ (2015), Liu S., Scheuermann G., Takahashi S., (Eds.), IEEE Computer Society, pp. 263–270.  doi:10.1109/PACIFICVIS.2015.7156386.
  * [OHW∗17] Oesterling P., Heine C., Weber G. H., Morozov D., Scheuermann G.:  Computing and visualizing time-varying merge trees for high-dimensional data.  In _Mathematics and Visualization_. Springer International Publishing, 2017, pp. 87–101.  doi:10.1007/978-3-319-44684-4_5.
  * [Pop04] Popinet S.:  Free computational fluid dynamics.  _ClusterWorld 2_ , 6 (2004).  URL: http://gfs.sf.net/.
  * [PVDT21] Pont M., Vidal J., Delon J., Tierny J.:  Wasserstein distances, geodesics and barycenters of merge trees.  _IEEE Transactions on Visualization and Computer Graphics_ (2021), 1–1.  doi:10.1109/TVCG.2021.3114839.
  * [RSL20] Rieck B., Sadlo F., Leitte H.:  Hierarchies and ranks for persistence pairs.  In _Topological Methods in Data Analysis and Visualization V: Theory, Algorithms, and Applications_ (02 2020).  doi:https://doi.org/10.1007/978-3-030-43036-8_1.
  * [SAL∗07] Squillacote A. H., Ahrens J., Law C., Geveci B., Moreland K., King B.:  _The paraview guide_ , vol. 366.  Kitware Clifton Park, NY, 2007.
  * [Sel77] Selkow S. M.:  The tree-to-tree editing problem.  _Inf. Process. Lett. 6_ , 6 (1977), 184–186.  doi:10.1016/0020-0190(77)90064-3.
  * [SGL∗16] Shu Q., Guo H., Liang J., Che L., Liu J., Yuan X.:  Ensemblegraph: Interactive visual analysis of spatiotemporal behaviors in ensemble simulation data.  In _2016 IEEE Pacific Visualization Symposium, PacificVis 2016, Taipei, Taiwan, April 19-22, 2016_ (2016), Hansen C., Viola I., Yuan X., (Eds.), IEEE Computer Society, pp. 56–63.  doi:10.1109/PACIFICVIS.2016.7465251.
  * [SHD∗20] Schnorr A., Helmrich D. N., Denker D., Kuhlen T. W., Hentschel B.:  Feature tracking by two-step optimization.  _IEEE Trans. Vis. Comput. Graph. 26_ , 6 (2020), 2219–2233.  doi:10.1109/TVCG.2018.2883630.
  * [SMKN20] Sridharamurthy R., Masood T. B., Kamakshidasan A., Natarajan V.:  Edit distance between merge trees.  _IEEE Trans. Vis. Comput. Graph. 26_ , 3 (2020), 1518–1531.  doi:10.1109/TVCG.2018.2873612.
  * [SMP15] Silva V., Munch E., Patel A.:  Categorified Reeb graphs.  _Discrete and Computational Geometry 55_ (01 2015).  doi:10.1007/s00454-016-9763-9.
  * [SN21] Sridharamurthy R., Natarajan V.:  Comparative analysis of merge trees using local tree edit distance.  _IEEE Transactions on Visualization and Computer Graphics_ (2021), 1–1.  doi:10.1109/TVCG.2021.3122176.
  * [SSW14] Saikia H., Seidel H., Weinkauf T.:  Extended branch decomposition graphs: Structural comparison of scalar data.  _Comput. Graph. Forum 33_ , 3 (2014), 41–50.  doi:10.1111/cgf.12360.
  * [SW17] Saikia H., Weinkauf T.:  Global feature tracking and similarity estimation in time-dependent scalar fields.  _Comput. Graph. Forum 36_ , 3 (2017), 1–11.  doi:10.1111/cgf.13163.
  * [Tai79] Tai K.:  The tree-to-tree correction problem.  _J. ACM 26_ , 3 (1979), 422–433.  doi:10.1145/322139.322143.
  * [TFL∗18] Tierny J., Favelier G., Levine J. A., Gueunet C., Michaux M.:  The topology toolkit.  _IEEE Trans. Vis. Comput. Graph. 24_ , 1 (2018), 832–842.  doi:10.1109/TVCG.2017.2743938.
  * [TMMH14] Turner K., Mileyko Y., Mukherjee S., Harer J.:  Fréchet means for distributions of persistence diagrams.  _Discret. Comput. Geom. 52_ , 1 (2014), 44–70.  doi:10.1007/s00454-014-9604-7.
  * [TN11] Thomas D. M., Natarajan V.:  Symmetry in scalar field topology.  _IEEE Trans. Vis. Comput. Graph. 17_ , 12 (2011), 2035–2044.  doi:10.1109/TVCG.2011.236.
  * [WLG21] Wetzels F., Leitte H., Garth C.:  Branch decomposition-independent edit distances (supplementary source code).  https://github.com/scivislab/bdi-ed, 2021.
  * [WN08] Whalen D., Norman M. L.:  Competition data set and description, in 2008 ieee visualization design contest, 2008.  URL: http://vis.computer.org/VisWeek2008/vis/contests.html.
  * [WT10] Weinkauf T., Theisel H.:  Streak lines as tangent curves of a derived vector field.  _IEEE Transactions on Visualization and Computer Graphics (Proceedings Visualization 2010) 16_ , 6 (November - December 2010), 1225–1234.  URL: http://tinoweinkauf.net/.
  * [WZ13] Wu K., Zhang S.:  A contour tree based visualization for exploring data with uncertainty.  _International Journal for Uncertainty Quantification 3_ , 3 (2013).  doi:https://doi.org/10.1615/INT.J.UNCERTAINTYQUANTIFICATION.2012003956.
  * [YMS∗21] Yan L., Masood T. B., Sridharamurthy R., Rasheed F., Natarajan V., Hotz I., Wang B.:  Scalar field comparison with topological descriptors: Properties and applications for scientific visualization.  _Comput. Graph. Forum 40_ , 3 (2021), 599–633.  doi:10.1111/cgf.14331.
  * [YWM∗20] Yan L., Wang Y., Munch E., Gasparovic E., Wang B.:  A structural average of labeled merge trees for uncertainty visualization.  _IEEE Trans. Vis. Comput. Graph. 26_ , 1 (2020), 832–842.  doi:10.1109/TVCG.2019.2934242.
  * [Zha96] Zhang K.:  A constrained edit distance between unordered labeled trees.  _Algorithmica 15_ , 3 (1996), 205–222.  doi:10.1007/BF01975866.
  * [ZJ94] Zhang K., Jiang T.:  Some MAX snp-hard results concerning unordered labeled trees.  _Inf. Process. Lett. 49_ , 5 (1994), 249–254.  doi:10.1016/0020-0190(94)90062-0.
  * [ZSS92] Zhang K., Statman R., Shasha D. E.:  On the editing distance between unordered labeled trees.  _Inf. Process. Lett. 42_ , 3 (1992), 133–139.  doi:10.1016/0020-0190(92)90136-J.