Computing Betti Tables and Minimal Presentations of Zero-Dimensional Persistent Homology

Betti tables are a classical descriptor of a multigraded modules [18, 29, 34], which encode the grades of the generators in a minimal projective resolution of the module (see, e.g., Figure 1 and Example 15). Informally, one can interpret the Betti tables of a graded module as recording the grades at which there is an algebraic change in the module. Graded modules have applications in a wide variety of areas of pure and applied mathematics, including topological data analysis, and more specifically, persistence theory [33, 6], where they are known as persistence modules, and where they are used to describe the varying topology of simplicial complexes and other spaces as they are filtered by one or more real parameters.

Informally, one-parameter persistence modules correspond to $\mathbb{Z}$-graded $𝕜[x]$-modules, and can thus be classified up to isomorphism effectively. Multiparameter persistence modules [11, 6] correspond to ${\mathbb{Z}}^n$-graded $𝕜[x_1,\mathrm{\dots },x_n]$-modules, and thus do not admit any reasonable classification up to isomorphism (formally, one is dealing with categories of wild representation type [31]; see [11, 2, 4] for manifestations of this phenomenon in persistence theory). For this reason, much of the research in multiparameter persistence is devoted to the study of incomplete descriptors of multiparameter persistence modules. Betti tables (also known as multigraded Betti numbers) provide one of the simplest such descriptors, and various properties of this descriptor from the point of view of persistence theory are well understood, including their effective computation [27, 25, 19, 3], their relationship to discrete Morse theory [22, 1, 21], their optimal transport Lipschitz-continuity with respect to perturbations [32], and their usage in supervised learning [28, 39].

The simplest case beyond the one-parameter case (i.e., the singly graded case) is the two-parameter case (i.e., the bigraded case). Here, one is usually given a finite simplicial complex $K$ together with a function $f:K\stackrel{}{\to }{ℝ}^2$ mapping the simplices of $K$ to ${ℝ}^2$, which is monotonic, i.e., such that $f(\sigma )\le f(\tau )$ whenever $\sigma \subseteq \tau \in K$ (see Figure 1 for an example). By filtering $K$ using $f$ and taking homology in dimension $i\in \mathbb{N}$ with coefficients in a field $𝕜$, one obtains an ${ℝ}^2$-graded module, or equivalently, a functor $H_i(K,f;𝕜):{ℝ}^2\stackrel{}{\to }{\mathrm{𝐕𝐞𝐜}}_{𝕜}$. Examples include geometric complexes of point clouds filtered by a function on data points, such as a density estimate [8, 12], and graphs representing, say, molecules or networks, filtered by two application-dependent quantities [15]. Applying homology to a bifiltered simplicial complex is justified by the fact that the output is automatically invariant under relabeling, meaning that any operation based on this module, such as computing its Betti tables, will result in a relabeling-invariant descriptor. In this setup, one of the main stability results of [32] implies that, for $f,g:K\stackrel{}{\to }{ℝ}^2$ any two monotonic functions, we have ${\Vert {\mu }_f-{\mu }_g\Vert }_1^{𝖪}\le \mathrm{\hspace{0.33em}2}\cdot {\Vert f-g\Vert }_1$, where $\parallel -{\parallel }_1^{𝖪}$ denotes the Kantorovich–Rubinstein norm between signed measures (also known as the $1$-Wasserstein distance), and ${\mu }_f$ and ${\mu }_g$ are the signed measures on ${ℝ}^2$ obtained as the alternating sum of Betti tables of $H_i(K,f;𝕜)$ and $H_i(K,g;𝕜)$, respectively; see [28, Theorem 1] for details. The upshot is that the Betti tables of the homology of bifiltered simplicial complexes form a perturbation-stable, relabeling-invariant descriptor of bifiltered simplicial complexes.

