Chapter 06 - Persistent Homology and Mapper

Structures from point-cloud data

Theory - Gromov-Hausdorff distance

Gromov-Hausdorff distance

Hausdorff distance

Suppose $A$ and $B$ are subsets of a metric space $(X,d)$.

The Hausdorff distance is:

$$d_H(A,B)=\max (\underset{x\in A}{\sup }d(x,B),\underset{y\in B}{\sup }d(A,y))$$

Here:

• $d(x,B)=\underset{y\in B}{\inf }d(x,y)$ smallest distance $x$ to $B$
• $d(A,y)=\underset{x\in A}{\inf }d(x,y)$ smallest distance $y$ to $A$

Therefore:

• $\underset{x\in A}{\sup }d(x,B)$ within $A$, how far away can you get from $B$?
• $\underset{y\in B}{\sup }d(A,y)$ within $B$, how far away can you get from $A$?

Gromov-Hausdorff distance

Suppose $A$ and $B$ are compact metric spaces and $(X,d)$ is some fixed compact metric space.

The Gromov-Hausdorff (GH) distance is:

$$d_{GH}(A,B)=\underset{f,g}{\inf }{d}_H(f(A),g(b))$$

where $f$, $g$ are isometric embeddings of $A$, $B$ into $X$.

Notice that this definition is relative to $(X,d)$.

Link to original

Theory - Dendrogram

Dendrogram

Persistent homology describes the clustering of point-cloud data.

The GH distance frequently serves as a pure math benchmark. Given finite sets of points $P,Q\subset {\mathbb{R}}^d$, the distance $d_{GH}(P,Q)$ is a measure of similarity of the shape of the point clouds $P$ and $Q$.

The GH distance cannot be computed efficiently (if at all), so other measures of similarity for point clouds are useful.

Desiderata for measures of point-cloud similarity:

• Quantifies topological and geometric features
• Distinguishes features from noise
• Is computable
• Recognizes when features are close in the GH metric

---

Suppose we have a finite set of points $P\subset X$ for a metric space $(X,d)$.

Fix $r\in {\mathbb{R}}_{\ge 0}$. Define a relation $x_1{\sim }_r{x}_2$ when $d(x_1,x_2)\le r$.

Let ${\simeq }_r$ be the transitive closure of ${\sim }_r$. This is an equivalence relation (generated by ${\sim }_r$) which partitions $P$ into equivalence classes. Members of each equivalence class can be obtained from one another by a sequence of “hops” between points no more than $r$ apart.

Draw a tree diagram with a junction at each $r$ where distinct clusters are joined:

Link to original

Theory - Filtrations

Filtrations

Filtered simplicial complex

A filtered simplicial complex is a complex $\mathcal{K}$ with a collection:

$$\varnothing \subset {\mathcal{K}}_{a_1}\subset {\mathcal{K}}_{a_2}\subset \cdots \subset {\mathcal{K}}_{a_n}=\mathcal{K}$$

where each ${\mathcal{K}}_{a_i}$ is a simplicial complex which is a subcomplex of ${\mathcal{K}}_{a_{i+1}}$.

(The vertices and simplices of a subcomplex must be vertices and simplices in the supercomplex.)

Filtered space

A filtered topological space is a collection $X_t$ of spaces indexed by $t\in [0,\infty ]$ with continuous maps:

$$f_{s,t}:X_s\to X_t\text{each }s\le t$$

and these maps satisfy a transitivity compatibility:

$$X_r\stackrel{f_{r,s}}{⟶}{X}_s\stackrel{f_{s,t}}{⟶}{X}_t{f}_{r,t}=f_{s,t}\circ f_{r,s}$$

It is sometimes convenient, if a little ungainly, to consider a filtered simplicial complex as a filtered space where ${\mathcal{K}}_s$ is a simplicial subcomplex of ${\mathcal{K}}_t$ whenever $s\le t$. Such a filtered space changes only at discrete values of $t$.

