Steinhaus Filtration and Stable Paths in the Mapper

The need to rigorously seed a solution with a notion of stability in topological data analysis (TDA) has been addressed primarily using topological persistence [4, 11, 17]. Persistence arises when we work with a sequence of objects built on a dataset, a filtration, rather than with a single object. One line of focus of this work has been on estimating the homology of the dataset. This typically manifests itself as examining the persistent homology represented as a diagram or barcode, with interpretations of zeroth and first homology as capturing significant clusters and holes, respectively [1, 14, 15, 37]. In practice it is not always clear how to interpret higher dimensional homology (even holes might not make obvious sense in certain cases). A growing focus is to use persistence diagrams to help compare different datasets rather than interpret individual homology groups [2, 8, 34].

The implicit assumption in most such TDA applications is that the data is endowed with a natural metric, e.g., points exist in a high-dimensional space or pairwise distances are available. In certain applications, it is also not clear how one could assign a meaningful metric. For example, memberships of people in groups of interest is captured simply as sets specifying who belongs in each group. An instance of such data is that of recommendation systems, e.g., as used in Netflix to recommend movies to the customer. Graph based recommendation systems have been an area of recent research. Usually these systems are modeled as a bipartite graph with one set of nodes representing recommendees and the other representing recommendations. In practice, these systems are augmented in bespoke ways to accommodate whichever type of data is available. It is highly desirable to analyze the structure without prescribing some ill-fit or incomplete metric to the data.

Another TDA approach for structure discovery and visualization of high-dimensional data is based on a construction called Mapper [32]. Defined as the nerve of a refined pullback cover of the data (See Figure 1), Mapper has found increasing use in diverse applications in the past several years [23]. Attention has recently focused on interpreting parts of the $1$-skeleton of the Mapper complex, which is a simplicial complex, as significant features of the data. Paths, flares, and cycles have been investigated in this context [21, 26, 33]. The framework of persistence has been applied to this construction to define a multi-scale Mapper, which permits one to derive results on stability of such features [13]. At the same time, the associated computational framework remains unwieldy and still most applications base their interpretations on a single Mapper object.

The Mapper construction works with covers. By default, one starts with overlapping hypercubes that cover a parameter space (usually a subset of ${ℝ}^d$ for some dimension $d$) and consider the pullback of this cover to the space of data. In recommendation systems, the cover is just a collection of abstract sets providing membership info. Could we define a topological construction on such abstract covers that still reveals the topology of the dataset?

We could study paths in this construction, but as the topological constructions are noisy, we would want to define a notion of stability for such paths. With this goal in mind, could we define a filtration from the abstract cover? But unlike in the setting of, e.g., multiscale Mapper [13], we do not have a sequence of covers (called a tower of covers) – we want to work with a single cover. How do we define a filtration on a single abstract cover? And could we prove is is stable? Finally, could we use our construction on real data?

We define the Steinhaus distance, a generalization of the Jaccard distance between two sets, and further generalize it to an arbitrary collection of subsets of a cover. These generalizations take a measure $\mu$ and assume that all sets are taken mod differences by sets of measure $0$.

This distance lies in $[0,1]$, is $0$ when sets are equal and $1$ when they do not intersect.

We make use of this generalized distance to associate birth times to simplices in a nerve. Given a cover, we define the Steinhaus filtration as the filtration induced from sublevel sets of the generalized Steinhaus distance function. In other words, consider a cover of the space and the nerve of this cover. For each simplex in the nerve, we assign as birth time the value of its Steinhaus distance of its corresponding cover elements. This filtration captures information about similarity of cover elements and overall structure of the cover.

Note that by definition for every simplex $\sigma \in 𝒰$. We will use ${\mathrm{Nrv}}_{St}$ when the cover $𝒰$ is evident from context. The weighting scheme satisfies the conditions of a filtration.

We provide a brief overview of persistence modules and the bottleneck distance. For details, see the book by Chazal, de Silva, Glisse, and Oudot [9].