The current standard algorithm for computing the Betti tables of $H_i(K,f;𝕜)$ in the two-parameter case is the Lesnick–Wright algorithm [27], which runs in time $O({|K|}^3)$. Because of results such as those of [17], one does not expect to find algorithms with better worst-case time complexity than matrix-multiplication time, at least when $i\in \mathbb{N}$ is arbitrary. Current options to speed up practical computations include sparsifying the filtered complex before computing homology [42], as well as computational shortcuts that are known to significantly reduce computational time in practice [25, 3]. Nevertheless, computational cost is still a main bottleneck in real-world applications of persistence, limiting the size of the datasets on which it can be applied.

In many applications, persistent homology in dimension zero is all that is required, as it encodes information about the changes in connectivity of filtered simplicial complexes, making it useful for clustering [10, 9, 14, 8, 35, 38] and graph classification [41, 13, 24, 28, 23].

But, if one is only interested in $0$-dimensional homology $H_0(K,f;𝕜)$, algorithms relying on linear algebra are usually far from the most efficient ones: For example, in the one-parameter case, the Betti tables of the $0$-dimensional homology of an $ℝ$-filtered graph $(G,f)$ can be computed in $O(|G|\log |G|)$ time by first sorting the simplices of $G$ by their $f$-value, and then doing an ordered pass using a union-find data structure; in the language of barcodes, the Betti tables simply record the endpoints of the barcode, and the barcode can be computed using the elder rule (see [16, pp. 188] or [35, Algorithm 1]).

The paper is concerned with the following question: What is the complexity of computing the Betti tables of graphs filtered by posets other than $ℝ$?

We introduce algorithms for the computation of a minimal set of generators and of a minimal presentation of $0$-dimensional persistent homology indexed by an arbitrary poset.

We also introduce a more efficient algorithm specialized to the two-parameter case, which computes all Betti tables, that is, $0$th, $1$st, and $2$nd, by Hilbert’s syzygy theorem.

Of note is the fact that Betti tables of $0$-dimensional two-parameter persistent homology can be computed in log-linear time, as in the one-parameter case.

As another main contribution, we establish a connection between minimal presentations and connectivity properties of filtered graphs (Theorems 23 and 25), which allows us to abstract away the algebraic problem, and focus on a simpler combinatorial problem. The correctness of our algorithms is based on this. Another interesting consequence of these results is that, for arbitrary posets, the $0$th and $1$st Betti tables of $0$-dimensional persistent homology are independent of the field of coefficients, while for the poset ${ℝ}^2$, all Betti tables of a filtered graph are independent of the field of coefficients.

The main body of the paper has three sections: one on background (Section 2), one on theoretical results (Section 3), and one on algorithms (Section 4). [30, Appendix A] contains proofs.

In order to describe and prove the correctness of our algorithms, we introduce, in the theory section, the notion of a minimal filtered graph (Definition 17). Informally, a minimal filtered graph is one whose vertices and edges induce a minimal presentation of its $0$-dimensional persistent homology (see Theorem 23). A graph is not minimal if it has some edge that can be either contracted or deleted without changing its $0$-dimensional persistent homology (for example, the graph of Figure 1 has both contractible and deletable edges, and is thus not minimal; see Examples 15 and 18). The idea is that, by contracting and deleting edges that do not change $0$-dimensional persistent homology, one inevitably ends up with a minimal filtered graph, from which a minimal presentation can be easily extracted. Our main theoretical contributions (Theorems 23 and 25) make this idea precise by giving an explicit minimal presentation of $H_0$ of any minimal filtered graph, and an explicit minimal resolution of $H_0$ of any minimal ${ℝ}^2$-filtered graph. Our main algorithmic contributions are efficient algorithms for contracting and deleting edges as necessary. Algorithm 4 makes use of a dynamic tree data structure [40], which is the main ingredient that allows us to compute the Betti tables of bifilitered graphs in log-linear time; we give more details in Section 4.