Link to original

Illustration

Čech complex as filtered complex

Čech complex as filtered complex

Let $\mathcal{P}=\{p_1,\dots ,p_n\}$ be a finite set of points in a metric space $(X,d)$.

Recall that the Čech complex of $\mathcal{P}$, written ${\mathcal{P}}_r$ for $r\in [0,\infty )$, is the nerve complex of the collection of open balls $\{B_r(p_i)\}$.

In other words, ${\mathcal{P}}_r$ is the complex with vertices the points of $\mathcal{P}$, and $k$-simplices the subsets $\sigma \subset \mathcal{P}$ with $k+1$ points whose $r$-balls have nonempty mutual intersection.

This is a filtered complex because $B_r(p_i)\subset B_s(p_i)$ whenever $r\le s$. Once in, always in, for a simplex.

Link to original

Theory - Vietoris-Rips complex

Vietoris-Rips complex

Vietoris-Rips complex

Let $\mathcal{P}=\{p_1,\dots ,p_n\}$ be a finite set of points in a metric space $(X,d)$.

The Vietoris-Rips complex $\mathrm{VR}(\mathcal{P},r)$ is the complex whose vertices are the points $\mathcal{P}$, and whose $k$-simplices are those subsets $\sigma \subset \mathcal{P}$ with $k+1$ points all of which are pairwise less than $2r$ apart:

$$\begin{array}{rl}& [p_{i_0},\dots ,p_{i_k}]\\ & \text{k-simplex}\in \mathcal{P}\end{array}⟷\begin{array}{rl}& d(p_j,p_{\ell })<2r\\ & \forall j,\ell \in \{i_0,\dots ,i_k\}\end{array}$$

The VR complex is a filtered space (filtered complex) because:

$$\mathrm{VR}(\mathcal{P},r)\subset \mathrm{VR}(\mathcal{P},s)\subset \mathrm{VR}(\mathcal{P},t)\text{when}r\le s\le t$$

Notice that the VR complex and the Čech complex include the same 1-simplices: a simplex $\sigma =[p_i,p_j]$ is in the VR complex if $d(p_i,p_j)<2r$, and in the Čech complex if $B_r(p_i)\cap B_r(p_j)\ne \varnothing$. These conditions are equivalent, at least in ${\mathbb{R}}^d$.

Pairwise vs. mutual intersection

• The VR complex includes simplices for points which pairwise intersect.
• The Čech complex includes simplices for points which mutually intersect.

For example:

The three blue circles all intersect pairwise, so $[p_1,p_2,p_3]$ is in the VR complex, but they don’t mutually intersect so this simplex is not in the Čech complex.

On the other hand, the four green circles do not intersect pairwise. The VR complex and the Čech complex are the same in this case.

VR complex computability

Since the VR complex depends only on the data of pairwise distances between points, it is very easy to compute.

---

Čech and VR containments

For any point cloud $\mathcal{P}\subset {\mathbb{R}}^d$, we have:

1. $\check{\mathrm{C}}\mathrm{ech}(\mathcal{P},r)\subset \mathrm{VR}(\mathcal{P},r)$ inclusion as subcomplex
2. $\mathrm{VR}(\mathcal{P},r)\subset \check{\mathrm{C}}\mathrm{ech}(\mathcal{P},2r)$ inclusion as subcomplex

The first is true because any mutual intersection implies the pairwise intersections.

The second is true because any pairwise intersection of $B_r$ balls implies that the $B_{2r}$ balls extend to cover other centers. So the centers of all points are in the $2r$-balls of each of the others, thus the centers are in the mutual intersection.

Link to original

Theory - Persistent homology, barcodes

Persistent homology, barcodes

Persistent homology

Let ${\mathcal{K}}_t$ be a filtered simplicial complex.

Fix $k\in \mathbb{N}$. For any $t\in [0,\infty )$, define:

