Robustness of Persistent Topological Features and Minimum Homological Cuts

As we explain in the full version of this paper [28], homological edge cuts of a class $\gamma \in H_1(K;ℝ)$ are naturally related to (ordinary) cuts in graphs. Namely, we show that a minimum homological edge cut can be found by optimizing the number ${\Vert \phi \Vert }_0$ of non-zero coefficients of a vector $\phi$ (indexed by the edges of $K$) under a set of linear constraints involving the boundary matrix of $K$. The relaxation of this problem obtained by optimizing the $1$-norm ${\Vert \phi \Vert }_1$ instead is a linear program. Its dual may be interpreted as a homological analog of the max-flow problem in graphs. Contrary to the graph setting, we show that there is no max-flow min-cut theorem in our case: homological max-flows are not necessarily integral, meaning the LP relaxation is not tight.

We prove positive and negative results on the computational complexity of the minimum homological cut problem (MHC) introduced above, in terms of the number of simplices $|K|$ in the complex $K$. By Proposition 4, these results have immediate implications on the complexity of determining adversarial robustness of bars. Our first contribution is an efficient algorithm for the case where $\gamma \in H_0(K)$ is a $0$-dimensional homology class, i.e., $p=0$.

Theorem 6 follows from the fact that a minimum homological cut of a class in $H_0$ is always equal to the vertex set of a connected component of $K$, as we show in Section 4.1.

Next, we show that finding a minimum homological cut is NP-hard, already when $p=1$.

We give the proof of Theorem 7 in Section 4.2. It relies on a reduction from Exact Cover by 3-Sets (X3C). In [23, pp. 246], X3C is used to show hardness of the problem of finding minimum weight solutions to linear equations. It was also used in [25] to show hardness of finding the sparsest approximate solution to a set of linear equations. As mentioned, we show in the full version of this paper [28] that (MHC) can be solved by finding the sparsest solution to a particular set of linear equations. In light of these observations, X3C is a natural candidate for showing hardness of (MHC). In our proof, we construct for any X3C-instance an equivalent instance of (MHC). Our construction relies on “gluing together” punctured discs, each representing a $3$-set of the X3C-instance, to obtain a topological space which is then triangulated carefully to ensure minimum homological cuts correspond to exact covers. This approach resembles earlier work on NP-hardness in homology localization [1, 15, 20]. A distinction is that these mostly rely on reductions from SAT-problems; to the best of our knowledge, a reduction from X3C was not considered before in this context. We remark that our construction can be extended to cover the case $s=0$. Via Proposition 4, our result also implies that testing $k$-adversarial robustness of bars (in degree $0$ and $1$) is hard in general.

Finally, we give an efficient algorithm for the following special case, which covers, e.g., subcomplexes of the Delauney triangulation of a finite metric data set in ${ℝ}^n$.

Our proof of Theorem 8 in Section 4.3 relies on Alexander duality, which can be used to construct the so-called extended dual graph of $K$. In [18], this graph was used to find optimal generators for certain homology classes: these correspond to minimum cuts in the graph. For us, the situation is precisely the opposite: as we will show, minimum homological cuts in $K$ correspond to shortest paths in the extended dual graph (allowing for efficient computation). The use of the extended dual graph in homology localization dates back to [31]; see also [9].

Complementing our hardness result, we give an efficiently computable heuristic based on the Hausdorff distance to test adversarial robustness of bars arising from the Rips filtration of a metric data set $X$. Namely, we show that any bar in the barcode of the Rips filtration of length at least

is automatically $k$-adversarily robust (in degree $0$)¹¹1The Rips filtration is not simplex-wise, therefore, as mentioned, we must break ties to obtain a simplex wise filtration to apply Definition 2. This result does not depend on the choice of tiebreaker.; see Section 5 for a precise statement. Moreover, we show that the parameter ${\mathscr{H}}_{X,k}$ can be computed in time $O({|X|}^2\log |X|)$. This result links adversarial robustness to classical stability results in persistent homology. It shows that our definition is at least as expressive as a naive definition based only on the length of bars and the Hausdorff stability of the Rips filtration. That is, sufficiently long bars are outlier-robust according to our definition (as one would expect). But importantly, our definition is also capable of recognizing relatively short bars as robust; see Figure 2.

