Locally Correct Interleavings Between Merge Trees

The interleaving distance is defined as an infimum, but in both [5, 10] the authors prove that the infimum can be replaced by a minimum: there always exists an interleaving with shift $d(T_1,T_2)$ (Theorem 6). We call an interleaving that realizes the interleaving distance an optimal interleaving. Both proofs rely on alternative definitions of the interleaving distance, namely in terms of labellings [5] and in terms of couplings [10]. We can show the same statement more directly: if the shift $\delta$ of an interleaving $ℐ$ is not equal to a critical value, we can obtain an interleaving whose shift is equal to a critical value. Intuitively, we “push down” each arrow of $ℐ$ so that its shift becomes ${\delta }^{\prime }$ (see Figure 5). Later, in Section 3.2, we describe a formal construction to prove a generalization of Theorem 6.

For the remainder of this section, we consider finite partial interleavings $𝒫$: both $\mathrm{dom}(\phi )$ and $\mathrm{dom}(\psi )$ consist of finitely many points. Recall from Section 2 that the non-residual interleaving distance always attains a value in the set of critical values $\mathrm{\Delta }≔\mathrm{\Delta }(T_1,T_2)$. For the residual interleaving distance, this set $\mathrm{\Delta }$ is not always sufficient (see Figure 7). Therefore, we extend $\mathrm{\Delta }$ to a set of $𝒫$-critical values. Specifically, we “mark” all vertices in $T_1$ and $T_2$, and all points $x$ of $T_1$ and $y$ of $T_2$ that appear in an arrow $(x,y)$ or $(y,x)$ of $𝒫$. We call these the $𝒫$-critical points of $T_1$ and $T_2$, denoted $C_1[𝒫]$ and $C_2[𝒫]$ respectively. Since $𝒫$ is finite, there are only finitely many critical points. We define a set ${\mathrm{\Delta }}_1[𝒫]$ that contains all height differences between critical points:

We define the set of $𝒫$-critical values as the set $\mathrm{\Delta }[𝒫](T_1,T_2)≔{\mathrm{\Delta }}_1[𝒫]\cup {\mathrm{\Delta }}_2\cup {\mathrm{\Delta }}_3$, where ${\mathrm{\Delta }}_2$ and ${\mathrm{\Delta }}_3$ are as defined in Eq. (2). Each critical value corresponds to a pair of critical points; we refer to such a pair $b$ as a $𝒫$-critical pair. We distinguish two types; see Figure 8.

• $\mathrm{■}$

  If $b=(v,w)$ for a point $v\in C_1[𝒫]$ and a point $w\in C_2[𝒫]$, then $b$ is an arrow critical pair that corresponds to the critical value $\sigma (v,w)$. We say a partial interleaving $(\phi ,\psi )$ uses $b$ if $\phi (v)=w$. The case that $b=(w,v)$ is symmetric.

• $\mathrm{■}$

  If $b=(v_1,v_2)$ for two vertices $v_1,v_2$ in $V(T_1)$, then $b$ is a zigzag critical pair that corresponds to the critical value $\frac{1}{2}(f_1(v_2)-f_1(v_1))$. We say a partial interleaving $(\phi ,\psi )$ uses $b$ if there is a point $y\in T_2$ with $f_2(y)=f_1(v_1)+\frac{1}{2}(f_1(v_2)-f_1(v_1))$ such that $\phi (v_1)=y$ and $\psi (y)=v_2$. The case that $b=(w_1,w_2)$ for two vertices $w_1,w_2$ in $V(T_2)$ is symmetric.

Similar to Lemma 2, we show that the $𝒫$-residual interleaving distance always attains a value in the set of $𝒫$-critical values. A $𝒫$-critical pair is a realizing critical pair if it corresponds to the $𝒫$-residual interleaving distance. We can additionally show that there always exists an optimal $𝒫$-extension and that any such extension uses a realizing critical pair.