$$V_k^t=H_k({\mathcal{K}}_t;\mathbb{R})$$

Whenever $s\le t$ there is a map ${\mathcal{K}}_s\to {\mathcal{K}}_t$ and this induces linear maps on homology:

$$L_k^{s,t}:V_k^s\to V_k^t$$

These satisfy $L_k^{r,t}=L_k^{s,t}\circ L_k^{r,s}$.

The persistent homology of ${\mathcal{K}}_t$ is the collection of vector spaces $V_k^t$ and linear maps $L_k^{s,t}$.

Persistent homology is defined for any filtered simplicial complex. For example, we can take persistent homology of the Čech complex or of the Vietoris-Rips complex.

Persistent VR homology - Structure Theorem

Let $V_k^r=H_k(\mathrm{VR}(\mathcal{P},r))$ for $r\in [0,\infty )$ be the persistent homology of the VR complex of a point cloud $\mathcal{P}$.

Fix $k\in \mathbb{N}$. Then $\{V_k^r{\}}_{r\in {\mathbb{R}}^{>0}}$ has a canonical decomposition as a direct sum of persistence intervals:

$$\{V_k^r{\}}_{r\in {\mathbb{R}}^{>0}}\stackrel{\sim }{⟶}\underset{i}{⨁}\mathrm{P}(a_i,b_i)$$

Persistence interval

For any $a<b$ with $a\in [0,\infty )$ and $b\in [0,\infty ]$, define:

$$\mathrm{P}(a,b{)}_r=\{\begin{array}{ll}\mathbb{R}& r\in [a,b)\\ \{0\}& r\notin [a,b)\end{array}$$

with (linear) filtration maps $L^{r,s}:\mathrm{P}(a,b{)}_r\to \mathrm{P}(a,b{)}_s$ given by $L^{r,s}={\mathrm{Id}}_{\mathbb{R}}$ when $r,s\in [a,b)$.

Link to original

Illustration

Illustration - barcode and persistence diagrams

Barcode diagram:

• Each $\mathrm{P}(a_i,b_i)$ receives a horizontal bar starting at $a_i$, ending at $b_i$.
• Bar colored according to degree $k$ in $H_k(\mathrm{VR}(\mathcal{P},r))$

Persistence diagram:

• Each $\mathrm{P}(a_i,b_i)$ receives a dot placed at $(a_i,b_i)$
• Horizontal ‘birth’ axis, vertical ‘death’ axis
• Dots colored according to degree $k$ in $H_k(\mathrm{VR}(\mathcal{P},r))$

Link to original

Point cloud - square

Point cloud: square

Basis:

Decomposition:

$$H_0(\mathrm{VR}(\mathcal{P}),r)\stackrel{\sim }{⟶}{\oplus }^3\mathrm{P}(0,d/2)\oplus \mathrm{P}(0,\infty )$$

Link to original

Filtered complex

Filtered complex

Abstract filtration:

Barcode and persistence diagram:

Link to original

Theory - Barcode basis

Barcode basis

We would like to understand the direct sum decompositions like the one in the example of the point cloud square:

$$H_0(\mathrm{VR}(\mathcal{P}),r)\stackrel{\sim }{⟶}{\oplus }^3\mathrm{P}(0,d/2)\oplus \mathrm{P}(0,\infty )$$

Understanding such a decomposition amounts to determining a basis of homology classes that have lifespans described by the persistence intervals.

We have:

$$H_0(\mathrm{VR}(\mathcal{P},r_2))\cong \frac{\ker ({\partial }_0)}{\mathrm{im}({\partial }_1)}\gg \gg \frac{{\mathbb{R}}^2}{\mathbb{R}}$$

A basis for $H_0$ is the equivalence class of all vectors in ${\mathbb{R}}^2$ which are not in the span $⟨v_2-v_1⟩$. For example, $v_1$ or $v_2$ or $v_1+v_2$.

Barcode diagram for $H_0$:

---

Now consider $H_1$. Cycles in $H_1$ are generated by 1-simplices which are sets of two points that are $\le 2r$ apart.

Consider again the square point cloud:

For $r<\frac{d}{2}$, we have $\mathrm{VR}(\mathcal{P},r)=\text{4 discrete points}$.

For $r=\frac{d}{2}+\epsilon$, we have $\mathrm{VR}(\mathcal{P},r)=\text{square}\simeq {\mathbb{S}}^1$.

For $r=\frac{d}{2}\sqrt{2}$, we have 4 additional 2-simplices (all combinations of 3 points).

The square will the boundary of the difference of two of the 2-simplices (complementary triangles), so the homology class of the square vanishes when $r$ reaches $\frac{d}{2}\sqrt{2}$.

Barcode diagram for $H_1$:

---

Thus:

$$\begin{array}{rl}{H}_0& \cong \mathrm{P}(0,1{)}^{\oplus 3}\oplus \mathrm{P}(0,\infty )\\ & \\ H_1& \cong \mathrm{P}\left(\frac{d}{2},\frac{d}{2}\sqrt{2}\right)\end{array}$$Link to original

Stability

Theory - Bottleneck distance

Bottleneck distance

The bottleneck distance is a metric on barcode diagrams. The bars in one barcode are matched against the bars in the other. The distance between barcodes is the worst discrepancy between bars in the optimal matching.

Suppose we are given two barcode diagrams. These are two finite collections of intervals:

$$\begin{array}{c}\mathbb{I}=\{I_a{\}}_{a\in A},\mathbb{J}=\{J_b{\}}_{b\in B}(A,B\text{ finite})\\ \\ I_a=[x_a,y_a),J_b=[x_b,y_b)\end{array}$$

Now define the $d_{\infty }$-distance between two intervals by:

$$d_{\infty }(I_a,J_b)=\max (|x_b-x_a|,|y_b-y_a|)$$

Also, define:

$$\lambda (I_a)=d_{\infty }(I_a,\varnothing )=\frac{|y_a-x_a|}{2}$$

This is the $d_{\infty }$-distance to the nearest point-interval $(x,x)$.

Now, suppose we are given subsets $A^{\prime }\subset A$ and $B^{\prime }\subset B$ along with a choice of bijection $\theta :A^{\prime }\to B^{\prime }$. Define the penalty of $\theta$ to be:

$$P_{\infty ;A^{\prime },B^{\prime },\theta }=\max \left(\begin{array}{rl}& {\max }_{a\in A^{\prime }}{d}_{\infty }(I_a,J_{\theta (a)})\\ & {\max }_{a\in A\backslash A^{\prime }}\lambda (I_a)\\ & {\max }_{b\in B\backslash B^{\prime }}\lambda (J_b)\end{array}\right)$$

Bottleneck distance

The bottleneck distance from $\mathbb{I}$ to $\mathbb{J}$ is:

$$d_{\infty }(\mathbb{I},\mathbb{J})=\underset{\begin{array}{c}{A}^{\prime }\subset A\\ B^{\prime }\subset B\\ \theta :A^{\prime }\to B^{\prime }\end{array}}{\min }{P}_{\infty ;A^{\prime },B^{\prime },\theta }$$

Bars far from the diagonal are matched to the closest bars (using the ${\ell }_{\infty }$-norm whose unit balls are squares). Bars near the diagonal can be matched to the closest diagonal point. The distance to the closest point on the diagonal is $\lambda (I_a)$.

Stability Theorem: Bottleneck Distance

Let $\mathcal{P}$ and $\mathcal{Q}$ be two finite metric spaces. Fix $k\in {\mathbb{Z}}_{\ge 0}$. Let $B_{\mathcal{P}}$ be the barcode diagram for $H_k(\mathrm{VR}(\mathcal{P},\mathrm{r}))$ and let $B_{\mathcal{Q}}$ be the barcode diagram for $H_k(\mathrm{VR}(\mathcal{Q},r))$. Then:

$$d_{\infty }(B_{\mathcal{P}},B_{\mathcal{Q}})\le d_{GH}(\mathcal{P},\mathcal{Q})$$

This theorem is a kind of “stability” result regarding barcode diagrams, since it says that when two data sets $\mathcal{P}$ and $\mathcal{Q}$ are close together (measured using the ideal, if not computable, metric $d_{GH}$), then the barcode diagrams are also close together. Barcode diagrams cannot jump apart without the data sets jumping apart.

For example, if $\mathcal{P}$ is a “noisy” version of $\mathcal{Q}$, then we expect $d_{GH}(\mathcal{P},\mathcal{Q})$ to be small, and therefore the barcode diagrams should be close. Conversely, if barcode diagrams are far, the data sets differ by “more than noise.”

Link to original

Theory - Wasserstein metrics

Wasserstein metrics

The Wasserstein metrics generalize the bottleneck metric. Instead of taking the worst discrepancy between two bars in the best matching, it uses a $p$-sum of the discrepancies of all bars in the best matching.

First define the $p$-penalty for a partial matching $\theta :A^{\prime }\to B^{\prime }$ as follows:

$$P_{p;A^{\prime },B^{\prime },\theta }={\left(\sum _{a\in A^{\prime }}{d}_{\infty }(I_a,J_{\theta (a)}{)}^p+\sum _{a\in A\backslash A^{\prime }}\lambda (I_a{)}^p+\sum _{b\in B\backslash B^{\prime }}\lambda (J_b{)}^p\right)}^{1/p}$$

Then we minimize the penalty (find the best matching):

$$d_p(\mathbb{I},\mathbb{J})=\underset{\begin{array}{c}{A}^{\prime }\subset A\\ B^{\prime }\subset B\\ \theta :A^{\prime }\to B^{\prime }\end{array}}{\min }{P}_{p;A^{\prime },B^{\prime },\theta }$$

Remark

We can recast the $p$-penalty in a more uniform symbolism by supplementing $A$ or $B$ with empty bars so that each has the same number of “bars,” and recalling the convention that $d_{\infty }(I_a,\varnothing )=\lambda (I_a)$. Then we have:

$$d_p(\mathbb{I},\mathbb{J})=\underset{\theta :A\to B}{\min }{\left(\sum _{a\in A}(||a-\theta (a)|{|}_{\infty }{)}^p\right)}^{1/p}$$

Link to original

Multi-dimensional persistent homology

Theory - Several parameters

Several parameters

Thus far the persistent homology we have considered is derived from filtered spaces/complexes with a single filtration parameter $r$:

$$\mathrm{VR}(\mathcal{P},r),f^{-1}((-\infty ,r))$$

It is possible to combine two types of filtration in a single structure having inclusion maps of each type.

Unfortunately there is no “structure theorem” for persistent homology with more than one parameter. This is basically because the structure theorem proof in one parameter involves homology with $\mathbb{R}[x]$ coefficients, while with $n$ parameters it involves homology with $\mathbb{R}[x_1,\dots ,x_n]$ coefficients.

Link to original

Illustration

Filtering also by density

Filtering also by density

Let us add a density filtration to $\mathrm{VR}(\mathcal{P},r)$. Fix $k\in {\mathbb{Z}}_{\ge 0}$ and define $\rho :\mathcal{P}\to \mathbb{R}$ by:

$$\rho (x_i)=\frac{1}{d_k(x_i)},d_k(x_i)=\text{distance to kth nearest neighbor}$$

Now the points in $\mathcal{P}$, and the $\mathrm{VR}$-complex itself, can be filtered by a density minimum:

$$\mathrm{VR}(\mathcal{P},r,s)=\mathrm{VR}(\{x\in \mathcal{P}\mid \rho (x)\ge s\},r)$$

This bi-filtered complex determines a 2-parameter persistence module:

$$H_k(\mathrm{VR}(\mathcal{P},r,s))$$

For large $s$, only points very close to $k$ distinct neighbors are included. As $s$ decreases, more points are brought in.

With data like this, the $s$ filtration (for middling $s$ values) removes points inside the disk because they are too sparse.

Link to original

Filtering also by distance to a subspace

Filtering also by distance to a subspace

Suppose $\iota :{\mathbb{R}}^k\hookrightarrow {\mathbb{R}}^n$ is an embedded $k$-dimensional subspace of the background space ${\mathbb{R}}^n$ that contains the data:$\mathcal{P}\subset {\mathbb{R}}^n$.

Let $f_{\iota }:\mathcal{P}\to \mathbb{R}$ measure the distance from data points to the image of $\iota$.

Define ${\mathcal{P}}_R=f^{-1}((-\infty ,R))$. This gives a filtration in terms of the parameter $R$. This filtration could be useful if the complete data set $\mathcal{P}$ is too big to process all at once. The filtration allows one to process the data in layers.

These filtrations determine inclusions of $\mathrm{VR}$ complexes. For fixed $R$ and $r<s$, we have:

$$\mathrm{VR}({\mathcal{P}}_R,r)\subset \mathrm{VR}({\mathcal{P}}_R,s)$$

Upon applying homology, for $k\in {\mathbb{Z}}_{\ge 0}$, we have:

$$H_k(\mathrm{VR}({\mathcal{P}}_R,r))\stackrel{L_{r,s}^R}{⟶}{H}_K(\mathrm{VR}({\mathcal{P}}_R,s)))$$