The filtrations considered in this paper are $1$-critical, meaning that each simplex (vertex or edge, in the case of graphs) appears at exactly one grade. In [30, Appendix B], we describe a simple preprocessing step to turn a finite multi-critical filtration by a lattice into a $1$-critical filtration with the same $0$-dimensional homology. In the two-parameter case, this construction does not change the input complexity, but for other lattices it may increase the input size. Note that the construction does not (necessarily) preserve $1$-dimensional homology.

To the best of our knowledge, the only subcubic algorithm related to Algorithm 4 is that of [8], which, in particular, can be used to compute the Betti tables of $H_0$ of a function-Rips complex of a finite metric space $X$ in time $O({|X|}^2\log |X|)$. When applied to a function-Rips complex, our Algorithm 4 has the same time complexity; however, our Algorithm 4 applies to arbitrary bifiltered graphs, while function-Rips complexes are very special (and do not include arbitrary filtered graphs). The inner workings of Algorithm 4 are also different from those of [8]: While we rely on dynamic trees, their algorithm relies on a dynamic minimum spanning tree, and, notably, on the fact that, in a function-Rips bifiltration, vertices are filtered exclusively by one of the two filtering functions (so that vertices are linearly ordered in the bifiltration).

The computation of minimal presentations of ${ℝ}^n$-filtered complexes is studied in [5]. Since they consider homology in all dimensions, their complexity is significantly worse than the quadratic complexity of Algorithm 3, which only applies to $0$-dimensional homology.

Part of the contributions in this paper could be rephrased using the language of discrete Morse theory for multiparameter filtrations [1, 37, 7], specifically, Algorithms 1 and 2 are essentially computing acyclic matchings which respect the filtration. However, this point of view requires extra background, and, to the best of our understanding, cannot be used to describe the more interesting Algorithm 4.

A graph $G=(V,E,\partial )$ consists of finite sets $V$ and $E$, and a function $\partial :E\stackrel{}{\to }V\times V$. We refer to the elements of $V$ as vertices, typically denoted $v,w,x,y\in V$, and to the elements of $E$ as edges, typically denoted $e,d,h\in E$. If $\partial e=(v,w)$, we write $e_0=v$ and $e_1=w$. The size of a graph $G$ is $|G|=|V|+|E|$.

A subgraph of a graph $G=(V,E,\partial )$ is a graph $G^{\prime }=(V^{\prime },E^{\prime },{\partial }^{\prime })$, where $V^{\prime }\subseteq V$, $E^{\prime }\subseteq E$, and such that ${\partial }^{\prime }={\partial |}_{E^{\prime }}$ takes values in $V^{\prime }\times V^{\prime }\subseteq V\times V$. If $G^{\prime }$ is a subgraph of $G$, we write $G^{\prime }\subseteq G$.

If $E^{\prime }\subseteq E$ is a set of edges of $G$, we let $G\setminus E^{\prime }$ be the subgraph of $G$ with the same vertices and $E\setminus E^{\prime }$ as set of edges.

Let $𝒫$ be a poset. A $𝒫$-filtered graph $(G,f^V,f^E)$ consists of a graph $G$ and functions $f^V:V\stackrel{}{\to }𝒫$ and $f^E:E\stackrel{}{\to }𝒫$ such that $f^V(e_0)\le f^E(e)$ and $f^V(e_1)\le f^E(e)$ for all $e\in E$. When there is no risk of confusion, we refer to $𝒫$-filtered graphs simply as filtered graph, and denote both $f^V$ and $f^E$ by $f$ and the filtered graph $(G,f^V,f^E)$ by $(G,f)$.

If $(G,f)$ is a $𝒫$-filtered graph and $r\in 𝒫$, we let ${(G,f)}_r$ be the subgraph of $G$ with vertices $\{v\in V:f(v)\le r\}$ and edges $\{e\in E:f(e)\le r\}$.

