A Tutorial in Persistent Homology

IMA journal title (to be updated during typesetting) () , 1–5 https://doi.org/ A Tutorial in Persistent Homology MOHAMMED FARHAAN Department of Computer Science, OmerCo Research Group, Bangalore, 560048, Karnataka, India *Corresponding author: [email protected] [] In this paper we aim to provide an intuitive idea of Persistent homology which will allow the reader to implement it from the perspective of finding the spatial structure of a dataset purely using the inherent metric of the dataset. We explain the idea behind persistent homology as well as its practical aspects. In the first section we explain the working of the algorithm. We then explain Non-Euclidean Persistent homology and how it generalizes well. We then explain concepts that are secretly implementations of Non-Euclidean Persistent Homology 1. Introduction Persistent Homology serves as the basis for the field of topological data analysis. As the field of Topological Data Analysis grows more and more, we would like to provide a easy guide to understand both the theory behind Persistent Homology as well as its relevance without sealing it off from readers unfamiliar with homology theory. Persistent Homology should be thought of as the process to assign a natural topological structure to a given point-cloud data set. To expand on the history of persistent homology, we can start from the time when it wasnt called ”persistent homology”. The ”homology” comes from study of the structure of holes in a given topological space. This field of study examines the differences in structure of spaces with 1 hole like a Donut/Torus, a Disc which has no holes and a Figure 8 which has two holes. These differences can be studied more quantitatively and rigourously by numbers assigned to such spaces known as Betti Numbers and the Euler Characteristic. These numbers allowed us to study homological features pertaining to the structure of holes and when alternatingly summed these Betti numbers give us the Euler Characteristic of a CW complex. These two numbers tell us how many holes exist in our structure where the index of the Betti number corresponds to the dimension of the hole being considered. All that gibberish to simply say , β0=0 dimensional holes, β1=1 dimensional holes and so on where βk=k dimensional holes. And β0−β1+β2−β3+··· =χaka the Euler Characteristic. And we started studying the seqeucnce of increasing simplicial complexes and their Betti Numbers under the guise of the ”persistent Betti numbers” to observe which ones remained unchanged as we went higher and higher in the sequence of complexes. To make sense of how long these Betti numbers actually ”persist” or remain unchanged which should imply that whatever hole it represents has been untouched for that time in the sequence of complexes, we make use of persistence pairs. Persistent Pairs allow us to visualize the lifespan of a topological/homological feature it represents. Say a 1 dimenstional hole pops up when we are at the p-th complex, ∑pin the sequence. So we see our ”Persistent Betti Number” β1increments by 1. Soon after p at around the q-th complex ∑qsuch that p<q, we see that this hole is no longer present in this complex for the first time since p. Then we can say this hole has lasted from p to q which is whats communicated by the ”persistent pair” (p,q). So all we mean by (p,q)is that a certain k dimensional hole was birthed at p and died at q. © The Author(s) . 2MOHAMMED FARHAAN ET AL. FIG. 1. These are examples of k-simplices (image taken from [Azam Khan]) FIG. 2. This is the sequence of simplicial complexes ∑ithat we’ve been so eagerly elaborating on ( image from [Bub15]) And lastly lets discuss what we mean by simplices and simplicial complexes. So lets start with the general idea and see some trivial examples for a simplex. Lets being by talking about a k-simplex (simplices for plural). So the first thing that should come to mind when we talk about a k-simplex is a complete graph with k+1 vertices. (i.e. A graph with k+1 vertices such that every vertex in this graph is connected to every other vertex in this graph). Now that was step 1. For step 2, we must realise that this imagination of a k-simplex as a graph is right now a 2D planar object full of edge-edge intersections. These kind of immersions happen when a higher dimensional object is immersed into a lower dimensional space. In this case the k-Complete graph is an immersion of some k dimensional object that has been forced to exist in a 2D space. Do not panic if this does not make immediate sense, as it will seem more intuitive after a few examples So now lets take some trivial values of k. at k =0, this is simply an empty graph hence trivial. At k =1 this is simply a point and is a 0 dimensional simplex. At k =2this is now a line between two points and this counts for the 1 dimensional simplex. At k =3this is now a triangular face and this is a 2 dimensional simplex. At k =3this is now a tetrahedral that is a 3 dimensional simplex. A 5-simplex exists in 4D space which is sadly not so trivial. 2. An Intuitive Idea Of Persistent Homology To capture the main idea of what Persistent Homology is doing, one can think of it as this. We are first Growing open balls of radius r which acts as our parameter. Since our data is just point cloud data, we note that this means the data is a simplicial complex where all the simplices are 0 dimensional. We first assign a distanc function d(x,y)on the set where x,y∈X where X is the dataset. SHORT ARTICLE TITLE 3 FIG. 3. Various visualizations of the persistence pairs in degree 1 of the filtration depicted in Figure 1: persistence diagram (a), barcode (b) and persistence landscape (c) (images from [Bub15]). Now look at all the pairs of points and iff d(x,y)<2r then we connect these points. In other words our 0 simplex gets upgraded to a 1 simplex. This process of promoting a k simplex to a k+1 simplex is called ”birthing of a k+1 simplex” and equivalently called ”death of the k simplex”. This perspective of birth and death play a central role in interpreting how homological features persist in the increasing radius r. This is very similar to the notion of an induced topology however the key difference is that while inducing a topology by a metric using open balls, we only consider the open balls and their resulting open sets formed by union of more than one of these open balls, whereas PH allows us to start from a 0 dimensional dataset and add more and more structure and study the invariants that remain as we have more and more structure. As we go up this sequence of complexes as r gets larger and larger, there comes a point where all points are connected. Or in other words our simplicial complex with |X|points is now just a completely connected graph. This is bad. Any structure we may have had has completely vanished into this over-connectedness. We clearly took it too far, making r too large. How do we fix this? We now have to settle for some r that lies in the middle of being completely disconnected to completely connected. This leads us to the search of a perfect r where σ⊆X|d(u,v)≤p,∀u,v∈σ Where σis some k-simplex in X. 2.0.1. So how do we even determine r? Good Question! We dont know! 4MOHAMMED FARHAAN ET AL. Thats why we need to visualize persistence pairs. We need a way to simultaniously look at all the persistence pairs to infer what simplex was killed to birth which simplex. This gives us an idea about what features are most relevant (the relevant features we expect to have larger lifespans) and what features flicker in and out of existence as r increases. There are several ways to visualize persistence pairs using visualizations namely: Bar Diagrams, Persistent Diagrams or ”Birth-Death” Plots and Persistent Landscapes 3. Non Euclidean Persistent Homology (Extra food for thought) The above section detailed how to think about a point cloud X in Rn. In other words we were inherently assigning a Euclidean metric to measure the distance between two points in a data cloud. The universality of Persistent homology reveals itself when we relax the usage of an Euclidean metric/distance function. At first the generalization that comes to mind is what happens when we consider metrics typically related to non-euclidean geometry. This would include metrics from spherical elliptical or even hyperbolic surfaces including any Riemannian metric in between. This is a good way to start thinking about Non Euclidean Persistent homology and this line of thinking is what allows one to notice that persistent homology is applicable anywhere where theres a notion of grouping things. Some examples of persistent Homology in disguise are Algorithms like ”k-nearest neighbour”.It works by finding the ”k” closest data points (neighbors) to a given input and makes a predictions based on the majority class (for classification) or the average value (for regression).. To see this connection , consider the simplicial complex formed when we grow an Open Ball of radius r around the new data point. While k-nearest neighbour prioritises the number of neighbours, we instead select a classification by applying the appropriate boundary homomorphisms (There are some excellent sources on this aspect of algebraic topology) and selecting the classification that survives the homomorphism. This application does not require a non Euclidean metric but its a helpful example to justify the applicability of Persistent Homology if we expand what we mean by ”point-cloud data” Our second example comes from the very well known Quinn McCluskey Method which is an alternate method to minimizing boolean functions. This method relies on grouping minterms such that they differ by a single digit. This notion of grouping can elegantly be rephrased as forming a an edge between all minterms that have a Hadamard distance of 1. By this we cleanly form a simplicial complex pertaining to each group and we continue to loosen our grouping rule by grouping those with Hadamard distance 2, then 3 and so on upto n . This loosening of Grouping occurs in the middle of the QM Method as one of the important steps and this connection may allow us to rephrase other problems in a Persistent homology context. In this example, the Non Euclidean aspect is implemented by performing Persistent homology using the Hadamard Distance rather than the Euclidean Distance. It is defined as the metric dh. dH(x,y) = n ∑ i=1 |xi−yi| Our Third Example shows that we can use persistent homology to construct Phylogenetic Trees which are used to analyze evolutionary relationships between a selected set of species at a time. These branching Diagrams use distance metrics to visualize which pair of species are closely related compared to the rest in the set. They are constructed using a metric called the evolutionary metric using a method called UPGMA. UPGMA stands for “unweighted pair group method using arithmetic SHORT ARTICLE TITLE 5 averages”. It is also known as the Average Linkage Method. So we basically Persistent Homology again using the metric di j Given two disjoint clusters Ci,Cjof sequences, di j =1 |Ci|×|Cj|∑ {p∈Ci,q∈Cj} dpq . It is easy to compute the distances between clusters incrementally using the following formula: dkl =dil |Ci|+djl|Cj| |Ci|+|Cj|. So with all this convincing that this algorithm is more universal than initially assumed, We would like to explore other ways it can be possibly explored. We can use Persistent homology to find the dimension of the MNIST Dataset of Handwritten digits that is embedded in a 28x28 image space. We can also use Persistent homology to algorithmically find the relations that define a Group’s Cayley graph using a given set of group generators. We expect this to be especially useful in showing the equivalence between two given Groups by trying to show an equivalence from their group diagrams/Cayley graphs by comparitively studying the topological invariants of each group which we know can very well be studied using Persistent homology. 4. Concluding Remarks Persistent homology is the foundational approach of topological data analysis to study the topological invariants found in data. It has much unexplored potential and has alot to offer for someone who knows how to exploit it’s strengths. We hope this paper shed some light on why research on Persistent Homology can serve as an excellent segway to higher level math and can turn out to be quite intuitive lens to view Topology and Homology from. Acknowledgments The authors thank the anonymous reviewers for their valuable suggestions. REFERENCES 1. U. Fugacci, S. Scaramuccia, F. Iuricich, and L. De Floriani. Persistent homology: a step-by-step introduction for newcomers. In STAG: Smart Tools and Applications in Graphics, pages 1–10. Eurographics Association, 2016. 2. S. Weinberger. What is... Persistent Homology? Notices of the American Mathematical Society, 58(1):36–39, 2011. 3. S. Eilenberg and S. MacLane. General Theory of Natural Equivalences. Transactions of the American Mathematical Society, 58(2):231–294, 1945. 4. P. Bubenik. Statistical Topological Data Analysis using Persistence Landscapes. Journal of Machine Learning Research, 16:77–102, 2015. Available at: https://www.jmlr.org/papers/volume16/bubenik15a/bubenik15a.pdf 5. U. Fugacci. Teaching & Notes. Available at: https://fugacci.github.io/home/notes.html. Accessed: 2023. 6. A. Herring. Topological characterization of fluid microstructure via Persistent Homology. PoreLab Channel, YouTube, Feb 17, 2021. URL: https://www.youtube.com/watch?v=g6KwJqTbWq4