And for fixed $r$ and $R<S$, we have:

$$\mathrm{VR}({\mathcal{P}}_R,r)\subset \mathrm{VR}({\mathcal{P}}_S,r)$$

Upon applying homology, we have:

$$\mathrm{VR}({\mathcal{P}}_R,r)\stackrel{L_r^{R,S}}{⟶}\mathrm{VR}({\mathcal{P}}_R,s)$$

Finally, these induced maps should commute with each other:

$$L_s^{R,S}\circ L_{r,s}^R=L_{r,s}^S\circ L_r^{R,S}$$

Link to original

Theory - Zig-zag persistent homology

Zig-zag persistent homology

Filtrations can be modified in another way by adding intermediate linking sets. Instead of the usual filtered space like this:

$${\mathcal{K}}_{r_1}\subset {\mathcal{K}}_{r_2}\subset {\mathcal{K}}_{r_3}\subset \cdots$$

We have a “zig-zag” filtered space like this:

$${\mathcal{K}}_1\hookleftarrow {\mathcal{K}}_{1,2}\hookrightarrow {\mathcal{K}}_2\hookrightarrow {\mathcal{K}}_{2,3}\hookleftarrow {\mathcal{K}}_3\hookrightarrow \cdots$$

In general, each arrow is allowed to go either direction. The induced map on homology will follow the same pattern.