Consider a $𝒫$-extension $ℐ=(\alpha ,\beta )$ with $𝒫$-shift $\delta$, and assume $𝒫$ does not use a critical pair that corresponds to $\delta$. We modify $ℐ$ into an extension ${ℐ}^{\prime }=({\alpha }^{\prime },{\beta }^{\prime })$ whose $𝒫$-shift is equal to a $𝒫$-critical value that is strictly less than $\delta$. Let ${\delta }^{\prime }\in \mathrm{\Delta }[𝒫]$ be the greatest value that satisfies . Intuitively, we modify $ℐ$ by “pushing down” each arrow (recall Figure 5). We describe the construction of ${\alpha }^{\prime }$; the construction of ${\beta }^{\prime }$ is symmetric.

We assume, without loss of generality, that each arrow of $\alpha$ has shift at least ${\delta }^{\prime }$. Otherwise, we replace $\alpha$ by ${\alpha }^{\uparrow }[{\delta }^{\prime }]$. Since the residual shift of an arrow is bounded by its shift, and since , the $\phi$-residual shift of ${\alpha }^{\uparrow }[{\delta }^{\prime }]$ is bounded by $\delta$. For $x\in T_1$, let $v_x\in C_1[𝒫]$ be the highest descendant critical point of $x$; if $x\in C_1[𝒫]$, then $v_x=x$. Moreover, let $w_x\in C_2[𝒫]$ be the highest descendant critical point of $\alpha (v_x)$. Let $h_x≔\max (f_1(x)+{\delta }^{\prime },f_2(w_x))$. We define ${\alpha }^{\prime }(x)$ as the ancestor of $w_x$ at height $h_x$, that is, ${\alpha }^{\prime }(x)≔w_x{|}^{h_x}$.

It is not hard to prove that ${\alpha }^{\prime }$ is an up-map that extends $\phi$. To show that the $\phi$-shift of ${\alpha }^{\prime }$ is bounded by ${\delta }^{\prime }$, we argue that any arrow $(x,y)$ of ${\alpha }^{\prime }$ with shift strictly greater than ${\delta }^{\prime }$ must be inside the fan of $\phi$. Specifically, we show that then also the shift ${\delta }^{\ast }$ of the arrow $(v_x,w_x)$ is strictly greater than ${\delta }^{\prime }$. The pair $(v_x,w_x)$ is a critical pair; since $ℐ$ does not use a critical pair that corresponds to $\delta$, it moreover follows that ${\delta }^{\ast }$ cannot be equal to $\delta$. So, by choice of ${\delta }^{\prime }$, we get ${\delta }^{\ast }>\delta$. As a result, $(v_x,w_x)$, and therefore also $(x,w_x)$ must lie within the fan of $\phi$: their residual shift is $0$. Symmetrically, the map ${\beta }^{\prime }$ is an up-map that extends $\psi$ and has $\psi$-shift at most ${\delta }^{\prime }$. We can then argue that the resulting pair ${ℐ}^{\prime }$ is an interleaving. $◀$ Lemma 8 directly implies Corollaries 9 and 10.

Let ${\delta }_1\in \mathrm{\Delta }[𝒫]$ be the greatest value that satisfies ${\delta }_1\le d_{𝒫}$ and let ${\delta }_2\in \mathrm{\Delta }[𝒫]$ be the smallest value that satisfies ${\delta }_2>d_{𝒫}$. By definition of $d_{𝒫}$, for all $\epsilon >0$ there is a $𝒫$-extension with $𝒫$-shift $d_{𝒫}+\epsilon$. In particular, for $\epsilon$ small enough, there is a $𝒫$-extension $ℐ$ with $𝒫$-shift . In other words, there are no critical pairs that correspond to ${\sigma }_{𝒫}(ℐ)$. This means that $ℐ$ cannot use a critical pair that corresponds to the $𝒫$-shift of $ℐ$. By Lemma 8, it then follows that there exists a $𝒫$-extension with $𝒫$-shift ${\delta }_1=d_{𝒫}$.

To reason about “greatest” shifts and “highest” ancestors, it is useful to have optimal extensions that satisfy two additional finiteness properties. Specifically, assume the $𝒫$-residual interleaving distance is strictly positive, that is, $d_{𝒫}>0$. We say an optimal $𝒫$-extension $ℐ$ is isolated if (1) the $𝒫$-shift of only finitely many arrows of $ℐ$ is equal to $d_{𝒫}$, and (2) there exists some $\epsilon >0$ such that for each arrow $(x,y)$ of $ℐ$ with $𝒫$-shift at least $d_{𝒫}-\epsilon$, there exists a descendant $x^{\prime }$ of $x$, such that $(x^{\prime },y)$ is an arrow in $ℐ$ with the same target and $𝒫$-shift $d_{𝒫}$.

