Introduction↩︎

Discrete homology groups of a graph, introduced in barcelo-capraro-white?, have proven over the previous decade to be both important and interesting graph invariants. Their importance is underscored by the wealth of applications that they have found, ranging from pure mathematics, specifically areas such as hyperplane arrangements barcelo-laubenbacher? and matroid theory chalopin-chepoi-osajda?, to quite applied fields, including network analysis atkin:i?, atkin:ii? and topological data analysis kapuklin-kershaw:data-analysis?. There is currently very little that we understand about discrete homology groups, even of very small graphs. Case in point: the Greene sphere, named after Curtis Greene, is a graph with 10 vertices and 16 edges whose discrete homology groups are known only up to degree \(3\).

In recent years, significant effort was devoted to developing software to compute discrete homology groups. The first major step in this direction was taken in barcelo-greene-jarrah-welker:comparison?, where machine-assisted computations were used to show that discrete homology sees qualitatively different information than path homology. The algorithms developed there could compute the second discrete homology groups of most small graphs, but were generally unable to go beyond that. The state of the art algorithm, independent of the homological degree, was developed several years later in a preprint kapuklin-kershaw:computations?, where several innovations were introduced, notably the pairing of lower-dimensional cubes to obtain higher-dimensional ones that subsequently unlocked numerous additional speedups. This algorithm is now commonly referred to in literature as cubical.

The aforementioned computational work has since informed many theoretical results and, conversely, was itself made possible by theoretical contributions. For example, the work of Behrens and Jamil behrens-jamil? used the degree spectral sequence to provide a theoretical justification of the computation of the third discrete homology group of the Greene sphere from kapuklin-kershaw:computations?. Likewise, carranza-kapulkin:discrete-homotopy-hypothesis? provided theoretical justification for several other computations of discrete homology and homotopy groups of graphs. In the opposite direction, the theoretical work of carranza-kapulkin:cubical-setting?, barcelo-greene-jarrah-welker:connections?, kapulkin-mavinkurve?, greene-welker-wille? provides the necessary mathematical foundation to ensure the correctness of algorithms developed in kapuklin-kershaw:computations?. Put together, the interactions between the theoretical and the computational side of the field make discrete homotopy theory an active and vibrant area.

In ender-kapulkin:fast-h1?, a new algorithm, termed cellular, for computing the first discrete homology group was proposed. The algorithm is based on the observation that the first discrete homology group of a graph can be computed as the (classical) first discrete homology group of a cell complex (hence ‘cellular’ algorithm) obtained from a graph by gluing 2-dimensional cells into every 3- and 4-cycle. In other words, the question of computing discrete homology can be reduced to finding 3- and 4-cycles in a graph and doing a matrix computation, with a host of efficient methods available for both of these operations. The present paper continues this line of research by outlining a strategy for finding higher-dimensional analogues of \(3\)- and \(4\)-cycles.

By definition, the basis of the singular chain complex \(C_\bullet(G)\) associated to a graph \(G\) is given, in degree \(n\), by non-degenerate graph maps from the \(n\)-dimensional hypercube \(Q^n \to G\). Its grows doubly exponentially with \(n\), making computations of the fourth discrete homology group not feasible in most cases. The work of ender-kapulkin:fast-h1? can be understood in this context as wanting to replace the chain complex \(C_\bullet(G)\) with a quasi-isomorphic one, call it \(S_\bullet(G)\), with the property that, for every positive integer \(n\), we have \(\dim S_n(G) \ll \dim C_n(G)\). Indeed, we can reinterpret the aforementioned result by saying that \(S_1(G)\) is free on the edges and \(S_2(G)\) is free on \(3\)- and \(4\)-cycles of \(G\).

While we are unable to find \(S_3(G)\) that extends this tentative chain complex, we are able to find a small subspace \(S_3(G) \subseteq C_3(G)\) spanned by injective maps from five basic shapes to \(G\) with the property that the restriction of the differential \(\partial_3 \colon C_3(G) \to C_2(G)\) to \(S_3(G)\) has the same image (and, in particular, the same rank) as the differential itself. Since the most expensive part of the computation of the second discrete homology group is identifying and reducing the matrix of this differential, we are able to improve computation time. It was perhaps well-known to experts that these basic shapes should be drawn from quotients of the 3-dimensional hypercube; our contribution lies in identifying the specific five shapes that need to be considered.