Link to original

Illustration

Morse layers

Morse layers

An application of zig-zag filtration arises by dividing the entire space into small layers for which the homology is easier to compute. For example, with a Morse function $f:\mathcal{K}\to {\mathbb{R}}_{\ge 0}$, we have this zig-zag filtration:

$$f^{-1}(0)\hookrightarrow f^{-1}([0,1])\hookleftarrow f^{-1}(1)\hookrightarrow f^{-1}([1,2])\hookleftarrow f^{-1}(2)\hookrightarrow \cdots$$

Link to original

Repeated samples

Repeated samples

Suppose some data is sampled repeatedly and data sets are generated in a sequence:

$$X_1,X_2,X_3,X_4,\dots$$

Then we can form a zig-zag filtration by:

$$X_1\hookrightarrow X_1\cup X_2\hookleftarrow X_2\hookrightarrow X_2\cup X_3\hookleftarrow X_3\hookrightarrow X_3\cup X_4\hookleftarrow \cdots$$

Link to original

Mapper algorithm

Theory - Clustering and Reeb graph

Clustering and Reeb graph

The mapper algorithm was introduced by Singh-Mémoli-Carlsson in 2007.

Recall the dendrogram (clustering) algorithm:

Given a fixed $\epsilon >0$, two points $x,y$ are considered equivalent if there is a sequence of points