Fix a partial interleaving $𝒫=(\phi ,\psi )$. In the remainder of this section, we assume that $𝒫$ is finite, and that the $𝒫$-residual interleaving distance is strictly positive, that is, $d_{𝒫}>0$. A $𝒫$-extension $𝒬$ is a $𝒫$-augmentation if (i) the $𝒫$-residual shift of $𝒬$ is at most $d_{𝒫}$, that is, ${\sigma }_{𝒫}(𝒬)\le d_{𝒫}$, and (ii) the $𝒬$-residual interleaving distance is strictly less than $d_{𝒫}$, that is, . We say that $𝒬$ is minimal if it does not extend any other $𝒫$-augmentation.

Let $𝒬$ be a minimal $𝒫$-augmentation. We refer to the relative difference $𝒬\setminus 𝒫$ as a $𝒫$-bottleneck. Intuitively, a bottleneck captures a minimal set of arrows that we need to “add” to decrease the residual interleaving distance. See Figure 10 for an illustration.

Recall (the proof of) Lemma 8. If we apply the lemma to a given $𝒫$-extension $ℐ$ that does not use a realizing critical pair, we can construct another $𝒫$-extension ${ℐ}^{\prime }$ that has strictly smaller shift. The exact same proof still works for a slightly stronger statement: it suffices to assume that the relative difference $ℐ\setminus 𝒫$ does not use a realizing critical pair.

We use this observation to prove the following lemma.

Let $ℐ$ be an optimal $𝒬$-extension. Since $𝒬$ extends $𝒫$, so does $ℐ$. Moreover, as $ℐ$ is optimal, the $𝒬$-shift of $ℐ$ is equal to the $𝒬$-residual interleaving distance, that is, ${\sigma }_{𝒬}(ℐ)=d_{𝒬}$. Since $𝒬$ is an augmentation, the shift of all arrows of $𝒬\setminus 𝒫$ is at most $d_{𝒫}$, and . Combining, we obtain ${\sigma }_{𝒫}(ℐ)\le d_{𝒫}$. In other words, $ℐ$ is an optimal $𝒫$-extension. By Observation 17, it follows that $ℐ\setminus 𝒫$ uses a realizing critical pair $b$. As , we get that the $𝒬$-shift of the arrows that correspond to $b$ must be $0$. In other words, $𝒬\setminus 𝒫$ uses $b$. $◀$ A direct consequence of Lemma 18 is that if, for a given $𝒫$-extension $𝒬$, the relative difference $𝒬\setminus 𝒫$ does not use a realizing critical pair, then $𝒬$ cannot be a $𝒫$-augmentation. In other words, we have the following corollary:

For a partial interleaving $𝒫=(\phi ,\psi )$, we use $𝒫.\phi$ and $𝒫.\psi$ to denote $\phi$ and $\psi$, respectively.

Formally, let $𝒫$ be a partial interleaving and assume $d_{𝒫}>0$. Recall that another partial interleaving $𝒬$ uses $𝒫$ if they completely agree on the domains of $𝒫.\phi$ and $𝒫.\psi$.

We use this lemma to argue that $𝒫$ remains locally correct throughout the construction.

We first argue that $𝒬$ is dominant. Let $a$ be an arrow of $𝒬$. If $a$ is also an arrow of $𝒫$, then from the fact that $𝒫$ is dominant we know that $\sigma (a)>d_{𝒫}>d_{𝒬}$. Otherwise, $a$ must be an arrow of the bottleneck $𝒬\setminus 𝒫$. By Lemma 20, it then directly follows that $\sigma (a)=d_{𝒫}>d_{𝒬}$.