Organization. This paper is organized as follows. In 1, we review the necessary background on discrete homology. In 2, we describe our algorithm for computing the second discrete homology group. Finally, in 3, we report on the experiments that compare our algorithm with the now-standard cubical algorithm.

Acknowledgments. We have greatly benefited from conversations with D. Carranza and N. Kershaw. The idea behind 10 and the implementation of the algorithm in 11 were given to the authors by ChatGPT.

1 Discrete homology↩︎

In this section, we review the definition of discrete homology of graphs, following barcelo-capraro-white?, barcelo-greene-jarrah-welker:comparison?, barcelo-greene-jarrah-welker:vanishing?. We begin by recalling the definition of a graph.

There is more than one notion of a product of two graphs, but for the purposes of defining discrete homology, we need only consider the box product.

Now that we have a notion of graph products, we can build up the structures that give us a chain complex to compute the homology of. The structures that we use are cubes in a graph, which are given by the following two definitions.

Given a singular \(n\)-cube, one can ask about its faces. In particular, defining faces allows us to track whether or not a singular \(n\)-cube is degenerate.

We now have everything we need to give a definition of discrete homology. We begin with the following definition.

We are now ready to give the definition of the boundary of a singular \(n\)-cube, and finally of the discrete homology groups of a graph.

We set \(\partial_0\) to be the trivial map. In barcelo-capraro-white?, it was shown that for any \(n \geq 0\), we have \(\partial_n \circ \partial_{n+1} = 0\) and \(\partial_n[D_n(G)] \subseteq D_{n-1}(G)\). Thus if we set \(C_{-1}(G) = (0)\), we obtain a chain complex \(C(G) = (C_{\bullet}, \partial_{\bullet})\).

2 Towards computing higher discrete homology groups↩︎

Computing discrete homology directly from the definition is virtually impossible by hand. Case in point: the second and third discrete homology group of the Greene sphere, a graph with only 10 vertices and 16 edges, was only identified using machine computations on large compute clusters, while the fourth and higher homology groups of that graph remain unknown. It is however possible to speed up computations of the first discrete homology group of a graph \(G\), which was already rather inefficient. To do so, we might instead compute cellular homology of a CW-complex \(X_G\) associated to \(G\). The \(1\)-skeleton of \(X_G\) is given by \(G\) and we glue in a single \(2\)-cell for every (simple) \(3\)- and \(4\)-cycle in \(G\).

This construction was exploited in ender-kapulkin:fast-h1? to obtain an algorithm for computing the first discrete homology group that outperforms existing algorithms kapuklin-kershaw:computations?. The key insight here is that the vector space \(C_2(G)\) can be replaced by a vector space \(U_2(G)\) of a much smaller dimension.

When trying to generalize this to higher dimensions, one must answer the following question: what are the higher-dimensional analogues of \(3\)- and \(4\)-cycles? Given an answer to this question, one can try to build a CW-complex by gluing \(n\)-cells into each such basic shape. The \(3\)- and \(4\)-cycles in a graph \(G\) need to be understood here in relation to the object they are replacing, namely maps \(Q^2 \to G\). More precisely, both \(3\)- and \(4\)-cycles arise as quotients of \(Q^2\), the notion that we now recall.

We note that a graph map surjective on edges is automatically surjective on vertices, since we assume that our graphs are reflexive.

