text:
\section{Interlevel-set Persistence}
\label{sec:appx:interlevelset}

In this section, we describe another formulation of persistent homology which is also closely related to the Reeb graph.
In particular, this construction has implications for the relationship between the Reeb graph distances and the ungraded bottleneck distance.
These ideas come from taking a categorical viewpoint of persistence; we direct the interested reader to \cite{Riehl2017} for an excellent introduction to the category theory basics.
In this section, we largely follow notation from \cite{Bjerkevik2021}.

Let $\ensuremath{\mathbf{Int}}$ be the poset category of connected, open intervals $I = (a,b)$ with a morphism $I \to J$ iff $I \subseteq J$.
Let $\ensuremath{\overline{\Int}}$ be the same setup with closed intervals $[a,b]$ instead.
Note that either of these constructions can also be thought of as a subcategory of $(\mathbb{R}^{op} \times \mathbb{R})$ where  morphisms are given by $\leq$ in $\mathbb{R}$, and $\geq$ in $\mathbb{R}^{op}$.
In the case of $\ensuremath{\mathbf{Int}}$, we have the pairs $(a,b) \in \mathbb{R}^{op} \times \mathbb{R}$ where $a < b$, and for $\ensuremath{\overline{\Int}}$ we allow $a \leq b$.

Certain special subsets of $\ensuremath{\overline{\Int}}$ are called blocks.
\begin{definition}
\label{def:blocks}
A block is a subset of $\ensuremath{\overline{\Int}}$ of one of the following forms, where $a,b \in \mathbb{R} \cup \{\pm \infty\}$
\begin{itemize}
    \item $[a,b]_{BL} =
    \{ (c,d) \in \ensuremath{\overline{\Int}} \mid c \leq b, d \geq a \}$
    \item $[a,b)_{BL} =
    \{ (c,d) \in \ensuremath{\overline{\Int}} \mid a \leq d < b \}$
    \item $(a,b]_{BL} =
    \{ (c,d) \in \ensuremath{\overline{\Int}} \mid a < c \leq b \}$
    \item $(a,b)_{BL} =
    \{ (c,d) \in \ensuremath{\overline{\Int}} \mid a < c, d < b \}$
\end{itemize}
\end{definition}
Since each interval $[a,b] \in \ensuremath{\overline{\Int}}$ can be viewed as a point in the plane, we can picture the set of possible blocks as in Fig.~\ref{fig:BjerkevikBlocks}.

\begin{figure}%
    \centering
    \includegraphics[width=\textwidth]{figures/bjerkevikBlocks.pdf}
    \caption{Blocks of an interlevel-set persistence module, as given in \ref{def:blocks}.
    From left to right, these are $[a,b]_{BL}$, $[a,b)_{BL}$, $(a,b]_{BL}$, and $(a,b)_{BL}$. }
    \label{fig:BjerkevikBlocks}
\end{figure}

Let $\Vec$ be the category of finite dimensional vector spaces over a field $k$.
Given a Reeb graph $(X,f)$, the $n$-dimensional interlevel-set persistence module   is a functor $F_n:\ensuremath{\overline{\Int}} \to \Vec$ given by $I \mapsto H_n(f^{-1}(I))$.
In the case of constructible data as we are assuming for our Reeb graphs, then $F_n$ is always block decomposable, meaning that it can be written as the direct sum of modules supported on blocks.
In the case of Reeb graphs, the interlevel-set information is contained in the $0$-dimensional portion, $F_0$.