A geometric $p$-simplex $\sigma$ in ${ℝ}^n$ is the convex hull of $p+1$ affinely independent vectors $v_0,\mathrm{\dots },v_p\in {ℝ}^n$. The elements of $V(\sigma ):=\{v_0,\mathrm{\dots },v_p\}$ are called the vertices of $\sigma$. If $\tau$ is the convex hull of a subset of the vertices of $\sigma$, then $\tau$ is called a face of $\sigma$. A geometric simplicial complex $K$ in ${ℝ}^n$ is a collection of geometric simplices in ${ℝ}^n$ with the properties that 1) the face of every simplex is in $K$; 2) for every pair of simplices $\sigma ,\tau \in K$ with non-empty intersection, $\sigma \cap \tau$ is in $K$. We denote the geometric realization of $K$ by $\Vert K\Vert :={\bigcup }_{\sigma \in K}\sigma \subseteq {ℝ}^n$, i.e. the subset of ${ℝ}^n$ consisting of the union of simplices that make up $K$. If $K$ is a geometric simplicial complex, then $A(K):=\{V(\sigma )|\sigma \in K\}$ is an abstract simplicial complex. We say that an abstract simplicial complex $L$ is embedded in ${ℝ}^n$ if $L\cong A(K)$ for some geometric simplicial complex $K$ in ${ℝ}^n$, and we define the geometric realization of the embedded simplicial complex $L$ to be $\Vert L\Vert :=\Vert K\Vert$.

For a field $𝔽$, and $p\in \mathbb{N}$, we denote by $C_p(K;𝔽)$ the simplicial $p$-chains on $K$. We write ${\partial }_p:C_p(K;𝔽)\to C_{p-1}(K;𝔽)$ for the boundary operator. We have subspaces of cycles $Z_p(K;𝔽)=\mathrm{Ker}({\partial }_p)$ and boundaries $B_p(K;𝔽)=\mathrm{Im}({\partial }_{p+1})$, and the simplicial homology of $K$ is defined as $H_p(K;𝔽)=Z_p(K;𝔽)/B_p(K;𝔽)$. Throughout, if we omit $𝔽$ from the notation, we mean homology over any field. For two complexes $K\subseteq K^{\prime }$, we denote the inclusion $K\hookrightarrow K^{\prime }$ by ${\iota }_{K\hookrightarrow K^{\prime }}$. Then, we write ${\iota }_{K\hookrightarrow K^{\prime }}^{\ast }:H_p(K)\to H_p(K^{\prime }),[c]\mapsto [{\iota }_{K\hookrightarrow K^{\prime }}(c)]$ for the induced maps in homology (suppressing $p$ in the notation).

Let $B=[b,d)$ be a bar in the barcode of ${\mathrm{PH}}_p(𝒦)$, thus with birth simplex ${\sigma }_B$ inserted at step $b$, and death simplex ${\tau }_B$ inserted at time $d$. Let $K_B=K_{d-1}$ be its predeath complex. Let $A\subseteq K^{(s)}$, and write ${𝒳}_{𝒦-A\hookrightarrow 𝒦}$ for the matching induced by the inclusion $𝒦-A\hookrightarrow 𝒦$. We show that $B\in \mathrm{Im}({𝒳}_{𝒦-A\hookrightarrow 𝒦})$ if and only $[\partial {\tau }_B]\in \mathrm{Im}({\iota }_{K_B-A\hookrightarrow K_B}^{\ast })$.

Note that any representative cycle for $B$ is homologous to a scalar multiple of $\partial {\tau }_B$ in $C_p(K_B)$, as $[\partial {\tau }_B]$ generates the kernel of $H_p(K_B)\to H_p(K_B\cup \{{\tau }_B\})$. If $B\in \mathrm{Im}({𝒳}_{𝒦-A\hookrightarrow 𝒦})$, there is thus a bar $B^{\prime }=[b^{\prime },d)$ in the barcode of the image module $\mathrm{Im}({\mathrm{PH}}_p(𝒦-A)\to {\mathrm{PH}}_p(𝒦))$. Then, any representative cycle $\xi \in C_p(K_{b^{\prime }}-A)\subseteq C_p(K_{b^{\prime }})$ for $[b^{\prime },d)$, when considered as a homology class $[\xi ]\in H_p(K_B)$ through the inclusions $K_{b^{\prime }}-A\hookrightarrow K_{b^{\prime }}\hookrightarrow K_B$, is in the kernel of $H_p(K_B)\to H_p(K_B\cup \{{\tau }_B\})$, and is hence homologous to a scalar multiple of $[\partial {\tau }_B]$.

Conversely, suppose that $[\partial {\tau }_B]$ is in the image of $H_p(K_B-A)\to H_p(K_B)$, and let $\xi \in C_p(K_B-A)$ be a cycle such that $[\xi ]=[\partial {\tau }_B]\in H_p(K_B)$. Let ${\xi }_1,\mathrm{\dots },{\xi }_k$ denote representative cycles for summands of $\mathrm{Im}({\mathrm{PH}}_p(𝒦-A)\to {\mathrm{PH}}_p(𝒦))$ so that the $[{\xi }_i]$ are linearly independent in $H_p(K_B)$, and $[\xi ]={\lambda }_1[{\xi }_1]+\mathrm{\dots }+{\lambda }_k[{\xi }_k]$. Since $[\xi ]$ is a non-zero element in the kernel of the map

