Strong Equivalence of the Interleaving and Functional Distortion Metrics for Reeb Graphs

Introduction

The Reeb graph is a construction that can be used to study a topological space with a real valued function by tracking the relationships between connected components of level sets. It was originally developed in the context of Morse theory , and was later introduced for shape analysis by Shinagawa et al. . Since then, it has attracted much attention due to its wide use for various data analysis applications, such as shape comparison , denoising , and shape understanding ; see for a survey. Recently, the applications of Reeb graphs have been further broadened to summarizing high-dimensional and/or complex data, in particular, reconstructing non-linear 1-dimensional structure in data and summarizing collections of trajectory data . Its practical applications have also been facilitated by the availability of efficient algorithms for computing the Reeb graph from a piecewise-linear function defined on a simplicial complex .

In addition to the standard construction, a generalization of the Reeb graph construction, known as Mapper, , has proven extremely useful in the field of topological data analysis . A variant of Mapper for real-valued functions, called the $\alpha$-Reeb graph, was used in to study data sets with 1-dimensional structure.

Given the popularity of the Reeb graph and related constructions for practical data analysis applications, it is desirable and increasingly necessary to understand how robust (stable) these structures are in the presence of noise. Consequently, several metrics for comparing Reeb graphs have been proposed recently. These include the interleaving distance , the functional distortion distance , and the combinatorial edit distance . We note that the latter is limited to Reeb graphs resulting from Morse functions defined on surfaces (2-manifolds). In addition, Morozov et. al proposed an interleaving distance for a simpler variant of the Reeb graph, the so-called merge tree .

In this paper, we study the relation between the only two distance measures for general Reeb graphs proposed in the literature: the functional distortion distance of and the interleaving distance of . The former is based on concepts from metric geometry, and is defined by treating both graphs as metric spaces and inspecting continuous maps between them. The latter, on the other hand, is defined using ideas of category theory, utilizing the equivalence between Reeb graphs and a particular class of cosheaves. However, in essence, both construct a near-isomorphism between the two input graphs of study. In Sections 4 and 5, we explore this connection between the two distances, and show that indeed, the functional distortion distance and the interleaving distances are strongly equivalent on the space of Reeb graphs, meaning that they are within constant factor of each other. This immediately leads to the bottleneck stability result for the Reeb graph interleaving distance.

Definitions

Note that because we assume that the function is monotone when restricted to the edges, we will often just think of the function as being given by the values on the vertices. As an aside, notice that the process of taking the Reeb graph of a space with a function is an isomorphism in $\mathbf{Reeb}$.

2. Interleaving Distance

We can use this definition of interleavings to define a distance on Reeb graphs.

Let the $\varepsilon$-thickening of an interval $I=(a,b)$ be denoted by $I^{\varepsilon}=(a-\varepsilon,b+\varepsilon)$. Then we can also consider the $\varepsilon$-interleavings for the cosheaves.

for each open interval $I$. These must be natural with respect to inclusions $I\subseteq J$, i.e., the following diagrams commute, where the vertical maps are induced by the inclusions $\iota:I\hookrightarrow J$ and $\iota_{\varepsilon}:I^{\varepsilon}\hookrightarrow J^{\varepsilon}$:

is the map induced by the inclusions $f^{-1}(I)\subset f^{-1}(I^{\varepsilon})$ and

is the map induced by the inclusions $g^{-1}(I)\subset g^{-1}(I^{\varepsilon})$ for all $I$.

First, notice that for $\varepsilon=0$ this is is precisely an isomorphism between $\mathsf{F},\mathsf{G}$. Note that an interleaving could be equivalently defined as a pair of natural transformations between the appropriate functors. Then, the interleaving distance can be equivalently defined as

3. Functional Distortion Distance

Then the functional distortion distance is defined to be

Note that since the maps $\varphi,\psi$ are not required to preserve the function values, they are not Reeb graph morphisms in the sense of Definition 2.1.

Multivalued Maps and Continuous Selections

A multivalued map (or multimap) $F:X\to Y$ is a correspondence which sends a point $x\in X$ to a nonempty set $F(x)\subset Y$. A selection of a multimap is a singlevalued function $f:X\to Y$ such that $f(x)\in F(x)$ for every $x\in X$. See for an introduction to multimaps.

Note that using the axiom of choice, a selection always exists; the trick is to find a continuous selection. The Michael selection theorem gives a criterion for a multimap to have a continuous selection. However, in order to state it, we will need several definitions.

A multivalued map $F:X\to Y$ is lower semicontinuous (LSC) if for every open $U\subset Y$, the set $F^{-1}(U)=\{x\in X\mid F(x)\cap U\neq\emptyset\}$ is open in $X$.

Finally we can state the Michael selection theorem. Note that we are working with a space of covering dimension 1, so we paraphrase the more general theorem here to relate it to our context.

A multivalued mapping $F:X\to Y$ admits a continuous single-valued selection provided that the following conditions are satisfied:

$X$ is a paracompact space with $\dim(X)\leq 1$;

For every $x\in X$, $F(x)$ is a 0-connected (path connected) subset of $Y$; and

ε𝜀\varepsilon-Interleaving and Functional Distortion

In order to prove the main result, Theorem 4.11, we will prove each inequality separately as Lemmas 4.1 and 4.9 .