Prior work~\cite{Bjerkevik2016a, Botnan2018} studies these full representations from a theoretical point of view, including understanding analogues of interleavings and bottleneck distances.  However, for this paper we are interested in the projection to the diagonal and then simply treating these blocks as their interval in $\mathbb{R}$.
Tellingly, if you simply drop the $BL$ subscript notation in Def.~\ref{def:blocks}, we get the associated interval in $\mathbb{R}$.
Then, we can define the interlevel-set persistence bottleneck as the ungraded bottleneck distance (Def.~\ref{def:UngradedBottleneckDistance}) between these $\mathbb{R}$-intervals.\footnote{This notation is written as
$\mathcal{B}_{\mathrm{diag}}
(C_{\mathbf{vec}}^R,C_{\mathbf{vec}}^{R'})$
in \cite{Bjerkevik2021}.
}

However, following this formalism, we find that the result is a distance which at first blush looks similar to the graded bottleneck distance between the extended persistence diagrams, but actually allows matching between points representing different kinds of structures.
Specifically, the ``types'' of points as labeled in extended persistence terminology align with the different kinds of endpoints of the four types of interval representations: $(-,-)$ for $\mathrm{Ext}_1$, $[-,-]$ for $\mathrm{Ext}_0$, $[-,-)$ for $\mathrm{Ord}_0$, and $(-,-]$ for $\mathrm{Rel}_1$.
However, the bottleneck distance on the diagonal projection of the interlevel-set projection loses the endpoint information, resulting in the ungraded bottleneck distance $d_b$.

Consider the example of Fig.~\ref{fig:interlevelset_example}.
In this case, the two Reeb graphs each have the same, single point in the $\mathrm{Ext}_0$ diagram; and one point in the $\mathrm{Rel}_1$ and $\mathrm{Ext}_1$ diagrams respectively which is nearly identical.
The result is that the interlevel-set blocks for the first graph are $\{[a_1,a_5]_{BL}, (a_2,a_4)_{BL}\}$, and for the second they are $\{[a_1,a_5]_{BL}, (a_2,a_3]_{BL}\}$.
For this example, then, we have
\begin{equation*}
    \tfrac12(a_3-a_2) = d_I(\mathcal{R}_f,\mathcal{R}_g) \leq d_B(\mathcal{R}_f,\mathcal{R}_g) = \tfrac{1}{2}(a_4-a_2)
\end{equation*}
but
\begin{equation*}
    d_{Bjerk}(F_0^f,F_0^g) = d_b(\mathcal{R}_f,\mathcal{R}_g) = (a_4-a_3) \leq d_I \leq d_B,
\end{equation*}
where $d_{Bjerk}(F_0^f,F_0^g)$ denotes the bottleneck distance on the diagonal projection of interlevel-set modules studied in \cite{Bjerkevik2021}.

\begin{figure}
    \centering
    \includegraphics[width = \textwidth]{figures/levelsetExample.pdf}
    \caption{\textbf{(upper-left)} Two Reeb graphs accompanied with their persistence diagrams \textbf{(upper-right)}. Corresponding blocks \textbf{(bottom)} are shown. Blue represents points of the 2-dimensional vector space while purple represents points of the 1-dimensional vector space.}
    \label{fig:interlevelset_example}
\end{figure}

\section{Multiple Connected Components}\label{sec:appx:multipleConnected}
In the preceeding work, we have assumed for that our Reeb graphs are connected. Furthermore, path componenet sensitivity states that Reeb graph metrics attain a value of $+\infty$ if the Reeb graphs have different numbers of connected components. However, computing the distance between two Reeb graphs with $n>1$ path-connected componenets is, in general, still possible. Yet, this point is often not expanded upon in the literature. Here we adopt the convention that the distance between these Reeb graphs is minimum distance over all possible matchings between the path-connected components of the Reeb graphs.

Suppose we have two Reeb graphs $\mathcal{R}_f,\mathcal{R}_g$, both with $n>1$ path-connected components and suppose we want to compute the value of a Reeb graph metric $d$ between $\mathcal{R}_f$ and $\mathcal{R}_g$. Let $\pi_0(\mathcal{R}_f)$ denote the set of path-connected components of $\mathcal{R}_f$ and let $\mathcal{R}_f^i$ denote the Reeb graph on the $i^{th}$ path-connected component. Then we define the distance $d$ between $\mathcal{R}_f,\mathcal{R}_g$ to be
\[d(\mathcal{R}_f,\mathcal{R}_g) = \min_{\sigma:\pi_0(\mathcal{R}_f) \to \pi_0(\mathcal{R}_g)}\max_i\big\{d(\mathcal{R}_f^i,\mathcal{R}_g^{\sigma(i)}\big\},\]
where we minimize over all possible bijections $\sigma: \pi_0(\mathcal{R}_f) \to \pi_0(\mathcal{R}_g)$ between the set of path-connected components.

When computing the bottleneck distance between Reeb graphs with multiple connected components, it is not necessary to adopt this convention since the persistence diagram of a Reeb graph is identical to the union of the persistence diagrams defined on the individual path-connected components. Note that, however, this will be bounded above by the bottleneck distance that \emph{does} use this convention. That is,

\[d_B\Big(\bigcup_i\mathrm{ExDgm}^i(f),\bigcup_i\mathrm{ExDgm}^i(g)\Big) \leq \min_{\sigma:\pi_0(\mathcal{R}_f) \to \pi_0(\mathcal{R}_g)}\max_i\big\{d_B(\mathcal{R}_f^i,\mathcal{R}_g^{\sigma(i)}\big\},\]
where $\mathrm{ExDgm}^i(f)$ refers to the full extended persistence diagram defined on the $i^{th}$ path-connected componenet of $\mathcal{R}_f$.

It is important to note that our goal here is to make the bottleneck distance measure features as similarly as the Reeb graph metrics due. In the end, our discrimintavity bounds still hold -- regardless of how close we construct the bottleneck distance to act similarly to the Reeb graph metric.

\section{Truncated Interleaving Distance Properties}\label{sec:appx:truncatedProperties}
The strong equivalence between the interleaving distance and truncated interleaving distance automatically leads us to several properties that the truncated interleaving distance exhibits. We state these properties without proof.

\begin{proposition}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two constructible Reeb graphs defined on the same space ${\mathbb X}$. Then for a fixed $m \in [0,1)$, we have
\[d^m_I(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{1}{1-m}||f-g||_{\infty}.\]
\end{proposition}

Since this is not quite stability, we are not guaranteed that the universal edit distance bounds the truncated interleaving distance for any fixed $m$. Ex.~\ref{example:globalMaxChange} shows an example of this.

\begin{corollary}
For a fixed $m\in[0,1)$, the truncated interleaving distance is isomorphism invariant.
\end{corollary}

\begin{corollary}\label{cor:truncated-interleaving-discrim}
For a fixed $m\in[0,1)$, the truncated interleaving distance is more discriminative than the graded bottleneck distance. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{9}{1-m}\cdot d^{m}_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{corollary}\label{cor:truncated-interleaving-discrim-ungraded}
For a fixed $m\in[0,1)$, the truncated interleaving distance is more discriminative than the ungraded bottleneck distance. That is
\[\db{}(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{2}{1-m}\cdot d^{m}_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{corollary}
For a fixed $m\in[0,1)$, the truncated interleaving distance is more discriminative than the graded bottleneck distance when the Reeb graphs are defined on simply connected domains. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{3}{1-m}\cdot d^{m}_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{proposition}[{\cite[Proposition~2.19]{Chambers2021}}]
For a fixed $m\in[0,1)$, the truncated interleaving distance is path component sensitive.
\end{proposition}
\section{Basic Definitions}
\label{sec:basicDef}

\subsection{Scalar Fields and Reeb Graphs}

\begin{definition}
A \textbf{scalar field} (equivalently an \textbf{$\mathbb{R}$-space}) is a pair $({\mathbb X},f)$ where ${\mathbb X}$ is topological space and $f:{\mathbb X} \to \mathbb{R}$ is a continuous real-valued function.
\end{definition}

\begin{definition}\label{def:reebGraph}
We define an equivalence relation $\sim_f$ on ${\mathbb X}$ by stating that $x \sim_f y$ if $f(x) = f(y)= a$ and $x$ and $y$ both lie in the same connected component of the level-set $f^{-1}(a)$. We define ${\mathbb X}_f$ to be the quotient space ${\mathbb X} / \sim_f$ and define $\tilde{f}:{\mathbb X}_f \to \mathbb{R}$ to be the restriction of $f$ to the domain ${\mathbb X}_f$. The pair $\mathcal{R}_f := ({\mathbb X}_f,\tilde{f})$ is called the \textbf{Reeb Graph} of $({\mathbb X},f)$.
\end{definition}

We call the pre-image of a critical point $x$ a \textbf{critical fiber} of ${\mathbb X}$. We then call the pre-image of the set of points between two consecutive critical points a \textbf{non-critical fiber}. That is, if $a_i$ and $a_j$ are two critical points such that $a$ is not a critical point for all $a \in (a_i,a_j)$, then $f^{-1}(a)$ is a non-critical fiber, and both $f^{-1}(a_i)$ and $f^{-1}(a_j)$ are critical fibers.

Without sufficient restrictions on $({\mathbb X},f)$, it is possible to have Reeb graphs which are not actually graphs at all. For example, if ${\mathbb X}$ is the unit disk minus the origin and $f(x,y) = y$, the resulting Reeb graph will be non-Hausdorff. To avoid these situations, we introduce several different restrictions for the scalar field $({\mathbb X},f)$ so that it is well-behaved. Each distance we will define was originally created with very specific criteria meaning it is not always apparent for which scalar fields the theorems and definitions apply. In each individual section, we will be sure to define our Reeb graph metrics in the original language as to keep the setting as generalized as possible. When discussing various theorems for these metrics, we will, when possible, state how the restrictions on the spaces can coincide so that the theorems apply to all metrics at once. In addition, to simplify the discussion of these distances, we will assume that our topological spaces are path-connected. This, in general, does not affect the validity of the succeeding proofs or definitions; see Appx.~\ref{sec:appx:multipleConnected} for a discussion on the relationship between the number of path connected components and Reeb graph metrics.

\begin{definition}
\label{def:ConstructibleSpace}
We say that a scalar field $({\mathbb X},f)$ is \textbf{constructible} if it is homemorphic to a scalar field $(\hat{{\mathbb X}},\hat{f})$ which is has a finite set of critical points $\{ a_i\}_i$ and is constructed in the following way:
\begin{itemize}
    \item Each critical fiber $\mathbb{V}_i $ is a locally path-connected, compact space;
    \item Each non-critical fiber $\mathbb{E}_i$ is a locally path-connected, compact space;
    \item The space ${\mathbb X}$ is homeomorphic to the disjoint union of the spaces $\mathbb{V}_i\times \{a_i\}$ and $\mathbb{E}_i\times [a_i, a_{i+1}]$ together with     continuous attaching maps from each non-critical fiber  $\mathbb{E}_i$ to the critical fibers  $\mathbb{V}_i$ and  $\mathbb{V}_{i+1}$.
    \item The function $f$ is defined by projection onto the second coordinate.
\end{itemize}
A Reeb graph arising from a constructible scalar field is known as a \textbf{constructible Reeb graph}.
\end{definition}

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/ConstructibleR-Space.pdf}
    \caption{An example of a constructible $\mathbb{R}$-space with notation following Def.~\ref{def:ConstructibleSpace}. Figure from \cite{deSilva2016}.}
    \label{fig:ConstructibleSpace}
\end{figure}

See Fig.~\ref{fig:ConstructibleSpace} for an example of this notation.
Constructibility guarantees that the Reeb graph will indeed by a finite graph by restricting the number of critical points and guaranteeing that the fibers between critical points have a predictable, cylindrical structure.

Another common niceness condition seen in the literature is is that of \textbf{tameness}, which essentially guarantees that there is a way to partition the function into critical and non-critical fibers based on information about the homology.

\begin{definition}\label{def:tame}
We say that a function $f:{\mathbb X} \to \mathbb{R}$, where ${\mathbb X}$ is a topological space, is \textbf{tame} if if there is a finite partition $-\infty = a_{-1} < min(f) = a_0 < \ldots < a_N = \max f < a_{N+1} = \infty$ such that the homology groups of the sublevel-sets and superlevel-sets do not change for between two points of a non-critical fiber. That is, for $s,t \in [a_i,a_{i+1})$ with $s < t$, the homomorphism $H_p({\mathbb X}_{\leq s}) \rightarrow H_p({\mathbb X}_{\leq t})$ induced by the inclusion $f^{-1}(-\infty,s] \subseteq f^{-1}(-\infty,t]$ is an isomorphism, and similarly for $s,t \in (a_i,a_{i+1}]$, the homomorphism $H_p({\mathbb X}_{\geq t}) \rightarrow H_p({\mathbb X}_{\geq t})$ induced by the inclusion $f^{-1}[t,\infty) \subseteq f^{-1}[s,\infty)$ is an isomorphism. A scalar $({\mathbb X},f)$ where $f$ is tame is called a \textbf{tame scalar field}, and the Reeb graph $\mathcal{R}_f$ arising from the scalar field as a \textbf{tame Reeb graph}.
\end{definition}

Note that any constructible function is tame.
Both of these conditions can be viewed as encapsulating some portion of the behavior of a Morse function, from which the original Reeb graph ideas originated \cite{Reeb1946}.

\begin{definition}
A \textbf{Morse function} is a smooth function $f:{\mathbb X} \to \mathbb{R}$ defined on a manifold ${\mathbb X}$ such that all critical points are non-degenerate. We say that a Morse function is \textbf{simple} if all critical points have distinct function values.
\end{definition}

Since, in practice, we would like to be able to compute or approximate these distances, is it common that our metrics are defined for spaces which are already packaged for these scenarios -- such as \textbf{triangulable} domains equipped with \textbf{piecewise linear functions}.

\begin{definition}
A \textbf{triangulation} of a space ${\mathbb X}$ is a simplicial complex $K$ paired with a homeomorphism from the underlying space of $K$ to the space ${\mathbb X}$. We say that a space ${\mathbb X}$ is \textbf{triangulable} if there exists a triangulation for ${\mathbb X}$. A \textbf{piecewise linear (PL) function} $f$ is a function defined on a triangulated space ${\mathbb X}$ such that $f(x) = \sum_i b_i(x)f(u_i)$, where $u_i$ are the vertices of ${\mathbb X}$ and $b_i(x)$ are the barycentric coordinates of $x$. If ${\mathbb X}$ is a compact, triangulable space and $f$ is a PL function, then we call the pair $({\mathbb X},f)$ a \textbf{piecewise linear (PL) scalar field}, and the Reeb graph $\mathcal{R}_f$ arising from this scalar field a \textbf{piecewise linear (PL) Reeb graph}.
\end{definition}

To reconcile these multiple definitions together, we note a few examples.
\begin{enumerate}
    \item A Morse function $f$ defined on a compact 2-manifold without boundary ${\mathbb X}$ is an example of both a constructible and tame scalar field.
    \item A PL function $f$ defined on a compact 2-manifold without boundary ${\mathbb X}$ is an example of a constructible, tame, and PL scalar field since we are guaranteed for ${\mathbb X}$ to be triangulable.
    \item A PL function $f$ defined on a compact polyhedra ${\mathbb X}$ is an example of a tame and  constructible scalar field.
\end{enumerate}

We refer the reader to \cite{DeyWang2021} for a more in-depth treatment of tame functions, triangulations, and PL functions; see \cite{deSilva2016} for details on constructibility.

For conceptual ease, we find it best to provide examples which are both illuminating and accessible. To this end, we often choose examples where the scalar field is defined on a compact, 2-manifold and the equipped function is Morse. Furthermore, we believe it best to visualize our scalar fields as having complicated manifolds whose functions are simply height functions, rather than the alternative which would be to construct more complicated functions on simpler domains.

In each distance we discuss, the restrictions we apply to the scalar field result in a Reeb graph that is a well-defined topological graph with discrete fibers, whose vertices are all homological critical values. Any graph which breaks these conditions is not a Reeb graph according to our definitions.
More specifically, the data of a Reeb graph in this setting can be presented as a \textbf{labeled multigraphs}.

\begin{definition}
A \textbf{labeled multigraph} is a triple $G = (V,E,\ell)$, where $V$ is a vertex set, $E$ is an edge multiset, and $l$ is a function $\ell: V \to \mathcal{L}$, with $\mathcal{L}$ being some label set.
\end{definition}

In the Reeb graph case, the vertex set $V$ is the set of critical points of the Reeb graph, the edge set $E$ is the set of non-critical fibers between critical points, and the labeling function $l$ is precisely $\tilde{f}$ -- making the label set $\mathcal{L}$ the real line $\mathbb{R}$. We can then define an equivalence between two Reeb graphs based on the definition of \textbf{labeled multigraph isomorphism}.

\begin{definition}\label{def:multigraphIsomoprhism}
We say that two labeled multigraphs $G_1 = (V_1,E_1,\ell_1)$, $G_2 = (V_2,E_2,\ell_2)$ are \textbf{isomorphic} if there exists a bijection $\alpha: V_1 \to V_2$ and a bijection $\beta: E_1 \to E_2$ such that
\begin{enumerate}[label=(\arabic*)]
    \item $e = e(v,v')$ is in $E_1$ if and only if $\beta(e) = e(\alpha(v),\alpha(v'))$ is in $E_2$ and
    \item for every $v \in V_1$, $\ell_1(v) = \ell_2(\alpha(v))$.
\end{enumerate}
\end{definition}

In general, however, we will consider our Reeb graphs as being topological spaces rather than simply graphs. In these cases, we have an equivalent definition for isomorphism between two Reeb graphs.

\begin{definition}\label{def:functionPreservingReebGraphIso}
We say that a continuous map $\alpha: \mathcal{R}_f \to \mathcal{R}_g$ is a \textbf{function preserving map} if $\tilde{f} = \tilde{g} \circ \alpha$ where $\tilde{f}$ and $\tilde{g}$ are the induced maps on the Reeb graphs.
If there exists a function preserving map which is also a homeomorphism, we say that $\mathcal{R}_g$ and $\mathcal{R}_f$ are \textbf{Reeb graph isomorphic}.
\end{definition}

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/GraphIsoNonRGIso.pdf}
    \caption{Two Reeb graphs where the function value of the nodes is indicated by height. The labels on the nodes themselves correspond to the labeling which shows that these two Reeb graphs are isomorphic \emph{as graphs}. However, since the there is no map between these two Reeb graphs which is an isomorphism and also function preserving, they are \emph{not} Reeb graph isomorphic. }
    \label{fig:graphIsoNonRGIso}
\end{figure}

Without condition \textit{(2)} for Def.~\ref{def:multigraphIsomoprhism},  the definition reduces to simply a (multi)graph isomorphism.
Fig.~\ref{fig:graphIsoNonRGIso} depicts an example of two Reeb graphs that are graph isomorphic but not Reeb graph isomorphic.
In Sec.~\ref{sec:interleaving}, we will see yet another equivalent definition of Reeb graph isomorphism using the category theory definition of a Reeb graph known as a \textbf{cosheaf}.

\subsection{Extended Persistence}

\begin{figure}
    \centering
    \includegraphics[width=1\textwidth]{CriticalPointExampleAlt.pdf}
    \caption{\textbf{(left)} A scalar field $({\mathbb X},f)$, where ${\mathbb X}$ is a compact 2-manifold without boundary and $f$ is a Morse function. \textbf{(center)} The Reeb graph $\mathcal{R}_f$ of the scalar field $({\mathbb X},f)$. \textbf{(right)} The extended persistence diagrams for the scalar field. Circles denote the points in $\mathrm{Ord}_0$, squares denote points in $\mathrm{Rel}_1$, triangles denote the points in $\mathrm{Ext}_1$, and stars denote the single point in $\mathrm{Ext}_0$.
    }
    \label{fig:surfaceForPersistence}
\end{figure}

While the Reeb graph studies the level-set topology of a scalar field, another common topological signature is the \textbf{persistence diagram} (and equivalently the \textbf{barcode}), which studies the sublevel-set topology. Given a scalar field (or its Reeb graph), we can imagine sweeping upwards in a linear fashion, keeping track of when particular features appear and disappear. \textbf{Persistence} intuitively captures the length of time that features of a scalar field (or other data sets \cite{Edelsbrunner2003b}) take to disappear once they have been introduced, and a persistence diagram plots this information in the form of a coordinate pair $(a,b)$, where $a$ is the \textbf{birth time} of the feature and $b$ is its death time.

Multiple distance metrics have been defined on persistence diagrams; the main ones utilized due to their theoretical properties linking the diagrams with the input data are the bottleneck distance and Wasserstein distance.
Here we provide the construction of the persistence diagram -- specifically the extended persistence diagram -- and in Sec.~\ref{sec:bottleneckDist} the definition of bottleneck distance. The bottleneck distance provides us with a good baseline for the comparison of the distances defined on Reeb graphs because 1) it can be efficiently computed, 2) it shares similar properties to the Reeb graph metrics, and 3) it has already been heavily utilized for comparison of persistence diagrams; see \cite{Yan2021} for a survey using bottleneck distance as a discriminative baseline.

Persistence diagrams are often defined directly on the scalar field, however \textbf{we will define our persistence diagrams directly on the Reeb graphs themselves} to be in line with the literature of Reeb graph and persistence diagram metrics.
To do this, we simply leverage the fact that the Reeb graph is itself a 1-dimensional scalar field.
We refer the reader to books on topological data analysis \cite{Oudot2015,DeyWang2021} for a more detailed overview of persistence diagrams defined on higher dimensional spaces and their corresponding distance metrics.

\subsubsection{Definition of extended persistence}
Let $({\mathbb X},f)$ be a tame scalar field with critical points $\{v_1,\ldots,v_k\}$. We define ${\mathbb X}_a := f^{-1}(-\infty,a]$ to be the \textbf{sublevel-set} of ${\mathbb X}$ at $a$. Now, let $\{b_0,\ldots,b_k\}$ be a set of real numbers such that
\[
b_0 < f(v_1) < b_1 < f(v_2) < \ldots < b_{k-1} < f(v_k) < b_k.
\]
This induces a sequence of nested subspaces
\[
\emptyset = {\mathbb X}_{b_0} \subset {\mathbb X}_{b_1} \subset \ldots \subset {\mathbb X}_{b_{k-1}} \subset {\mathbb X}_{b_k} = {\mathbb X},
\]
called a \textbf{filtration} of the scalar field $({\mathbb X},f)$. We can then associate each ${\mathbb X}_{b_i}$ with a corresponding homology group $H_n({\mathbb X}_{b_i})$ for a fixed dimension $n$ to obtain the sequence
\[
\emptyset = H_d({\mathbb X}_{b_0}) \rightarrow H_d({\mathbb X}_{b_1}) \rightarrow \ldots \rightarrow H_d({\mathbb X}_{b_{k-1}}) \rightarrow H_d({\mathbb X}_{b_{k}}),
\]
where each arrow between homology group represents the homomorphism
$h^{i,j}_d: H_d({\mathbb X}_{b_i}) \rightarrow H_d({\mathbb X}_{b_j})$
induced by the inclusion ${\mathbb X}_{b_i} \subset {\mathbb X}_{b_j}$.
Note that we have chosen these $\{b_0,\ldots,b_k\}$ to be specifically interleaved between the critical values of $f$ so that the homology (in some dimension) of the sequence changes at every iteration\footnote{The homology groups do not necessarily change, but the only possible places that these sublevel-sets have different topologies is when we pass over critical points. Choosing values that are not surrounding the critical points would cause our sequence to have multiple homology groups that are guaranteed to be repeated.}.

The elements of homology groups intuitively represent various $n$-dimensional holes in the surface. Elements of $H_0$ represent connected components and elements of $H_1$ represent closed loops. The Betti numbers corresponding to a particular topological space then simply count the number of elements. Thus, the $0$-dimensional Betti numbers tell us the number of connected components, while the $1$-dimensional Betti numbers tell us the number of loops, and so on.

\begin{definition}
The \textbf{$\bm{d^{th}}$-persistent homology groups} are the images of the homology group homomorphisms, $H^{i,j}_d : = \Im(h^{i,j}_d)$ and the \textbf{$\bm{d^{th}}$-persistent Betti numbers} are their corresponding ranks, $\beta^{i,j}_d = \mathsf{Rank}(H^{i,j}_d)$.
\end{definition}

The persistent Betti numbers now correspond to the number of $n$-dimensional holes present in a specific portions of the filtration. As we step through the filtration, the number of features (and thus the persistent Betti numbers) may change. The notion of \textbf{persistence} quantifies this change.

\begin{definition}
We say that a class $\alpha$ is \textbf{born} at $i$ if $\alpha \in H_d({\mathbb X}^i) - \Im(h^{i-1,i}_d$). We say that $\alpha$ \textbf{dies} at $j$ if $h^{i,j-1}_d(\alpha) \notin \Im(h^{i-1,j-1}_d(\alpha))$ but $h^{i,j}_d(\alpha) \in \Im(h^{i-1,j}_d(\alpha))$. The \textbf{persistence} of $\alpha$ is $f(v_j)-f(v_i)$. If $\alpha$ never dies, then we say that the persistence of $\alpha$ is $+\infty$.
\end{definition}

Low persistence features are often (but not always \cite{Bubenik2020}) attributed to \textit{noise} or \textit{insignificant} features of the data being studied, while high persistence features are often associated with \textit{significant} features.
Of course, what determines significant or insignificant features is dependent on the application domain and question being asked of the data. In any case, persistence allows us to scale our view of the data as we see fit. We can plot these persistent features in a scatter plot known as a \textbf{persistence diagram}.

\begin{definition}
The \textbf{$\bm{d^{th}}$-persistence diagram} of $f$, denoted as $\text{Dgm}_d(f)$, is a scatterplot of its persistent features that records each feature $\alpha$ of the $d^{th}$-persistent homology groups as a coordinate pair $(f(v_i),f(v_j))$, where $\alpha$ is born in ${\mathbb X}_i$ and dies entering ${\mathbb X}_j$, in the extended plane $\bar{\mathbb{R}}^2 := \mathbb{R}\cup\{+\infty\} \times \mathbb{R}\cup\{+\infty\}$. We call the ordered pair $((f(v_i),f(v_j))$ a \textbf{persistence pair}.
\end{definition}

The ordered pairs of a persistence diagram correspond directly to pairs of critical points in a Morse function, which in turn correspond to nodes in the Reeb graph. For example, index 0 critical points create connected components (0-dimensional homology classes) which are then destroyed by down-forks (saddles with two decreasing edges). However, it is possible that a class $\alpha$ is born at ${\mathbb X}_i$ and never dies, such as a cycle in a Reeb graph corresponding to a $1$-dimensional hole in the scalar field. Such classes are known as \textbf{essential} homology classes and are represented as $(f(v_i),+\infty)$ in the persistence diagram, where $f(v_i)$ is when the class is born.
We can immediately see that this can cause issues by considering two 1-cycles that are born at the same top function value of the loop.
These two cycles will be represented by two identical persistence pairs, even if the bottoms of the loops are at different function values.

To alleviate this, we can leverage Poincar\'{e} and Lefschetz duality to create a new sequence of homology groups where we begin and end with the trivial group \cite{Steiner2009}. This guarantees that each homology class that is born will also die at a finite value, replacing all the problematic points paired with $\infty$, and implying that each critical point in the Reeb graph will be matched with another critical point at least once.

Let ${\mathbb X}^a := f^{-1}[a,\infty)$ be the \textbf{superlevel-set} of ${\mathbb X}$ at $a$ and let $H_d({\mathbb X},{\mathbb X}^a)$ denote the relative homology group. From this, we can create a new sequence of homology groups
\begin{align*}
    0 = & H_d({\mathbb X}_{b_0}) \rightarrow H_d({\mathbb X}_{b_1}) \rightarrow \ldots \rightarrow H_d({\mathbb X}_{b_{k-1}}) \rightarrow H_d({\mathbb X}_{b_k}) \\
    = & H_d({\mathbb X},{\mathbb X}^{b_k}) \rightarrow H_d({\mathbb X},{\mathbb X}^{b_{k-1}}) \rightarrow \ldots \rightarrow H_d({\mathbb X},{\mathbb X}^{b_1}) \rightarrow H_d({\mathbb X},{\mathbb X}^{b_0}) = 0.
\end{align*}

This creates three different \textbf{classes} of points: those that are born and die in the upwards sweep (ordinary persistence points), those that are born and die in the downwards sweep (relative persistence points), and those that are born in the upwards sweep and die in the downwards sweep (extended persistence points). We denote the class of ordinary, relative, and extended points as $\text{Ord}_d(f)$, $\text{Rel}_d(f)$, and $\text{Ext}_d(f)$, respectively.

\begin{definition}
The \textbf{$\bm{d^{th}}$-extended persistence diagram} of $f$, denoted as $\text{ExDgm}_d(f)$, is the union of the persistence pairs contained in \textbf{classes} $\mathrm{Ord}_d(f)$, $\mathrm{Rel}_d(f)$, and $\mathrm{Ext}_d(f)$.
We can visualize the extended persistence diagram via a scatterplot that records each feature $\alpha$ of the $d^{th}$- extended persistent homology group as a coordinate pair $(f(v_i),f(v_j))$, where $\alpha$ is born in
$H_d({\mathbb X}_i)$ or $H_d({\mathbb X},{\mathbb X}^i)$ and dies entering $H_d({\mathbb X}_j)$ or $H_d({\mathbb X},{\mathbb X}^j)$, drawn as a point in $\mathbb{R}^2$.
We call the ordered pair $((f(v_i),f(v_j))$ an \textbf{extended persistence pair}.

Finally, we define the $\textbf{full extended persistence diagram}$ of $f$ as the union of the $d^{th}$-extended persistence diagrams for all dimensions $d$, and denote it as $\text{ExDgm}(f)$.

\end{definition}

Note that in this definition, points of the extended diagram can be both above and below the diagonal.
Preliminary results in \cite{agarwal2006} showed a pairing between all critical points of a 2-manifold while \cite{Steiner2009} extended this to general manifolds.
While the Reeb graph is \emph{not} a manifold, we are still guaranteed that each critical point will be matched with another.

Simple Morse functions defined on compact manifolds create Reeb graphs which are \textbf{generic}: each critical value is unique and no single critical point can be the birth and death of two separate events. This prevents critical points of the Reeb graph from belonging to two pairs in the persistence diagram. In most cases, genericness is not needed to prove the theorems in subsequent sections. However, just as we will provide examples which are Morse functions on compact manifolds for conceptual ease, our discussion will only deal with generic Reeb graphs as well.

Persistence diagrams defined directly from Reeb graphs only have four different classes of points in the full extended persistence diagram \cite{agarwal2006}: $\text{Ord}_0$, $\text{Ext}_0$, $\text{Rel}_1$, and $\text{Ext}_1$.
Below we provide a standard example of constructing this diagram and the process behind it.

\begin{example}
Fig.~\ref{fig:surfaceForPersistence}(left) shows a genus-2 surface embedded in $\mathbb{R}^3$ along with its Reeb graph (center). Fig.~\ref{fig:surfaceForPersistence}(right) shows the full extended persistence diagram for this Reeb graph. To find the persistence pairs, we begin by sweeping upwards and tracking the features which are born and destroyed.
Critical points $a_1$ and $a_2$ both create classes in $H_0$ by introducing new connected components in the sublevel-sets; $a_6$ and $a_8$ both create classes in $H_1$ by closing the cycles which started at $a_3$ and $a_5$, respectively. These two cycles are examples of \textbf{essential homology classes} and so will only be destroyed on the downwards sweep. We pair $a_2$ with $a_4$ since $a_4$ merges two connected components together.

Going downwards, $a_{10}$ destroys the class in $H_0$ created by $a_1$; $a_9$ creates a relative $H_1$ class which is destroyed at $a_7$; $a_3$ and $a_5$ destroy the classes in $H_1$ created by $a_6$ and $a_8$, respectively.
Thus, we can summarize the off-diagonal points of the diagram $\text{ExDgm}(f)$ as follows:
\begin{align*}
    \text{Ord}_0 & = \{(a_2,a_4)\} \\
    \text{Ext}_0 & = \{(a_0,a_{10})\} \\
    \text{Rel}_1 & = \{(a_9,a_7)\} \\
    \text{Ext}_1 & = \{(a_6,a_3),(a_8,a_5)\}
\end{align*}
Fig.~\ref{fig:surfaceForPersistence}(b) shows the full extended persistence diagram with accompanying legend.
\end{example}

\section{Bottleneck Distance}
\label{sec:bottleneckDist}

As the topological summary provided by the extended persistence diagram is a useful tool for describing the data encoded in a scalar field, it is natural for us to consider how we would compare two persistence diagrams to one another. The \textbf{bottleneck distance} provides us with such a device. While the bottleneck distance was originally defined in terms of ordinary persistence diagrams, \cite{Steiner2009} extended the results and definitions to extended persistence diagrams.

The idea behind bottleneck distance is to find a minimal cost matching between the points of the diagrams, where some nuance must be dealt with for dealing with the diagonal.
There are two notions of bottleneck distance that appear in the literature, and since both are called ``bottleneck distance'', it is often difficult to tease out which is being discussed in a given paper.
The core issue is that, given some collection of persistence diagrams that come either from different dimensions of persistence or from different types of points in the extended persistence diagrams, we can either allow only matchings between points of the same sub-diagrams, or we can ignore that labeling information and look for matchings that can potentially cross these barriers.
In order to carefully discuss results in the literature, we therefore separate these ideas into what we call \textit{ungraded} and \textit{graded} bottleneck distances, which we will denote as $d_b$ and $d_B$, respectively.  We note that while the majority of the literature uses the graded bottleneck distances~\cite{DeyWang2021,Oudot2015}, the ungraded version is used to derive stability bounds in more algebraic settings, notably when using interlevel set persistence~\cite{Botnan2018,Bjerkevik2021}; hence, we include both versions in our analysis and discussion.

\subsection{Ungraded and graded bottleneck distance definitions}
Assume we are given two persistence diagrams with no additional labeling information on different types of points.
The ungraded bottleneck distance finds a best possible matching between these sets of points, allowing a point from one diagram to be matched to the diagonal of the other diagram.   More formally:

\begin{definition}\label{def:UngradedBottleneckDistance}
We define the  \textbf{(ungraded) bottleneck distance} $\db{}$ between $D_1,D_2$ as
\[
\db{}(D_1,D_2) = \inf_{\zeta} \sup_{x \in D_1}||x - \zeta(x)||_{\infty},
\]
where $\zeta$ is a bijection between multiset of points of $D_1$ and $D_2$ where points are allowed to be matched to the diagonal.
\end{definition}
In order to allow matchings with the diagonal, often one thinks of the persistence diagram as being a collection of off-diagonal points along with countably infinite copies of every point on the diagonal.
An alternate view point which achieves the same result but might be more accessible to the combinatorially minded is the following.
\begin{definition}[Combinatorial version]
\label{def:UngradedBottleneckDistance-v2}
A matching between  $D_1$ and $D_2$ is a bijection on a subset of the off-diagonal points of the two diagrams
\begin{equation*}
    M: D_1' \to D_2'
\end{equation*}
for $D_1' \subseteq D_1$ and $D_2'\subseteq D_2$.
The cost of this matching is given by
\begin{align*}
    c(M) = \sup \Bigg(&
    \{\|x-M(x)\|_\infty \mid x \in D_1' \} \\
    &\cup
    \left\{ \tfrac{1}{2}|x_1-x_2| \mid (x_1,x_2) \in D_1 \setminus D_1' \cup D_2 \setminus D_2' \right\}
    \Bigg)
\end{align*}
The \textbf{(ungraded) bottleneck distance} between $D_1$ and $D_2$ is
\begin{equation*}
    \db{}(D_1,D_2) = \inf_M c(M)
\end{equation*}
where the infimum runs over all possible matchings.
\end{definition}

This definition of \textit{ungraded} bottleneck distance is often seen when the input diagrams to be compared each have points of only one (and the same) type.
For instance, $D_1$ and $D_2$ could each be a single subdiagram, such as $\mathrm{Ord}_0$.
When this is the case, the matchings obviously only match points of the same type.
However, in the case where multiple types are available but are forgotten, the distance can still be defined.
Thus, we also give the definition of the \textit{graded} bottleneck distance which can accept multiple types of points in the diagram and ensures that they are differentiated.
In our case, we are particularly interested in the extended persistence diagram of a Reeb graph, where we have four different types of points: $\mathrm{Ext}_0$, $\mathrm{Ext}_1$, $\mathrm{Rel}_0$, and $\mathrm{Ord}_0$.
In this case, we define the graded bottleneck distance as follows.

\begin{definition}[Graded bottleneck distance]
\label{def:GradedBottleneck}
Let $\mathrm{ExDgm}_1$ and $\mathrm{ExDgm}_2$ be extended persistence diagrams, each of which has four sub diagrams:
$$\mathrm{ExDgm}^{\mathrm{Ext}_0}_i \qquad
\mathrm{ExDgm}^{\mathrm{Ext}_1}_i \qquad
\mathrm{ExDgm}^{\mathrm{Rel}_1}_i \qquad
\mathrm{ExDgm}^{\mathrm{Ord}_0}_i.$$
Denote the individual ungraded distances by $$
\db{\mathrm{type}} = \db{}(\mathrm{ExDgm}^{\mathrm{type}}_1, \mathrm{ExDgm}^{\mathrm{type}}_2).
$$
Then the \textbf{(graded) bottleneck distance} is
\begin{equation*}
    \dB{}(\mathrm{ExDgm}_1,\mathrm{ExDgm}_2) = \max \left\{
            \db{\mathrm{Ext}_0},
            \db{\mathrm{Ext}_1},
            \db{\mathrm{Rel}_1},
            \db{\mathrm{Ord}_0}
    \right\}.
\end{equation*}

\end{definition}

As previously noted, the majority of work available uses (often implicitly) this graded bottleneck distance when comparing diagrams with multiple types, and so it is the one more commonly introduced in the literature~\cite{Oudot2015,DeyWang2021}.
Sometimes the (graded) bottleneck distance is equivalently defined by writing a more combinatorial definition that looks like Def.~\ref{def:UngradedBottleneckDistance-v2} but requires that matchings go between points of the same type.
However, when carefully checking definitions, some of the algebraic literature, particularly that exploring the idea of \textbf{interlevel set persistence}~\cite{Bjerkevik2016a,Botnan2018}, is in fact using an ungraded version on full extended persistence diagram information.
We defer a full discussion of the details of interlevel set persistence to Sec.~\ref{sec:appx:interlevelset}, but note that this distinction will be important when discussing the relationship between available metrics in Sec.~\ref{sec:distProp}.
We will, however, note one immediate relationship between the two distances.
\begin{proposition}
\label{prop:bottleneckBoundedByBottleneck}
Let $D_1$ and $D_2$ be two persistence diagrams with labeling information on the points. Then
\[d_b(D_1,D_2) \leq d_B(D_1,D_2).\]
\end{proposition}
\begin{proof}
A matching which preserves labeling as used for $d_B$ is  also a valid matching which does not preserve labeling.
However, an optimal matching with labeling might not be optimal when types are ignored, making $d_b$ potentially smaller, proving the inequality.
\end{proof}

\subsection{Viewing the bottleneck distances as a distance on Reeb graphs}

Since we are constructing our persistence diagrams from the Reeb graph, we can  view the bottleneck distance as a distance between Reeb graphs.
This will allow us to directly compare the properties of bottleneck distance to the properties of the strictly Reeb graph metrics that we will define in Sec.~\ref{sec:interleaving},Sec.~\ref{sec:FDD}, and Sec.~\ref{sec:EditDist}.
\begin{definition}
The \textbf{(ungraded/graded) bottleneck distance} between two Reeb graphs is the (ungraded/graded) bottleneck distance between the extended persistence diagrams.
Specifically,
\begin{align*}
    \db{}(\mathcal{R}_f,\mathcal{R}_g) &:=  \db{}(\mathrm{ExDgm}(f),\mathrm{ExDgm}(g)),\\
    \dB{}(\mathcal{R}_f,\mathcal{R}_g) &:=  \dB{}(\mathrm{ExDgm}(f),\mathrm{ExDgm}(g))
\end{align*}
where the first does not take the types of points into account, while the second does. Similarly, we denote the ungraded bottleneck distance between individual subdiagrams of the Reeb graphs as \[\dbc{}{type}(\mathcal{R}_f,\mathcal{R}_g) := d_b(\mathrm{ExDgm}^{\emph{type}}(f),\mathrm{ExDgm}^{\emph{type}}(g)).\]
\end{definition}

Of course, by Property \ref{prop:bottleneckBoundedByBottleneck}, we know that $d_b(\mathcal{R}_f, \mathcal{R}_g)\leq d_B(\mathcal{R}_f,\mathcal{R}_g)$.
However, even for the same input Reeb graphs, it is possible to have a strict inequality $d_b(\mathcal{R}_f, \mathcal{R}_g)\lneq d_B(\mathcal{R}_f,\mathcal{R}_g)$.
Consider the example of Fig.~\ref{fig:BottleneckDistancesAreDifferent}.
When comparing the two resulting Reeb graphs, we see that the diagrams are the same if the point type is ignored, making $d_B(\mathcal{R}_f,\mathcal{R}_g) = 0$.
However, the bottleneck distance is non-zero if we take the labeling into account.

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/ungradedLGraded.pdf}
    \caption{Two Reeb graphs with non-equal graded and ungraded bottleneck distances. Specifically, $d_b = |a_4-a_3| < \frac12|a_4-a_2| = d_B$.
    }
    \label{fig:BottleneckDistancesAreDifferent}
\end{figure}

\section{Discussion}
\label{sec:discussion}

The examples which we have constructed are illustrative of the various differences in each metric which go past the above inequalities. We have seen that the bottleneck distance treats several feature changes differently: Ex.~\ref{example:graphIsoEqPers} shows us that non-isomorphic Reeb graphs can have a bottleneck distance of 0, and Ex.~\ref{example:globalMaxChange} showed us that changing the which feature is a global max or global min will shift the pairing of nodes in the Reeb graph -- ultimately changing the bottleneck distance in an unintuitive way. This difference in feature distinction is partly due to the fact that bottleneck distance is defined on a different topological summary.

We have also seen that both bottleneck distance and the Reeb graph edit distances treat loops and leaves in the Reeb graph equally, while interleaving and functional distortion distance treat loops with half as much weight as leaves.

To the best of our knowledge, the properties which we have discussed in Section \ref{sec:distProp} is a comprehensive list of the individual properties which have been discussed in the literature. We can see that the Reeb graph metrics all have the same properties of stability, isomorphism invariance, path component sensitivity, and discriminativity to the bottleneck distance. The Reeb graph edit distance has also been shown to be universal -- a property making it as discriminative as possible among stable Reeb graph distances. While the functional distortion distance and interleaving distance have been shown to be strongly equivalent, there still is no current example of the interleaving distance being strictly less than the functional distortion distance, to the best of our knowledge, which raises the question of equality between the metrics. We state this as the following conjecture.
\begin{conjecture}\label{conjecture:fdd-interleaving-equiv}
The functional distortion and interleaving distance are equivalent on the space of constructible Reeb graphs.
\end{conjecture}

Universality also does not remove the possibility that the universal edit distance is strongly equivalent to the functional distortion distance nor the interleaving distance. In fact, based on the examples we have shown as well as intuition behind the weighting of leaves versus loops for each of the distances, we arrive at the following conjecture:

\begin{conjecture}\label{conjecture:fdd-interleaving-edit-strong-equiv}
The functional distortion distance and interleaving distance are both strongly equivalent to the universal edit distance defined on the space of PL Reeb graphs. More specifically, we conjecture
\[d_{FD} \leq \delta_E \leq 2d_{FD}\] and \[d_I \leq \delta_E \leq 2d_I\].
\end{conjecture}

Of course, if Conjecture \ref{conjecture:fdd-interleaving-equiv} is true, then Conjecture \ref{conjecture:fdd-interleaving-edit-strong-equiv} can be reduced to just the single statement \[d_{FD} = d_I \leq \delta_E \leq 2d_I = 2d_{FD}.\]

We now finish our discussion as a series of open questions and challenges that we hope will summarize the current research landscape.

\textbf{Each metric is computationally complex.} To our discontent, the interleaving distance has been shown to be graph isomorpism complete \cite{deSilva2016,Bjerkevik2017}, and there currently exists no polynomial time algorithm for computing the functional distortion distance (nor Gromov Hausdorff distance).

There also exists no polynomial time algorithm for the Reeb graph edit distance \cite{Sridharamurthy2018,Yan2021}. In general, the labeled graph edit distance is known to be NP-hard \cite{Zhiping2009} and also APX-hard \cite{Chich-Long1994}. While the Reeb graph edit distance is slightly different than the general labeled Reeb graph edit distance, this leaves little hope of efficient, exact algorithms for the most general settings.

For the interleaving distance, a glimmer of hope arises with work investigating fixed parameter tractable algorithms \cite{FarahbakhshTouli2019,Stefanou2020}, and comparisons are possible if the Reeb graph has simple enough structure, such as the labeled merge tree \cite{Gasparovic2019,Stefanou2020}.

\textbf{Are there distances defined on the simpler case contour tree or merge tree?}
The \textbf{merge tree} is constructed similarly to the Reeb graph except that the equivalence relation is defined on \emph{sublevel set} rather than levelsets. While the distances we have constructed still apply merge trees, many have devoted research specifically for distances on merge trees: \cite{Morozov2013} constructed the interleaving distance between merge trees and showed that the interleaving distance is bounded below by the 0-dimensional ordinary bottleneck distance; \cite{Gasparovic2019} introduced the intrinsic interleaving distance on labeled merge trees and was subsequently used in practice for uncertainty visualization in \cite{Yan2019a}; \cite{Sridharamurthy2018} introduced an edit distance on merge trees which has experimentally shown promise and is also computationally tractable; \cite{Beketayev2014} constructed a distance on merge trees based on a previously defined notion of a \textbf{branch decomposition tree} with an accompanying computation. The simplified structure of the merge tree has allowed researchers to construct distances which are actually computationally feasible.

The \textbf{contour tree} is a Reeb graph defined on a simply connected domain (see example \ref{example:globalMaxChange}). Each Reeb graph metric is still a well-defined distance for contour trees, but this distances have still proven difficult to compute. Other distances have been constructed specifically for the contour tree, such as \cite{Buchin2017} which utilized the well-studied Fr\'{e}chet distance to do so.

The only examples in the literature which show the difference between the universal edit distance and functional distortion and interleaving distances have been for domains which are not simply connected. This leads us to the following conjecture:

\begin{conjecture}
The functional distortion distance, interleaving distance, and universal edit distance are equivalent on the space of PL Reeb graphs where the domain ${\mathbb X}$ is simply connected. That is
\[d_B \leq d_I = d_{FD} = \delta_E.\]
\end{conjecture}

\textbf{What are the possible applications of these metrics?}
Reeb graphs and other topological signatures have already been utilized in various areas of data analysis \cite{Yan2021}. The merge tree edit distance was utilized in studying time-dependent scalar fields, 3D cryo electron micoscopy data, shape data, and other synthetic data sets. In \cite{Saikia2017,SaikiaAlgorithm2017}, researchers used a heuristic approach for defining distance between merge trees for feature tracking of time-dependent scalar fields.

Depending on the application domain, these Reeb graph metrics may be suitable. These distances do seem to be well-suited for the analysis of time-dependent scalar fields since the domains remain consistent and the changes are incremental. We can infer that these distances will perform well in areas that the bottleneck distance has been utilized since, from a data analysis perspective, they share many of the same properties. A case where they may not be suitable is when the scalar fields have vary in scale, since these Reeb graph metrics are sensitive to scales/shifts of the data.

\textbf{Are these Reeb graph metrics well-equipped to measure similarity on different domains?} The construction of each of these distances have allowed us to compare scalar fields with completely different domains. This in general is an extremely desirable property since comparing functions defined on different domains is intrinsically difficult. The property of stability, for example, is only defined for the spaces with identical domains because defining the $L^{\infty}$ distance is only well-defined on identical domains. We can then think of each of these distances as having similar utility to the Gromov-Hausdorff distance, which is a distance metric constructed for spaces defined on arbitrary domains.

However, as we have seen in examples such as Ex.~\ref{example:compound}, the distances do not necessarily have a way to differ between features like holes and leaves. Furthermore, since each distance is constructed to only look at the largest feature, the features that are smaller are not encoded in the distance at all. This leads to situations where a single scalar field with leaves can be equidistant from a single edge Reeb graph and a Reeb graph with multiple loops.

\textbf{Sensitivity to multiple features may be desirable.} From the analysis and examples we have constructed, we can see that there are several areas where each of these distances would lack in an application setting. One of the most notable properties is that each distance is insensitive to the presence of multiple features. This is completely due to each metric involving some sort of ``worst-case" function. The interleaving distance finds the smallest $\varepsilon$ to remove $\emph{all}$ features needed, functional distortion distance finds the largest distortion among all distortions for a given set of maps, and the universal edit distance find the largest displacement of a single vertex. Consider the \textbf{degree-q Wasserstein distance}, which is a variation of the bottleneck distance that is indeed sensitive to multiple features:

\begin{definition}
Let $D_1$ and $D_2$ be two persistence diagrams.The \textbf{degree-$q$ Wasserstein distance} between $D_1$ and $D_2$, for any positive real number $q$, is defined as \[W_q(D_1,D_2) = \Bigg[\inf_{\eta: D_1 \to D_2} \sum_{x \in X}||x - \eta(x)||^q_{\infty} \Bigg]^{1/q}\]
\end{definition}

As we can see, the distance is sensitive to each pairing in the bijection $\eta$ as opposed to just the pairing that creates the largest $L^{\infty}$ distance. However, we understand that adjusting the distances similar to the Wasserstein distance is not a catch-all from a data analysis standpoint. It is easy to construct examples such that the Wasserstein distance to a single object from two distinct objects is equal, despite one object possibly having multiple small features (i.e. multiple small holes in the surface) and the other object having just one large feature (i.e. one large hole in the surface). The Wasserstein distance does, however, require additional constraints on the function $f$ of the scalar field to guarantee a stability result \cite{DeyWang2021}.

    %

    %

    %

Through the examples we have constructed, we can see where the bottleneck distance differs from other Reeb graph metrics in many ways -- specifically in its inability to discern between different Reeb graphs in some cases as well as its treatment of global maxima/minima. Unfortunately, the computational difficulty of these well-constructed Reeb graph distances will prove a challenge for those intending to utilize these in a data analysis context. Between each other, the Reeb graph metrics have some very unintuitive similarities which are difficult to discover without these concrete examples.

\section{Distance Properties}
\label{sec:distProp}

We will next seek to understand the relationships between each Reeb graph metric to each other and to the bottleneck distance, as well as understanding crucial results of stability which make these distances robust to input perturbations.
In the following sections, we summarize the relationships between each of the Reeb graph metrics -- including their relationship to bottleneck distances and the $L^{\infty}$ distance. A visual summary of the results are depicted in Fig.~\ref{fig:distanceLandscape}. We will also provide explicit statements concerning other properties that the Reeb graph metrics exhibit which distinguish them from the bottleneck distance. Since these properties were originally defined for only a subset of these distances, we will provide additional statements with proof for the remaining distances to bridge this gap.

Table~\ref{table:distProps} displays the relevant citations for each property of each distance. We refer the reader to Appendix \ref{sec:appx:truncatedProperties} for explicit statements about the properties of the truncated interleaving distance.

\begin{table}
\centering
\begin{tabular}{@{}ccccccc@{}}
                         & $d_B$              & $d_I$              & $d^m_I$             & $d_{FD}$          & $d_E$              & $\delta_E$       \\ \midrule
Stable                   & \cite{Steiner2009} & \cite{deSilva2016} & -                   & \cite{Bauer2014}  & \cite{DiFabio2016} & \cite{Bauer2020} \\
Discriminative           & -                  & \cite{Bauer2015b}, \ref{cor:interleaving-discrim}  & \cite{Chambers2021}, \ref{cor:truncated-interleaving-discrim} & \cite{Bauer2014}, \ref{cor:FDD-discrim}  & \cite{DiFabio2016} & \cite{Bauer2020} \\
Isomorphism Invariant    & -                  & \cite{deSilva2016} & \cite{Chambers2021} & \cite{Bauer2015b}, \ref{cor:FDD-iso} & \cite{DiFabio2016} & \cite{Bauer2020} \\
Path Component Sensitive & -                  & \cite{deSilva2016} & \cite{Chambers2021} & \cite{Bauer2015b} & -                  & \cite{Bauer2020}, \ref{prop:universal-pcs} \\
Universal                & -                  & -                  & -                   & -                 & -                  & \cite{Bauer2020} \\ \bottomrule
\end{tabular}
\caption{Table of distance properties. Entry corresponds to a citation where the distance was proved. We supply additional references to statements we contributed in this work which solidify these properties. We denote disproven properties or properties that are not applicable to the given distance with ``-".\label{table:distProps}}
\end{table}

\subsection{Stability}

The notion of stability in TDA was first introduced for the persistence diagrams in \cite{Steiner2005}, where it is stated as demonstrating that small changes in the input data would only lead to small changes in the persistence diagram.
Although stability is often described as some property of the topological signature, it is actually a property of the metric chosen.

\begin{property}[\textbf{Stability}]\label{p:stability}
Let $f,g:{\mathbb X} \to \mathbb{R}$ be two real-valued continuous functions defined on the same topological space ${\mathbb X}$. The $L^\infty$ \textbf{distance} between $f$ and $g$ is defined as \[||f-g||_\infty := \max_{x \in {\mathbb X}} |f(x) - g(x)|.\] If $d$ is a metric between the two Reeb graphs $\mathcal{R}_f,\mathcal{R}_g$, we say that $d$ is \textbf{stable} if \[d(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_\infty\]
\end{property}

To understand stability, consider $({\mathbb X},f)$ and $({\mathbb X},g)$, where $g$ is equivalent to $f$ except for additional noise added to a set $U \subseteq {\mathbb X}$. In many scenarios, we would like to quantify the bound on this noise rather than the total displacement of all points in the subset $U$. Stability guarantees that we will only be capturing the maximum displacement rather than the conglomerate.

\begin{theorem}[{\cite[Stability Theorem for Tame Functions]{Steiner2009}}]
Let $({\mathbb X},f)$, $({\mathbb X},g)$ be two scalar fields with where ${\mathbb X}$ is a triangulable topological space and $f,g$ are tame functions. Then we have \[\db{}(\emph{ExDgm}(f),\emph{ExDgm}(g)) \leq ||f-g||_{\infty}.\]
\end{theorem}

As stated in \cite{Steiner2009}, this above result can be strengthened to apply to the individual subdiagrams. That is,
\[\db{}(\text{ExDgm}^{\text{type}}(f),\text{ExDgm}^{\text{type}}(g) \leq ||f-g||_{\infty},\]
implying that $\dB{}(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_{\infty}$.

\begin{theorem}[{\cite[Theorem~4.1]{Bauer2014}}]
Let $({\mathbb X},f)$, $({\mathbb X},g)$ be two scalar fields with where ${\mathbb X}$ is a topological space and $f,g$ are tame functions, and whose Reeb graph quotient maps $\rho_f:{\mathbb X} \to {\mathbb X}_f$ and $\rho_g:{\mathbb X} \to {\mathbb X}_g$ have continuous sections (i.e. $\rho_f \circ s_f = \mathbf{id}_{\mathcal{R}_f}$). Then, \[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_{\infty}.\]
\end{theorem}

We next provide the references from the literature showing that every Reeb graph distance discussed in this paper is stable

\begin{theorem}[{\cite[Theorem~4.4]{deSilva2016}}]
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two constructible Reeb graphs defined on the same domain ${\mathbb X}$. Then
\[d_I(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_{\infty}.\]
\end{theorem}

\begin{proposition}[{\cite[Theorem~28]{DiFabio2016}}]
Let $\mathcal{R}_f, \mathcal{R}_g \in \mathcal{M}$. Then \[d_E(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_{\infty}.\]
\end{proposition}

\begin{theorem}[{\cite[Theorem~5.6]{Bauer2020}}]
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be PL Reeb graphs and let ${\mathbb X}$ be a connected, triangulable space ${\mathbb X}$. Let $\rho_f:{\mathbb X} \to \mathcal{R}_f$ and $\rho_g:{\mathbb X} \to \mathcal{R}_g$ be quotient maps such that $\tilde{f} \circ \rho_f = f, \tilde{g} \circ \rho_g = g$. Then \[\delta_E(\mathcal{R}_f,\mathcal{R}_g) \leq ||f-g||_{\infty}.\]
\end{theorem}

For each distance to be guaranteed stable at once, we could require that ${\mathbb X}$ is a compact polyhedra and $f$ is a PL function.

\truncatedOptionalImportant{
The strong equivalence of the interleaving distance and truncated interleaving does not imply that the truncated interleaving distance is stable in the traditional sense.
\begin{proposition}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two constructible Reeb graphs defined on the same space ${\mathbb X}$. Then for a fixed $m \in [0,1)$, we have
\[d^m_I(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{1}{1-m}||f-g||_{\infty}.\]
\end{proposition}
}

\subsection{Isomorphism Invariance}

Each Reeb graph metric attains a value of $0$ whenever the Reeb graphs are Reeb graph isomoprhic to one another. This is a core property which distinguishes these from the bottleneck distance.
Stating that a Reeb graph metric is isomorphism invariant is equivalent to saying that the distance is an extended metric on the isomorphism classes of Reeb graphs, rather than an extended psuedometric on Reeb graphs.

\begin{property}[\textbf{Isomorphism Invariance}]\label{p:isomorphismInvariance}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two Reeb graphs. We say that $d$ is \textbf{isomorphism invariant} if $d(\mathcal{R}_f,\mathcal{R}_g) = 0$ if and only if $\mathcal{R}_f$ and $\mathcal{R}_g$ are Reeb graph isomorphic.
\end{property}

\begin{theorem}
The bottleneck distance is not isomorphism invariant.
\end{theorem}

\begin{proof}
See Ex.~\ref{example:graphIsoEqPers} for a counterexample.
\end{proof}

\begin{proposition}[{\cite[Proposition~4.6]{deSilva2016}}]
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be constructible Reeb graphs. Then, the interleaving distance is isomorphism invariant.
\end{proposition}

\begin{corollary}\label{cor:FDD-iso}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be constructible Reeb graphs. Then, the functional distortion distance is isomprhism invariant.
\end{corollary}

\begin{proof}
This follows directly from strong equivalence of the interleaving distance and functional distortion distance; see Thm.~\ref{thm:strongEquiv}.
\end{proof}

\begin{corollary}[{\cite[Corollary~39]{DiFabio2016}}]
Let $\mathcal{R}_f,\mathcal{R}_g \in \mathcal{M}$. Then the Reeb graph edit distance is isomorphism invariant.
\end{corollary}

\begin{corollary}[{\cite[Corollary~3.6 \& 4.3]{Bauer2020}}]
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be PL scalar fields. Then, the universal edit distance is isomorphism invariant.
\end{corollary}

\subsection{Discriminativity}

Along with stability, it is crucial that our Reeb graph metrics are also able to capture more information in their distances than some baseline distance. \textbf{Discriminativity} is a property which states that a distance is bounded below by a baseline distance up to a constant. Essentially, this states that the baseline distance is not able to discern between two objects as well as the non-baseline distance in certain cases.

\begin{property}[\textbf{Discriminativity}]\label{p:discriminativity}
Let $({\mathbb X},f),({\mathbb X},g)$ be two constructible scalar fields. Let $d_0$ and $d$ be two stable distance metrics on Reeb graphs. We say that $d$ is more \textbf{discriminative} than $d_0$ (the baseline) if there exists a constant $c > 0$ such that \[d_0(\mathcal{R}_f,\mathcal{R}_g) \leq c\cdot d(\mathcal{R}_f,\mathcal{R}_g),\]
and if there does \emph{not} exist a constant $c'$ such that $d_0(\mathcal{R}_f,\mathcal{R}_g) = c'\cdot d(\mathcal{R}_f,\mathcal{R}_g)$. We call the constant $c$ the \textbf{discriminativity constant}.
\end{property}

As stated in Sec.~\ref{sec:bottleneckDist}, the difference between the graded and ungraded bottleneck distance has caused some discrepancies when stating the discriminative power of these Reeb graph metrics. Bauer et. al \cite{Bauer2014} discussed the relationship between the functional distortion distance and the ungraded bottleneck distance defined on the individual diagrams of $\text{Ord}_0$, $\text{Rel}_1$, and $\text{Ext}_1$. Subsequent bounds for the interleaving distance were constructed for the same diagrams in \cite{Bauer2015b} when the interleaving distance and functional distortion distance were shown to be strongly equivalent. We add the final bound comparing $\dbc{0}{Ext}$ to the interleaving and functional distortion distance so that we can give a final statement on the discriminative property when compared to the graded bottleneck distance. We then discuss bounds for the ungraded bottleneck distance in Sec.~\ref{subsubsec:ungradedDiscrim}.

Note that the Reeb graph metrics are not scaled versions of the bottleneck distance since they are isomorphism invariant while the bottleneck distance is not. Thus, to state that these distances are more discriminative than the bottleneck distance only requires that $d_B(\mathcal{R}_f,\mathcal{R}_g) \leq c\cdot d(\mathcal{R}_f,\mathcal{R}_g)$ for some $c$. We begin with the strong equivalence of the functional distortion distance and interleaving distance.

\begin{theorem}[{\cite[Theorem~16]{Bauer2015b}}]\label{thm:strongEquiv}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two constructible Reeb graphs. Then, the functional distortion distance and interleaving distance are strongly equivalent. Specifically,
\[d_I(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \leq 3d_I(\mathcal{R}_f,\mathcal{R}_g).\]
\end{theorem}

As stated in \cite{Bauer2015b} and to the best of our knowledge, there has currently been no example in which the functional distortion distance is strictly greater than the interleaving distance. Thus, we cannot immediately conclude that the functional distortion distance is more discriminative than the interleaving distance.

For statements involving the functional distortion distance and interleaving distance, we will assume that $\mathcal{R}_f$ and $\mathcal{R}_g$ are constructible Reeb graphs.

\begin{theorem}[{\cite[Theorem~4.2]{Bauer2014}}]\label{thm:FDD-discrim-0-orig}
The functional distortion distance is more discriminative than the ungraded bottleneck distance defined on the $0$-dimensional ordinary persistence diagrams of $f,g$ and their reflections $-f,-g$. That is
\[\dbc{}{}(\mathrm{Dgm}(f),\mathrm{Dgm}(g)) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g)\] and \[\dbc{1}{}(\mathrm{Dgm}(-f),\mathrm{Dgm}(-g)) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g)\]
\end{theorem}

\begin{corollary}\label{cor:FDD-discrim-0}
The functional distortion distance is more discriminative than the ungraded bottleneck distance defined on diagrams $\mathrm{Ord}_0$ and $\mathrm{Rel}_1$. That is
\[\db{0}{\mathrm{Ord}}(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g)\] and \[\db{1}{\mathrm{Rel}}(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g)\]
\end{corollary}

\begin{proof}
The diagrams $\mathrm{Dgm}(f)$ and $\mathrm{Dgm}(-f)$ are essentially equivalent diagrams to $\mathrm{Ord}_0(f)$ and $\mathrm{Rel}_1(f)$, except for that $\mathrm{Dgm}(f)$ and $\mathrm{Dgm}(-f)$ have points at $+\infty$ which represents the global minimum \cite{Steiner2009}. The bottleneck distance defined on these diagrams then measures the distance between these points at $+\infty$ by just measuring the difference in their birth times (the differences in the global minimums). The addition of these points only increases the bottleneck distance -- making $\db{0}{\mathrm{Ord}}$ and $\db{1}{\mathrm{Rel}}$ a lower bound to these values.
\end{proof}

\begin{theorem}[{\cite[Theorem~4.3]{Bauer2014}}]\label{thm:FDD-discrim-1}
The functional distortion distance is more discriminative than the ungraded bottleneck distance defined on $\mathrm{Ext}_1$. That is
\[\dbc{1}{Ext}(\mathcal{R}_f,\mathcal{R}_g) \leq 3\cdot d_{FD}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{theorem}

 The original construction for discriminativity of the functional distortion distance in \cite{Bauer2014} looked at subdiagrams of the full extended persistence diagram in a way that only captured the difference in the global minima, but not the global maxima. The below proposition makes certain that the difference in the global minimum - global maximum pair under the bottleneck distances is bounded above by the functional distortion distance.

\begin{proposition}\label{prop:FDD-discrim-0-ext}
The functional distortion distance is more discriminative than the ungraded bottleneck distance defined on  $\mathrm{Ext}_0$. That is
\[\dbc{0}{Ext}(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{proposition}

 We now introduce the following Lemma to aid in the proof of Prop.~\ref{prop:FDD-discrim-0-ext}.

\begin{lemma}\label{lem:FDD-global}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two connected, constructible Reeb graphs. Let $(v_0,v_1)$ and $(u_0,u_1)$ be the $(global min,global max)$ of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively. Then,
\[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq \max\{|f(v_1)-g(u_1)|,|f(v_0)-g(u_0)\}.\]
\end{lemma}

\begin{proof}
Let $f(v_1) = a_1, f(v_0) = a_0, g(u_1) = b_1,$ and $g(u_0) = b_0$. If $\Phi(v_1) = u_1$ and $\Phi(v_0) = u_0$, then $d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq ||f-g\circ\Phi||_{\infty} \geq \max\{|a_1-b_1|,|a_0-b_0|\}$. If $\Phi(v_1) = x_1$ and $\Phi(v_0) = x_0$, for some $x_0 \neq u_0, x_1 \neq u_1$, then $d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq ||f-g\circ\Phi||_{\infty} \geq \max\{|a_1-g(x_1)|,|a_0-g(x_0)|\} \geq \max\{|a_1-b_1|,|a_0-b_0|\}$, since $x_0$,$x_1$ are not the the global min and global max of $\mathcal{R}_g$.

Thus, $d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq \max\{|f(v_1)-g(u_1)|,|f(v_0)-g(u_0)\}. $
\end{proof}

\begin{proof}[Proof of Prop.~\ref{prop:FDD-discrim-0-ext}]
We will first assume that $\mathcal{R}_f$ and $\mathcal{R}_g$ have only one connected component. Then in each persistence diagram defined on the Reeb graphs there is only one pair in the class $\text{Ext}_0(f)$ -- the persistence pair representing the global minimum and global maximum.

Let $({\mathbb X},f)$, $({\mathbb Y},g)$ be constructible scalar fields with corresponding Reeb graphs $\mathcal{R}_f,\mathcal{R}_g$. Let $(a_0,a_1) \in \text{Ext}_0(f)$ and $(b_0,b_1) \in \text{Ext}_0(g)$, and let the vertices of the Reeb graphs which achieve these values to be $v_0,v_1 \in \mathcal{R}_f$ and $u_0,u_1 \in \mathcal{R}_g$. Furthermore, without loss of generality, assume that there is only one vertex in each graph which achieve the global max and global min values. There are two choices for a bijection $\eta$ between these diagrams: (1) let $\eta((a_0,a_1)) = (b_0,b_1)$ or (2) let $\eta$ map both points to the diagonal. Thus, \[\db{0}{\mathrm{Ext}}(\mathcal{R}_f,\mathcal{R}_g) = \min\{\max\{|a_1-b_1|,|a_0-b_0|\},\max\{\frac12|a_1-a_0|,\frac12|b_1-b_0|\}\}.\]
By Lem.~\ref{lem:FDD-global}, we know that $d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq \max\{|a_1-b_1|,|a_0-b_0|\}.$

Now, suppose that $\mathcal{R}_f$ and $\mathcal{R}_g$ both have $n > 1$ connected component. Then the bottleneck distance on $\mathrm{Ext}_0$ finds the best pairing between the global pairs of each component, possible mapping some pairs to the diagonal. When computing the functional distortion distance on multiple connected components, we find best way to map one component of $\mathcal{R}_f$ to a componenet of $\mathcal{R}_g$; see Sec.~\ref{sec:appx:multipleConnected}. For every possible mapping between global pairs, we are guaranteed that $d_{FD} \geq \db{0}{\mathrm{Ext}}$.

 Thus, $d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \geq \dbc{0}{Ext}(\mathcal{R}_f,\mathcal{R}_g)$

\end{proof}

\begin{corollary}\label{cor:FDD-discrim}
The functional distortion distance is more discriminative than the botteleneck distance. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq 3 \cdot d_{FD}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{proof}
This is immediate by combining the definition of graded bottleneck distance with Cor.~\ref{cor:FDD-discrim-0}, Thm.~\ref{thm:FDD-discrim-1}, and Prop.~\ref{prop:FDD-discrim-0-ext}.
\end{proof}

We now turn to comparisons of the interleaving distance with the bottleneck distance.

\begin{corollary}[{\cite[Corollary~18]{Bauer2015b}}]\label{cor:interleaving-discrim-0}
The interleaving distance is more discriminative than the ungraded bottleneck distance defined on diagrams $\mathrm{Ord}_0$,$\mathrm{Rel}_1$, and $\mathrm{Ext}_1$. That is,
\[
\dbc{0}{Ord}(\mathcal{R}_f,\mathcal{R}_g) \leq 3\cdot d_{I}(\mathcal{R}_f,\mathcal{R}_g),
\]
\[
\dbc{1}{Rel}(\mathcal{R}_f,\mathcal{R}_g) \leq 3\cdot d_{I}(\mathcal{R}_f,\mathcal{R}_g),
\]
and
\[\dbc{1}{Ext}(\mathcal{R}_f,\mathcal{R}_g) \leq 9\cdot d_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

Again, the relationship with between the interleaving distance and $\mathrm{Ext}_0$ is missing in the literature, so we provide it here.

\begin{proposition}\label{prop:interleaving-discrim-0-ext}
The interleaving distance is more discriminative than $\dbc{0}{Ext}$. That is
\[\dbc{0}{Ext}(\mathcal{R}_f,\mathcal{R}_g) \leq d_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{proposition}

\begin{lemma}\label{lem:interleaving-global}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be two connected, constructible Reeb graphs. Let $v_0,v_1$ and $u_0,u_1$ be the global min and global max of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively. Then,
\[d_{I}(\mathcal{R}_f,\mathcal{R}_g) \geq \max\{|f(v_1)-g(u_1)|,|f(v_0)-g(u_0)\}.\]
\end{lemma}

\begin{proof}
Let $f(v_1) = a_1, f(v_0) = a_0, g(u_1) = b_1,$ and $g(u_0) = b_0$. Without loss of generality, assume $b_1 > a_1$ and assume $\max\{|a_1-b_1|,|a_0-b_0|\} = b_1 - a_1$. Then, set let $A = b_1-a_1$.

Suppose that cosheaves $\mathsf{F}$ and $\mathsf{G}$ are $\varepsilon$-interleaved with $\varepsilon < A$. Then, there exists a $\delta > 0 $ such that $\varepsilon +\delta < A$ and an interval $I = (c - \delta, c + \delta)$ such that $I^{\varepsilon} = (c - \delta - \varepsilon, c + \delta + \varepsilon)$. Since $a_1$ is the global max of $\mathcal{R}_f$ and $c - \delta - \varepsilon > a_1$, we have that $\mathsf{G}(I) \neq \emptyset$ while $\mathsf{F}(I^{\varepsilon}) = \emptyset$. This implies that $\text{Im}(\mathcal{S}_{e}[\phi] \circ \psi) = \emptyset$ and $\text{Im}(\sigma^{2\varepsilon}_{\mathsf{G}}) \neq \emptyset$, meaning that $\mathsf{F}$ and $\mathsf{G}$ cannot be $\varepsilon$-interleaved.

Thus, $d_{I}(\mathcal{R}_f,\mathcal{R}_g) \geq \varepsilon \geq \max\{|f(v_1)-g(u_1)|,|f(v_0)-g(u_0)\}$.
\end{proof}

\begin{proof}[Proof of Prop.~\ref{prop:interleaving-discrim-0-ext}]
Just as in the proof for Prop.~\ref{prop:FDD-discrim-0-ext}, we know that $\db{0}{\mathrm{Ext}}(\mathcal{R}_f,\mathcal{R}_g) = \min\{\max\{|a_1-b_1|,|a_0-b_0|\},\max\{\frac12|a_1-a_0|,\frac12|b_1-b_0|\}\}.$, where $(a_0,a_1)$ and $(b_0,b_1)$ are the global persistence pairs of $\mathcal{R}_f$ and $\mathcal{R}_g$.

By Lem.~\ref{lem:interleaving-global}, we know that $d_I(\mathcal{R}_f,\mathcal{R}_g) \geq \max\{|a_1-b_1|,|a_0-b_0|\}$. Thus, $d_{I}(\mathcal{R}_f,\mathcal{R}_g) \geq \dbc{0}{Ext}(\mathcal{R}_f,\mathcal{R}_g)$.
\end{proof}

\begin{corollary}\label{cor:interleaving-discrim}
The interleaving distance is more discriminative than the graded bottleneck distance. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq 9\cdot d_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}
\begin{proof}
This follows directly from Cor.~\ref{cor:interleaving-discrim-0} and Prop.~\ref{prop:interleaving-discrim-0-ext}.
\end{proof}

\truncatedOptional{
\begin{corllary}
For a fixed $m\in[0,1)$, the truncated interleaving distance is more discriminative than the graded bottleneck distance. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{9}{1-m}\cdot d^{m}_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corllary}
}

Finally, we focus on the discriminativity of the edit distances.

\begin{corollary}[{\cite[Corollary~40, Corollary~41]{DiFabio2016}}]
Let $\mathcal{R}_f, \mathcal{R}_g \in \mathcal{M}$. Then the Reeb graph edit distance is more discriminative than the bottleneck distance, interleaving distance, and functional distortion distance. That is,
\[d_B(\mathcal{R}_f,\mathcal{R}_g) \leq d_E(\mathcal{R}_f,\mathcal{R}_g)\]
and
\[d_I(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \leq d_E(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{corollary}
Let $\mathcal{R}_f$ and $\mathcal{R}_g$ be PL Reeb graphs. Then, the universal edit distance is more discriminative than the bottleneck, the interleaving, and the functional distortion distance. That is
\[d_B(\mathcal{R}_f,\mathcal{R}_g) \leq \delta_E(\mathcal{R}_f,\mathcal{R}_g)\]
and
\[d_I(\mathcal{R}_f,\mathcal{R}_g) \leq d_{FD}(\mathcal{R}_f,\mathcal{R}_g) \leq \delta_E(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\begin{proof}
This follows from the universality of the Reeb graph edit distance coupled with the non-universality of the bottleneck, functional distortion, and interleaving distance; see Sec.~\ref{sec:universality}.
\end{proof}

\subsubsection{Discriminativity to Ungraded Bottleneck Distance}\label{subsubsec:ungradedDiscrim}
A major issue we have discovered in the literature is that overloading of terminology (``the bottleneck distance'') has led to some confusion as to what exactly is being computed.
Indeed, the investigation of algebraic generalizations of persistence in particular has led to generalizations of the idea of bottleneck distance which can be applied to wildly different algebraic constructions.
Nearly every instance of the bottleneck distance, however, is defined in the manner of what we have defined as the graded bottleneck distance (Def.~\ref{def:GradedBottleneck}) but only as a consequence of passing diagrams with points of a single type.
However, an issue arises with the investigation of the interlevelset persistence (see Appx.~\ref{sec:appx:interlevelset} for further details and examples).
In this case, data about $H_p(f^{-1}(a,b))$ is encoded for each interval $(a,b)$.
The result is that what would be viewed as 1-dimensional structure in the Reeb graph, namely loops, is now encoded in the 0-dimensional information as the ``left'' and ``right'' sides of the loop are stored as two components  in $H_0(a,b)$ for intervals contained inside the function bounds of the loop.
Further, the different types of persistence points encoded in the extended persistence diagram are differentiated by the endpoint types of intervals in the interlevel-set persistence.

This results in the ``bottleneck distance'' as studied in \cite{Botnan2018,Bjerkevik2021} comparing two sets of intervals with different kinds of endpoints, but endpoint type is forgotten when comparing them in the bottleneck distance.
This results in the following theorem, which strengthens the constant of 5 proved in \cite{Botnan2018}, which is a relationship between the interleaving distance and the \textit{ungraded} bottleneck distance.

\begin{theorem}[{\cite[Theorem~3.8]{Bjerkevik2021}}]
\label{thm:ungradedBottleneck_and_interleaving}
Let $\mathcal{R}_f, \mathcal{R}_g \in \mathcal{M}$. Then the interleaving distance is more discriminative than the ungraded bottleneck distance with a discriminative constant of $2$. That is, \[d_b(\mathcal{R}_f,\mathcal{R}_g) \leq 2d_I(\mathcal{R}_f,\mathcal{R}_g).\]
\end{theorem}

We note that this theorem is often mis-cited in the literature as being a bound on the usual interpretation of bottleneck distance (i.e., the graded version), however in that case the best constant known is 9 (see Cor.~\ref{cor:interleaving-discrim}).

Finally, we note that the combination of \ref{thm:ungradedBottleneck_and_interleaving} with strong equivalence to get a bound on the functional distortion distance.

\begin{corollary}
Let $\mathcal{R}_f, \mathcal{R}_g \in \mathcal{M}$. Then the functional distortion distance is more discriminative than the ungraded bottleneck distance with a discriminative constant of $2$. That is, \[d_b(\mathcal{R}_f,\mathcal{R}_g) \leq 2d_{FD}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corollary}

\truncatedOptional{
\begin{corllary}
For a fixed $m\in[0,1)$, the truncated interleaving distance is more discriminative than the ungraded bottleneck distance. That is
\[d_{B}(\mathcal{R}_f,\mathcal{R}_g) \leq \frac{2}{1-m}\cdot d^{m}_{I}(\mathcal{R}_f,\mathcal{R}_g).\]
\end{corllary}
}
\begin{proof}
This follows directly from Thm.~\ref{thm:strongEquiv} -- the strong equivalence between interleaving and functional distortion distance.
\end{proof}

\subsubsection{Discriminativity on Contour Trees}
The \textbf{contour tree} is a Reeb graph where the underlying domain ${\mathbb X}$ is simply connected, i.e. ${\mathbb X}$ is path-connected and its fundamental group is trivial. Reeb graphs have the inherent property that the $1^{st}$ Betti number is bounded above by that of the original domain \cite{DeyWang2021}. This implies that the Reeb graph of a domain with a first Betti number of $0$ has no cycles and is thus a tree. In this case, we have a stronger result for the disciminativity of the interleaving and functional distortion distance compared to the bottleneck distance.

\begin{proposition}\label{prop:FDD-discrim-contour}
The functional distortion distance is more discriminative than the bottleneck distance with a discriminativity constant of 1 when the Reeb graphs are defined on simply connected domains. That is
\[d_b(\mathcal{C}_f,\mathcal{C}_g) \leq d_B(\mathcal{C}_f,\mathcal{C}_g) \leq d_{FD}(\mathcal{C}_f,\mathcal{C}_g).\]
\end{proposition}

\begin{proof}
Let $\mathcal{C}_f, \mathcal{C}_g$ be two contour trees. The 1-dimensional extended persistence diagrams $Ext_1(f)$, $\mathrm{Ext}_1(g)$ are then empty since there are no cycles in $\mathcal{C}_f$ and $\mathcal{C}_g$. Combining the bounds of Cor.~\ref{cor:FDD-discrim-0} and Prop.~\ref{prop:FDD-discrim-0-ext} we achieve \[d_b(\mathcal{C}_f,\mathcal{C}_g) \leq d_B(\mathcal{C}_f,\mathcal{C}_g) \leq d_{FD}(\mathcal{C}_f,\mathcal{C}_g).\]
\end{proof}

\begin{proposition}
The interleaving distance is more discriminative than the bottleneck distance with a discriminativity constant of 3 when the Reeb graphs are defined on simply connected domains. That is,
\[
d_b(\mathcal{C}_f,\mathcal{C}_g) \leq d_B(\mathcal{C}_f,\mathcal{C}_g) \leq 3d_{I}(\mathcal{C}_f,\mathcal{C}_g).
\]
\end{proposition}

\begin{proof}
As in the proof for Prop.~\ref{prop:FDD-discrim-contour}, this follows from combining Cor.~\ref{cor:interleaving-discrim-0} and Prop.~\ref{prop:interleaving-discrim-0-ext} and noting that the diagram $\mathrm{Ext}_1$ is empty.
\end{proof}

\subsubsection{Intrinsic metrics and discriminativity}

Given that the functional distortion distance between two Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ is sufficiently small, the functional distortion distance and graded bottleneck distance are strongly equivalent \cite{Carriere2017}. That is,
\begin{theorem}[{\cite[Theorem~9]{Carriere2017}}]
Let $K \in (0, 1/22]$. If $d_{FD}(\mathcal{R}_f , \mathcal{R}_g) \leq \max\{a_f , a_g/(8(1 + 22K))\}$, then
\[Kd_{FD}(\mathcal{R}_f,\mathcal{R}_g) \leq d_B(\mathcal{R}_f,\mathcal{R}_g) \leq 3d_{FD}(\mathcal{R}_f,\mathcal{R}_g),\]
where $a_f$ and $a_g$ are the global maximum values of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively.
\end{theorem}

The original Theorem \cite[Theorem~9]{Carriere2017} uses a constant of $2$ rather than $3$ for the upper bound on the functional distortion distance. This is due to an incorrect citation to \cite{Bjerkevik2021} which is using the ungraded bottleneck distance rather than the graded bottleneck distance.

This theorem leads to the construction of \textbf{induced intrinsic metrics}: the intrinsic bottleneck distance $\hat{d}_B$, the intrinsic interleaving distance $\hat{d}_I$, and the intrinsic functional distortion distance $\hat{d}_{FD}$. Intuitively, these metrics define the cost between two Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$ to be the length of the longest path from $\mathcal{R}_f$ to $\mathcal{R}_g$ in the space of Reeb graphs, where the length of the path is defined using the original distances $d_B$, $d_I$, and $d_{FD}$. These metrics have the property that they are all strongly equivalent to one another.

\subsection{Universality}\label{sec:universality}

If we believe that discriminativeness is a desirable property for comparison of Reeb graphs, it would be wise to find distances which are as discriminative as possible -- a \textbf{universal} distance.

\begin{property}[\textbf{Universality}]\label{p:universality}
We say that a stable distance $d_U$ between two Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$ is \textbf{universal} if for all other stable distances $d_S$, we have
\[d_S(\mathcal{R}_f,\mathcal{R}_g) \leq d_U(\mathcal{R}_f,\mathcal{R}_g).\]
\end{property}

\begin{theorem}[{\cite[Corollary~5.7]{Bauer2020}}]
The universal edit distance is universal.
\end{theorem}

\begin{proposition}
Neither the functional distortion distance, interleaving distance, nor bottleneck distance are universal.
\end{proposition}

\begin{proof}
While Ex.~\ref{example:graphIsoEqPers} is not using a PL Reeb graph, the fact that these are compact 2-manifolds guarantees that it is triangulable. Furthermore, we can easily define a PL functions $\hat{f}$ and $\hat{g}$ which approximate $f$ and $g$ well enough to ensure that $({\mathbb X},\hat{f})$ and $({\mathbb Y},\hat{g})$ have Reeb graphs equivalent to $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively. Thus, Ex.~\ref{example:graphIsoEqPers} is enough to show that these distances are not universal.
\end{proof}

\truncatedOptionalImportant{
\begin{remark}
Since the truncated interleaving distance is not a stable distance, there is no guarantee that the universal edit distance bounds the truncated interleaving distance for any fixed $m$.
\end{remark}
}

\subsection{Path Component Sensitivity}\label{subsec:PCSensitivity}

Path component sensitivity is an inherent property of each of the Reeb graph metrics -- it essentially states that the Reeb graph metrics are not readily equipped to compare Reeb graphs with different numbers of connected components.

\begin{property}[\textbf{Path Component Sensitivity}]\label{p:pathComponentSensitive}
Let $({\mathbb X},f)$ and $({\mathbb Y},g)$ be two constructible scalar fields.
 We say that $d$ is \textbf{path component sensitive} if  $d(\mathcal{R}_f,\mathcal{R}_g) = \infty$
 if and only if
 $\mathcal{R}_f$ and $\mathcal{R}_g$ have a different number of path connected components.
\end{property}

\begin{proposition}
The bottleneck distance is not path component sensitive.
\end{proposition}
\begin{proof}
Suppose $\mathcal{R}_f$ has more connected components than $\mathcal{R}_g$. By definition, the extended persistence diagram has no points at $+\infty$ and the bijection $\eta$ between two extended persistence diagrams does not discern from which connected components the features arise. Thus, we are able to pair features from multiple connected components in $\mathcal{R}_f$ to the same connected component in $\mathcal{R}_g$. Since all points are finite, the bottleneck distance is also finite. Thus, the bottleneck distance is not path component sensitive.
\end{proof}

In the next statements we see that all the Reeb graph metrics are path componenet sensitive.

\begin{proposition}[{\cite[Proposition~4.5]{deSilva2016}}]
The interleaving distance is path component sensitive.
\end{proposition}

\begin{corollary}
The functional distortion distance is path component sensitive.
\end{corollary}

\begin{proof}
This follows directly from strong equivalence of the interleaving distance and functional distortion distance.
\end{proof}

\begin{proposition}\label{prop:universal-pcs}
The universal edit distance is path component sensitive.
\end{proposition}

\begin{proof}
From Remark 3.4 in \cite{Bauer2020}, we can see that the universal distance is $\infty$ if the number of path connected components of $\mathcal{R}_f$ and $\mathcal{R}_g$ differ. If they do not differ, then they are finite due to stability of the universal distance. Corollary 4.3 in \cite{Bauer2020} states that the universal distance is equivalent to our universal edit distance, completing the proof.
\end{proof}

The Reeb graph edit distance is not defined with multiple connected components in mind \cite{DiFabio2016}. Thus, the Reeb graph edit distance is the only distance we have defined that is just a pseudo-metric on Reeb graphs, not an extended pseudo-metric. This is due to the fact that there are no elementary deformations which are able to insert isolated vertices or delete edges between vertices without deleting the vertices as well.

\section{Edit Distance}
\label{sec:EditDist}

\subsection{History}

The graph edit distance was first formalized by Sanfeliu and Fu~\cite{Sanfeliu1983} as a similarity measure for graphs; their original motivation/application was recognizing lower case handwritten English characters.  While various approximations and heuristics for the general problem are known~\cite{Gao2009}, it is nevertheless NP-Hard to compute~\cite{garey1979computers,Zhiping2009} as well as being APX-hard to approximate~\cite{Chih-Long1994}.  There are many well studied variants of graph edit distance for restricted classes of graphs, including the geometric graph distance~\cite{Cheong2009}, which compares embedded plane graphs.  We refer the interested reader to a comprehensive survey on the graph edit distance for discussion of further  variants~\cite{Bille2005}.

The Reeb graph edit distance was first introduced for 1-dimensional closed curves by Di Fabio and Landi ~\cite{DiFabio2012} and then later introduced for 2-dimensional manifolds by the same authors~\cite{DiFabio2016}. Originally, the core intuition was that we can think of Reeb graphs as having various topological \emph{events} -- such as the prescense of a maximum or minimum -- and to change one Reeb graph to another, we add, remove, or rearrange these events. For closed curves, the elementary deformations simply allowed for the birth, death, and relabeling (changing of function values) of events. When extrapolating to 2-dimensional manifolds, our set of edit operations is expanded to include three different operations responsible for changing the adjacencies of events. While the core idea of birth and death events in these two scenarios are the same, the structure of these events are fundamentally different. More specifically, introducing an event for a 1-dimensional closed curve involved adding two additional vertices to an edge to create a maxima - minima pair. For 2-dimensional manifolds, birth events were defined as adding upwards pointing or downwards pointing leaves.  Thsese sets of elementary deformations are different from the classic graph edit distance where the edits can be categorized as insertion, deletion, and relabeling of vertices and edges, often times without restrictions on degrees of vertices or positions of edges \cite{Blumenthal2019}.

One of the main drawbacks to this distance was its inability to compare spaces where were non-homeomorphic. Furthermore, having different sets of edit operations dependent on the dimension of the space we are working with causes a lack of cohesiveness. A new distance was introduced in \cite{Bauer2016} which bridged this gap. It simultaneously provided a set of edit operations which worked for a wide class of Reeb graphs as well as allowing for insertion and deletion of loops -- the operation needed to be able to compare non-homeomorphic spaces. However, an issue with the cost model allowed for the addition of events while incurring no cost -- essentially rendering the distance defined on these operations invalid; see Rem.~\ref{rem:bug}. This work was later expanded upon in \cite{Bauer2020} which fixed this error by creating a purely categorical framework for defining a distance between Reeb graphs. In addition, this work proved that this distance is the largest possible stable distance on Reeb graphs and is thus labeled as being a \textbf{universal distance}; see Sec.~\ref{sec:universality} for a discussion of this property.

Below we will describe the edit distance discussed in \cite{DiFabio2016}, which we will call the \textbf{Reeb graph edit distance} and denote it as $d_E$. This requires a rather restricted setting; each Reeb graph $\mathcal{R}_f, \mathcal{R}_g$ are defined on homeomorphic, compact 2-manifolds without boundary. We will then separately discuss the one of the distances constructed from \cite{Bauer2020}, which we will call the \textbf{universal edit distance} and denote it as $\delta_E$. While this latter distance is completely categorical, it is useful to think of this distance as having a canonical set of edit operations -- either those stemming from \cite{DiFabio2016} when applicable, or the more general operations from \cite{Bauer2016}.

It is important to note that while the universal edit distance $\delta_E$ is inspired by its predecessors, it has not been shown that it is equivalent to the Reeb graph edit distance $d_E$ in a common setting, nor is it equivalent to the more directly related distance of \cite{Bauer2016}.

\subsection{Reeb Graph Edit Distance}
\label{sec:EditDistanceTake1}

While functional distortion distance considered $\mathcal{R}_f$ as a topological space and the interleaving distance considered $\mathcal{R}_f$ as a cosheaf $\mathsf{F}$, here we only need to consider it as a labeled multigraph, known as the \textbf{combinatorial Reeb graph}, $\Gamma_f$.

\begin{definition}
The \textbf{combinatorial Reeb graph}, $(\Gamma_f,\ell_f) = (V_f,E_f,\ell_f)$ is the labeled multigraph where the vertex set $V$ is the set of critical points of the Reeb graph, the edge set $E$ is the set of non-critical fibers between critical points, and the labeling function $\ell_f$ is $f|_{V(\Gamma_f)}$ -- the function $f$ restricted to the vertices of the graph. We will often denote $(\Gamma_f,\ell_f)$ as $\Gamma_f$ when the labeling function is implied.
\end{definition}

We will define a set of elementary deformations which are a set of allowed operations for deforming a combinatorial Reeb graph $\Gamma_f$. Elementary deformations can be chained together to form a sequence of operations to which we will then associate a \textbf{cost}. The goal is to find a sequence of deformations $S$ which deforms a labeled multigraph $\Gamma \cong \Gamma_f$ into another labeled multigraph $\Gamma' \cong \Gamma_g$. We then define the Reeb graph edit distance as the infimum cost ranging over all sequences carrying $\Gamma_f$ to $\Gamma_g$.

Here we will assume that each Reeb graph $\mathcal{R}_f$ is defined on a smooth, connected, compact 2-manifold without boundary ${\mathbb X}$ and assume that $f$ is a simple Morse function. We denote this space of Reeb graphs as $\mathcal{M}$. Note that the restriction on $({\mathbb X},f)$ will be different for the universal Reeb graph edit distance in Sec.~\ref{sec:EditDistanceTake2}.

The assumption of connectedness is not necessarily needed for the deformations we define below, nor for the cost model; it is only for simplicity of the proofs. Similarly, there are examples where ${\mathbb X}$ \emph{does} have a boundary and the distance is still well-defined.

\subsubsection{Elementary Deformations}

The operations that are permitted to be performed on the graph $\Gamma$ are known as \textbf{elementary deformations}. The allowed operations are specific to the Reeb graph scenario and are designed to add, remove, relabel, and change adjacencies of events. Here we will provide brief definitions of each elementary deformation; see \cite{DiFabio2016} for explicit definitions of each deformation. Fig.~\ref{fig:elementaryDeformations} depicts each elementary deformation as well as their inverses.

For the remainder of these definitions, we denote the initial graph as $(\Gamma_0,l_0)$ and the transformed graph as $T(\Gamma_0,l_0) = (\Gamma_1,\ell_1)$, where $T$ is an elementary deformation.

\begin{definition}[Basic Deformations]\label{def:basicDeformations}
The set of basic deformations consist of three different types:
\begin{enumerate}
    \item an \textbf{elementary birth deformation} (B-type) adds a pair $\{u_0,u_1\}$ such that $u_0$  is a degree-3 vertex bisecting an existing edge and $u_1$ is a local maxima or minima. The edge $e(u_0,u_1)$ is known as a \textbf{up-leaf} if $f(u_1) > f(u_0)$ and a \textbf{down-leaf} otherwise.
    \item an \textbf{elementary death deformation} (D-type) removes an existing leaf from the initial graph.
    \item a \textbf{elementary relabel deformation} (R-type) assigns new function values to any number of vertices of $(\Gamma_0,l_0)$, while only changing the function value ordering of at most two non-adjacent vertices.
\end{enumerate}
\end{definition}

The restriction given to the relabel operation prevents us from changing any up-leaf into a down-leaf. Essentially, we are restricting our edit distance so that ``changing" and up-leaf into a down-leaf requires destroying the up-leaf and inserting the down-leaf. As we will see, the universal edit distance defined in Sec.~\ref{sec:EditDistanceTake2} will retain this property as well as restricting us from comparing cycles to either up-leaves or down-leaves as well.

\begin{definition}[K-type Deformations]\label{def:kTypeDeformations}
    The $K$-type deformations are responsible changing the adjacencies and function value labelings of saddles and leaves.
    \begin{enumerate}
    \item An  \textbf{elementary $K_1$ type deformation} moves an up-leaf (down-leaf) whose root bisects an up-leaf (down-leaf) $e_1$ to bisect an up-leaf (down-leaf) $e_2$ that shares a root with $e_1$.
    \item Let $u_1,u_2$ be two adjacent degree-3 vertices such that $u_1$ has two downwards-pointing edges incident to it while $u_2$ has two upwards-point edges incidient to it. An \textbf{elementary $K_2$ type deformation} switches the function value ordering of $u_1,u_2$ while and simultaneously changing the adjacencies of the connecting edges such that both $u_1$ and $u_2$ each have one downwards-point edge and one up-wards pointing edge.
    \item Let $u_1,u_2$ be two adjacent degree-3 vertices such that both $u_1$ and $u_2$ each are incident to one upwards-pointing edge and one downwards-pointing edge. An \textbf{elementary $K_3$ type deformation} switches the function value ordering of $u_1,u_2$ while and simultaneously changing the adjacencies of the connecting edges such that both $u_1$ now has two downwards-pointing edges incident to it and $u_2$ has two upwards-pointing edges incident to it.
    \end{enumerate}
\end{definition}

Each deformation we have described above inherently has an inverse deformation. Birth and death deformations are inverses of each other, $K_2$ and $K_3$-type deformations are inverses of each other, and both relabel and $K_1$ type deformations are inverses of themselves.

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/ElementaryDeformations.pdf}
    \caption{Simple depiction of elementary deformations. \textbf{(a)} A birth (B), death (D) and relabel (R) deformation. \textbf{(b)} A $K_2$-type deformation and its inverse; a $K_3$-type deformations. \textbf{(c)} A $K_1$-type deformation with all up-leaves. \textbf{(d)} A $K_1$-type deformation with all down-leaves.}
    \label{fig:elementaryDeformations}
\end{figure}

\subsubsection{Edit Sequences}

Since $T(\Gamma,\ell)$ is another labeled multigraph, we can chain together these elementary deformations to form a sequence of edit operations.

\begin{definition}
An $\textbf{edit sequence}$ of the labeled graph $(\Gamma,\ell)$ is any finite ordered sequence $S = (T_1,T_2,\ldots,T_n)$ of edit operations such that $T_1$ is an edit operation acting on $(\Gamma,\ell)$, $T_2$ is an operation acting on $T_1(\Gamma,\ell)$, and so on. We denote the result of applying this entire sequence to $(\Gamma,\ell)$ as $S(\Gamma,\ell)$. Finally, we denote $\mathcal{S}((\Gamma,\ell),(\Gamma',\ell'))$ to be the set of edit sequences $S$ that carry $(\Gamma,\ell)$ to $(\Gamma',\ell')$.
\end{definition}

It has been shown that there always exists an edit sequence carrying one Reeb graph $\mathcal{R}_f \in \mathcal{M}$ to another $\mathcal{R}_g \in \mathcal{M}$ \cite{DiFabio2016} and thus the edit distance is well defined.

\begin{definition}
Let $T \in \SS((\Gamma_f,\ell_f),(\Gamma_g,\ell_g))$ be an elementary deformation. The \textbf{cost} of $T$ is defined as follows:
\begin{itemize}[label={-}]
    \item If $T$ is an elementary birth deformation which inserts $u_1,u_2 \in V(\Gamma_g)$, then the cost of $T$ is \[c(T) = \frac{|\ell_g(u_1)-\ell_g(u_2)|}{2}.\]
    \item If $T$ is an elementary death deformation which removes vertices $u_1,u_2 \in V(\Gamma_f)$, then the cost of $T$ is
    \[c(T) = \frac{|\ell_f(u_1)-\ell_f(u_2)|}{2}.\]
    \item If $T$ is an elementary relabel deformation, then the cost of $T$ is
    \[c(T) = \max_{v \in V(\Gamma_f)}|\ell_f(v) - \ell_g(v)|.\]
    \item If $T$ is a $K_i$-type for $i = 1,2,3$, changing the relabeling and vertices of $u_1,u_2 \in V(\Gamma_f)$, then the cost of $T$ is
    \[c(T) = \max\{|\ell_f(u_1)-\ell_g(u_1)|,|\ell_f(u_2)-\ell_g(u_2)|\}.\]
\end{itemize}
\end{definition}

\begin{definition}
Let $S = (T_1,\ldots,T_n) \in \mathcal{S}((\Gamma,\ell),(\Gamma',\ell'))$. Setting $(\Gamma_1,\ell_1) := (\Gamma,\ell)$ and $(\Gamma_{n+1},\ell_{n+1}) := (\Gamma',\ell')$, let $(\Gamma_{i+1},\ell_{i+1}) = T_i(\Gamma_i,l_i)$, for all $i \in \{1,\ldots,n\}$. The \textbf{cost} of $S$ is then
\[c(S) = \sum_{i=1}^n c(T_i).\]
\end{definition}

Just as in standard graph edit distance, our goal will be to find the best possible sequence by attempting to minimize the associated cost. The Reeb graph edit distance is then defined to be the infimum cost over all possible sequences carrying one Reeb graph $\mathcal{R}_f$ to another $\mathcal{R}_g$.

\begin{definition}
The \textbf{Reeb graph edit distance}, $d_E$, between two Reeb graphs $\mathcal{R}_f,\mathcal{R}_g\in\mathcal{M}$ is defined to be
\[d_E((\Gamma_f,\ell_f),(\Gamma'_g,\ell_g)) = \inf_{\mathcal{S}((\Gamma,\ell),(\Gamma',\ell'))}c(S),\]
where $(\Gamma_f,\ell_f)$, $(\Gamma_g,\ell_g)$ are the combinatorial Reeb graphs of $\mathcal{R}_f,\mathcal{R}_g$, respectively and $(\Gamma_f,\ell_f) \cong (\Gamma,\ell)$ and $(\Gamma_g,\ell_g) \cong (\Gamma',\ell')$.
\end{definition}

\optional{
This style of edit distance is similar to the traditional style of the (labeled) graph edit distance; each deformation in a sequence has a cost, the cost of the sequence is the sum of the individual costs, and our goal is to find the lowest cost sequence from our source graph to the target graph.
}

\begin{remark}\label{rem:spreadRelabel}
There is a rather subtle consequence of the costs defined above: although adding leaves individually each incur a cost, we often have sequences where, if we need to have multiple birth/death events in the sequence, it is best to use relabel operations to expand/shrink the leaves rather than add/remove them at their final/initial size. This is because a single relabel operation only incurs the \emph{max} cost of each relabeling. We show an example of this in Ex.~\ref{example:graphIsoEqPers}. We will see in Sec.~\ref{sec:EditDistanceTake2} that the universal Edit distance solely defines their cost model as the ``largest'' relabeling of vertices within the sequence constructed.
\end{remark}

\subsection{Universal Edit Distance}
\label{sec:EditDistanceTake2}

\begin{remark}
Here we will restrict our setting to have $\mathcal{R}_f$ and $\mathcal{R}_g$ be Reeb graphs as in Def.~\ref{def:reebGraph} (i.e. 1-dimensional topological graphs). However, the original work loosens the restriction on these structures to be more general PL scalar fields.
\end{remark}

Suppose we have two PL scalar fields $({\mathbb X},f)$ and $({\mathbb X},g)$ defined on the same domain ${\mathbb X}$. Then, we can construct two different Reeb graphs, $\mathcal{R}_f,\mathcal{R}_g$, equipped with scalar functions $\tilde{f}$  and $\tilde{g}$. Naturally, there exist quotient maps $p_f$ and $p_g$ such that $f = \tilde{f} \circ p_f$ and $g = \tilde{g} \circ p_g$. In other words, the following diagram commutes:

\begin{equation}\label{dgm:relabel}
    \begin{tikzcd}
    \mathbb{R}                           &                                                                                & \mathbb{R}                            \\
    \mathcal{R}_f \arrow[u, "\tilde{f}"] &                                                                                & \mathcal{R}_g \arrow[u, "\tilde{g}"'] \\
                                         & \mathbb{X} \arrow[lu, "p_f"] \arrow[ru, "p_g"'] \arrow[ruu, "g"] \arrow[luu, "f"'] &
    \end{tikzcd}
\end{equation}

Similarly, we can construct two slightly different topological spaces ${\mathbb X}_1$ and ${\mathbb X}_2$ which, when endowed with different functions $f_1$ and $f_2$, can create the same Reeb graph $\mathcal{R}_f$. This creates the following commutative diagram:

\begin{equation}\label{dgm:edit}
    \begin{tikzcd}
                                                       & \mathbb{R}                            &                                                    \\
                                                       & \mathcal{R}_f \arrow[u, "\tilde{f}"'] &                                                    \\
    \mathbb{X}_1 \arrow[ru, "p_1"'] \arrow[ruu, "f_1"] &                                       & \mathbb{X}_2 \arrow[lu, "p_2"] \arrow[luu, "f_2"']
    \end{tikzcd}
\end{equation}

Given two Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$, we can find a sequence of Reeb graphs
$$\{\mathcal{R}_f = \mathcal{R}_1, \mathcal{R}_2, \ldots, \mathcal{R}_{n-1},\mathcal{R}_n = \mathcal{R}_g\}$$
and a sequence of topological spaces $\{X_1,\ldots,{\mathbb X}_{n-1}\}$ such that the following diagram commutes:

\begin{equation}\label{dgm:zigzag}
\adjustbox{width=0.9\textwidth,center}{
\begin{tikzcd}
\mathbb{R}                                             &                                                      & \mathbb{R}                             &                                                 &        &                                                        & \mathbb{R}                                     &                                                                & \mathbb{R}                                             \\
\mathcal{R}_f = \mathcal{R}_1 \arrow[u, "\tilde{f}_1"] &                                                      & \mathcal{R}_2 \arrow[u, "\tilde{f}_2"] &                                                 & \ldots &                                                        & \mathcal{R}_{n-1} \arrow[u, "\tilde{f}_{n-1}"] &                                                                & \mathcal{R}_n = \mathcal{R}_g \arrow[u, "\tilde{f}_n"] \\
                                                       & X_1 \arrow[lu, "{p_{1,1}}"'] \arrow[ru, "{p_{1,2}}"] &                                        & X_2 \arrow[lu, "{p_{2,2}}"'] \arrow[ru, dotted] &        & X_{n-2} \arrow[ru, "{p_{n-2,n-1}}"] \arrow[lu, dotted] &                                                & X_{n-1} \arrow{lu}[swap]{ p_{n-1,n-1}} \arrow{ru}[swap]{p_{n-1,n}} &
\end{tikzcd}
}
\end{equation}

This zigzag diagram above can be thought of as being constructed by combining alternating copies of the Dgm.~\ref{dgm:relabel} and Dgm.~\ref{dgm:edit} -- essentially constructing a sequence of edit and relabel operations carrying $\mathcal{R}_f$ to $\mathcal{R}_g$.

Now, rather than think of $X_1,\ldots,X_{n-1}$ as being arbitrary topological spaces, we restrict the conditions on each $X_i$ such that each is a  1-dimensional topological graph. That way, the transformations we apply from $X_i$ to $X_{i+1}$ can be thought of as edit operations in the classical sense, such as adding or deleting leaves and changes from $\mathcal{R}_{i}$ to $\mathcal{R}_{i+1}$ can be thought of as a relabeling. Similar to the Reeb graph edit distance case, we are always guaranteed a way to construct this zigzag diagram between any two PL Reeb graphs.

This zigzag diagram can now be considered a sequence of relabel and edit operations which carry the Reeb graph $\mathcal{R}_f$ to $\mathcal{R}_g$. We call Dgm.~\ref{dgm:zigzag} a \textbf{Reeb zigzag diagram}. We assign a cost to this zigzag diagram by introducing the notion of a \textbf{Reeb cone}.

\begin{definition}
Let $Z$ be a zigzag diagram in the form of Dgm.~\ref{dgm:zigzag}. Let $V$ be a space such that there exists Reeb quotient maps $V \to X_i$ for all $i \in \{1,\ldots,n-1\}$. By commutativity of Reeb quotient maps, this creates Reeb quotient maps from $V \to \mathcal{R}_i$ for all $i \in \{1,\ldots,n\}$. We call $V$ a \textbf{Reeb cone}\footnote{This definition of Reeb cone makes $V$ a well-defined cone in the category theory sense as well.} of the diagram $Z$.
\end{definition}

Adding the Reeb cone to Dgm.~\ref{dgm:zigzag} creates the following commutative diagram:
\begin{equation}\label{dgm:zigzagFull}
\adjustbox{width=0.9\textwidth,center}{
\begin{tikzcd}
\mathbb{R}                                             &                                                      & \mathbb{R}                             &                                                 &                                                                                &                                                        & \mathbb{R}                                     &                                                                & \mathbb{R}                                             \\
\mathcal{R}_f = \mathcal{R}_1 \arrow[u, "\tilde{f}_1"] &                                                      & \mathcal{R}_2 \arrow[u, "\tilde{f}_2"] &                                                 & \ldots                                                                                &                                                        & \mathcal{R}_{n-1} \arrow[u, "\tilde{f}_{n-1}"] &                                                                & \mathcal{R}_n = \mathcal{R}_g \arrow[u, "\tilde{f}_n"] \\
                                                       & X_1 \arrow[lu, "{p_{1,1}}"'] \arrow[ru, "{p_{1,2}}"] &                                        & X_2 \arrow[lu, "{p_{2,2}}"'] \arrow[ru, dotted] &                                                                                & X_{n-2} \arrow[ru, "{p_{n-2,n-1}}"] \arrow[lu, dotted] &                                                & X_{n-1} \arrow[lu, "{p_{n-1,n-1}}"'] \arrow{ru}[swap]{p_{n-1,n}} &                                                        \\
                                                       &                                                      &                                        &                                                 & V \arrow[lllu, "q_1"'] \arrow[lu, "q_2"'] \arrow[ru, "q_{n-2}"] \arrow[rrru, "q_{n-1}"] &                                                        &                                                &                                                                &
\end{tikzcd}
}
\end{equation}

\noindent This cone provides a common space for us to assign a cost function rather than splitting the function across various $X_i$'s.

\begin{definition}
Let $Z$ be a Reeb zigzag diagram and $V$ be a Reeb cone of $Z$. We define the \textbf{spread} of $V$ to be the function
\[s^V: V \to \mathbb{R}, \hspace{10PX} x \mapsto \max_{i=1,\ldots,n}f_i(x) - \min_{i=1,\ldots,n}f_i(x),\]
where $f_i = \tilde{f}_i \circ p_{i-1,i} \circ q_{i-1} = \tilde{f}_i \circ p_{i,i} \circ q_i$. Moreover, we define the \textbf{cost} of $Z$ to be the supremum of the spread of $\ell$, where $\ell$ is the limit of the diagram $Z$. That is,
\[c_Z = ||s^\ell||_{\infty} = \sup_{x\in \ell}\bigg(\max_{i=1,\ldots,n}f_i(x) - \min_{i=1,\ldots,n}f_i(x)\bigg)\]
\end{definition}

While $V$ is any arbitrary space abiding by the above conditions, we can actually construct $\ell$ in a systematic way. To do this, we review the universal definition of \textbf{pullback}.

\begin{definition}
The \textbf{pullback} of two morphisms $f:X_1 \to Y$, $g:X_2 \to Y$ is the set of pairs $(x_1,x_2)$, where $x\in X_1$, $x \in X_2$ and $f(x_1) = g(x_2)$. The pullback is denoted $X_1 \times_Y X_2$. The pullback is also known as the \textbf{fiber product} of the morphisms $f:X_1 \to Y$ and $g:X_2 \to Y$.
\end{definition}

The pullback is intuitively then the cartesian product of spaces $X_1$, $X_2$ with the restriction that the elements in the tuple $(x_1,x_2)$ map to the same point in $Y$. In Dgm.~\ref{dgm:relabel}, the pullback is $X_1 \times_{\mathcal{R}_f} X_2$, which is the limit of the diagram.

The limit of Dgm.~\ref{dgm:zigzag} is then the iterated pullback of the zigzag diagram. That is, \[\ell = X_1 \times_{\mathcal{R}_2} \times X_2 \times_{\mathcal{R}_3} X_3 \times_{\mathcal{R}_4} \ldots \times_{\mathcal{R}_{n-2}} X_{n-2} \times_{\mathcal{R}_{n-1}} X_{n-1}.\] Then a point $x = (x_1,x_2,\ldots,x_{n-1}) \in \ell$ if $(p_{i,i+1}\circ q_i)(x_i) = (p_{i+1,i+1}\circ q_{i+1})(x_{i+1}) \in \mathcal{R}_{i+1}$ for all $i \in \{1,\ldots,n-2\}$.

Finally, we can define the edit distance between Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$:

\begin{definition}
We define the \textbf{universal edit distance} $\delta_E$ between $\mathcal{R}_f$ and $\mathcal{R}_g$ to be the infimum cost over all zigzag diagrams carrying $\mathcal{R}_f$ to $\mathcal{R}_g$. That is,
\[\delta_E(\mathcal{R}_f,\mathcal{R}_g) = \inf_Z c_Z\]
\end{definition}

The distance defined above is denoted as $\delta_{eGraph}$ in \cite{Bauer2020}.

At this point, while the edit distance has been fully defined, it is still not completely clear exactly how we should go about finding this zigzag diagram. As we have said before, this zigzag diagram can be thought of as a sequence of edit and relabel operations. Any set of edit operations that can guarantee to be able to carry a Reeb graph $\mathcal{R}_f$ to a Reeb graph $\mathcal{R}_g$ can then be used as a framework for finding these zigzag diagrams. For example, in the case of Reeb graphs $\mathcal{R}_f, \mathcal{R}_g \in \mathcal{M}$ where $f$ is also a PL function, we can use the set of elementary deformations in Def.~\ref{def:basicDeformations} and Def.~\ref{def:kTypeDeformations} to inform our decision how to construct this sequence as long as the edit operations abide by the rules of the construction for this zigzag diagram. If the spaces happen to be non-homeomorphic or are defined on higher dimensional manifolds, we can use the deformations laid out in \cite{Bauer2016}. We find that this latter sequence of deformations is particularly useful since the allowable operations more closely align with the zigzag construction in the sense that the combinatorial Reeb graphs made at each step more closely resembles allowable spaces in the diagram.

The deformations described in \cite{Bauer2016} consist of vertex insertion/deletion, edge insertion/deletion, loop insertion/deletion, relabel, and a slide operation. There are restrictions imposed on the insertion/deletion of vertices and edges so that we can mimic the Reeb graph edit deformations. The \textbf{slide} operation is responsible for replacing the various $K$-type operations. We leave out explicit definitions for these deformations and instead provide Fig.~\ref{fig:universalOperations} which shows simple examples of each deformation. To distinguish between the deformations of \cite{DiFabio2016} and \cite{Bauer2016}, we call the latter set of deformations the \textbf{universal deformations}.

\begin{remark}\label{rem:bug}
The cost model defined in \cite{Bauer2016} closely resembles the cost model defined for the zigzag diagrams of \cite{Bauer2020} above. Unfortunately, there is a small bug which essentially allows for adding any size leaf with a cost approaching 0. If we want to relabel a maxima node $v_1$, for example, to have function value $a$, instead we can do the following: relabel $v_1$ to have function value $a/3$, then add an edge $e(v_1,v_2)$ where $v_2$ is degree 1 and then relabel its function value to be $2a/3$. Repeat once more with a new node $v_3$ and set its function value to $a$. We then delete vertices $v_1$ and $v_2$. Since the cost model only tracks the individual vertices, the cost induced by this is $a/3$ instead of $a$. As the number of intermittent vertices increases towards $\infty$, the cost would decrease towards $0$. This issue does not change any proofs of completeness of this set of elementary deformations. By constructing the cost model in this categorical way, this bug is completely fixed.
\end{remark}

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/UniversalOperations.pdf}
    \caption{\textbf{(Top):} Simple example of insert/delete operations for vertices, edges, and loops. \textbf{(Bottom):} Simple example of slide and relabel operations.}
    \label{fig:universalOperations}
\end{figure}

\section{Examples}
\label{sec:examples}

Here we discuss several examples which present the differences between the bottleneck, interleaving, functional distortion, and Reeb graph edit distance. In each, we present the original scalar field, corresponding Reeb graphs and full extended persistence diagram, as well as figures showing how each of the Reeb graph metrics can be computed.
Each of the scalar field examples are compact 2-manifolds, all without boundary except for Ex.~\ref{example:globalMaxChange}. As stated before, the universal edit distance is only defined for PL Reeb graphs. It is known, however, that each compact 2-manifold is triangulable. Furthermore, we can also construct PL functions which approximate the original function well enough such that the Reeb graphs are identical. Thus, we will show the universal edit distance for each of the examples defined below.
For the interleaving distance diagrams, we will alternate between several slightly different representations that we believe are the most enlightening for the particular example we are discussing. However, each description of the interleaving distance will use notation that is inline with the cosheaf definition.
Since the truncated interleaving distance acts similarly to the original interleaving distance due to strong equivalence (Cor.~\ref{cor:strongEquivTruncated}, we leave out this distance for all examples except for Ex.~\ref{example:globalMaxChange}.

Fig.~\ref{fig:exampleSummary} provides a visual summary of the various examples we have show. We label the value corresponding to $2d_I$ to show that none of the Reeb graph metrics pass this bound. We also show the $L^{\infty}$ distance where applicable.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/exampleSummary.pdf}
    \caption{Visual summary of the distance values attained for each example. For Example 4, we show two different choices of $m$ for the truncated interleaving distance to illustrate the affect that $m$ plays on the distance values.}
    \label{fig:exampleSummary}
\end{figure}

\subsection{Example: Scalar fields with graph isomorphic Reeb graphs and identical persistence diagrams}
\label{example:graphIsoEqPers}

Let $({\mathbb X},f)$, $({\mathbb Y},g)$ be constructible scalar fields as shown in  Fig.~\ref{fig:exampleOne}(a). Both ${\mathbb X}$ and ${\mathbb Y}$ are compact 2-manifolds without boundary. The labels $\{a_1,\ldots,a_8\}$ represent identical function values for both scalar fields. We denote the vertices of $\mathcal{R}_f$ and $\mathcal{R}_g$ corresponding to $\{a_1,\ldots,a_8\}$ as $\{v_1,\ldots v_8\}$ and $\{u_1,\ldots,u_8\}$, respectively.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleOneAlt.pdf}
    \caption{Summary figure for Ex.~\ref{example:graphIsoEqPers}. \textbf{(a)} Two scalar fields $({\mathbb X},f)$ and $({\mathbb X},g)$ with their corresponding Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ below them. To the right is the persistence diagrams of the scalar fields overlayed on top of each other. Smaller points without color indicate that these features are plotted in both diagrams. \textbf{(b)} Diagram displaying the interleaving distance between the two Reeb graphs. \textbf{(c)} Diagram displaying the optimal mappings $\Phi$,$\Psi$ for the functional distortion distance.}
    \label{fig:exampleOne}
\end{figure}

\paragraph{Bottleneck Distance} The persistence diagrams are identical, making the bottleneck distances equal to 0. That is
\[d_b(\mathcal{R}_f,\mathcal{R}_g) = d_B(\mathcal{R}_f,\mathcal{R}_g) = 0.\]

\paragraph{Interleaving Distance} Before determining the interleaving distance between these two scalar fields, recall that from Fig.~\ref{fig:graphIsoNonRGIso} we know that their Reeb graphs are isomorphic as \emph{graphs}, but not as \emph{Reeb graphs}.  Fig.~\ref{fig:nonZeroInterleaving} shows why these are not isomorphic as cosheafs as well. By  Property~\ref{p:isomorphismInvariance}, this implies that the two Reeb graphs do not have a $0$-interleaving between them.

The squares overlayed on the Reeb graphs of Fig.~\ref{fig:exampleOne}(a) represent the elements of the cosheafs at various fibers. For there to be a $\varepsilon$-interleaving, we need to construct a map from $\mathsf{F}$ to $\SS_{\varepsilon}(\mathsf{G})$ such that these components respect inclusion. In this case, our issue is that the component labeled $c_1$ eventually merges into $c_2$ in $\mathsf{F}$, but merges into $c_0$ in $\mathsf{G}$, while the rest of the components are equivalent in both. Switching the labelings of $c_0$ and $c_2$ in $\mathsf{G}$ results in a similar situation for the upper leaf.

We must choose $\varepsilon$ so that the maps $\phi:\mathsf{F} \to \SS_{\varepsilon}(\mathsf{G})$,$\psi:\mathsf{G} \to \SS_{\varepsilon}(\mathsf{F})$ respect inclusions (and are therefore well-defined morphisms between the cosheafs). Our only choice is choose $\varepsilon$ large enough so that the root of the component $c_1$ merges with the rest of the Reeb graph below the 1-cycle. Choosing $\varepsilon = \frac{1}{2}|a_4 - a_3|$ achieves this. We can see from the diagram that this allows us to choose maps $\phi$ and $\psi$ which respect inclusion and allow for $\SS_{\varepsilon}[\psi] \circ \phi = \sigma_{\mathsf{F}}^{2\varepsilon}$ and $\SS_{\varepsilon}[\phi] \circ \psi = \sigma_{\mathsf{G}}^{2\varepsilon}$. Thus, since this is the optimal choice of $\varepsilon$, we have that \[d_I(\mathcal{R}_f,\mathcal{R}_g) = \frac12(a_4-a_3).\]

\paragraph{Functional Distortion Distance} Let $\ell_f$ denote the downward leaf of $\mathcal{R}_f$ whose minimum is $v_2$ and that merges with the rest of $\mathcal{R}_f$ at $v_4$, and let $\ell_g$ be defined analogously.  To define continuous maps between $\mathcal{R}_f$ and $\mathcal{R}_g$, first note that if we remove $\ell_f$ and $\ell_g$ from $\mathcal{R}_f$ and $\mathcal{R}_g$, the Reeb graphs become isomorphic. Thus, we can define $\Phi$ as being the Reeb graph isomorphism from $\mathcal{R}_f \setminus \ell_f$ to $\mathcal{R}_g \setminus \ell_g$, and $\Psi$ as its inverse. By continuity, there is no way for us to map the bottom leaves directly to each other without disturbing the identity map that we have just defined. Thus, our best plan is to assign $\ell_f$ to be horizontally ``flattened'' as in  Fig.~\ref{fig:exampleOne}(c) and assign $\ell_g$ to analogously.

The largest point distortion then comes from the pairs $(v'_4,u'_4),(v_4,u'_4)$ (or similarly $(v'_4,u'_4),(v'_4,u_4)$). Thus, we have
\[D(\Phi,\Psi) = \lambda((v_2,u'_4),(v_4,u'_4)) = \frac12|d_f(v'_4,v_4) - d_g(u'_4,u'_4)| = \frac12(a_4-a_3).\] Since $\Phi$ and $\Psi$ are optimally chosen, \[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) = \frac12(a_4-a_3).\]

Note that we could have defined $\Phi$ and $\Psi$ such that they contracted the leaves into a single point, which would result in the same exact map distortion $D(\Phi,\Psi)$. However, this would cause $||f-g\circ\Phi||_{\infty} = ||f\circ\Psi - g||_{\infty} = (a_4-a_2)$, which would imply that $\Phi$ and $\Psi$ are not optimally chosen.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleOneRGED.pdf}
    \caption{\textbf{(a)} Reeb graph edit distance for Ex.~\ref{example:graphIsoEqPers}/Fig.~\ref{fig:exampleOne} through an insertion of a small leaf, then relabeling vertices to simultaneously increase this leaf and then flatten the leaf we intend to remove, finally followed by a deletion of the shrunken leaf. \textbf{(b)} An alternate, suboptimal sequence carrying $\Gamma_f$ to $\Gamma_g$ through a K-3 type operation followed by a K-2 operation to move the target leaf from the right side of the stem to the left side of the stem.}
    \label{fig:exampleOneRGED}
\end{figure}

\paragraph{Reeb graph edit distance.} To compute the Reeb graph edit distance $d_E$, we investigate two different edit sequences carrying $(\Gamma_f,\ell_f)$ to $(\Gamma_g,\ell_g)$. While the first sequence we show yields a lower edit cost in this case, we find it appropriate to investigate both sequences since their cost is dependent on the values of different vertices. Specifically, if the length of $e(v_2,v_4) \in E(\Gamma_f)$ and $e(u_2,u_4) \in E(\Gamma_g)$ was to increase such that $\frac12|a_4 - a_2| > |a_3 - a_2|$, the actual edit distance would be governed by the latter sequence rather than the former.

The most intuitively direct way of carrying $(\Gamma_f,\ell_f)$ to $(\Gamma_g,\ell_f)$ would be to delete the leaf $e(v_4,v_2) \in E(\Gamma_f)$ and then birth a new leaf to correspond to $e(u_4,u_2) \in E(\Gamma_g)$. As stated in Rem.~\ref{rem:spreadRelabel}, it is cheaper to first birth a flat edge, perform a relabel deformation to change both edges simultaneously, and then delete the newly flattened edge.  Fig.~\ref{fig:exampleOneRGED}(a) shows this sequence.

Let $(\Gamma_1,\ell_1) \cong (\Gamma_f, \ell_f)$. We insert the edge $e(u_4,u_2)$ such that $\ell_2(u_4) = \frac12|a_4 + a_2| + \delta$,  $\ell_2(u_2) = \frac12|a_4 + a_2| - \delta$, with $0 < \delta << 1$, making the length of this leaf $2\delta$. This $\delta$ is added strictly for purposes of aligning with the definition of elementary birth deformation which states that the introduced vertices cannot have the same function value. A relabel operation is then applied to $(\Gamma_2,\ell_2)$ so that $l_3(u_4) = a_4$, $l_3(u_2) = a_2$, $l_3(v_4) = \frac12|a_4-a_2| + \delta$, and $l_3(v_2) = \frac12|a_4-a_2| + \delta$. A death deformation is then applied to $e(v_4,v_2)$. We compute the cost of this edit sequence $S_1$ to be

\[c(S_1) = \bigg[\frac12(2\delta)\bigg] + \bigg[\frac12|a_4-a_2| - \delta\bigg] +  \bigg[\frac12(2\delta)\bigg] =  \frac12|a_4-a_2| + \delta.\] As $\delta \to 0$, we have $c(S_1) \to \frac12|a_4-a_2|$.

Fig.~\ref{fig:exampleOneRGED}(b) shows a sequence $S$ carrying $(\Gamma_f,\ell_f)$ to $(\Gamma_g,\ell_g)$ through a $K_3$-type deformation followed by a $K_2$-type deformation. Simply put, we move the leaf $e(v_2,v_4)$ to the other side of the Reeb graph. We use the $K_3$-type deformation to set $\ell_f(v_3) = \frac{1}{2}|a_4 + a_3| + \delta$ and  $\ell_f(v_4) = \frac{1}{2}|a_4 + a_3| - \delta$, where $0 < \delta << \frac{1}{2}|a_4 - a_3|$. Composing the two $K$-type deformations means that the cost of this edit sequence is
\begin{align*}
    c(S_2) = & \big[\max\{|\ell_f(v_4)-\ell_2(v_4)|,|\ell_f(v_3)-\ell_2(v_3)|\}\big] \\       & +  \big[\max\{|\ell_2(v_4)-\ell_g(v_4)|,|\ell_2(v_3)-\ell_g(v_3)|\}\big] \\
           = & |a_4-a_3|+2\delta.
\end{align*}

\noindent As we have $\delta \to 0$, we have $c(S_2) \to |a_4-a_3|$. Thus, since the Reeb graph edit distance is defined as the infimum cost among all sequences, we have \[d_E(\mathcal{R}_f,\mathcal{R}_g) = \frac12|a_4-a_2|\].

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleOneCategorical.pdf}
    \caption{\textbf{(a)} Depiction of the universal edit distance by inserting a new leaf on the leaft side and deleting the old leaf on the right side. \textbf{(b)} A suboptimal sequence for the universal edit distance is given by mapping $X_1$ and ${\mathbb X}_2$ both into the common space $\mathcal{R}_2$ which allows us to switch the leaf from the right side to the left side of the Reeb graph.}
    \label{fig:exampleOneuniversal}
\end{figure}

\paragraph{Universal Edit Distance} To compute the universal edit distance, we investigate two different zigzag diagrams which are analogous to the first and second edit sequences from Fig.~\ref{fig:exampleOneRGED}, respectively.

The zigzag diagram $z_1$ in  Fig.~\ref{fig:exampleOneuniversal}(a) consists of just a single space $X_1$ with different Reeb quotient maps going to $\mathcal{R}_1 \cong \mathcal{R}_f$ and $\mathcal{R}_2\cong \mathcal{R}_g$. The left quotient map contracts the edge $e(x_1,x_2)$ to a single point in $\mathcal{R}_1$, and maps $e(x_3,x_4)$ to $e(v_4,v_2) \in \mathcal{R}_1$. The right quotient map is defined similarly. Contracted points in $\mathcal{R}_1$ and $\mathcal{R}_2$ are such that their function value is half the distance between the root and tip of that leaf. Specifically, the function value is $\frac12|a_4-a_2|$.

If we were to construct universal deformations moving $\mathcal{R}_1$ to $\mathcal{R}_2$ in this way, we would have a relabel operation to flatten the leaf, an insert operation to add the new leaf, followed by another relabel deformation to alter the newly introduced leaf, and finally a death deformation to remove the previously flattened leaf.

To compute the cost of this sequence, first note that $X_1$ is the limit of this diagram. We have that $(f_1 \circ p_{1,1})(x_1) - (f_2 \circ p_{1,2})(x_1) = \frac12|a_4-a_2|$ and similarly for $x_2,x_3,x_4 \in X_1$. Thus, the cost of this sequence $c_{z_1}$ is $\frac12|a_4-a_2|$.

Fig.~\ref{fig:exampleOneuniversal}(b) shows an zigzag diagram $z_2$ carrying $\mathcal{R}_f$ to $\mathcal{R}_g$. We have a relabel operation, followed by two slide operations, and then a final relabel operation. As we perform the two slide operations, since no relabel operation is needed between them, the Reeb graphs $\mathcal{R}_2$ and $\mathcal{R}_3$ are identical. This implies that we could in fact shrink this zigzag diagram slightly by removing both $X_2$ and $\mathcal{R}_3$. However, removing these two pieces in the diagram will not change the final cost of the sequence since only relabel operations can affect the cost.

Given that this diagram  is the most optimal diagram carrying $\mathcal{R}_f$ to $\mathcal{R}_g$, we compute the cost by constructing the iterated pullback of $X_1,X_2$, and $X_3$. Now, let $x_1 \in X_1$ be the point along edge $e(v_4,v_5)$ such that $(f_1\circ p_{1,1})(x_1) = a_4 + \delta_0$, with $0 < \delta_0 << 1$. Let $x_2\in X_2$ be such that $(f_2\circ p_{1,2})(x_1) = (f_2\circ p_{2,2})(x_2)$, and let $x_3 \in X_3$ be such that $(f_3\circ p_{2,3})(x_2) = (f_3\circ p_{3,3})(x_3)$. This implies that $(x_1,x_2,x_3) \in X_1 \times_{\mathcal{R}_2} X_2 \times_{\mathcal{R}_3} X_3$. We can see then that $(f_4 \circ p_{3,4})(x_3) = a_3 + \delta_1$, where $\delta_1$ approaches $0$ as $\delta_0$ approaches $0$. Thus, as $\delta_0 \to 0$, we have $c_{z_2} \to |a_4-a_3|$. Finally, as in the Reeb graph edit distance case, this implies that \[\delta_E(\mathcal{R}_f,\mathcal{R}_g) = \frac12|a_4-a_2|.\]

Note that the universal edit distance does require us to view these Reeb graphs as topological spaces rather than just combinatorial Reeb graphs. If we were only considering the function values associated with the vertices of the graph, we can see that the maximum change in function value would be the total distance covered by either $v_3$ or $v_4$, which in this case is only $\frac{1}{2}|a_4-a_3|$.

\subsection{Example: Stretched Tori results in equality of metrics.}
\label{example:stretchedTori}

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleTwo.pdf}
    \caption{Summary figure for Ex.~\ref{example:stretchedTori} \textbf{(a)} Two scalar fields $({\mathbb X},f)$ and $({\mathbb X},g)$ with their corresponding Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ below them. To the right is the persistence diagrams of the scalar fields overlayed on top of each other. Smaller points without color indicate that these features are plotted in both diagrams. The colored points indicate features which are unique to that diagram. \textbf{(b)} The interleaving distance between the two Reeb graphs. We choose to lay these mappings horizontally instead of interleaved as in Ex.~\ref{example:graphIsoEqPers}(b) to more adequately express the mappings between the pre-cosheafs. \textbf{(c)} Optimal mappings $\Phi$,$\Psi$ for the functional distortion distance. \textbf{(d)} Optimal sequence of edit operations for the Reeb graph edit distance. \textbf{(e)} Shortest and optimal zigzag diagram for the universal edit distance.}
    \label{fig:exampleTwo}
\end{figure}

Let $({\mathbb X},f)$ and $({\mathbb X},g)$ be two scalar fields defined as in  Fig.~\ref{fig:exampleTwo}. Let $\{v_1,\ldots,v_4\}$ and $\{u_1,\ldots,u_4\}$ denote the vertices of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively, defined in increasing function value order. Note that while these scalar fields are defined on the same ${\mathbb X}$ (a torus), we assign $f$ and $g$ such that $a_2 = f(v_2) > g(u_2) = a'_2$ and $a_3 = f(v_3) < g(v_3) = a'_3$.

\paragraph{Bottleneck Distance} We can see that the persistence diagrams for the tori are quite similar. The smallest square centered at $(a_3,a_2)$ which encompasses $(a'_3,a'_2)$ has side length equal to $a'_3 - a_3$, implying that the bottleneck distance between these diagrams is $d_{B^1} = a'_3 - a_3$. Since the 0 dimensional extended diagrams are identical, we have that \[\dB{}(\mathcal{R}_f,\mathcal{R}_g) = a'_3-a_3.\]

\paragraph{Interleaving Distance} We claim that $\varepsilon = a'_3 - a_3$. To show this, first note that there will be no issue with mapping the correct components so that they respect inclusion since the spaces are identical besides the stretching of the loop. Our concern is that, in the interleaving, we may have a point $a\in \mathbb{R}$ such that $|\mathsf{G}(a^{\delta})| = |\mathcal{S}_{2\varepsilon}(\mathsf{G})(a^{\delta})| = 2$ and $|\mathcal{S}_{\varepsilon}(\mathsf{F})(a^{\delta})| = 1$, where $a^{\delta} = (a-\delta,a+\delta)$ with $\delta > 0$. This would mean the map $\psi \circ \mathcal{S}_{\varepsilon}[\phi] \neq \sigma^{2\varepsilon}_{\mathsf{G}}$ since the image of $\psi$ would be one component, causing the image of $\psi \circ \mathcal{S}_{\varepsilon}[\phi]$ to be one component as well, while the image of $\sigma^{2\varepsilon}_{\mathsf{G}}$ would be two components.

Smoothing this loop by $\varepsilon$ will cause the maxima node to shift down by $\varepsilon$ and the bottom node to be shifted up by $\varepsilon$. Thus, the values of the nodes of $\mathcal{S}_{\varepsilon}(\mathsf{F})$ would have values $a_3 - \varepsilon$ and $a_2+\varepsilon$. Similarly, the nodes for $\mathcal{S}_{2\varepsilon}(\mathsf{G})$ would have values $a'_3-2\varepsilon$ and $a'_2+2\varepsilon$.

If $\varepsilon = a'_3 - a_3$, we have $2a_3 - a'_3$, $a_2+a'_3-a_3$, $2a_3-a'_3$, and $a'_2 + 2a'_3 - 2a_3$ for the respective nodes. Thus, if $x\in \mathbb{R}$ satisfies $2a_3 - a'_3 > x > a_2+a'_3-a_3$, then $|\mathcal{S}_{\varepsilon}(\mathsf{F})(x^{\delta})| = 2$. Similarly, if $x \in \mathbb{R}$  satisfies $2a_3-a'_3  > x > a'_2+2a'_3-2a_3$, we have $|\mathcal{S}_{2\varepsilon}(\mathsf{G})(x^{\delta})| = |\mathsf{G}(x^{\delta})| = 2$. Since $a'_3 - a_3 > a_2 - a'_2$, we have $a'_2+2a'_3-2a_3 > a_2 + a'_3 - a_3$.

From this, we guarantee $\varepsilon = a'_3 - a_3$ will provide us an $\varepsilon$-interleaving by observing that $(2a_3-a'_3,a'_2+2a'_3-2a_3) \subset (2a_3 - a'_3, a_2+a'_3-a_3)$. We leave the other direction to the interested reader. Thus, \[d_I(\mathcal{R}_f,\mathcal{R}_g) = a'_3 - a_3.\]

\paragraph{Functional Distortion Distance} We can define optimal continuous maps $\Phi = \Psi^{-1}$ between $\mathcal{R}_f$ and $\mathcal{R}_g$ by stretching $\mathcal{R}_f$ so that $v_2 \mapsto u_2$ and $v_3 \mapsto u_3$, as depicted in  Fig.~\ref{fig:exampleTwo}(c). This implies that $D(\Phi,\Psi) = \frac{1}{2}(a'_3 - a_3)$, since the max point distortion is $\max\{|f(v_2)-g(v_2)|,|f(v_3)-g(v_3)|\}$. However, note that $||f - g \circ \Psi||_{\infty} = ||f \circ \Psi - g||_{\infty} = |f(v_3)-f(u_3)| = a'_3 - a_3$. Thus, the functional distortion distance between $\mathcal{R}_f$ and $\mathcal{R}_g$ is \[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) = a'_3 - a_3\].

\paragraph{Reeb Graph Edit Distance} Let $(\Gamma_f,\ell_f) = (\Gamma_1,\ell_1)$ and $(\Gamma_g,\ell_g) = (\Gamma_2,\ell_2)$ be the combinatorial Reeb graphs of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively.  Fig.~\ref{fig:exampleOne}(d) shows the simple, optimal sequence $S$ of edit operations to carry $\Gamma_f$ to $\Gamma_g$ consisting of one relabel operation. The Reeb graph edit distance takes the max function shift in these two relabelings, which is the shift from $a_3$ to $a'_3$ for node $v_3$. Thus, \[d_E = a'_3-a_3.\]

\paragraph{Universal Edit Distance} Similar to the Reeb graph edit distance, the universal edit distance consists of one relabel operation as in Dg domains of these~\ref{dgm:relabel}. The maximum function value change is then from $a_3$ to $a'_3$ for node $v_3$. Thus, \[\delta_E = a'_3 - a_3\].

\subsection{Example: Genus-2 surface and simply connected domain with leaves}
\label{example:compound}

Let $({\mathbb X},f)$ and $({\mathbb Y},g)$ be the scalar fields shown in  Fig.~\ref{fig:exampleThree}(a). Let $\{v_1,\ldots,v_6\}$ and $\{u_1,\ldots,u_6\}$ denote the vertices of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively. As compared to previous examples, the domains of these two scalar fields are not homeomorphic to one another.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleThree.pdf}
    \caption{Summary figure for Ex.~\ref{example:compound}. \textbf{(a)} Two scalar fields $({\mathbb X},f)$ and $({\mathbb X},g)$ with their corresponding Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ below them. To the right is the persistence diagrams of the scalar fields overlayed on top of each other. Smaller points without color indicate that these features are plotted in both diagrams. The colored points indicate features with are unique to that diagram. \textbf{(b)} Diagram displaying the interleaving distance between the two Reeb graphs. We choose to lay these mappings horizontally instead of interleaved as in Ex.~\ref{example:graphIsoEqPers}\textbf{(b)} to more adequately express the mappings between the pre-cosheafs. \textbf{(c)} Diagram displaying the optimal mappings $\Phi$,$\Psi$ for the functional distortion distance.}
    \label{fig:exampleThree}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleThreePt2.pdf}
    \caption{Figure depicting the universal edit distance for Ex.~\ref{example:compound}. \textbf{(a)} Zigzag diagram carrying $\mathcal{R}_f$ to $\mathcal{R}_g$. \textbf{(b)} Universal deformations which would be involved to carry $X_1$ to $X_2$. Since these deformations have no relabels, we are able to consolidate this entire sequence into just $X_1 \to \mathcal{R}_2 \to X_2$.}
    \label{fig:exampleThreePt2}
\end{figure}

\paragraph{Bottleneck Distance} We can see in the persistence diagrams that the best matchings for each point is either to its duplicate in the other diagram or to the diagonal. This makes the largest distance in this matching to be $||(a_5,a_7)-(\frac{a_5+a_7}{2},\frac{a_5+a_7}{2})||_{\infty}$, implying that \[\dB{}(\mathcal{R}_f,\mathcal{R}_g) = \frac12(a_7-a_5).\]

\paragraph{Interleaving Distance} Fig.~\ref{fig:exampleThree}(b) depicts an $\varepsilon$-interleaving between the two Reeb graphs. The color coding illustrates how we can partition $\mathsf{F}$ and $\mathsf{G}$ into pieces where the number of connected components changes. We choose $\varepsilon$ to be $\frac{1}{2}(a_8-a_6)$ so that interval $I$ corresponds to only one component in $\mathcal{S}_{2\varepsilon}(\mathsf{G})$ since it will always correspond to only one component in $\mathcal{S}_{\varepsilon}(\mathsf{F})$. This choice of $\varepsilon$ will also cause each hole to be completely closed in $\mathcal{S}_{2\varepsilon}(\mathsf{F})$, meaning the equality $\mathcal{S}_{\varepsilon}[\psi] \circ \phi = \sigma^{2\varepsilon}_{\mathsf{F}}$ is guaranteed. Thus, the interleaving distance is \[d_I(\mathcal{R}_f,\mathcal{R}_g) = \frac{1}{2}(a_8-a_6)\].

\paragraph{Functional Distortion Distance} In Fig.~\ref{fig:exampleThree}(c), we choose $\Phi$ to map every point straight across to $\mathcal{R}_g$ and choose $\Psi$ to do the same. Focusing on $\Phi$, we can see that the two points in the center of the loop between $v_4$ and $v_5$ are mapped to the same point on $\mathcal{R}_g$. Let $x_1$ and $x_2$ denote the points such that $f(x_1) = f(x_2) = \frac12(f(v_5)+f(v_4)) = \frac12(a_7+a_5)$. Thus, the height of any path from $x_1$ to $x_2$ is $|f(v_5) - \frac12(f(v_5)+f(v_4))| = |\frac12(f(v_5)+f(v_4)) - f(v_4)| = \frac12(a_7-a_5)$, meaning the point distortion $\lambda((x_1,\Phi(x_1)),(x_2,\Phi(x_2))) = \frac12(a_7-a_5)$.

From $\Psi$, we can see that $d_g(u_5,u'_5) = a_8 - a_6$ and $\Psi(u_5) = \Psi(u'_5)$. Thus, $\lambda((\Psi(u_5),u_5),(\Psi(u'_5),u_5)) = a_8 - a_6 > \frac{1}{2}(a_7-a_5)$. Thus, $D(\Phi,\Psi) = \frac{1}{2}(a_8-a_6)$. Since $||f-g\circ \Phi||_{\infty} = ||f\circ\Psi - g||_{\infty} = 0$ due to our functions not distorting the function values at all, we have that \[d_{FD} = \frac{1}{2}(a_8-a_6)\].

\paragraph{Reeb Graph Edit Distance} Since these Reeb graphs are constructed from two non-homeomorphic spaces, the Reeb graph edit distance is not defined.

\paragraph{Universal Edit Distance}
Fig.~\ref{fig:exampleThreePt2}(a) shows the optimal zigzag diagram carrying $\mathcal{R}_f \cong \mathcal{R}_1$ to $\mathcal{R}_g \cong \mathcal{R}_2$. There is no single space $X$ which is able to map the cycles of $\mathcal{R}_f$ to the leaves of $\mathcal{R}_g$, meaning we have to ``delete" the 1-cycles and then ``insert" the two leaves. To do this, we have two spaces $X_1$ and $X_2$ which map to a common $\mathcal{R}_2$ where the cycles are removed and the leaves are yet to be inserted. The only condition on $X_1$ and $X_2$ is that the features have equal endpoints so that they can all contract to single points in $\mathcal{R}_2$. The universal edit distance is then \[\delta_E = \frac12|f(v_5) - f(v_4)| = \frac12|a_7 - a_5|,\] which is half the size of the largest 1-cycle in $\mathcal{R}_f$.

Fig.~\ref{fig:exampleFourEdit}(b) depcits the universal deformations that are involved in carrying $X_1$ to $X_2$. Since there are no relabels in this sequence, we are able to consolidate all of this information into a much smaller zigzag diagram.

\paragraph{Observations} This is an example of two Reeb graphs whose FDD and interleaving distance is strictly less than the bottleneck distance. This also shows how each metric depdendent on the ``largest" features in each Reeb graph rather than being dependent on multiple features. In fact, if $\mathcal{R}_f$ were replaced with a single edge from $v_1$ to $v_6$, the interleaving distance and FDD would both be unchanged, the bottleneck distance would be $\frac{1}{2}(a_8-a_6)$, and the universal edit distance would be $(a_8-a_6)$. Similarly, if $\mathcal{R}_g$ were replaced with a single edge, the bottleneck distance and universal edit distance would remain unchanged, and both the interleaving distance and FDD would be $\frac{1}{4}(a_7-a_5)$.

\subsection{Example: Stretching local maximum past the global maximum}
\label{example:globalMaxChange}

Let $({\mathbb X},f)$ and $({\mathbb X},g)$ be the scalar fields shown in  Fig.~\ref{fig:exampleFour}(a). Let $\{v_1,\ldots,v_8\}$ and $\{u_1,\ldots,u_8\}$ denote the vertices of $\mathcal{R}_f$ and $\mathcal{R}_g$, respectively. Both scalar fields are defined on the same domain. The only change from $({\mathbb X},f)$ to $({\mathbb X},g)$ is that the local maximum located at $v_7$ is assigned to $a_9$ instead of $a_7$ as its function value.  The peak surrounding $v_7$ is scaled to match.  This change ultimately makes $u_8$ the new global maximum of $({\mathbb X},g)$.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleFour.pdf}
    \caption{Summary figure for Ex.~\ref{example:globalMaxChange}.\textbf{(a)} Two scalar fields $({\mathbb X},f)$ and $({\mathbb X},g)$ with their corresponding Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ below them. To the right is the persistence diagrams of the scalar fields overlayed on top of each other. Smaller points without color indicate that these features are plotted in both diagrams. The colored points indicate features with are unique to that diagram. \textbf{(b)} Diagram displaying the interleaving distance between the two Reeb graphs. \textbf{(c)} Diagram displaying the optimal mapping $\Phi$ for the functional distortion distance. The map $\Psi$ is implied. \label{fig:exampleFour}}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/ExampleFourEdit.pdf}
    \caption{Zigzag diagram depicting the optimal edit sequence carrying $\mathcal{R}_1 \cong \mathcal{R}_f$ to $\mathcal{R}_3 \cong \mathcal{R}_g$.}
    \label{fig:exampleFourEdit}
\end{figure}

\paragraph{Bottleneck Distance} The coordinate in the persistence diagram which represents the global maximum and global minimum pairing is $(a_1,a_8)$. Since the global maximum has changed in $({\mathbb X},g)$, the pair is now represented as $(a_1,a_9)$. The value $a_9-a_8$ is the largest difference in the best matching for these persistence diagrams, making the bottleneck distance \[\dB{}(\mathcal{R}_f,\mathcal{R}_g) = a_9-a_8.\]

This is equivalent to the situation where we take the global maximum of $({\mathbb X},f)$ and raise it to have function value $a_9$. In essence, this bottleneck distance has measured that the global maximum has increased in value, but \emph{not} necessarily that the global maximum has changed in position.

\paragraph{Interleaving Distance} We have, at this point, gained some intuition that the interleaving distance should be at most determined by the growth in this single maxima. Let $x_f$ represent the leaf of $\mathcal{R}_f$ beginning at $v_5$ and ending at $v_8$, let $y_f$ be the leaf beginning at $v_4$ and ending at $v_7$, $x_g$ be the leaf of $\mathcal{R}_g$ beginning at $u_4$ and ending at $u_8$, and let $y_g$ be the leaf beginning at $u_5$ and ending at $u_7$. Since $x_g$ ends at a higher function value than $x_f$, we know that there cannot exist a $0$-interleaving because $\mathsf{G}(a^{\delta})$, where $a_7 < a < a_9$, will have two components and $\mathcal{S}_0(\mathsf{F})(a^{\delta}) = \mathsf{F}(a^{\delta})$ will only have one. Because of this, $\varepsilon \geq |a_9-a_8|$, since any smaller causes the same situation. Verifying, however, that this is the true interleaving distance requires us to check the continuity around the roots of these two leaves. Since the distance between the root nodes of $x_f$ and $y_f$ is less than $\varepsilon$, we are allowed to map the leaf $x_f$ to $x_g$ and $y_f$ to $y_g$ without breaking continuity. Thus, \[d_I(\mathcal{R}_f,\mathcal{R}_g) = a_9-a_8\].

\paragraph{Truncated Interleaving Distance} Just as in the standard interleaving case, to find a $e$-interleaving for truncated interleaving, we need to apply the truncated smoothing operator $\mathcal{S}^{m\varepsilon}_{\varepsilon}$ such that the resulting graph $\mathcal{S}^{m\varepsilon}_{e}(\mathsf{F})$ is stretched enough so that $v_8$ has a new function value of $a_9$. Note that smoothing by $\varepsilon = a_9-a_8$ is not enough to construct an interleaving since we will then truncate by $m\varepsilon$ -- making the highest function value of $\mathcal{S}^{m\varepsilon}_{e}(\mathsf{F})$ to be $a_9 - m(a_9-a_8)$. Thus, we must choose a value of $\varepsilon$ for a fixed $m$ such that $\varepsilon - m\varepsilon \geq a_9-a_8$, implying that $\varepsilon \geq \frac{a_9-a_8}{1-m}$.

From Cor.~\ref{cor:strongEquivTruncated}, we know that $d_I(\mathcal{R}_f,\mathcal{R}_g) = a_9-a_8 \leq d^m_I(\mathcal{R}_g,\mathcal{R}_g) \leq \frac{1}{1-m}(a_9-a_8)$. Thus, \[d_I^m(\mathcal{R}_g,\mathcal{R}_g) = \frac{1}{1-m}(a_9-a_8)\].

\paragraph{Functional Distortion Distance} The continuous maps between these Reeb graphs involve mapping the leaf corresponding to the global maximum of $\mathcal{R}_f$ to the leaf corresponding to the global maximum of $\mathcal{R}_g$.  Fig.~\ref{fig:exampleFour}(c) depicts the optimal mapping. Note that we only show the mapping $\Phi$ since the other map $\Psi$ can be easily inferred from $\Phi$.

In this mapping, the single-edge path from $v_5$ to $v_8$ is mapped to the path from $u_5$ to $u_8$. Additionally, the path from $v_5$ to $u_1$ is mapped to $u_5$ to $u_1$. This means that the path from $u_5$ to $u_4$ is covered twice. Without overlapping these paths (or overlapping two other paths in a similar configuration), we would not have a continuous mapping.

From this mapping, we can see that the functional distortion distance is the change in function value due to mapping $v_8$ to $u_8$, i.e. \[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) = |a_9-a_8|.\]

One thing to keep in mind is that this scalar field does in fact have a boundary, as compared to every other example that we generated. As stated in Rem.~\ref{rem:boundaryRemark}, this can complicate the continuity of our maps $\Phi,\Psi$ if we do not take into account which pieces of the Reeb graph are also boundaries. Since vertex $v_2$ is the minima of $({\mathbb X},f)$ which lies on its boundary, we can conclude that the entire leaf containing $v_2$ is a non-open set. Thus, if our map $\Psi$ was constructed in such a way that this was the pre-image of some open set in $\mathbb{R}_g$, it would not in fact be continuous. We avoid this situation by making sure that boundary nodes of $\mathbb{R}_f$ are mapped to boundary nodes of $\mathbb{R}_g$, and vice versa.

\paragraph{Reeb Graph Edit Distance}
As previously noted in Sec.~\ref{sec:EditDistanceTake1}, the older Reeb graph edit distance is defined only on 2-manifolds without boundary.
Since this example does in fact have a boundary, we do not consider the Reeb graph edit distance further, although it is interesting to note that in some cases a sequence of edits is possible in this setting as well.

\paragraph{Universal Edit Distance} We can trivially deform $\mathcal{R}_f$ to $\mathcal{R}_g$ using a single relabel operation which relabels $v_7$ to have function value $a_9$. However, this leads to a suboptimal value. The best course of action is to switch the roots of the two maxima $v_8$ and $v_7$, then apply a relabel to stretch $v_7$ and $v_8$ to have function values $a_8$ and $a_9$, respectively. Thus, \[\delta_E(\mathcal{R}_f,\mathcal{R}_g) = a_9-a_8\], since the relabeling needed to switch the adjacencies of the leaves is much less. We illustrate this edit sequence in Fig.~\ref{fig:exampleFourEdit}.

\paragraph{Observations} This is our first example where the Reeb graphs are \textbf{contour trees} -- the loop free variant of the Reeb graph, which prevents the existence of points in $\text{Ext}_1$. Furthermore, while each of the distances ended up being equal in value, there are still several intricacies that are involved in computing the Reeb graph metrics. We can view each of these computations as trying to define a matching between the leaves of the contour trees and computing the cost of doing so. For example, in the universal edit distance case, we assign the leaf $e(v_4,v_7)$ to $e(u_5,u_7)$. However, since the $e(v_4,v_7)$ is not adjacent to $e(v_4,v_6)$ but $e(u_5,u_7)$ \emph{is} adjacent to the corresponding leaf $e(u_5,u_6)$, the adjacencies of the leaves must be changed. In order to do this, we perform the slide operation. Since this slide operation induces a relabeling \emph{less} than that of relabeling $v_8$ to $u_8$, the cost is essentially ignored. This is exactly the same process as in the interleaving and functional distortion distance -- the cost of the corresponding ``slide" operation is less than the cost of the other operations and is therefore not accounted for. In the bottleneck distance case, no matter how complicated these adjacencies become, they will never be taken into account.

\section{Functional Distortion Distance}
\label{sec:FDD}

\subsection{History}

The functional distortion distance was first defined as a metric in \cite{Bauer2014}, inspired from the well-known Gromov-Hausdorff distance which was first introduced in \cite{Gromov1981}. The Gromov-Hausdorff distance is a way to measure the distance between two Banach or metric spaces. More formally, suppose $A$ and $B$ are two metric spaces and let $i_A:A \to Z$ and $i_B:B \to Z$ be isometric embeddings into a common metric space $Z$. We can then find the Hausdorff distance between the embedded spaces: $d_H(i_A(A),i_B(B))$.

The goal of the Gromov-Hausdorff distance is then to find the minimum Hausdorff distance achieved when ranging over all possible embeddings and the common space to which they are embedded. Intuitively, we are trying to determine a common space where we can embed both $A$ and $B$, while preserving the integrity of the spaces (hence the embeddings being isometries), such that the $A$ and $B$ fit nicely together. We can picture $A$ and $B$ as being two crumpled up pieces of paper (of varying sizes) and our common metric space to be a flat surface. One way to measure the difference in sizes between $A$ and $B$ is to stretch both out flat onto the surface and then compare them in their flattened form. Trying to determine the sizes while the paper is still crumpled would be a much more difficult task.
The Gromov-Hausdorff (GH) distance has multiple different equivalent definitions; see \cite{Memoli2008}. Functional distortion distance (FDD) borrows from a very specific variation of the GH distance.

\subsection{Definition}

Here, we break down the definition of FDD into several parts which we will stitch together to form the final definition. We begin by noting that the functional distortion distance is defined on tame scalar fields and we will assume that each Reeb graph discussed here is a tame Reeb graph; see Def.~\ref{def:tame}

\begin{definition}
Let $u,v \in \mathcal{R}_f$ (not necessarily vertices) and let $\pi$ be a continuous path between $u$ and $v$, denoted $u\rightsquigarrow v$. The \textbf{range} of this path is the interval $\emph{range}(\pi) = [\min_{x\in\pi}f(x),\max_{x\in\pi}f(x)]$. The \textbf{height} is the length of the range, denoted $\emph{height}(\pi) = \max_{x\in\pi}f(x) - \min_{x\in\pi}f(x)$. We define the distance between $u$ and $v$ to be \[d_f(u,v) = \min_{\pi:u\rightsquigarrow v}\emph{height}(\pi),\]
where $\pi$ ranges over all continuous paths from $u$ to $v$.
\end{definition}
\begin{definition}
Let $\Phi:\mathcal{R}_f \to \mathcal{R}_g$, $\Psi:\mathcal{R}_f \to \mathcal{R}_g$ be two continuous maps.\footnote{These continuous maps need not be function preserving like in the category of Reeb graphs. In other words, these maps are not well-defined morphisms between $\mathcal{R}_f$ and $\mathcal{R}_g$ as objects in \ensuremath{\mathbf{Reeb}}.} We define the \textbf{supergraph} of $\Phi$ and $\Psi$ as \[G(\Phi,\Psi) = \{(x,\Phi(x)):x\in\mathcal{R}_f\}\cup\{(\Psi(y),y):y\in\mathcal{R}_g\}.\]
\end{definition}
$G(\Phi,\Psi)$ is the union of the two graphs of $\Phi$ and $\Psi$.
\begin{definition}
The \textbf{point distortion} $\lambda$ between $(x,y),(x',y') \in G(\Phi,\Psi)$ is defined as \[\lambda((x,y),(x',y')) = \frac12|d_f(x,x') - d_g(y,y')|.\]
The \textbf{map distortion} $D(\Phi,\Psi)$ between $\mathcal{R}_f$ and $\mathcal{R}_g$ is the supremum of point distortions ranging over all possible pairs in the supergraph $G(\Phi,\Psi)$. That is, \[D(\Phi,\Psi) = \sup_{(x,y),(x',y') \in G(\Phi,\Psi)}\lambda((x,y),(x',y')).\]
\end{definition}
In essence, this distance will measure how much each Reeb graph is being altered to map into the other Reeb graph. For example, if $x$ and $x'$ are relatively close (in terms of $d_f$) but their outputs under $\Phi$ are far apart (in terms of $d_g$), then this distance will be larger. This distance finds the worst case scenario where two points are close on one Reeb graph and their correspondences are far on the other. Keep in mind that there are two maps $\Phi$ and $\Psi$. Thus, even if both maps are non-surjective, every point of each Reeb graph still has at least one correspondence in the supergraph $G(\Phi,\Psi)$.

\begin{example}\label{example:FDDExample}
Fig.~\ref{fig:MapDistortionExamples} displays two different pairs of continuous maps between $\mathcal{R}_f$ and $\mathcal{R}_g$. The functions $f$ and $g$ are height functions which map each point of $\mathcal{R}_f$ and $\mathcal{R}_g$ horizontally to the real line. So, for example, $f(a_1) = g(b_1)$ and $f(a_3) = g(b_4)$. We assume here that the spaces ${\mathbb X}$ and ${\mathbb Y}$ are compact, 2-manifolds without boundary.

In $\mathbf{(a)}$, the map $\Phi$ maps like an isometry up to $a_2$, where it then maps the rest of $\mathcal{R}_f$ into the leaf of $\mathcal{R}_g$.  The point distortion between the points $(a_3,b_3)$ and $(a_2,b_2)$ would then be $|d_f(a_3,a_2)-d_g(b_3,b_2)| = f(a_3)-g(b_3)$. For $\Psi$, the map also acts like an isometry, except the leaf is collapsed, mapping horizontally to $\mathcal{R}_f$. In this case, the supergraph contains the points $(a'_2,b'_3)$ and $(a'_2,b_3)$. Thus, the point distortion between these would be $|d_f(a'_2,a'_2) - d_g(b'_3,b_3)| = g(b_3)-g(b_2)$. We can check that other pairs of points from the supergraph will not lead to a higher map distortion. Therefore, $D(\Phi,\Psi) = \max\{f(a_3)-g(b_3),g(b_3)-g(b_2)\}$.

\end{example}

\begin{definition}
The \textbf{functional distortion distance} is defined as \[d_{FD}(\mathcal{R}_f,\mathcal{R}_g) = \inf_{\Phi,\Psi}\max\{D(\Phi,\Psi),||f-g\circ\Phi||_{\infty},||f\circ\Psi -g||_{\infty}\},\] where $\Phi$ and $\Psi$ range over all continuous maps between $\mathcal{R}_f$ and $\mathcal{R}_g$.
\end{definition}

If $\Phi$ and $\Psi$ are translations or negations, the distances $d_f$ and $d_g$ are not affected since these will preserve the relative closeness of the pairs $(x,x')$ and $(y,y')$. In this case, $D(\Phi,\Psi)$ would be 0. The two terms $||f-g\circ\Phi||_{\infty}$ and $||f\circ\Psi-g||$ are introduced to address this fact. They measure the length of the translation or similar isometries. See Fig.~\ref{fig:fddIsometryExamples}(a) for an example of translation, and Fig.~\ref{fig:fddIsometryExamples}(b) for a negation example.

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/FDDMappingExample.pdf}
    \caption{Two examples of continuous maps between Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$. Dotted lines indicate the correspondences that these maps are creating, while the color indicates which section we are referring to.  $\mathbf{(a)}$ The map $\Phi$ distorts $\mathcal{R}_f$ to fit into the leaf on the right side. The map $\Psi$ maps each value straight across. $\mathbf{(b)}$ The map $\Phi$ is an isometry, which will not alter the distortion alone. The distortion will be solely be based on $\Psi$, which is almost an isometry except for collapsing the leaf to a single point. It turns out that the map contracting the leaf to a single base point at $a_2$ will result in an equivalent distortion value to mapping it horizontally as in in $\mathbf{(a)}$.}
    \label{fig:MapDistortionExamples}
\end{figure}

In Fig.~\ref{fig:MapDistortionExamples}(b), the map $\Phi$ is an isometry and therefore no points in the supergraph which come from $\Phi$ will contribute to the distortion value. The map $\Psi$ is close to an isometry besides contracting the leaf to a single point. The point distortion between the pairs $(a_2,b_2)$ and $(a_2,b_3)$ is simply $g(b_3)-g(b_2)$. Note that this is the same distortion value which was achieved in part $\mathbf{(a)}$ when we mapped the leaf straight across to $\mathcal{R}_f$. This comes from the definition of $d_g$ which only looks at the height of the path that is traversed from one point to the next and does not take into account the total distance traversed. However, note that contracting this leaf to a single point at the base of the leaf causes the value of $||f\circ\Psi-g||_{\infty}$ to be at least $g(b_3)-f(a_2)$. In Fig.~\ref{fig:MapDistortionExamples}$(a)$, this value is $||f\circ\Psi-g||_{\infty} = 0$ since $\Psi$ is \textbf{function preserving}.

\begin{remark}
\label{rem:boundaryRemark}
When finding continuous maps between two topological Reeb graphs, it is important to remember that the topology defined on the Reeb graph is quotient topology induced by the original space ${\mathbb X}$. Let $\mathcal{R}_g$ be as in Fig.~\ref{fig:MapDistortionExamples} and let $\Psi$ be the same map constructed for Fig.~\ref{fig:MapDistortionExamples}(b). Let $p$ be the quotient map carrying ${\mathbb X}$ to $\mathcal{R}_g$ and let $U$ be any open set containing $a_2$. Then, $\Psi^{-1}(U)$ contains the entire leaf in $\mathcal{R}_g$ from $b_2$ to $b_3$. Whether this set is open depends on the structure of the manifold ${\mathbb X}$. Recall that in Ex.~\ref{example:FDDExample}, $\mathcal{R}_f$ and $\mathcal{R}_g$ are both stated to be Reeb graphs of compact, 2-manifolds without boundary. In this case, $p^{-1}(\Psi^{-1}(U))$ will be an open set since any open set $V$ surrounding a point $x$ on the leaf will also be contained within the leaf. Thus, by definition of the quotient map, the set $\Psi^{-1}(U)$ is also open. From this, one can draw the conclusion that if ${\mathbb X}$ has no boundary, then the space $\mathcal{R}_g$ also has no boundary. It is important to keep this in mind when handling continuous maps between Reeb graphs where the boundary consists of a subset of these vertices.
\end{remark}

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/FDDIsometryExamples.pdf}
    \caption{$\mathbf{(a)}$ An example of maps where $\Phi$ is a translation and $\Phi = \Psi^{-1}$. In this, $d_f(x,x') = \delta = d_g(y,y')$, which implies that $D(\Phi,\Psi) = 0$. Without the $||f-g\circ\Phi||_{\infty}$ and $||f\circ\Psi -g||_{\infty}$ terms, the functional distortion distance between these two Reeb graphs would be 0. With these terms included, we can see that the functional distortion distance will be $\delta$, which is equal to the magnitude of the translation. $\mathbf{(b)}$ An example of maps where $\Phi$ and $\Psi$ are negations of each other. Because of this, the, the point distortion between any two pairs of points will always be 0.}
    \label{fig:fddIsometryExamples}
\end{figure}

\section{Interleaving Distance}
\label{sec:interleaving}

\subsection{History}

The interleaving distance on Reeb graphs takes root in earlier work that defines the interleaving distance for persistence modules \cite{Chazal2009b},
and is heavily inspired by the subsequent category theoretic treatment \cite{Bubenik2014,Bubenik2014a}.
It intuitively captures distance between two \textbf{cosheaves} $\mathsf{F}$ and $\mathsf{G}$ representing the two Reeb graphs by defining an approximate isomorphism between them, known as an $\varepsilon$-interleaving. The distance is then defined as being the infimum $\varepsilon$ such that there exists an $\varepsilon$-interleaving between $\mathsf{F}$ and $\mathsf{G}$.

In order to utilize interleavings to define a distance measure on Reeb graphs, we can encode the data of a Reeb graph in a constructible set-valued cosheaf \cite{Curry2014,Curry2015a,Curry2016}.
In fact, it is known that this metric is a special case of a more general theory of interleaving distances given on a \textit{category with a flow} \cite{deSilva2018,Stefanou2018, Cruz2019}; this more general theory also encompasses other metrics including the $\ell_\infty$ distance on points or functions, regular Hausdorff distance, and the Gromov-Hausdorff distance \cite{Stefanou2018,Bubenik2017a}.

Interleaving metrics have been studied in the context of
$\mathbb{R}$-spaces \cite{Blumberg2017},
multiparameter persistence modules \cite{Lesnick2015},
merge trees \cite{Morozov2013}, and
formigrams \cite{Kim2017,Kim2019a},
and on more general category theoretic constructions \cite{Botnan2020,Scoccola2020a}, as well as developed for Reeb graphs~\cite{deSilva2016,Chambers2021}.
There are also interesting restrictions to labeled merge trees, where one can pass to a matrix representation and show that the interleaving distance is equivalent to the point-wise $\ell_\infty$ distance
\cite{Munch2019,Gasparovic2019,Yan2019a,Stefanou2020}. Furthermore, the interleaving distance has been used in evaluating the quality of the mapper graph \cite{Singh2007}, which can be proven to be a approximation of the Reeb graph using this metric \cite{Munch2016,Brown2019}.

\subsection{Definition}

We can construct a category of Reeb graphs, denoted as $\mathbf{Reeb}$, by defining the objects to be constructible Reeb graphs and the \textbf{morphisms} to be continuous, function preserving maps; see Def.~\ref{def:functionPreservingReebGraphIso}. It turns out that this category is equivalent to the category of \textbf{cosheaves}. We provide an abridged construction of the category of cosheaves by first introducing the notion of \textbf{pre-cosheaves}.

A pre-cosheaf for our purposes\footnote{In general, we can define pre-cosheaves where the domain category is the open sets of any topological space and the range category is unrestricted, but is most commonly defined to be the category of vector spaces.} is a functor $\mathsf{F}$ from the category of connected intervals on the real line $\mathbf{Int}$ to the category of sets $\mathbf{Set}$. Intuitively, it is a way to assign data to the open intervals of the real line in a way that respects inclusion of the intervals. Given a constructible Reeb graph $\mathcal{R}_f$, we can construct its pre-cosheaf $\mathsf{F}$ by the formulas
\[\mathsf{F}(I) = \pi_0(f^{-1}(I)), \hspace{0.5in} \mathsf{F}[I\subseteq J] = \pi_0[f^{-1}(I) \subseteq f^{-1}(J)],\]
where $\pi_0(U)$ is the set of path connected components of the space $U$. Figure \ref{fig:reebToCosheaf} provides a depiction of converting a Reeb graph $\mathcal{R}_f$ to its pre-cosheaf $\mathsf{F}$. The \textbf{category of pre-cosheaves} is denoted as $\ensuremath{\mathbf{Pre}}$.

It turns out that the Reeb graph satisfies additional ``gluing'' constraints which guarantee that its pre-cosheaf is actually a well-defined \textbf{cosheaf}; see \cite{deSilva2016} for this equivalence and \cite{Curry2014} for a rigorous treatment of cosheaves and their applications to topological data analysis. For the remainder of this document, we will refer to $\mathsf{F}$ as a cosheaf rather than a pre-cosheaf. The category of cosheaves, denoted as $\ensuremath{\mathbf{Csh}}$, is a proper subcategory of $\ensuremath{\mathbf{Pre}}$, defined as the pre-cosheaves which satisfy the aforementioned constraints.

Stating that two Reeb graphs $\mathcal{R}_f,\mathcal{R}_g$ are Reeb graph isomorphic is equivalent to stating that their associated cosheaves $\mathsf{F},\mathsf{G}$ are isomorphic. Recall that an isomoprhism between two functors is a pair of natural transformations $\phi:\mathsf{F} \Rightarrow \mathsf{G}$, $\psi:\mathsf{G} \Rightarrow \mathsf{F}$ such that $\psi_I \circ \phi_I = \mathbf{Id}_{\mathsf{F}(I)}$ and $\phi_I \circ \psi_I = \mathbf{Id}_{\mathsf{G}(I)}$, for all $I \in \mathbf{Int}$. If we do not have a true isomorphism between these cosheaves, we can approximate the isomorphisms to form an $\varepsilon$-\textbf{interleaving}. Fig.~\ref{fig:nonZeroInterleaving} shows the same Reeb graphs as Fig.~\ref{fig:graphIsoNonRGIso} to demonstrate why these graphs fail to be isomorphic as cosheaves. Note that the dashed lines in this figure are the maps $\phi_I,\phi_J$ and $\phi_K$. For there to be an isomorphism between the cosheaves $\mathsf{F}$ and $\mathsf{G}$ in Fig.~\ref{fig:nonZeroInterleaving}, we need to define a natural transformation $\eta: \mathsf{F} \Rightarrow \mathsf{G}$ such that $\eta_U$ is an isomorphism for all intervals $U \subset \mathbb{R}$. The arrows from $\mathsf{F}(I)$ and $\mathsf{F}(J)$ to $F(K)$ denote the maps induced by the inclusions $I, J \subset K$ (and similarly for $\mathsf{G}$). We can see that it is possible for us to define isomorphism for $\mathsf{F}(J)$ and $\mathsf{F}(K)$ which respect these inclusions, but there exists no isomorphism between $\mathsf{F}(I)$ and $\mathsf{G}(I)$ that does. Thus any map between these Reeb graphs that respect these inclusions will be a non-injective function.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/nonZeroInterleaving.pdf}
    \caption{Two cosheaves $\mathsf{F}$ and $\mathsf{G}$ with three specifically chosen intervals $I,J \subset K$, with $I$ and $J$ disjoint to display that these Reeb graphs are graph isomorphic but not \emph{cosheaf isomorphic} -- and equivalently not Reeb graph isomorphic.}
    \label{fig:nonZeroInterleaving}
\end{figure}

\begin{definition} Let $I = (a,b) \subseteq \mathbb{R}$ and $I^{\varepsilon} = (a-\varepsilon,b+\varepsilon)$. The $\varepsilon$-\textbf{smoothing functor}, $\SS_\varepsilon:\ensuremath{\mathbf{Csh}} \to \ensuremath{\mathbf{Csh}}$, where $\varepsilon > 0$, is defined by $\SS_\varepsilon(\mathsf{F}(I)) = \mathsf{F}(I^\varepsilon)$ for each $I$ and morphisms are induced by inclusion.
\end{definition}

In essence, the $\varepsilon$-smoothing functor expands each interval $I$ by $\varepsilon$ in both directions before assigning data. This implies that the infimum width of an interval seen by the functor is now $2\varepsilon$ rather than a single point. In several cases, the increase in the intervals causes the data associated to these intervals to be fundamentally changed, sometimes removing features entirely. Fig.~\ref{fig:smoothingExamples} shows two examples of smoothing for various simple features. We will discuss the effects of smoothing on larger features composed of multiple smaller features in Fig.~\ref{fig:exampleThree} from Sec.~\ref{sec:examples}.

Note that while the smoothing operation is done on the cosheaves directly, we can represent this using the Reeb graph since the fundamental structure of the cosheaf is captured completely in the Reeb graph, as seen in Fig.~\ref{fig:reebToCosheaf}.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{BothSmoothingExamples.pdf}
    \caption{\textbf{(a)} A Reeb graph of a torus along with its $\varepsilon$-smoothed version. To cover the hole completely, $\varepsilon$ has to be large enough so that every interval $I$, the expanded interval $I^{\varepsilon}$ will only have one path connected component. Setting $\varepsilon \geq \frac{a_3-a_2}{2}$ will guarantee this. \textbf{(b)} A Reeb graph with a single up-leaf and its $\varepsilon$-smoothed version. As the center of the interval passes $\frac{a_3+a_2}{2}$, the number of components changes from one to two, essentially creating a leaf in the smoothed version that is shifted upwards. Note that the last component (purple) maps to only \textit{one} component in the smoothed Reeb graph. Similarly, a down-leaf will be shifted downwards.}
    \label{fig:smoothingExamples}
\end{figure}

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{ReebToCosheaf.pdf}
    \caption{A Reeb graph (top) with its corresponding cosheaf (bottom).
    The larger, darker blue sets were chosen specifically to surround the critical points of the Reeb graph.
    The smaller, light blue sets are the pairwise intersection of the sets surrounding it. The arrows represent the morphisms from each small set to the larger sets they are included in. While a cosheaf is defined for \emph{all} intervals on the real line, the intervals above are enough to capture the topology of the Reeb graph fully. This figure was adapted from \cite{deSilva2016}. }

    \label{fig:reebToCosheaf}
\end{figure}

\begin{definition}
Let $\sigma^{\varepsilon}_{\mathsf{F}}$ be the natural transformation $\mathsf{F} \Rightarrow \SS_{\varepsilon}(\mathsf{F})$ created by noting that $I \subseteq I^\varepsilon$ implies $\mathsf{F}(I) \to \mathsf{F}(I^\varepsilon) = \SS_\varepsilon(\mathsf{F})$. We say that two cosheaves $\mathsf{F},\mathsf{G}$ are $\varepsilon$-\textbf{interleaved} if there exists a pair of natural transformations $\varphi: \mathsf{F} \Rightarrow \SS_\varepsilon(\mathsf{G})$ and $\psi: \mathsf{G}\Rightarrow \SS_\varepsilon(\mathsf{F})$ such that the following diagrams commute:
\end{definition}

\begin{center}
\begin{tikzcd}
\mathsf{F} \arrow[dd, "\sigma^{2\varepsilon}_{\mathsf{F}}"', Rightarrow] \arrow[rd, "\varphi", Rightarrow] &                                                                                &  &                                                                                & \mathsf{G} \arrow[ld, "\psi"', Rightarrow] \arrow[dd, "\sigma^{2\varepsilon}_{\mathsf{G}}", Rightarrow] \\
                                                                                & \mathcal{S}_{\varepsilon}(\mathsf{G}) \arrow[ld, "{\mathcal{S}_{\varepsilon}[\psi]}", Rightarrow] &  & \mathcal{S}_{\varepsilon}(\mathsf{F}) \arrow[rd, "{\mathcal{S}_{\varepsilon}[\varphi]}"', Rightarrow] &                                                                                \\
\mathcal{S}_{2\varepsilon}(\mathsf{F})                                                                     &                                                                                &  &                                                                                & \mathcal{S}_{2\varepsilon}(\mathsf{G})
\end{tikzcd}
\end{center}

If $\varepsilon = 0$, then this is exactly the definition of an isomorphism between $\mathsf{F}$ and $\mathsf{G}$. When two cosheaves are $\varepsilon$-interleaved, we say that there exists an $\varepsilon$-\textbf{interleaving} between them.

\begin{definition}
The interleaving distance between two constructible Reeb graphs $\mathcal{R}_f,\mathcal{R}_g$ is the infimum $\varepsilon$ such that their respective cosheaves are $\varepsilon$-interleaved. Formally,
\[d_I(\mathcal{R}_f,\mathcal{R}_g) = \inf_{\varepsilon \in \mathbb{R}^+}\{\varepsilon|\text{ there exists an $\varepsilon$-interleaving between $\mathsf{F}$ and $\mathsf{G}$} \},\]
where $\mathsf{F},\mathsf{G}$ are their respective cosheaves.
\end{definition}

While the definitions above are rooted in category theory, it has been shown that there is a geometric way of understanding the interleaving distance \cite{deSilva2016}. We think of our smoothing operation instead as first ``thickening'' the Reeb graph by $\varepsilon$ which creates a new scalar field, and then finding the Reeb graph of the newly constructed space, resulting in a more ``coarse'' Reeb graph. We re-define the interleaving distance in this context below.

\begin{definition}
For $\varepsilon \geq 0$, the \textbf{thickening functor} $\mathcal{T}_{\varepsilon}$ is defined as follows:
\begin{itemize}
    \item Let $({\mathbb X},f)$ be a scalar field. Then $\mathcal{T}_{\varepsilon}({\mathbb X}^{\varepsilon},f^{\varepsilon})$ where ${\mathbb X}^{\varepsilon} = {\mathbb X} \times [-\varepsilon,\varepsilon]$ and $f_{\varepsilon}(x,t) = f(x) + t$.
    \item Let $\alpha: ({\mathbb X},f) \to ({\mathbb Y},g)$ be a morphism. Then $\mathcal{T}_{\varepsilon}[\alpha]: ({\mathbb X}^{\varepsilon},f^{\varepsilon}) \to ({\mathbb Y}^{\varepsilon},f^{\varepsilon}):(x,t) \mapsto (\alpha(x),t)$.
\end{itemize}
\end{definition}

\begin{definition}
We define the \textbf{Reeb functor} $\mathcal{R}$ as the functor which maps a scalar field $({\mathbb X},f)$ to its Reeb graph $\mathcal{R}_f = ({\mathbb X}_f,\tilde{f})$. That is,
\[\mathcal{R}({\mathbb X},f) := ({\mathbb X}_f,\tilde{f}) = \mathcal{R}_f.\]
\end{definition}

\begin{definition}
Let $\mathcal{R}_f = ({\mathbb X}_f,\tilde{f})$ be a constructible Reeb graph. We define the \textbf{Reeb smoothing functor} $\mathcal{U}_{\varepsilon}$ as the functor which thickens a Reeb graph $\mathcal{R}_f$ into a new scalar field, and then converts it back into a Reeb graph. That is,
\[\mathcal{U}_{\varepsilon}({\mathbb X},f) := \mathcal{R}(\mathcal{T}_{\varepsilon}({\mathbb X}_f,\tilde{f})) = \mathcal{R}({\mathbb X}_f^{\varepsilon},\tilde{f}^{\varepsilon}).\]
\end{definition}

Since $\mathcal{U}_{\varepsilon}(\mathcal{R}_f)$ is indeed another Reeb graph, we can define morphisms $\alpha:\mathcal{R}_f \to \mathcal{U}_{\varepsilon}(\mathcal{R}_g)$ and $\beta: \mathcal{R}_g \to \mathcal{U}_{\varepsilon}(\mathcal{R}_f)$. We then define other morphisms $\iota,\iota_{\varepsilon},\alpha_{\varepsilon}$ as follows:
\begin{align}
    \iota_{\varepsilon}: \mathcal{R}_f \to \mathcal{U}_{\varepsilon}(\mathcal{R}_f),                  & \hspace{50PX} x \mapsto [x,0], \\
    \alpha^{\varepsilon}_{2\varepsilon}: \mathcal{U}_{\varepsilon}(\mathcal{R}_f) \to \mathcal{U}_{2\varepsilon}(\mathcal{R}_g), & \hspace{50PX} [x,t] \mapsto [\alpha(x),t]
\end{align}
where $[x,t]$ refers to the equivalence class of $(x,t)$ under the quotient map $\rho^{\varepsilon}_f: \mathcal{T}_{\varepsilon}(\mathcal{R}_f) \to \mathcal{U}_{\varepsilon}(\mathcal{R}_f)$.

Fig.~\ref{fig:thickeningExample} depicts an example of a Reeb graph $\mathcal{R}_f$ along with its smoothed version $\mathcal{U}_{\varepsilon}(\mathcal{R}_f)$.

\begin{figure}
    \centering
    \includegraphics[width=0.9\textwidth]{figures/ThickeningReebGraph.pdf}
    \caption{A depcition of the thickening process which expands the original Reeb graph $\mathcal{R}_f$ into a 2-dimensional scalar field and then constructs the Reeb graph of that resulting scalar field -- creating $\mathcal{U}_{\varepsilon}(\mathcal{R}_f)$.. Figure adapted from \cite{deSilva2016}.}
    \label{fig:thickeningExample}
\end{figure}

\begin{definition}
We say that two Reeb graphs $\mathcal{R}_f$,$\mathcal{R}_g$ are $\varepsilon$-\textbf{interleaved} if the following diagram commutes:
\begin{center}
\begin{tikzcd}
\mathcal{R}_f \arrow[dd, "\iota_{2\varepsilon}"'] \arrow[rd, "\alpha_{\varepsilon}"] &                                                                            &                                                                              & \mathcal{R}_g \arrow[ld, "\beta_{\varepsilon}"'] \arrow[dd, "\iota_{2\varepsilon}"] \\
                                                                      & \mathcal{U}_{\varepsilon}(\mathcal{R}_g) \arrow[ld, "\beta^{\varepsilon}_{2\varepsilon}"] & \mathcal{U}_{\varepsilon}(\mathcal{R}_f) \arrow[rd, "\alpha^{\varepsilon}_{2\varepsilon}"'] &                                                                       \\
\mathcal{U}_{2\varepsilon}(\mathcal{R}_f)                              &                                                                            &                                                                              & \mathcal{U}_{2\varepsilon}(\mathcal{R}_g)
\end{tikzcd}
\end{center}

The \textbf{interleaving distance} between two Reeb graphs is the infimum $\varepsilon$ such that $\mathcal{R}_f$ and $\mathcal{R}_g$ are $\varepsilon$-interleaved. That is,
\[d_I(\mathcal{R}_f,\mathcal{R}_g) = \inf_{\varepsilon \in \mathbb{R}^+}\{\varepsilon|\text{ there exists an $\varepsilon$-interleaving between $\mathcal{R}_f$ and $\mathcal{R}_g$} \}.\]

\end{definition}

\begin{figure}
    \centering
    \includegraphics[width = .4\textwidth]{figures/InterleavingExample-B.pdf}
    \qquad
    \includegraphics[width = .4\textwidth]{figures/InterleavingExample-A.pdf}
    \caption{An example of two Reeb graphs and computation of the interleaving distance. In this example, the first $\varepsilon$ chosen is not large enough to allow for an interleaving since points on either side of the loop of $\mathcal{R}_f$ will stay on opposite sides of the loop following the top maps, but end up on the same side going down and up. However, in the second case, we have chosen a larger $\varepsilon$ value, making only one possible point to be sent to in $\mathcal{U}_{2\varepsilon}(\mathcal{R}_f)$, implying the diagrams commute. }
    \label{fig:InterleavingExample}
\end{figure}

Here we have provided two different ways of computing the interleaving distance: (1) consider an equivalent structure of a Reeb graph called a cosheaf and construct an interleaving between two cosheaves $\mathsf{F}$ and $\mathsf{G}$ by increasing the minimum interval size until there exists an interleaving based on the definition of isomorphisms between cosheaves, or (2) thicken the Reeb graphs themselves by adding an extra dimension to the space and alter the original function to ultimately construct a new, 2-dimensional scalar field and then take the Reeb graph of this newly constructed space in an attempt to create two Reeb graphs which are $\varepsilon$-interleaved based on the definition of function preserving maps between Reeb graphs. In Sec.~\ref{sec:examples}, we will mostly rely on the cosheaf definition of interleaving distance for computation since, in practice, it seems to lead to more concise proofs.
See Fig.~\ref{fig:InterleavingExample} for two choices of $\varepsilon$ values, one of which is not large enough to allow for an interleaving, while the second, increased value does.

\subsection{Truncated Interleaving Distance}

Truncated smoothing is a more recently developed variation of the smoothing functor, which intuitively smooths and then ``chops off" tails in the smoothed graph~\cite{Chambers2021}.

We define a \textbf{path} from $x$ to $x'$ in a constructible Reeb graph $\mathcal{R}_f:=({\mathbb X}_{f},\tilde{f})$ to be a continuous map $\pi:[0,1] \to {\mathbb X}_f$ such that $\pi(0) = x$ and $\pi(1) = x'$. A path is called an $\textbf{up-path}$ if it is monotone-increasing with respect to the function $\tilde{f}$, i.e. $\tilde{f}(\pi(t)) \leq \tilde{f}(\pi(t'))$ whenever $t \leq t'$. Similarly, a \textbf{down-path} is a path which is monotone-decreasing.

Let $U_\tau $ be the set of points of $\mathcal{R}_f$ that do not have a height $\tau$ up-path and let $D_\tau$ be the set of points of $\mathcal{R}_f$ that do not have a height $\tau$ down-path. We defined the truncation of Reeb graph $\mathcal{R}_f$ by
$$T^{\tau}(\mathcal{R}_f)= \mathcal{R}_f \backslash (U_\tau \cup D_\tau)$$
so that we keep only the subgraph of $\mathcal{R}_f$ that consists of the points that have both up-path and down-path of height $\tau$.
We then define the truncated smoothing of Reeb graph  $\mathcal{R}_f$ as
$S^{\tau}_{\varepsilon}(\mathcal{R}_f) = T^\tau S_\varepsilon(\mathcal{R}_f)$.
See Fig.~\ref{fig:graphandSmoothing} for an illustration of this operation for several values of $\varepsilon$ and $\tau$.

\begin{figure}
    \centering
  \includegraphics[width=\textwidth, page=2]{smoothingOperation}
  \caption{A Reeb graph shown alongside several smoothed and truncated versions; figure from~\cite{Chambers2021}. }
    \label{fig:graphandSmoothing}
\end{figure}

The truncated smoothing operation inherits many of the useful properties of regular smoothing.
First, for $0<\tau \le 2\varepsilon$, $S_\varepsilon^\tau$ is a functor.  In addition, we have a map $\eta: S_\varepsilon^\tau(\mathcal{R}_f) \to S_{\varepsilon'}^{\tau'}$ for any $0 \leq \tau'-\tau \leq \varepsilon'-\varepsilon$.
Note that we abuse notation and write $\eta$ since this map is a restriction of the map $\eta:S_\varepsilon(\mathcal{R}_f) \to S_{\varepsilon'}(\mathcal{R}_f)$.\footnote{This map is denoted $\rho$ in \cite{Chambers2021}. }

In essence, the $0 \leq \tau'-\tau \leq \varepsilon'-\varepsilon$ restriction can be viewed as requiring a slope of at most 1 in the $\varepsilon$-$\tau$ parameter space.
So, fixing a parameter $m \in [0,1]$, we define the truncated interleaving distance as follows.

\begin{definition}
For $\varepsilon\geq 0$, $m \in [0,1]$ and a pair of Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$, an $\varepsilon$-interleaving is defined as a pair of function preserving maps $\phi:\mathcal{R}_f \to S_\varepsilon^{m\varepsilon}(\mathcal{R}_g)$ and $\psi:\mathcal{R}_g \to S_\varepsilon^{m\varepsilon}(\mathcal{R}_f)$ such that
\begin{equation*}
    \begin{tikzcd}[row sep = huge, column sep = huge]
    \mathcal{R}_f \ar[r, "\eta"] \ar[dr, "\phi"', very near start]
        & S_\varepsilon^{m\varepsilon}(\mathcal{R}_f) \ar[r, "\eta"] \ar[dr, "{S_\varepsilon^{m\varepsilon}[\phi]}"', very near start]
        & S_{2\varepsilon}^{2m\varepsilon}(\mathcal{R}_f) \\
    \mathcal{R}_g \ar[r, "\eta"] \ar[ur, "\psi", very near start]
        & S_\varepsilon^{m\varepsilon}(\mathcal{R}_g) \ar[r, "\eta"] \ar[ur, "{S_\varepsilon^{m\varepsilon}[\psi]}", very near start]
        & S_{2\varepsilon}^{2m\varepsilon}(\mathcal{R}_g)
    \end{tikzcd}
\end{equation*}
If such a pair exists, we say that $\mathcal{R}_f$ and $\mathcal{R}_g$ are $\varepsilon$-interleaved (using $S_\varepsilon^{m\varepsilon}$ when not clear from context) and define the interleaving distance as
\begin{equation*}
    d_I^m(\mathcal{R}_f,\mathcal{R}_g) = \inf_{\varepsilon\geq 0} \{ \mathcal{R}_f \text{ and }\mathcal{R}_g \text{ are }\varepsilon\text{-interleaved} \}.
\end{equation*}
\end{definition}
Note that if $m=0$, we recover the original interleaving distance.
As proved in \cite{Chambers2021},  $d_I^m$ is an extended pseudo-metric for every $m \in [0,1]$.
Further, this family excluding $m=1$ are all strongly equivalent. This was proved in \cite{Chambers2021}; here we strengthen the results to include bounds for the general case in Cor.~\ref{cor:strongEquivTruncated}.
\begin{theorem}\label{thm:truncatedEquivalence}
[{\cite[Theorem~2.27]{Chambers2021}}]
For any pair
    %
    $m,m' \in [0,1)$ with $0 \leq m'-m < 1-m'$
    the metrics $d_I^m$ and $d_I^{m'}$ are strongly equivalent.
    Specifically, given Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$,
    \begin{equation*}
    d_I^m(\mathcal{R}_f, \mathcal{R}_g)\leq d_I^{m'}(\mathcal{R}_f, \mathcal{R}_g)\leq \frac{1-m}{1-m'}d_I^m(\mathcal{R}_f, \mathcal{R}_g).
    %
    %
    %
    \end{equation*}
\end{theorem}

\begin{corollary}\label{cor:strongEquivTruncated}
For all pairs $0 \leq M \leq M' < 1$, $d_I^M$ and $d_I^{M'}$ are strongly equivalent. Specifically,
\[d_I^M(\mathcal{R}_f, \mathcal{R}_g)\leq d_I^{M'}(\mathcal{R}_f, \mathcal{R}_g)\leq \frac{1-M}{1-M'}d_I^M(\mathcal{R}_f, \mathcal{R}_g).\]
\end{corollary}

\begin{proof}
In the following, we let $d_I^{m_i}$ denote $d_I^{m_i}(\mathcal{R}_f,\mathcal{R}_g)$ to avoid cumbersome notation. Suppose we have a sequence of values $\{m_0,\ldots,m_n\}$ such that $0 < m_{i+1} - m_i < 1 - m_{i+1}$. We can show by induction that $d_I^{m_0}\leq d_I^{{m_n}}\leq \frac{1-{m_0}}{1-{m_n}}d_I^{m_0}$. Given that $d_I^{m_0}\leq d_I^{{m_1}}\leq \frac{1-{m_0}}{1-{m_1}}d_I^{m_0}$ and  $d_I^{m_1}\leq d_I^{{m_2}}\leq \frac{1-{m_1}}{1-{m_2}}d_I^{m_1}$, we obtain
\[d_I^{m_0} \leq d_I^{m_2} \leq \frac{1-m_1}{1-m_2}d_I^{m_1} \leq \frac{1-m_1}{1-m_2}\cdot \frac{1-m_0}{1-m_1}d_I^{m_0} = \frac{1-m_0}{1-m_2}d_I^{m_0}.\]

Now, suppose $d_I^{m_0} \leq d_I^{m_j} \leq \frac{1-m_0}{1-m_j}d_I^{m_0}$. Then, similar to our base case, we get
\[d_I^{m_0} \leq d_I^{m_j} \leq \frac{1-m_j}{1-m_{j+1}}\cdot \frac{1-m_0}{1-m_j}d_I^{m_0} = \frac{1-m_0}{1-m_{j+1}}d_I^{m_0}.\]

What is left to show is that given two numbers $0 \leq M \leq M' < 1$, there exists a sequence $\{M = m_0,m_1,\ldots,m_{n-1},m_n = M'\}$ such that $0 < m_{i+1} - m_i < 1 - m_{i+1}$ for all $i \in \{0,\ldots,n-1\}$. Rearranging the inequality, we get that $m_{i+1} \in [m_i, \frac{1+m_i}{2})$. If $M' \in [M,\frac{1+M}{2})$, then we are done. Otherwise, let $A_n := \frac{m_0}{2^n} - \frac{1}{2^n} + M'$ Then, $A_n$ defines a sequence of real numbers such that $A_{i+1} \in [A_i, \frac{1+A_i}{2})$. Since $A_n$ converges to $M'$, we have that for all $\varepsilon > 0$, there exists some $N$ such that for all $n \geq N$, $|M' - A_n| < \varepsilon$. If we choose $\varepsilon = 1-M'$, we get that $A_n < M'$ and
\begin{align*}
    \frac{1+A_n}{2} = & \frac{1+A_n}{2} + \frac{M'}{2} - \frac{M'}{2}
                    =  \frac12 + \frac{M'}{2} - \frac12(M' - A_n) \\
                 \geq & \frac12 + \frac{M'}{2} - \frac12\varepsilon
                    = \frac12 + \frac{M'}{2} - \frac12(1-M')
                    =  M'.
\end{align*}
Thus, there exists some $N$ such that $M' \in [A_N,\frac{1+A_N}{2})$, and so the sequence $\{M,A_0,\ldots,A_N,M'\}$ then satisfies all the criteria needed.
\end{proof}

\section{Introduction}

In numerous application fields, there is an increasing need to analyze topological and geometric information about shapes.
Given a real-valued function on a topological space, a commonly used object for such analysis is the Reeb graph, which encodes the changing component structure of the level sets of the object. Given specific restrictions on the function and topological space, the Reeb graph is a 1-dimensional topological graph with a function inherited from the input data.
Reeb graphs are utilized in a variety of computational topology and topological data analysis (TDA) applications in order to obtain a lower dimensional representation of a structure which maintains topological properties of the original data, such as shape analysis \cite{Escolano2013,Hilaga2001}, data skeletonization \cite{Chazal2014, Ge2012}, and surface denoising \cite{Wood2004}; see the recent survey on Reeb graph applications~\cite{Yan2021} for a more exhaustive list of applications.

The Reeb graph is constrfucted on input data known as an $\mathbb{R}$-space, which is an assignment of scalar data to each point of a topological space. More formally, we say an $\mathbb{R}$-space is a pair $({\mathbb X},f)$, where ${\mathbb X}$ is a topological space and $f:{\mathbb X} \to \mathbb{R}$ is a continuous, scalar-valued function. We then construct the Reeb graph by first defining an equivalence relation between elements of the $\mathbb{R}$-space if they have the same function value and lie in the same path connected component of their levelset. We denote the Reeb graph defined on $({\mathbb X},f)$ as $\mathcal{R}_f$.

In data analysis and other applied settings, $\mathbb{R}$-spaces are more commonly referred to as \emph{scalar fields}. While the definitions of these two objects are identical, it is common to think of scalar fields having some additional restrictions on the space, such as requiring a simply connected domain. Many common physical phenomena, such as temperature of a surface or distribution of pressure in a liquid, can be described using scalar fields.

Increases in computational power and the availability of large data sets has lead to increased interest in comparing such scalar fields. Since Reeb graphs have already been utilized for analyzing single scalar fields, there has been recent interest in defining distances on Reeb graphs so that we can compare multiple scalar fields to one another via this topological summary.

This survey will focus on five distances which have been defined on Reeb graphs:
the \textbf{bottleneck distance}, which can be graded \cite{Steiner2009} or ungraded \cite{Bjerkevik2016a} \footnote{We note that these two notions of the bottleneck distance are closely related but seem to be often conflated or confused in the literature, which leads to incorrect bounds in some prior work on this topic.  Graded bottleneck distance is the older of the two concepts and arises from early work on comparing persistence diagrams, where dimensions are handled separately when comparing the diagrams.  In contrast, ungraded bottleneck is a more recent contribution from the algebraic side and to the best of our knowledge first arose from considering interlevel set persistence. We discuss these in more depth in Section~\ref{sec:bottleneckDist}, and adopt the terminology of graded versus ungraded in order to clarify the distinction.},
the \textbf{interleaving distance} \cite{deSilva2016},
the \textbf{functional distortion distance} \cite{Bauer2014},
the \textbf{Reeb graph edit distance} \cite{DiFabio2016},
and the \textbf{universal edit distance} \cite{Bauer2020}.
These distances vary in their goals and properties: bottleneck distance finds matchings between points of persistence diagrams associated to the Reeb graphs; interleaving distance finds approximately height-preserving isomorphisms between the graphs; functional distortion distance measures the amount of distortion to continuously map one Reeb graph into another; and the edit distances deform Reeb graphs into one another through a sequence of steps and assigns a cost to this sequence.
Each distance has been inspired from different mathematical disciplines such as Banach and metrics spaces, category theory, sequence and string matching, and graph theory \cite{DiFabio2016,Bauer2016,Bauer2020}. While the bottleneck distance is usually defined as a distance on persistence diagrams, we will frame it as a distance on Reeb graphs to provide a baseline of comparison to the other four distances. We reserve the term \emph{Reeb graph metrics} to refer to the interleaving, functional distortion, and two edit distances.

When we say that we are defining a ``distance'' or ``metric'' between Reeb graphs, we often mean an \textbf{extended psuedometric}.

\begin{definition}
An \textbf{extended psuedometric} is a function $d: X \times X \to [0,+\infty]$ such that for every $x,y,z \in X$ we have
\begin{enumerate}
    \item $d(x,x) = 0$
    \item $d(x,y) = d(y,x)$
    \item $d(x,z) \leq d(x,y) + d(y,z)$
\end{enumerate}
\end{definition}

The term ``extended'' refers to the metric possibly taking values at $+\infty$, and the term ``pseudo" refers to the fact that $d(x,y) = 0$ does not necessarily imply that $x = y$. We will see in Sec.~\ref{sec:distProp} that each of these Reeb graph metrics attain a value of 0 between Reeb graphs $\mathcal{R}_f$ and $\mathcal{R}_g$ if and only if the Reeb graphs are isomorphic -- making these distances an \textbf{extended metric} on the space of isomorphism classes of Reeb graphs.

In Sec.~\ref{sec:basicDef}, we provide preliminary definitions of scalar fields, Reeb graphs, and (extended) persistence diagrams. The following four sections are devoted to the individual distances: Sec.~\ref{sec:bottleneckDist} for the bottleneck distance, Sec.~\ref{sec:interleaving} for the interleaving distance, Sec.~\ref{sec:FDD} for the functional distortion distance, and Sec.~\ref{sec:EditDist} for both the Reeb graph edit distance and universal edit distance. We will use small examples in each of these sections to build the understanding and intuition of the reader and then explore full working examples in Sec.~\ref{sec:examples}.

A commonality between the aforementioned distance is that they are each proven to be \textbf{stable}, meaning that small perturbations to the input scalar field do not result in  large changes in the distance. The Reeb graph metrics have also all been shown to be more \textbf{discriminative} than the bottleneck distance. In conjunction with stability, this leads us to believe that these Reeb graph metrics can be used in various application settings. In Sec.~\ref{sec:distProp} we will conglomerate previously proven theorems of stability, discriminativity, universality and other properties. While many of the previously defined properties apply to each of the Reeb graph metrics, some claims have not yet been explicitly proven. We take this opportunity to provide a more comprehensive list of properties for the distances along with supporting proofs. Fig.~\ref{fig:distanceLandscape} depicts the inequality relationships between these distances.

Lastly, we would like to take note of the computational difficulties and overall complexity of these metrics which introduces challenges for both the applied researcher intending to compute these distances, as well as the newcomer who is attempting to develop an intuition for how these distances operate. In Sec.~\ref{sec:examples}, we use examples to illustrate their complexity and develop the reader's intuition. We then discuss the individual computational hurdles for each distance in Sec.~\ref{sec:discussion}.

While we attempt a self-contained presentation as much as possible, we do assume general familiarity with topology and the basics of category theory; some familiarity with persistent homology is also beneficial.  We refer the reader to various references on algebraic topology~\cite{Munkres84}, category theory~\cite{Riehl2017}, and topological data analysis~\cite{Oudot2015,DeyWang2021} for further background and more detailed discussion.

\begin{figure}
    \centering
    \includegraphics[width=\textwidth]{figures/DistanceDiagram.pdf}
    \caption{Diagram showing the established relationship between distances defined on Reeb graphs. Here, $d_b$ and $d_B$ indicate the ungraded and graded bottleneck distance, $d_I$ is the interleaving distance on Reeb graphs, $d_{FD}$ is the functional distortion distance, and $\delta_E$ is the universal Reeb graph edit distance.  Color indicates the paper in which these bounds were first proven. Dashed lines indicate that the bounds are tight, while solid lines are not tight. The label $a \xrightarrow{C\times} b$ indicates $a \leq C \times b$.}
    \label{fig:distanceLandscape}
\end{figure}

\subsection{Our contribution}
This work is a constructive survey focusing on these five distances -- the interleaving distance, functional distortion distance, and two edit distances -- as well as an analysis of the properties of each metric so that we can better understand the relationships to one another and use cases for each. Specifically, this paper:
\begin{itemize}
    \item provides concrete examples for these distances to help develop the intuition of new researchers;
    \item provides returning researchers a reference for fundamental properties of each metric;
    \item compares and contrasts the various metrics and introduces a common nomenclature for their properties in general.
\end{itemize}

\subsection{Notation}
Throughout the literature, Reeb graphs not only have different notation, but the interpretation of them varies. Here, we list the notation we will use throughout this document:
\begin{itemize}
    \item $({\mathbb X},f)$ is a constructible $\mathbb{R}$-space/scalar field.
    \item $\mathcal{R}_f$ is the \emph{topological} Reeb graph of $({\mathbb X},f)$ -- the Reeb graph viewed as an $\mathbb{R}$-space $({\mathbb X}_f,\tilde{f})$, where the space ${\mathbb X}_{f}$ is a topological graph and $\tilde{f}$ is $f$ induced by the quotient to ${\mathbb X}_{f}$. That is, if $p$ is the quotient map carrying ${\mathbb X}$ to ${\mathbb X}_{f}$, then $\tilde{f} = f \circ p$.
    \item $\mathsf{F}$ is the \emph{abstract} Reeb graph of $({\mathbb X},f)$ -- the Reeb graph viewed as a cosheaf $\mathsf{F}: \mathbf{Int} \to \mathbf{Set}$.
    \item $\Gamma_f$ is the \emph{combinatorial} Reeb graph of $({\mathbb X},f)$ -- the Reeb graph viewed as a labeled multigraph.
    \item $\mathrm{ExDgm}_d$ refers to the $d$-dimensional extended persistence diagram, and $\mathrm{ExDgm}(f)$ refers to the full extended persistence diagram.
    We will use the term ``persistence diagram" for the ``full extended persistence diagram" in later sections to avoid cumbersome language, and call the sublevelset persistence diagram the ``ordinary'' diagram when necessary.
\end{itemize}

Each distance treats the Reeb graph differently. However, we will always write our distance measures as simply being a distance between the topological Reeb graphs since we can always convert a topological Reeb graph to its abstract or combinatorial counterpart. Furthermore, unless otherwise noted, we allow for the possibility that two Reeb graphs to be compared
arise from scalar fields defined on potentially non-homeomorphic spaces, i.e.~$({\mathbb X},f)$, $({\mathbb Y},g)$ with ${\mathbb X} \not \cong {\mathbb Y}$.

\section*{Acknowledgements}
We thank Tim Ophelders for his permission to include Fig.~\ref{fig:graphandSmoothing}. In addition, we thank Ulrich Bauer for the inspiration for Figure~\ref{fig:distanceLandscape} from his talk at SoCG 2020 as well as for clarifications regarding the edit distance, and Håvard Bjerkevik for a helpful discussion on interlevel set persistence.

The work of EM was funded in part by the NSF through CCF-1907591 and CCF-2106578.
The work of EC was funded in part by the NSF through grants  CCF-1907612, CCF-2106672, and DBI-1759807.
BB and JL were supported by the U.S. Department of Energy, Office of Science, Office of Advanced Scientific Computing Research, under Award Number(s) DE-SC-0019039.

\printbibliography

redpajama_set_name: RedPajamaArXiv