we see that one of the generators ${\xi }_j$ must be in this kernel, and thus generate a summand isomorphic to ${𝕀}_{[b^{\prime },d)}$ for some . This shows that $B$ is in the image of ${𝒳}_{𝒦-A\hookrightarrow 𝒦}$. $◀$

Write $V=V(K)$. For any $A\subseteq V$, and any $v\in V\setminus A$ we have ${\iota }_{K-A\hookrightarrow K}^{\ast }([v])=[v]$. Furthermore, for any $v,w\in V$, we have $[v]=[w]$ (in $H_0(K)$) if and only if $v$ and $w$ lie in the same connected component of $K$. Since the classes $[v]$, $v\in V\setminus A$, generate $H_0(K-A)$, we thus have $\gamma \in \mathrm{Im}({\iota }_{K-A\hookrightarrow K}^{\ast })$ if and only if $V\setminus A$ contains a vertex in each connected component ${\mathrm{\Gamma }}_i$ of $K$ with ${\lambda }_i\ne 0$. Thus, $\gamma \notin \mathrm{Im}({\iota }_{K-A\hookrightarrow K}^{\ast })$ (i.e., $A$ is a homological cut) iff $A$ contains all the vertices of at least one connected component ${\mathrm{\Gamma }}_{\mathrm{\ell }}$ of $K$ with ${\lambda }_{\mathrm{\ell }}\ne 0$. $◀$

To determine a minimum homological vertex cut of a $0$-dimensional class in a simplicial complex $K$, it suffices by Proposition 10 to find its connected components. We can do so in time linear in $|V(K)|+|E(K)|$ using a depth-first search. $◀$

We give an explicit construction in the full version of this paper [28]. $◀$ Using Lemma 13, we can sketch our reduction; a complete proof is given in the full version [28].

We show that there exists a solution to the X3C-instance $(U,𝒮)$ if and only if there exists a cut for $\gamma \in H_1(K(U,𝒮))$ consisting of at most $c\cdot |U|+\frac{|U|}{3}+1$ edges. If ${𝒮}^{\ast }\subseteq 𝒮$ is a solution to $(U,𝒮)$, for each $u\in U$, we pick a cut $C_u$ for $[u]\in H_1(L_u)$ with the property that it contains one edge in the boundary labelled by $u$, and one in the boundary labeled by the set $S_u\in S^{\ast }$ for which $u\in S_u$. If we consistently choose the same edges in the intersections between surfaces, we can verify that $C={\bigcup }_{u\in U}{C}_u$ is a cut for $\gamma$ consisting of precisely $c\cdot |U|+\frac{|U|}{3}+1$ edges. Conversely, suppose $C$ is any cut for $\gamma$. Then it can be shown that for each $u\in U$, $C\cap L_u$ is a cut for $[u]\in H_1(L_u)$. By point 3 of Lemma 13, we then obtain a cover ${𝒞}_C$ for $U$. It can be checked that $|C|\ge c\cdot |U|+|{𝒞}_C|+1$. It follows that if $|C|\le c\cdot |U|+\frac{|U|}{3}+1$, then $|{𝒞}_C|=\frac{|U|}{3}$, and so ${𝒞}_C$ is an exact cover. $◀$

See the full version of this paper [28]. $◀$ Recall that $H^0({ℝ}^n\setminus \Vert K\Vert )$ consists of functions $f:{ℝ}^n\setminus \Vert K\Vert \to ℝ$ that are constant on each connected component of ${ℝ}^n\setminus \Vert K\Vert$. We represent ${\tilde{H}}^0({ℝ}^n\setminus \Vert K\Vert )$ by locally constant functions that are $0$ on the unbounded connected component. Similarly, we think of ${\tilde{H}}^0({𝒢}_C)$ as functions that are constant on the components of ${𝒢}_C$, and $0$ on the component containing $v_{\mathrm{\infty }}$. Moreover, if $C\subseteq C^{\prime }$, the map ${\tilde{H}}^0({𝒢}_{C^{\prime }})\to {\tilde{H}}^0({𝒢}_C)$ is given by a restriction of functions. The following proposition allows us to relate cuts for specific elements of $H_{n-1}(K)$ to paths in the extended dual graph ${𝒢}_K^{\ast }$ of $K$.