$$x=x_0,x_1,x_2,\dots ,x_k=y$$

and the distance between successive points is much less than $\epsilon$.

Now consider connected components (“clusters”) for each fixed $\epsilon$. The clustering algorithm computes this and the calculation is essential the same as persistent homology $H_k$ for $k=0$.

Reeb graph

Given a Morse function $f:M\to \mathbb{R}$ on a manifold $M$, the Reeb graph is formed by the equivalence relation:

Two points $x,y\in M$ are equivalent if:

• $f(x)=f(y)$ AND
• $x,y$ are in the same connected component of $f^{-1}(f(x))$

Link to original

Mapper algorithm

Mapper algorithm

Let us be given:

• A finite metric space $(X,d)$
  • I.e. a finite collection of points $\{x_1,x_2,\dots ,x_k\}$ with distances between them; usually $X\subset {\mathbb{R}}^n$
• A “filter function” $f:X\to {\mathbb{R}}^n$
• A finite cover $\mathcal{C}=\{C_{\alpha }{\}}_{\alpha \in A}$ of $f(X)$ in ${\mathbb{R}}^n$
  • Typically a collection of boxes in ${\mathbb{R}}^n$

Proceed as follows:

(1) Consider the clustering of each $f^{-1}(U_{\alpha })$:

• Choose $\epsilon >0$ and consider clusters at this scale $\epsilon$.
• Write $C_{\alpha ,i}$ for the clusters, so $f^{-1}(U_{\alpha })={⨆}_i{C}_{\alpha ,i}$

(2) Form a discrete version of the Reeb graph:

• Vertices: clusters $C_{\alpha ,i}$
• Edges: when $C_{\alpha ,i}$ and $C_{\beta ,j}$ overlap
• Color the vertices according to values of $f$ (on average):

Link to original

Illustration

Simple cover

Simple cover

Suppose $f:X\to \mathbb{R}$ and suppose $\mathcal{C}$ is just the interval $[-L,L]$ containing the entire $f^{-1}(X)$.

In this case Mapper produces a graph with no edges. Its vertices correspond to clusters of $X=f^{-1}([-L,L])$.

Link to original

2-Component cover

2-Component cover

Suppose $f:X\to \mathbb{R}$ and suppose $\mathcal{C}$ is the pair $U_{\alpha }=[0,5]$ and $U_{\beta }=[6,10]$. Mind the gap $(5,6)$.

Vertices in the Mapper graph are $\epsilon$-clusters of $f^{-1}(U_{\alpha })$ and of $f^{-1}(U_{\beta })$. These clusters must be all disjoint. So there are no edges between the vertices.

If, however, the cover had been chosen to be $U_{\alpha }=[0,5]$ and $U_{\beta }=[4,10]$, there could be vertices between clusters in $f^{-1}(U_{\alpha })$ and clusters in $f^{-1}(U_{\beta })$.

Consider data points sampled around the unit circle. Let $f:{\mathbb{R}}^2\to \mathbb{R}$ by $f(x,y)=x$. Suppose the image $f(X)$ is covered by small overlapping intervals of equal length. Mapper recovers the topology of the circle:

If we had used a simple cover (single interval), the Mapper graph would have no edges and thus would not express the circle’s topology.

Link to original

Illustration - Mapper figures from the literature

(Rabadan-Blumberg 2020)

(Nikolau-Levine 2011)

Link to original