An important way of constructing quotient graphs is by taking factorizations of graph maps. More precisely, given a graph map \(f \colon G \to H\), we can factor it through its image as follows: \[\begin{tikzcd} G && H \\ & {\operatorname{Im}f} \arrow["f", from=1-1, to=1-3] \arrow["{q_f}"', two heads, from=1-1, to=2-2] \arrow["{i_f}"', hook, from=2-2, to=1-3] \end{tikzcd}\] Explicitly, we define an equivalence relation \(\sim_f\) on the vetex set of \(G\) by declaring \(v \sim_f v'\) if and only if \(f(v) = f(v')\). The set of vertices of \(\operatorname{Im}f\) is then the quotient \(G_V/\sim_f\) with the edge relation given by \([v] \sim [w]\) if there are \(v' \in [v]\) and \(w' \in [w]\) such that \(v' \sim_f w'\), or equivalently, \(f(v') = f(w')\). In the factorization above, the graph map \(q_f \colon G \to \operatorname{Im}f\), given by \(q_f(v) = [v]\), is a quotient map and \(i_f \colon \operatorname{Im}f \to H\), given by \(i_f[v] = f(v)\) is a monomorphism (i.e., injective on both vertices and edges). It is easy to see that the factorization of \(f \colon G \to H\) into a quotient map followed by a monomorphism is unique up to a unique isomorphism of factorizations.

Returning to the question at hand, since \(3\)- and \(4\)-cycles are quotients of \(Q^2\), one might reasonably expect that the set of basic shapes in dimension \(3\) will be a set of quotients of \(Q^3\). However, things become slightly more complicated, since one needs to keep track not only of the quotient graph itself but also of the relation by which the quotient was formed. To this end, we define the category of shapes.

Although the cardinality of \(S_R(n)\) is always finite, it might be computationally difficult to find it. Such a search would naturally involve the \(2^n\)-th Bell number \(B_{2^n}\), which counts partitions of the set with \(2^n\) elements. These correspond to the number of isomorphism classes of objects in the full subcategory of \(Q^n/\mathsf{Graph}\) spanned by quotient maps. The Bell numbers nevertheless provide some estimate for the number of isoclasses \(S_R(n)\), namely: \(B_1 = 1\), \(B_2 = 2\), \(B_8 = 4140\), and \(B_{16} = 10480142147\), thus yielding already uncomputable results for \(n = 4\).

To see how shapes can aid computations of discrete homology, we need the notion of universality.

If we can find a small, universal set \(T\) of \(n\)-shapes for some nonnegative integer \(n\), then we need only look for injective maps from each shape in \(T\) to a graph \(G\). However, 11 requires us to iterate over all graphs \(G\), which is impossible. The following proposition removes this obstacle, allowing us to decide if a set \(T\) is universal only by comparing elements of \(T\) to elements of the finite set \(S_R(n)\).

[prop:local95universality] gives us a finite computer-verifiable procedure for deciding whether a set \(T\) of \(n\)-shapes is universal. Namely, we can compute all possible isomorphism classes of \(n\)-shapes and perform finitely many membership tests on the \(n\)-shapes in \(S_R(n)\).

It remains to see how to construct a small, universal subset of \(n\)-shapes given the full list \(S_R(n)\). One way to accomplish this is by means of a greedy algorithm.

Note that while this algorithm provides a procedure for obtaining a reduced universal list of \(n\)-shapes, it does not guarantee that the reduced list is minimal. Different orderings of \(S_R(n)\) may produce different reduced lists \(F_N\).

Up to this point, we have developed a procedure that produces a reduced, universal list of \(n\)-shapes, for each \(n \geq 0\). We give the \(n\)-shapes in such a list a name.

Using these new definitions, our work so far can be distilled into the following result.

Of course, our results alone do not fully solve the basic shapes conjecture outlined in the introduction. It is at least unclear whether the \(R\)-modules \(\{U_n(G; R)\}_{n \geq 0}\) form a chain complex \((U_\bullet, \partial_\bullet)\) along with a quasi-isomorphism \(U_n(G; R) \hookrightarrow C_n(G; R)\). Despite these obstacles, the local criterion established by [prop:basic95comm95diag] allows us to compute \(\mathcal{H}_n(G; R)\) provided we can compute \(U_{n+1}(G; R), C_n(G; R)\) and \(C_{n-1}(G; R)\). As we saw at the beginning of the section, the cardinality of these objects blow up exponentially with \(n\), making computation intractable for \(n \geq 3\). However, in the case \(n = 2\), the sets are still small enough that we can find a set of basic 3-shapes and use it to compute \(\mathcal{H}_2(G)\).

3 Experiments↩︎

