This essay was written as part of the Wolfram Emerging Leaders Program: Undergraduate, which is a year long, project-based program designed for gifted undergraduate students to take a deep dive into a topic of their choice. Students work remotely to take their project from ideation to completion, with the guidance of Wolfram experts. Wolfram Emerging Leaders Program participants are selected from the Wolfram High School Summer Research Program or the Wolfram Summer School, which is open to talented, STEM-oriented students.
Introduction
Introduction
More than likely, you’ve heard of the popular joke “topologists can’t tell the difference between a coffee mug and a donut” at some point. Indeed, topologists seem to care quite a bit about holes. But maybe so should we. The theory of homology--the mathematical formalization of the notion of holes-- has proven to be a powerful tool in domains such as image processing, medical research, and machine learning, to name a few. We will dive into some of the fundamental concepts relevant to Topological Data Analysis, and show how they could be implemented in Mathematica. We will also take a detour into Discrete Morse Theory to explore how it could be used to build more efficient TDA algorithms.
Simplicial Homology
Simplicial Homology
Betti numbers of abstract simplicial complexes
Betti numbers of abstract simplicial complexes
Geometric objects are often quite difficult to work with, especially in higher dimensions. The motivating philosophy of algebraic topology is therefore to study these objects indirectly through the lens of algebra. Homology theory, in particular, offers a way of associating the so-called homology groups with topological spaces, which encode certain global properties of the given space. The rank of the n-th homology group is known as the n-th Betti number, and for , these numbers could reasonably be interpreted as the number of n-dimensional holes in the space. In TDA settings, simplicial homology groups are of particular interest due to their combinatorial nature. These groups can be computed directly from an abstract simplicial complex, which is defined as a collection , where each is some ordered set of points , and for . That is to say, the faces of a simplex is also a member of the collection. To realize an abstract simplicial complex as a geometric one, we can imagine each as a point in space, and as the convex hull of such points. For instance:
n1,2
S:
{}
n
Δ
i
i,n
n
Δ
i
[,...,]
x
1
x
n
k<n,⊂⇒∈S
k
Δ
i
n
Δ
i
k
Δ
i
x
i
k
Δ
i
In[]:=
S={{1},{2},{3},{4},{5},{1,5},{2,5},{1,3},{1,2},{2,3},{1,4},{2,4},{3,4},{1,2,3},{1,3,4},{1,2,4},{2,3,4}};HighlightMesh[MeshRegion[{{0,0,0},{1,0,0},{0,1,0},{0,0,1},{0,0,2}},{Line[{5,1}],Line[{5,2}],Tetrahedron[{1,2,3,4}]},MeshCellStyle->{{1,All}->Red}],Labeled[0,"Index"]]
Out[]=
Observing the geometric representation of S, we see that the hollow tetrahedron encloses a 2-dimensional hole, and there’s also a 1-dimensional hole (a loop) enclosed by {2,4,5}. This fact is captured by the rank of and , the 1st and 2nd simplicial homology groups of S. These groups are defined to be the quotient groups Ker/Im , where (the k-th boundary operator) is the alternating formal sum [,...,]:,..,,..,, with denoting the omission of to obtain a k-1 simplex. If we want to compute the rank of these groups, we could view as a quotient vector space, whose dimension is then precisely the n-th Betti number. This gives us a simple way to compute the Betti numbers: write and as matrices, so that the n-th Betti number is just Dim(Ker ) - Rank(). The following is an implementation of this algorithm:
Δ
H
1
Δ
H
2
∂
n
∂
n+1
∂
k
∂
k
x
1
x
k
∑
i
i+1
(-1)
x
1
x
i
x
k
x
i
x
i
Δ
H
n
∂
n
∂
n+1
β
n
∂
n
∂
n+1
In[]:=
nSkeleton[complex_List,n_Integer]:=With[{A=Sort[#]&/@Cases[complex,x_/;Length[x]==n+1]//Sort},A[[#]]->SparseArray[{1,#}->1,{1,Length[A]}]&/@Range[1,Length[A]]]//AssociationboundaryVector[simplex_List,A_Association]:=(-1)^(#+1)*A[Drop[simplex,{#}]]&/@Range[1,Length[simplex]]//TotalboundaryOperator[complex_List,n_]:=With[{A=nSkeleton[complex,n-1],B=Sort[#]&/@Cases[complex,x_/;Length[x]==n+1]//Sort},If[n==0,{Array[0&,Length[B]]},Join[Sequence@@(boundaryVector[#,A]&/@B)]//Transpose]]BettiNumber[complex_List,n_Integer]:=With[{M1=boundaryOperator[complex,n],M2=boundaryOperator[complex,n+1]},If[M1=={},0,Dimensions[M1][[2]]-MatrixRank[M1]]-If[M2=={},0,MatrixRank[M2]]]
Testing this on S,
Print[BettiNumber[S,1]];Print[BettiNumber[S,2]]
1
1
As expected.
Graphs as simplicial complexes
Graphs as simplicial complexes
Graphs are closely associated with simplicial structures. Give a graph G, we can define a simplicial complex as follows: if and only if are spanned by a subgraph isomorphic to the complete graph . This is only one of many ways to associate a simplicial structure with a graph; in fact, similar constructions can be made w.r.t. any monotone graph property (see [1]).
S
G
[,...,]∈
v
1
v
n
S
G
{,...,}
v
1
v
n
K
n
With this observation, an interesting application is that we can represent triangulations of various surfaces by ‘gluing together the boundaries of a diagonal grid graph with VertexContract[]. Below we construct a graph representing the Moebius strip (≅Z) by identifying two sides of a grid graph with reverse orientations:
H
1
diagonalGridGraph[n_,m_]:=UndirectedGraph[RelationGraph[ChessboardDistance[#1,#2]==1&&(#1[[1]]-#2[[1]]+#2[[2]]-#1[[2]])!=0&,GraphEmbedding@GridGraph[{n,m}]],VertexCoordinates->Join[Sequence@@Table[{i,j},{i,1,m},{j,1,n}]]]mobiusStripGrid[n_Integer,m_Integer]:=Graph[VertexContract[diagonalGridGraph[n,m],MobiusIdentifications[n,m]],VertexCoordinates->Automatic]MobiusIdentifications[n_,m_]:=N[{{1,#},{m,n+1-#}}&/@Range[1,n]]GraphicsRow[{diagonalGridGraph[5,20],Graphics[{Thick,{Arrowheads[Large],Arrow[{{0,0},{0.5,0}}]}}],mobiusStripGrid[5,20]}]
Out[]=
We could then compute the 0th and 1st Betti numbers from the simplicial complex associated with the cliques of the graph:
In[]:=
GraphComplex[g_Graph,n_]:=DeleteCases[Union[Sequence@@Subsets[#,n+2]&/@FindClique[g,Infinity,All]],{}]
In[]:=
GraphBettiNumber[g_Graph,n_]:=With[{K=GraphComplex[g,n]},BettiNumber[K,#]&/@Range[0,n]]GraphBettiNumber[mobiusStripGrid[5,20],1]
Out[]=
{1,1}
We could construct a real-projective plane ( ≅,0) by also identifying the horizontal sides in the same fashion:
H
1
Z
2
H
2
In[]:=
RP2Identifications[n_,m_]:=Union[MobiusIdentifications[n,m],N[{{#,1},{m+1-#,n}}&/@Range[1,m]]]RP2Grid[n_Integer,m_Integer]:=Graph[VertexContract[diagonalGridGraph[n,m],RP2Identifications[n,m]],VertexCoordinates->Automatic]GraphicsRow[{diagonalGridGraph[20,20],Graphics[{Thick,{Arrowheads[Large],Arrow[{{0,0},{0.5,0}}]}}],RP2Grid[20,20]}]
Out[]=
Its oth through 2nd Betti numbers are:
In[]:=
GraphBettiNumber[RP2Grid[20,20],2]
Out[]=
{1,0,0}
Or, we could have a Klein bottle (≅Z⊕,0) by identifying the horizontal edges in parallel orientation:
H
1
Z
2
H
2
In[]:=
kleinBottleIdentifications[n_,m_]:=Join[MobiusIdentifications[n,m],N[{{#,1},{#,n}}&/@Range[1,m]]]kleinBottleGrid[n_Integer,m_Integer]:=Graph[VertexContract[diagonalGridGraph[n,m],kleinBottleIdentifications[n,m]],VertexCoordinates->Automatic]GraphicsRow[{diagonalGridGraph[20,20],Graphics[{Thick,{Arrowheads[Large],Arrow[{{0,0},{0.5,0}}]}}],kleinBottleGrid[20,20]}]
Out[]=
Where its oth through 2nd Betti numbers are:
GraphBettiNumber[kleinBottleGrid[20,20],2]
Out[]=
{1,1,0}
Topological data analysis
Topological data analysis
With the machinery developed in the previous sections, now we could actually do some elementary topological data analysis. The basic idea is that given a discrete dataset, we could try to reconstruct a family of possible underlying continuous shapes and then compute their topological features, which we might hope to capture some essential and global properties of the dataset.
Vietoris-Rips complex
Vietoris-Rips complex
We could then plug these graphs into GraphBettiNumber[]:
Persistent Homology
Persistent Homology
To illustrate, lets consider a set of points sampled from a donut-shaped torus:
Discrete Morse theory
Discrete Morse theory
When conducting topological data analysis, one issue that we quickly come up against is the sheer amount of computational demand associated with computing Betti numbers of large simplicial complexes, as we’d be required to perform row reduction on extremely large matrices. One thing one might notice is that the Vietoris-Rips complex generated from a dataset often contains many ‘redundant simplices, in that removing them would not affect the topology of the complex. Luckily, Discrete Morse theory offers us a way to ‘ignore’ the vast majority of simplices in a simplicial complex when computing their homology.
Discrete Morse functions and critical simplices
Discrete Morse functions and critical simplices
The central idea of Morse theory is to study the topological properties of smooth manifolds by looking at the critical points of a particular type of smooth function defined on the manifold. In the same spirit, the discrete analogue of Morse theory, pioneered by Robin Forman [1], seeks to study the combinatorial properties of simplicial complexes through a class of functions defined on the simplices, known as discrete Morse functions.
Gradient vector fields and acyclic matchings
Gradient vector fields and acyclic matchings
In practice, what this means is that we don’t have to explicitly work with Morse functions--all we need is an acyclic partial matching of the Hasse diagram to identify the critical simplices of a Morse function.
Morse Homology
Morse Homology
The critical simplices are then the unmatched vertices (in this case there is precisely one in each dimension):
We could then simply count the number of paths going from one critical simplex to another, and determine their parity:
Generating Morse matchings
Generating Morse matchings
As seen from the above example, having a Morse matching that minimizes the number of critical simplices will make calculating Betti numbers significantly more straightforward. Ideally, we’d want to have a computationally efficient algorithm of searching for such matchings. We start by finding a topological ordering of the initial Hasse diagram, and proceed with a greedy algorithm starting at the lowest dimensional simplex in the ordering that iteratively checks if each simplex could be matched with another without creating cycles:
In simple cases, this algorithm is already sufficient for finding the optimal matching. For instance, with the same example as previously, it produced a matching that again leaves one critical simplex per dimension:
And as expected, the Morse boundary operators are also trivial in this new matching:
We turn our attention to a slightly more complicated example-a triangulation of the torus:
Our greedy algorithm indeed produced a valid Morse matching:
We then find that the Morse boundary operators all vanish:
Thus agreeing with the Betti numbers of the torus.
Using this idea of cancelling critical simplices, one could generate an initial matching on a given Hasse diagram using something like the greedy algorithm as demonstrated above, then proceed to iteratively check for the existence of such paths to further augment the matching if the initial matching wasn’t maximal.
Concluding remarks
Concluding remarks
This computational essay was in many ways a continuation to the project I did for WS22, where I explored the behavior of cellular automaton on various topological surfaces, as it sparked my interest in exploring the computable aspects of topology.
Needless to say, I’ve barely scratched the surface of computational topology and discrete Morse theory--there’s just so much more to be explored, such as finding a fast algorithm for generating Vietoris-Rips complexes on datasets and optimal Morse matchings, or using TDA to feature engineer data in a machine learning pipeline, or simulating dynamical systems on simplicial complexes, etc. What fascinates me about these topics is that they turn esoteric mathematics into a common playground, where people who are interested in different things could find their own way of playing around with ideas in these rich theories that would otherwise only have been known to and appreciated by a very small minority of people.
Please feel free to point out any mistakes that you spot. I’d also like to thank Rory and my advisor Isabel for all the help they’ve given me, as well the people who’ve made the WELP program possible.
Needless to say, I’ve barely scratched the surface of computational topology and discrete Morse theory--there’s just so much more to be explored, such as finding a fast algorithm for generating Vietoris-Rips complexes on datasets and optimal Morse matchings, or using TDA to feature engineer data in a machine learning pipeline, or simulating dynamical systems on simplicial complexes, etc. What fascinates me about these topics is that they turn esoteric mathematics into a common playground, where people who are interested in different things could find their own way of playing around with ideas in these rich theories that would otherwise only have been known to and appreciated by a very small minority of people.
Please feel free to point out any mistakes that you spot. I’d also like to thank Rory and my advisor Isabel for all the help they’ve given me, as well the people who’ve made the WELP program possible.
References
References
1
.Robin Forman, A user’s guide to Discrete Morse Theory
2
.Frederic Chazal et al. , An Introduction to Topological Data Analysis: Fundamental and Practical Aspects for Data Scientists
CITE THIS NOTEBOOK
CITE THIS NOTEBOOK
Introduction to Persistent Homology and Discrete Morse Theory
by Shuheng Li
Wolfram Community, STAFF PICKS, August 30, 2023
https://community.wolfram.com/groups/-/m/t/3001504
by Shuheng Li
Wolfram Community, STAFF PICKS, August 30, 2023
https://community.wolfram.com/groups/-/m/t/3001504