Let $𝒫$ be a poset. A $𝒫$-persistence module is a functor $𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$, where $𝒫$ is the category associated with $𝒫$. Explicitly, a $𝒫$-persistence module $M:𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$ consists of the following:

• $\mathrm{■}$

  for each $r\in 𝒫$, a vector space $M(r)$;

• $\mathrm{■}$

  for each pair $r\le s\in 𝒫$, a linear morphism ${\phi }_{r,s}^M:M(r)\stackrel{}{\to }M(s)$; such that

• $\mathrm{■}$

  for all $r\in 𝒫$, the linear morphism ${\phi }_{r,r}^M:M(r)\stackrel{}{\to }M(r)$ is the identity;

• $\mathrm{■}$

  for all $r\le s\le t\in 𝒫$, we have ${\phi }_{s,t}^M\circ {\phi }_{r,s}^M={\phi }_{r,t}^M:M(r)\stackrel{}{\to }M(t)$.

When there is no risk of confusion, we may refer to a $𝒫$-persistence module as a persistence module. An $n$-parameter persistence module ($n\ge 1\in \mathbb{N}$) is an ${ℝ}^n$-persistence module.

A morphism $g:M\stackrel{}{\to }N$ between persistence modules is a natural transformation between functors, that is, a family of linear maps ${\{g_r:M(r)\stackrel{}{\to }N(r)\}}_{r\in 𝒫}$ with the property that ${\phi }_{r,s}^N\circ g_r=g_s\circ {\phi }_{r,s}^M:M(r)\stackrel{}{\to }N(s)$, for all $r\le s\in 𝒫$. Such a morphism is an isomorphism if $g_r:M(r)\stackrel{}{\to }N(r)$ is an isomorphism of vector spaces for all $r\in 𝒫$.

If $M,N:𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$ are persistence modules, their direct sum, denoted $M\oplus N:𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$, is the persistence module with $(M\oplus N)(r)≔M(r)\oplus N(r)$ and with ${\phi }_{r,s}^{M\oplus N}≔{\phi }_{r,s}^M\oplus {\phi }_{r,s}^N:M(r)\oplus N(r)\stackrel{}{\to }M(s)\oplus N(s)$, for all $r\le s\in 𝒫$.

Similarly, a $𝒫$-persistent set is a functor $𝒫\stackrel{}{\to }\mathrm{𝐒𝐞𝐭}$. The concepts of $n$-parameter persistent set, and of morphism and isomorphism between persistent sets are defined analogously.

If $S\in \mathrm{𝐒𝐞𝐭}$, we let ${⟨S⟩}_{𝕜}\in \mathrm{𝐕𝐞𝐜}$ denote the free vector space generated by $S$; this defines a functor ${⟨-⟩}_{𝕜}:\mathrm{𝐒𝐞𝐭}\stackrel{}{\to }{\mathrm{𝐕𝐞𝐜}}_{𝕜}$. Let $G=(V,E,\partial )$ be a graph. Consider the $𝕜$-linear map

The $0$-dimensional homology of $G$, denoted $H_0(G;𝕜)$, is the $𝕜$-vector space $\mathrm{coker}(d)$, and the $1$-dimensional homology of $G$, denoted $H_1(G;𝕜)$, is the $𝕜$-vector space $\ker (d)$. In particular, every vertex $v\in V$ gives an element $[v]\in H_0(G;𝕜)$. When there is no risk of confusion, we omit the field $𝕜$ and write $H_i(G)$ instead of $H_i(G;𝕜)$.

Homology is functorial, in the following sense. If $G^{\prime }=(V^{\prime },E^{\prime },{\partial }^{\prime })$ is a subgraph of $G$, we have a commutative square