Given a poset $T$, we define a persistence module $𝕍$ over $T$ to be an indexed family of vector spaces ${\{V_a\}}_{a\in T}$ with a family of linear maps $\{v_a^b:V_a\to V_b\}$ that satisfy $v_b^c\circ v_a^b=v_a^c$ whenever $a\le b\le c$. The homologies of the Steinhaus filtered simplicial complex $H_{\ast }({\text{Nrv}}_{St}(𝒱))$ defines a persistence module where each space $V_a\in H_{\ast }({\text{Nrv}}_{St}(𝒱))$ is the homology of the simplicial complex consisting of simplices whose corresponding Steinhaus distance is at most $a$. Herein, we use simplicial homology with coefficients in some field $k$.

Given two persistence modules $𝕌$ and $𝕍$ over $ℝ$ and $ϵ\in ℝ$, a homomorphism of degree $ϵ$ is a collection of linear maps $\mathrm{\Phi }={\{{\varphi }_a:U_a\to V_{a+ϵ}\}}_{a\in ℝ}$ such that $v_{a+ϵ}^{b+ϵ}\circ {\varphi }_a={\varphi }_b\circ u_a^b$. We denote the set of homomorphisms of degree $ϵ$ by ${\text{Hom}}^{ϵ}(𝕌,𝕍)$. The composition of a homomorphism of degree $ϵ$ and a homomorphism of degree ${ϵ}^{\prime }$ is a homomorphism of degree $ϵ+{ϵ}^{\prime }$ given by the composition of their linear maps. For $ϵ\ge 0$, a crucial endomorphism of degree $ϵ$ is the shift map $1_{𝕍}^{ϵ}\in {\text{Hom}}^{ϵ}(𝕍,𝕍)$ given by the maps

We say that two persistence modules $𝕌$ and $𝕍$ are $ϵ$-interleaved if there are homomorphisms $\mathrm{\Phi }\in {\text{Hom}}^{ϵ}(𝕌,𝕍)$ and $\mathrm{\Psi }\in {\text{Hom}}^{ϵ}(𝕍,𝕌)$ such that $\mathrm{\Psi }\mathrm{\Phi }=1_{𝕌}^{2ϵ}$ and $\mathrm{\Phi }\mathrm{\Psi }=1_{𝕍}^{2ϵ}$.

When a persistence module $𝕍$ is $q$-tame, i.e., whenever , then the persistence module decomposes into the direct sum of interval modules $𝕍={\displaystyle \underset{k\in K}{⨁}}𝕀(p_k^{\ast },q_k^{\ast }).$ Each term $𝕀(p_k^{\ast },q_k^{\ast })$ represent the birth time and death time of a particular feature. This decomposition is often represented by the multiset of points $(p_k,q_k)$ in the extended plane ${\overline{ℝ}}^2$. This multiset is called the persistence diagram of $𝕍$ and denoted $\text{dgm}(𝕍)$.

In typical applications, the simplicial complex is finite. As a result, their homologies are finite and any map between their homologies will have finite rank. In other words, in typical cases the homologies of the Steinhaus filtration will be $q$-tame. However, if we allow for infinitely many cover elements then $H_{\ast }({\text{Nrv}}_{St}(𝒱))$ may not be $q$-tame.

To situate the Steinhaus filtration in the context of standard filtrations built on point clouds in Euclidean space, we wish to show the equivalence of the Steinhaus filtration to the Čech and VR filtrations under certain conditions. We first show that the Čech filtration on a finite set of points in dimension one, i.e., the nerve of balls with radius $r$ around each point and over a sequence of $r$, and the Steinhaus Nerve constructed from the terminal cover of the Čech filtration are isomorphic (see Theorem 4.1).

We provide experimental evidence for the $1$-skeletons of the Steinhaus filtration and the VR filtration being isomorphic. We prove one direction of this equivalence in arbitrary dimension – that the VR filtration completely determines the $1$-skeleton of the Steinhaus filtration (see Lemma 4.2). We prove by example that the Steinhaus filtration and the Čech filtration in two (or higher) dimension(s) may not be isomorphic (see Proposition 4.3).