Next, we argue that $𝒬$ is locally correct. Consider a restriction $ℛ$ of $𝒬$; we need to show that $d_{ℛ}\ge {\sigma }_{ℛ}(𝒬)$. If $ℛ=𝒬$, we immediately obtain ${\sigma }_{ℛ}(𝒬)=0\le d_{ℛ}$. Otherwise, let ${ℛ}^{\prime }$ be the restriction of $ℛ$ to the domains of $𝒫.\phi$ and $𝒫.\psi$. Since $𝒬$ uses $𝒫$, it follows that ${ℛ}^{\prime }$ uses $𝒫$ and is hence a restriction of $𝒫$. If ${ℛ}^{\prime }=𝒫$, then by definition of an augmentation we know that the ${ℛ}^{\prime }$-shift of any arrow of $𝒬$ is $d_{𝒫}$. We obtain ${\sigma }_{{ℛ}^{\prime }}(𝒬)=d_{𝒫}$. Moreover, since $ℛ\ne 𝒬$, the $ℛ$-shift of at least one arrow of $𝒬\setminus 𝒫$ is non-zero. We obtain ${\sigma }_{ℛ}(𝒬)={\sigma }_{{ℛ}^{\prime }}(𝒬)=d_{𝒫}$. Since $𝒬$ is a minimal augmentation and extends $ℛ$, we know that $ℛ$ cannot be an augmentation of $𝒫$. It follows that $d_{ℛ}\ge d_{𝒫}$. Putting it together, we obtain $d_{ℛ}={\sigma }_{ℛ}(𝒬)$.

Lastly, if ${ℛ}^{\prime }\ne 𝒫$, then since $𝒫$ is locally correct and ${ℛ}^{\prime }$ is a restriction of $𝒫$, we have

We first show that ${\sigma }_{{ℛ}^{\prime }}(𝒫)\ge {\sigma }_{ℛ}(𝒬)$. First, none of the arrows of $ℛ\setminus {ℛ}^{\prime }$ are arrows of $𝒫$, so ${\sigma }_{{ℛ}^{\prime }}(𝒫)={\sigma }_{ℛ}(𝒫)$. Next, the $ℛ$-residual shift of $𝒬$ is the maximum of the $ℛ$-residual shifts of $𝒫$ and $𝒬\setminus 𝒫$. Since $𝒫$ is dominant, we know that the shift of any arrow of $𝒫$ is strictly greater than $d_{𝒫}$. As $𝒫\setminus ℛ$ is not empty, it follows that ${\sigma }_{ℛ}(𝒫)>d_{𝒫}$. On the other hand, by definition of an augmentation, we know that the shift of any arrow of $𝒬\setminus 𝒫$ is at most $d_{𝒫}$. So, we get ${\sigma }_{ℛ}(𝒬)=\max ({\sigma }_{ℛ}(𝒫),{\sigma }_{ℛ}(𝒬\setminus 𝒫))={\sigma }_{ℛ}(𝒫)$. Combining, we obtain ${\sigma }_{{ℛ}^{\prime }}(𝒫)\ge {\sigma }_{ℛ}(𝒬)$.

Next, we argue that $d_{ℛ}\ge d_{{ℛ}^{\prime }}$. By construction, $ℛ$ extends ${ℛ}^{\prime }$. As observed before, we have ${\sigma }_{{ℛ}^{\prime }}(𝒫)={\sigma }_{ℛ}(𝒫)>d_{𝒫}$. Combining with Equation (4), we obtain $d_{{ℛ}^{\prime }}\ge {\sigma }_{{ℛ}^{\prime }}(𝒫)>d_{𝒫}$. Let $a$ be an arrow of $ℛ\setminus {ℛ}^{\prime }$. Then $a$ is an arrow of the bottleneck $𝒬\setminus 𝒫$, so the shift of $a$ is exactly $d_{𝒫}$. In other words, . This means that we can apply Corollary 19, for the finite interleaving ${ℛ}^{\prime }$ and the ${ℛ}^{\prime }$-extension $ℛ$, to obtain $d_{ℛ}\ge d_{{ℛ}^{\prime }}$.