induced by the inclusions $V^{\prime }\subseteq V$ and $E^{\prime }\subseteq E$. This induces linear maps $H_0(G^{\prime })\stackrel{}{\to }{H}_0(G)$ and $H_1(G^{\prime })\stackrel{}{\to }{H}_1(G)$. Moreover, the morphism $H_{\bullet }(G^{\prime \prime })\stackrel{}{\to }{H}_{\bullet }(G)$ induced by a subgraph $G^{\prime \prime }\subseteq G^{\prime }\subseteq G$ is equal to the composite $H_{\bullet }(G^{\prime \prime })\stackrel{}{\to }{H}_{\bullet }(G^{\prime })\stackrel{}{\to }{H}_{\bullet }(G)$.

If $(G,f)$ is a $𝒫$-filtered graph, and $i\in \{0,1\}$, we get a $𝒫$-persistence module $H_i(G,f):𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$, with $H_i(G,f)(r)=H_i({(G,f)}_r)$, and with structure morphism $H_i(G,f)(r)\stackrel{}{\to }{H}_i(G,f)(s)$ for $r\le s\in 𝒫$ induced by the inclusion of graphs ${(G,f)}_r\subseteq {(G,f)}_s$.

The set of connected components of $G$, denoted ${\pi }_0(G)$, is the quotient of $V$ by the equivalence relation $\sim$ where $v\sim w\in V$ if and only if there exists a path in $G$ between $v$ and $w$. If $v\in V$, we let $[v]\in {\pi }_0(G)$ denote its connected component, so that $[v]=[w]\in {\pi }_0(G)$ if and only if $v$ and $w$ belong to the same connected component.

The set of connected components is also functorial with respect to inclusions $G^{\prime }\subseteq G$, since $[v]=[w]\in {\pi }_0(G^{\prime })$ implies $[v]=[w]\in {\pi }_0(G)$. In particular, if $(G,f)$ is a $𝒫$-filtered graph, we get a $𝒫$-persistent set ${\pi }_0(G,f):𝒫\stackrel{}{\to }\mathrm{𝐒𝐞𝐭}$, with ${\pi }_0(G,f)(r)={\pi }_0({(G,f)}_r)$, and with the structure morphism ${\pi }_0(G,f)(r)\stackrel{}{\to }{\pi }_0(G,f)(s)$ for $r\le s\in 𝒫$ induced by the inclusion of graphs ${(G,f)}_r\subseteq {(G,f)}_s$.

The following is straightforward to check.

Given $r\in 𝒫$, let ${𝖯}_r:𝒫\stackrel{}{\to }\mathrm{𝐕𝐞𝐜}$ be the persistence module with ${𝖯}_r(s)=𝕜$ if $r\le s$ and ${𝖯}_r(s)=0$ if $r\nleqq s$, with all structure morphisms $𝕜\stackrel{}{\to }𝕜$ being the identity. Equivalently, one can define ${𝖯}_r$ to be $H_0(\{x\},\mathrm{\varnothing },\partial ,f)$, with $f(x)=r$.

Note that, drawing inspiration from commutative algebra, projective persistence modules are sometimes also called free. The following result justifies the term projective used in Definition 3; see, e.g., [36, Section 3.1] for the usual notion of projective module.

The next result is standard; see, e.g., [26, Proposition 6.24].

The following notation is sometimes convenient.

In particular, a minimal finite projective $0$-resolution is simply a projective cover.

The Betti tables of $M$ are also sometimes called the (multigraded) Betti numbers of $M$. The Betti tables of $M$, as defined in Definition 12, are independent of the choice of minimal presentation or resolution, thanks to the following standard result.

We first introduce some technical notions and overview the algorithms.

Two $𝒫$-filtered graph $(G,f)$ and $(G^{\prime },f^{\prime })$ are homology-equivalent (over $𝕜$) if $H_0(G,f;𝕜)\cong H_0(G^{\prime },f^{\prime };𝕜)$ and $H_1(G,f;𝕜)\cong H_1(G^{\prime },f^{\prime };𝕜)$.