By Lemma 16, $\mathrm{AD}({\mathrm{𝟏}}_v)$ is in the image of $H_{n-1}(K-C)\to H_{n-1}(K)$ if and only if ${\mathrm{𝟏}}_v$ is in the image of ${\tilde{H}}^0({𝒢}_C)\to {\tilde{H}}^0({𝒢}_{\mathrm{\varnothing }})$. This is the case if and only if the function ${\mathrm{𝟏}}_v$ extends to a function $\phi \in {\tilde{H}}^0({𝒢}_C)$, which is possible if and only if $v$ is in a different component from any other vertex of $V_{{ℝ}^n\setminus K}$ inside ${𝒢}_C$. That means that $C$ is a homology cut for $\mathrm{AD}({\mathrm{𝟏}}_v)$ if and only if there is a path in ${𝒢}_C$ from $v$ to some other vertex of $V_{{ℝ}^n\setminus K}$, proving our claim. $◀$

We need the following generalization of the above proposition, that allows us to relate cuts for arbitrary elements of $H_1(K)$ to paths in ${𝒢}_K^{\ast }$; see Figure 4 for an example.

The proof is similar to that of Proposition 17, with the following adjustment: The function $\psi ={\sum }_{v\in V_{{ℝ}^n\setminus K}}{\alpha }_v{\mathrm{𝟏}}_v\in {\tilde{H}}^0({𝒢}_{\mathrm{\varnothing }})$ extends to a function $\phi \in {\tilde{H}}^0({𝒢}_C)$ iff no pair of vertices $v,w\in V_{{ℝ}^n\setminus K}$ for which $\psi (v)={\alpha }_v\ne {\alpha }_w=\psi (w)$ is in the same component of ${𝒢}_C$. $◀$

To compute a minimum homological cut for a class $\gamma \in H_{n-1}(K)$ of an $n$-complex $K$ embedded in ${ℝ}^n$, we proceed in three steps:

1. 1.

   Constructing the extended dual graph. First, we construct ${𝒢}_K^{\ast }$. For this we use the Void Boundary Reconstruction algorithm [18, Section 4], which outputs sets of oriented simplices $({\overrightarrow{\xi }}_1,\mathrm{\dots },{\overrightarrow{\xi }}_k)$ that constitute the boundaries of the components of ${ℝ}^n\setminus \Vert K\Vert$ (cf. Figure 4) in time bounded by $O({|K|}^2)$. We assume wlog that ${\overrightarrow{\xi }}_k$ constitutes the boundary of the unbounded component of ${ℝ}^n\setminus \Vert K\Vert$. The sum of oriented simplices in any of the ${\overrightarrow{\xi }}_i$ with bounding a component $R_i\subseteq {ℝ}^n\setminus \Vert K\Vert$, which we denote by $[{\overrightarrow{\xi }}_i]$, represents the Alexander dual to the function $f_i\in {\tilde{H}}^0({ℝ}^n\setminus \Vert K\Vert )$ that is constant $1$ on $R_i$, and $0$ everywhere else. From the $({\overrightarrow{\xi }}_1,\mathrm{\dots },{\overrightarrow{\xi }}_k)$ we can construct ${𝒢}_K^{\ast }$ in time linear in $k+|K|$. Each ${\overrightarrow{\xi }}_i$ corresponds to a vertex $v_i=v_{R_i}\in V_{{ℝ}^n\setminus K}\subseteq V({𝒢}_K^{\ast })$.

2. 2.

   Expressing $\gamma$ in an appropriate basis. We write $\gamma$ as $\gamma ={\sum }_{i=1}^k{\alpha }_i[{\overrightarrow{\xi }}_i]$ with ${\alpha }_i\in 𝔽$, ${\alpha }_k=0$. This comes down to a change of basis, which can be done in matrix-multiplication time. The representation of $\gamma$ is precisely the representation as assumed in Proposition 18, as $[{\overrightarrow{\xi }}_i]$ is the Alexander dual of ${\mathrm{𝟏}}_{v_i}$.

3. 3.

   Determining shortest paths. Using breadth-first search, we can find the minimum distance between any two vertices $v_i,v_j\in V_{{ℝ}^n\setminus K}$ inside ${𝒢}_K^{\ast }$ for which ${\alpha }_i\ne {\alpha }_j$ in time bounded by $O(k\cdot |{𝒢}_K^{\ast }|)$. Let $P$ denote a path in ${𝒢}_K^{\ast }$ achieving this minimum. The set of $(n-1)$-simplices $C_P$ dual to the edges constituting $P$ form a cut for $\gamma$ by Proposition 18. Since the edges dual to any cut $C$ for $\gamma$ must contain a path between vertices of $V_{{ℝ}^n\setminus K}$ with differing coefficients, the cut $C_P$ is a minimum cut by minimality of $P$.

$◀$