Thus, $d_{ℛ}\ge d_{{ℛ}^{\prime }}\ge {\sigma }_{{ℛ}^{\prime }}(𝒫)={\sigma }_{ℛ}(𝒬),$ which concludes the proof. $◀$ Recall that for each arrow $(x,y)$, with $x\in T_1$ and $y\in T_2$, of $𝒫$, both $x$ and $y$ are critical points. However, only the point $x$ has a “specified” target in the other tree. We say a point $x\in T_1$ or $y\in T_2$ is specified by $𝒫$, if $x\in \mathrm{dom}(𝒫.\phi )$ or $y\in \mathrm{dom}(𝒫.\psi )$ respectively (see Figure 11). For our last invariant, we argue that $𝒫$ specifies all critical points that are not vertices, i.e., $C_1[𝒫]\setminus V(T_1)\subseteq \mathrm{dom}(𝒫.\phi )$ and $C_2[𝒫]\setminus V(T_2)\subseteq \mathrm{dom}(𝒫.\psi )$.

By Lemma 20, we know that the bottleneck $𝒬\setminus 𝒫$ uses only $𝒫$-critical pairs. Consider such a pair $b$. If $b$ is an arrow critical pair, then without loss of generality assume $b=(x,y)$ for a point $x\in T_1$ and a point $y\in T_2$; the case $b=(y,x)$ is symmetric. By definition of an arrow critical pair, both $x$ and $y$ are $𝒫$-critical points. So the pair $b$ does not create any additional $𝒬$-critical points. As $𝒫$ already specifies all critical points that are not vertices and $𝒬$ uses $𝒫$, we know that $x$ must be a vertex. Since $𝒫$ is dominant, the shift of any arrow of $𝒫$ is strictly greater than $d_{𝒫}$. Moreover, the shift of any arrow of $𝒬\setminus 𝒫$ is exactly $d_{𝒫}$. Hence, the vertex $x$ cannot be specified by $𝒫$: at least one new vertex is specified.

If $b$ is a zigzag critical pair, then without loss of generality assume $b=(x_1,x_2)$ for two points $x_1$ and $x_2$ of $T_1$; if it is a pair of points of $T_2$ the argument is analogous. By definition of a zigzag critical pair, we know that both $x_1\in V(T_1)$ and $x_2\in V(T_1)$. Moreover, there is a point $y\in T_2$ such that $Q.\phi (x_1)=y$ and $Q.\psi (y)=x_2$. So, $x_1$ is a vertex that is specified by $𝒬$ but not by $𝒫$. Lastly, $b$ creates a single $𝒬$-critical point $y$, which is immediately specified. $◀$

Let $𝒫$ be the empty interleaving. Trivially, $𝒫$ is dominant and locally correct. Moreover, there are no (unspecified) critical points that are not vertices. Now, we iteratively replace $𝒫$ with a finite minimal $𝒫$-augmentation until the $𝒫$-residual interleaving distance becomes zero. By applying Lemmas 21 and 22 inductively, we maintain that $𝒫$ is dominant and locally correct, and specifies all critical points that are not vertices. Additionally, by Lemma 22, each iteration specifies at least one additional vertex. So after $i$ iterations, at least $i$ vertices are specified, and the total number of iterations is at most $|V(T_1)|+|V(T_2)|$. Afterwards, the residual interleaving distance is zero. Lemma 23 guarantees that a locally correct interleaving exists; its proof is similar to that of Lemma 21.

We sketch how the above construction can be translated into an incremental algorithm. To compute the residual interleaving distance, we modify the dynamic program by Touli and Wang [15] to also incorporate constraints induced by partial interleavings. We use the output to extract some augmentation. We then iteratively reduce the set of critical pairs by repeatedly calling the modified dynamic program until we obtain a (finite) minimal augmentation. This minimal augmentation, in turn, reduces the residual interleaving distance; we iterate until it has dropped to zero. To obtain a locally correct interleaving, we select suitable entries from the table filled by the modified dynamic program. A naive implementation of this algorithm takes $n$ iterations, each of which needs to compute the residual interleaving distance $O(n^2)$ times to obtain a minimal augmentation (since an augmentation contains $O(n^2)$ critical pairs). So, the total running time of our algorithm is $O(n^{3}T(n))$, where $T(n)$ is the running time of computing the residual interleaving distance. The algorithm by Touli and Wang [15] takes $O(n^4{2}^{\tau }{\tau }^{\tau +2}\log n)$ time, where $\tau$ is a parameter related to the maximum degrees in the input trees.