Let ${\check{C}}_r(X)$ be cover of $X$ by balls of radius $r$ centered on points in $X$. The Čech complex is the nerve of this cover. The Čech filtration is sequence of simplicial complexes for all $r$.

We develop a theory of stable paths within a Steinhaus filtration. We provide an algorithm for computing a most stable path from one vertex to another. Note that a most stable path might not be a shortest path in terms of number of edges. Conversely, a shortest path might not be highly stable. Since the two objectives are at odds with each other, we provide an algorithm to identify a family of shortest paths as we vary the stability level.

We were studying shortest paths in a Mapper graph constructed on a machine learning model as ways to illustrate the relations between the data as identified by the model. In this context, shortest paths found could have low Steinhaus distance, and thus could be considered noise. This motivated our desire to find stable paths, as they would intuitively be most representative of data and stable with respect to changing or data.

It follows that a ${\rho }_1$-stable path is also ${\rho }_2$-stable for any ${\rho }_2\ge {\rho }_1$. Also, a ${\rho }_1$-stable path $P_1$ is more stable than a ${\rho }_2$-stable path $P_2$ when . In this case, we have a higher confidence that the edges in $P_1$ do exist, and are not due to noise, than the edges in $P_2$.

The problem of finding the most stable $s$-$t$ path can be solved as a minimax path problem on an undirected graph, which can solved efficiently using, e.g., range minimum queries [12].

We are then left with two paths between vertices $s$ and $t$, the shortest and the most stable. As these two notions, stable and short, are at odds with each other, we are interested in computing the entire Pareto frontier between the short and stable path. Algorithm 1 identifies the Pareto frontier, and its sample output is shown in Figure 7.

The blue points in Figure 7 are on the Pareto frontier, while the orange points are the pairs $[P^{\prime },{\rho }^{\prime }]$ that get replaced from the LIST in the course of the algorithm. We then visualize the paths on the Pareto frontier in Figure 8. Continuing our analogy to persistence, the path corresponding to a point on the Pareto frontier which sees a steep rise to the left is considered highly persistent, e.g., the path with length $21$ on the frontier.

We apply the Steinhaus filtration and stable paths to recommendation systems and Mapper analysis. We show how recommendation systems can be modeled using the Steinhaus filtration and then show how stable paths in this filtration can answer the question what movies should I show my friend first, to wean them into my favorite (but potentially weird) movie? We then define an extension of the traditional Mapper complex [32, 6] called the Steinhaus Mapper Filtration, and show how stable paths within this filtration can provide valuable explanations of populations in the Mapper construction. As a direct illustration, we focus on the case of explainable machine learning, where the Mapper complex is constructed with a supervised machine learning model as the filter function, and address the question what can we learn about the model?

We introduced the Steinhaus filtration, a new kind of filtration that enables application of TDA to previously inaccessible types of data. We then developed a theory of stable paths in the Steinhaus filtration, and provide algorithms for computing the Pareto frontier between short and stable paths. As proof of their utility to real world applications, we show how these two ideas can be applied to the analysis of recommendation systems and of Mapper in the context of explainable machine learning.

Our results suggest many new questions. The application of recommendation systems leaves us curious if the Steinhaus filtration along with new results such as the one on predicting links in graphs using persistent homology [3] could help answer the main question in recommendation system research: what item to recommend to the user next?

While paths and connected components are most amenable to practical interpretations, could other structures in the Steinhaus filtration also suggest insights? What would holes and loops in the Steinhaus filtration for recommendation systems mean?

We showed that when the cover is finite, the Steinhaus filtration is stable to small changes within the cover. The example showing non $q$-tameness for instances with infinite covers even when it is in a totally bounded space motivates this following question: can we find a finite subcover that approximates such infinite covers?