Let $\varepsilon>d_{FD}(f,g)$. By definition of the functional distortion metric, there are maps

for every $I$. By the functoriality of $\pi_{0}$, these maps commute with the maps induced by the inclusions $\iota:I\hookrightarrow J$ and $\iota_{\varepsilon}:I^{\varepsilon}\hookrightarrow J^{\varepsilon}$; that is, the diagrams

commute. In addition, the functoriality of $\pi_{0}$ implies that the diagrams

commute. These are exactly the properties necessary to call $\varphi^{*}$ and $\psi^{*}$ an $\varepsilon$-interleaving of the associated cosheaves. Since the above holds for any $\varepsilon>d_{FD}(f,g)$, we conclude $d_{I}(f,g)\leq\varepsilon=d_{FD}(f,g)$.

2. The Hard Direction

Then since $\bar{\varphi}(x^{\prime})\cap U\neq\emptyset$ and $x^{\prime}\in B_{\delta}(x^{\prime\prime})$, we must have $x^{\prime\prime}\in\bar{\varphi}_{\delta}^{-1}(U)$.

As checking this property is by far the most complicated, we prove it in Lemma 4.3.

$\kappa B_{r}\iota(x)\subseteq B_{r+2\varepsilon}(x)$.

Note that the previous lemma can also be stated using $\iota_{\varepsilon}$, so $\kappa_{\varepsilon}B_{r}\iota_{\varepsilon}\subseteq B_{r+2\varepsilon}$. Since this lemma works for $r=0$, this also implies that $\kappa\iota\subset B_{2\varepsilon}$.

$\Psi\Phi(x)\in B_{6\varepsilon+2\delta}(x)$.

By definition of $\Phi$ and $\Psi$, we have

Now using, Lemma 4.5, the definition of the interleaving, and the fact that for any map $\nu$, $x\in\nu^{-1}\nu(x)$, we have

Finally, we can prove the main result of the section.

and hence $\|f-g\circ\Phi\|_{\infty}\leq\varepsilon+\delta$. Likewise, $\|g-f\circ\Psi\|_{\infty}\leq\varepsilon+\delta$.

Thus, using Lemma 4.7 and the triangle inequality,

Therefore, $|d_{f}(x,\Psi(y))-d_{g}(\Phi(x),y)|\leq 8(\varepsilon+\delta)$.

Since this is true for any $\varepsilon>d_{I}(f,g)$ and for any $\delta>0$, this completes the proof.

Putting together Lemmas 4.1 and 4.9, our main theorem is immediate.

Relationship Between the Interleaving and Bottleneck Distances

Combining this result with Theorem 4.11 gives an immediate stability result relating the interleaving distance with the bottleneck distance.

Discussion

In this paper, we study the relation between the two existing distance measures for Reeb graphs, and show that they are strongly equivalent on the space of Reeb graphs. This relationship will be a powerful tool for understanding convergence properties of the different metrics. For example, if we have a Cauchy sequence in one metric, we have a Cauchy sequence in the other and can therefore pass around completeness results. This relationship also means that algorithms for computation and approximation of the metrics can be written using whichever method is most helpful and applicable to the context.

These two distances in general may not be the same. An immediate question is whether the relations provided in Theorem 4.11 are tight. In particular, it is easy to construct examples where the bound $d_{I}(f,g)\leq d_{FD}(f,g)$ of Lemma 4.1 is tight; it will be interesting to investigate the tightness of the bound $d_{FD}(f,g)\leq 7d_{I}(f,g)$ of Lemma 4.9. While that bound is obtained using an arbitrary selection, a better bound may be achievable using a particular optimal selection. In addition, this may shed light on whether the bounds given between the bottleneck distance of the extended persistence diagrams and the two Reeb graph distances are tight. Finally, we will explore the applications of these distance measures to studying the stability of Reeb-like structures, such as Mapper and $\alpha$-Reeb graphs.

Appendix A Appendix: The Category of Constructible Cosheaves

It has been shown in that the category $\mathbf{Reeb}$ is equivalent to a particular class of cosheaves. This allows a definition of distance for cosheaves to be pulled back to a definition of distance for Reeb graphs. A brief overview of the necessary sheaf theory follows; a better introduction can be found in .

$\mathbf{Set}$ consists of sets with morphisms given by set maps.

$\mathbf{Top}$ consists of topological spaces with continuous maps.

Finally, we have the notion of a natural transformation $\eta:F\to G$ between functors $F,G:\mathbf{A}\to\mathbf{B}$. It is a collection of morphisms $\eta_{A}:F(A)\to G(A)$, one for each $A\in\mathbf{A}$, such that for any morphism $f:A\to A^{\prime}$ in $\mathbf{A}$,

Then a set-valued pre-cosheaf, in our context, is a functor $F:\mathbf{Int}\to\mathbf{Set}$. A cosheaf is a pre-cosheaf which satisfies the following property. For any $\mathcal{I}$, a collection of open intervals whose union is an open interval $U$, $\mathsf{F}(U)$ must be the colimit of the diagram

if $I\subseteq J$ are open intervals with $I\cap S=J\cap S$, then $\mathsf{F}[I\subseteq J]$ is an isomorphism, and

if $I$ is contained in $(-\infty,\min(S))$ or $(\max(S),\infty)$, $\mathsf{F}(I)=\emptyset$.

Will of these definitions in hand, we have the following theorem from .

References