As an experiment, we compute a reduced set \(T(3)\) of 3-shapes using the greedy algorithm outlined in 12. In this section, all computations will be done over \(R = \mathbb{Z}/2\) and we will omit the subscript for brevity. To do so, we first enumerate each element of \(S(3)\) by brute force, and then use the greedy algorithm to reduce this list to a small, universal set of 3-shapes. For this experiment, we order the elements of \(S(3)\) in ascending order by the number of vertices in the associated quotient of \(Q^3\), with ties being broken arbitrarily. As remarked before, choosing a different ordering may well produce a different \(T(3)\). In this case, we recover the reduced, universal set of five 3-shapes depicted below (where we omit the associated boundaries for brevity). \[\begin{figure}\includegraphics[width=0.8\textwidth]{_pdflatex/vqzgntfs.png}\label{zcfphxty}\end{figure}\tag{2}\] The cell \(E_5\) is simply \(Q^3\). The cell \(E_4\) is \(Q^3\) with one edge contracted. The triangular prism \(E_3\) is obtained by identifying two pairs of adjacent vertices that form parallel edges of \(E_3\). The cell \(E_2\) is isomorphic (as graphs) to the complete bipartite graph \(K_{2,3}\). Finally, the cell \(E_1\) is isomorphic to the complete tripartite graph \(K_{1,1,2}\).

We run the following experiment using this set of basic 3-shapes.

1. Pre-compute the set \(S(3)\) by enumerating every set partition of 8 vertices with nondegenerate quotient maps and nonzero boundaries.

2. Use the greedy algorithm from 12 with the aforementioned ordering of the elements of \(S(3)\) to pre-compute \(T(3)\).

3. For an input graph \(G\), perform the following steps.

   1. Let \(C_1(G)\) consist of all non-loop edges in \(G\);

   2. Let \(C_2(G)\) consist of all nondegenerate singular 2-cubes in \(G\);

   3. For each element \(t = (P, q) \in T(3)\), enumerate all injective graph maps \(\varphi \colon P \hookrightarrow G\). This computes \(U_3(G)\).

   4. Compute the matrices of the boundary operators \(\partial^C_2\) and \(\partial^U_3\).

   5. Compute \(\dim \mathcal{H}_2(G) = \operatorname{nullity} \partial^C_2 - \operatorname{rank} \partial^U_3\).

4. Run the cubical homology algorithm from kapuklin-kershaw:computations? on \(G\), and compare the results with this new algorithm, which we call the “basic shapes algorithm”.

Correctness of this algorithm is guaranteed by [prop:basic95comm95diag]. We compare our results against those of the previously-developed cubical homology algorithm in order to benchmark the relative speedup obtained by only filling in these basic shapes.

For our test graphs, we use Erdős-Rènyi graphs. For an integer \(n \geq 0\) and real number \(p \in [0,1]\), an Erdős-Rènyi graph \(G(n,p)\) is a graph with \(n\) vertices, with pairs of vertices connected by an edge independently with fixed probability \(p\).

We use Erdős-Rènyi graphs because by taking \(p\) small (in this case, all of our test graphs satisfy \(0.03 \leq p \leq 0.07\)), we can ensure the presence of sparse graphs with a mix of trivial and nontrivial second discrete homology groups. After running both the basic shapes algorithm and the cubical algorithm on 200 test Erdős-Rènyi graphs, all second homology dimensions matched, as expected. All test graphs had between 100 and 200 vertices, and since they are random graphs, their topology is random. Plots comparing the runtimes from this experiment are below.

The new algorithm outlined above was faster than the cubical algorithm from kapuklin-kershaw:computations? on each of the 200 test graphs, with a median ratio of 47.4532 between the runtime of the cubical algorithm and that of the basic shapes algorithm. All source code, plots, data files and a CSV file containing the full results of this experiment can be found at https://github.com/JacobEnder/DiscreteHomology-Algorithms.

This experiment serves as a valuable proof of concept that our new procedure can indeed be used to considerably speed up computations of discrete homology, provided the appropriate chain groups are known in advance. As discussed, the primary limitation of this approach is computational — it very quickly becomes impossible to precompute \(T(n)\). However, this new procedure already gives a considerably faster algorithm for computing \(\mathcal{H}_2(G)\).