Algorithm 2 reduces the input filtered graph to a vertex-minimal filtered graph by collapsing edges; it relies on Algorithm 1, which collapses local collapsible edges. A local collapsible edge of $(G,f)$ is an edge $e$ such that $e_0\ne e_1$ and $f(e)=f(e_0)=f(e_1)$. Algorithm 2 then identifies minimal vertices, that is, vertices with no adjacent collapsible edge decreasing the grade, and runs a depth-first search from each of these to build and collapse a tree of collapsible edges.

Algorithm 3 first calls Algorithm 2 to perform all collapses and then deletes deletable edges until there are no more deletable edges. It then builds the presentation of Lemma 16.

Algorithm 4 first calls Algorithm 2 to perform all collapses, and then goes through all edges, with respect to the lex order on their grades, and identifies deletable edges, non-deletable edges, and cycle-creating edges.

Since this is used in Algorithm 4, we now introduce the dynamic dendrogram data structure, which, informally, represents a dendrogram where elements merge as time goes from $-\mathrm{\infty }$ to $\mathrm{\infty }$, and is dynamic in that one is allowed to change the dendrogram by making two elements merge earlier.

A dynamic dendrogram $D$ can easily and efficiently be implemented using a mergeable tree $T$ in the sense of [20]. These trees store heap-ordered forests, i.e., a collection of rooted labeled trees, where the labels decrease (or in our case increase) along paths to the root. The data structures support a wealth of operations for dynamic updates. We need only three of them: $\mathrm{𝗂𝗇𝗌𝖾𝗋𝗍}(v,t)$ inserts node $v$ with label $t$ into the forest; $\mathrm{𝗇𝖼𝖺}(v,w)$ finds the nearest common ancestor of two nodes $v$ and $w$; $\mathrm{𝗆𝖾𝗋𝗀𝖾}(v,w)$ merges the paths of $v$ and $w$ to their root(s) while preserving the heap order. We use these operations to implement dynamic dendrograms as follows:

• $\mathrm{■}$

  To implement $D.\mathrm{𝗍𝗂𝗆𝖾}\mathrm{\_}\mathrm{𝗈𝖿}\mathrm{\_}\mathrm{𝗆𝖾𝗋𝗀𝖾}(v,w)$, return the label of $T.\mathrm{𝗇𝖼𝖺}(v,w)$.

• $\mathrm{■}$

  To implement $D.\mathrm{𝗆𝖾𝗋𝗀𝖾}\mathrm{\_}\mathrm{𝖺𝗍}\mathrm{\_}\mathrm{𝗍𝗂𝗆𝖾}(v,w,t)$, let $h$ be a new vertex not already in the mergeable tree $T$, do $T.\mathrm{𝗂𝗇𝗌𝖾𝗋𝗍}(h,t)$, then $T.\mathrm{𝗆𝖾𝗋𝗀𝖾}(v,h)$, and $T.\mathrm{𝗆𝖾𝗋𝗀𝖾}(w,h)$.

In the algorithms, to represent a Betti table ${\beta }_i(M)$ we use a list of elements of the indexing poset. If we have represented the $0$th and $1$st Betti tables of $M$ with lists ${\beta }_0$ and ${\beta }_1$, we represent a minimal presentation for $M$ with a sparse matrix using coordinate format, that is, with a list of triples $(i,j,v)$ representing the fact that $v$ is the entry at row $i$ and column $j$, and where $i$ represents the $i$th element of ${\beta }_0$ and $j$ represents the $j$th element of ${\beta }_1$.

We conclude the paper by using the theoretical results of Section 3 to prove the main results in the introduction. Proofs for the results in this section are in [30, Appendix A.3].

We start by with a convenient lemma, which gives conditions under which one can collapse an entire subgraph and produce a homology-equivalent filtered graph. The following definition describes the type of subgraph that can be collapsed.

With these results, we prove Theorem A and Theorem B in [30, Appendix A.4].