Cover Filtration and Stable Paths in the Mapper
Authors: Dustin L. Arendt
Matthew Broussard
Bala Krishnamoorthy
Nathaniel Saul
Venue:  (2020)
Keywords: cover and nerve
Jaccard distance
stable paths in filtration
Mapper
recommender systems
explainable machine learning

Abstract: The contributions of this paper are two-fold. We define a new filtration called the cover filtration built from a single cover based on a generalized Steinhaus distance, which is a generalization of Jaccard distance. We then develop a language and theory for stable paths within this filtration, inspired by ideas of persistent homology. This framework can be used to develop several new learning representations in applications where an obvious metric may not be defined but a cover is readily available. We demonstrate the utility of our framework as applied to recommendation systems and explainable machine learning.

We demonstrate a new perspective for modeling recommendation system data sets that does not require manufacturing a bespoke metric. As a direct application, we find that the stable paths identified by our framework in a movies data set represent a sequence of movies constituting a gentle transition and ordering from one genre to another.

For explainable machine learning, we apply the Mapper for model induction, providing explanations in the form of paths between subpopulations. Our framework provides an alternative way of building a filtration from a single mapper that is then used to explore stable paths. As a direct illustration, we build a mapper from a supervised machine learning model trained on the FashionMNIST data set. We show that the stable paths in the cover filtration provide improved explanations of relationships between subpopulations of images.


Under review as a conference paper at ICLR 2020
COVER FILTRATION AND STABLE PATHS IN MAPPER
Anonymous authors
Paper under double-blind review
ABSTRACT
The contributions of this paper are two-fold. We define a new filtration called the cover filtration built from single cover based generalized Jaccard distance. We provide stability results for the cover filtration, and show its equivalence to the Čech filtration under certain settings. We then develop a language and theory for stable paths within this filtration, inspired by ideas of persistent homology. This framework can be used to develop new learning representations in applications where obvious metric may not be defined but cover is readily available. We demonstrate the utility of our framework as applied to recommendation systems and explainable machine learning.
We demonstrate a new perspective for modeling recommendation system data sets that does not require defining bespoke metric. As application, we find that stable paths identified by our framework in a movies data set represent sequences of movies constituting gentle transition and ordering from one genre another.
For explainable machine learning, we present stable paths between subpopulations in the mapper of a model as explanations. Our framework provides an alternative way to build a filtration from a single mapper, and explore stable paths in it. For illustration, build mapper from a supervised machine learning model trained on the FashionMNIST data set. Stable paths in the cover filtration provide im- proved explanations of relationships between subpopulations of images.
Keywords: cover and nerve, Jaccard distance, stable paths in filtration, Mapper, recommender sys- tems, explainable machine learning.
INTRODUCTION AND MOTIVATION
The need to rigorously seed a solution with a notion of stability in topological data analysis (TDA) has been addressed primarily using topological persistence (Carlsson 2009 Ghrist 2008). Persis- tence arises when we work with sequence of objects built on a data set, filtration, rather than with a single object. One line of focus of this work has been on estimating the homology of the data set. This typically manifests itself as examining the persistent homology represented as dia- gram or barcode, with interpretations of zeroth and first homology as capturing significant clusters and holes, respectively (Adams & Carlsson 2009 Edelsbrunner al. [002] Edelsbrunner & Harer 2009 Zomorodian] 2005). 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 as a form of feature engincering to help compare different data sets rather than interpret individual homology groups (Adams al. 2017 Chazal al. 2009 Turner et al. 2014).
The implicit assumption in most such TDA applications is that the data is endowed with a natural metric, e.g., points exist in high-dimensional space or pairwise distances are available. In certain applications, it is also not clear how one could assign meaningful metric. For example, member- ships of people in groups of interest captured simply as sets specifying who belongs each group. An instance of such data is that of recommendation systems, e.g., used in Netflix to recommend movies to the customer. Graph based recommendation systems have been an area of recent research. Usually these systems modeled mendees and the other representing recommendations. In practice, these systems are augmented in bespoke ways accommodate whichever type of data is available. It is highly desirable analyze the structure directly using the membership information.
bipartite graph with one set of nodes representing recom-
Another distinct TDA approach for structure discovery and visualization of high- sigh-dimensional data is based on a construction called Mapper (Singh et al.) (007). Defined as a dual construction to a cover of the data (see Figure Mapper has found increasing in diverse applications in the past several

---

Under review as a conference paper at ICLR 2020
years (Lum al. 2013). Attention has recently focused on interpreting parts of the 1-skeleton of the Mapper, which is a simplicial complex, as sigmificant features of the data. Paths, flares, and eycles have been investigated in this context (Li et al., 2015; Nicolau et al., [011] Torres et al. 2016). The framework of persistence has been applied to this construction to define a multi-scale Mapper, which permits one derive results on stability of such features (Dey et al. (2066). At the same time, the associated computational framework remains unwieldy and still most applications base their interpretations on a single Mapper object.
We illustrate the standard Mapper construction in Figure We start with overlapping intervals cover- ing values of parameter, e.g., height of the points sampled from a circle. We then cluster the data points falling in each interval, and represent each cluster by a vertex. If two clusters share data points, we add an edge connecting the corresponding ver- tices. If three clusters share data points, we add the triangle, and on. The Mapper could present highly sparse representation of the data set that still captures its structure-the the large number of points sampled from the circle is represented by just four vertices and four edges here. More generally, we consider higher dimensional intervals covering subspace of Rd But in recommendation systems, the cover is just a collection of abstract sets providing membership info (rather than intervals over the range of function values). Could we define a topological construction on such abstract covers that still reveals the topology of the dataset?
Figure I: Mapper constructed on a noisy set of points sampled from a circle.
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 filtration from the abstract cover? But unlike the setting of, e.g., multiscale Mapper (Dey et al. 2016), we do not have a sequence of covers (called tower of covers) we want to work with single cover. How do we define a filtration on a single abstract cover? Could we prove stability results for such a filtration? Finally, could we demonstrate the usefulness of our construction real data?
1.1 OUR CONTRIBUTIONS
We introduce new type of filtration defined on single abstract cover. Termed cover filtra- tion, our construction uses Steinhaus distances between elements of the cover. We generalize the Steinhaus distance between two elements to those multiple elements in the cover, and de- fine a filtration single cover using the gen- eralized Steinhaus distance as the filtration in- dex. Working with bottleneck distance on covers, we show a stability result on the cover filtration-the the cover filtrations of two covers are a m interleaved, where a is bound on the bot- tleneck distance between the covers and m is the cardinality of the smallest element in either cover (see Theorem 3.5). We conjecture that in Euclidean space, the cover filtration is isomor- phic to the standard Čech filtration built on the data set. We prove the conjecture holds in di- mension 1 and independently that the Victoris- Rips filtration completely determines the cover filtration in arbitrary dimensions (see Section[
Figure 2: A cover with 7 elements, and the cor- responding nerve (left column). The cyan and green vertices are connected by single edge. But this edge is generated by a single point in the intersection of the cyan and green cover el- ements. Removing this point from the data set gives the cover and nerve shown the right col- umn. The path from cyan to green node now has six edges.
This filtration is quite general, and enables the computation of persistent homology for data sets without requiring strong assumptions. With real life applications in mind, we study paths in the 1-skeleton of construction. Paths provide intu-
2

---

Under review as a conference paper at ICLR 2020
itive explanations of the relationships between the objects that the terminal vertices represent. Our perspective of path analysis is that shortest may not be more descriptive see Figure for an illus- tration. Instead, we define a notion of stability of paths in the cover filtration. Under this notion, stable path is analogous to a highly persistent feature as identified by persistent homology.
We demonstrate the utility of stable paths in cover filtrations in movie recommendation system and Mapper. We first show how recommendation systems can be modeled using the cover filtration, and then show how stable paths within this filtration suggest sequence of movies that represent a "smooth" transition from one genre to another (Appendix C.T)) We then define an extension of the traditional Mapper (Singh al., 2007) termed the Steinhaus Mapper Filtration, and show how stable paths within this filtration can provide valuable explanations of populations in the Mapper, focusing on the case of explainable machine learning (Appendix C.2
real life applications: problem
1.2 RELATED WORK
Cavanna & Sheehy (2177) developed theory for a cover filtration, built from a cover of filtered simplicial complex. But we work from more general covers of arbitrary spaces.
We are inspired by similar goals as those of Dey et al. (2016) and Carrière et al. (2018), who ad- dressed the question of stability in the Mapper construction. Our goal is to provide some consistency, and thus interpretability, to the Mapper. We incorporate ideas of persistence in a different manner into construction using single cover, which considerably reduces the effort generate results.
While stability of persistence diagrams is a well studied topic (Edelsbrunner & Harer 2009), we may not get stability to simplices and cycles that generate the persistence homology classes (Bendich et al. 2019). In contrast, our definition of path stability (Section 5) aligns exactly with our result on stability for cover filtrations (Section 3). We believe this is unique feature of our method and its stability result-paths are automatically stable with respect to perturbations of input data.
The multi-scale Mapper defined by Dey al. (016)) builds filtration the Mapper by varying the parameters of a cover. This construction yields nice stability properties, but is unwieldy in practice and difficult to interpret. Carrière et al. develop ways based on extended persistence to automatically select a single cover that best captures the topology of the data (Carrière et al. 2018 8), producing one final Mapper that easy to interpret
Methods have been developed to track populations within the Mapper by identifying interesting paths (Kalyanaraman al.] 2019) and interesting flares (Kamruzzaman et al., [0088. Interesting paths maximize an interestingness score, and are manifested in the Mapper as long paths that track particular populations that show trending behavior. Flares capture subpopulations that diverge, i.e.,
show branching behavior. In our context, we are interested in shorter paths, under the assumption that they provide the most succinct explanations for relationships between subpopulations.
Our work is similar to that of Parthasarathy et al. (2017) in that they use the Jaccard Index of an observed graph to estimate the geodesic distance of the underlying graph. We take an approach more akin to persistence and make fewer assumptions about underlying data. Hence are unable to make rigorous estimates of distances and instead provide many possible representative paths.
S- S-paths defined by Purvine al. (2018) are similar to stable paths when we realize that covers can be modeled as hypergraphs, and vice versa. Stable paths incorporate the size each cover elements (or hyperedges), normalizing the weights by relative size. This perspective allows to compare different parts of the resulting structure which may have wildly difference sizes of covers. In this context, a large overlap of small elements is considered more meaningful than a proportionally small intersection of large elements.
2 COVER FILTRATIONS
We introduce the notions of distance on covers required to construct our filtrations and then provide the general definition of the cover filtration.
We begin with the definition of Steinhaus distance, a generalization of the standard Jaccard distance between two sets, and further generalize it to arbitrary collection of subsets of cover. These generalizations take a measure j and assumes that all sets are taken modulo differences by sets of measure O. We will take y arbitrary unless otherwise stated.
3

---

Under review as a conference paper at ICLR 2020
Definition 2.1 (Steinhaus Distance (Marczewski & Steinhaus 1958)) Given measure μa, the Stein- haus distance between two sets A, B
dst (A, B) 1 MA B) MAU B) MANB) p(AUB)
(AUB)
This distance also bounded on [0. 1], i.e., two sets have Steinhaus distance O when they are equal (as sets differing by measure 0 are identified) and distance 1 when they do not intersect.
We extend this distance from an operator on a pair elements to an operator on a set of elements.
Definition 2.2 (Generalized Steinhaus distance). Define the generalized Steinhaus distance of collection of sets } as
dsr (st((U;)) = M U:)
P(U))
Much of results that consider paths used the standard version of Jaccard distance for finite sets. But we require the Steinhaus distance for general measures present equivalence results Cech and VR filtrations ( Hence we present all results for the generalized Steinhaus distance.
We make use of this generalized distance associate birth times to simplices in nerve. Given cover, we define the cover filtration as the filtration induced from sublevel sets of the generalized Steinhaus distance function. In other words, consider 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. This filtration captures information about similarity of cover elements, and the overall structure of the cover.
Definition 2.3 (Nerve). A nerve of cover 24 = bec is an abstract simplicial complex defined such that each subset {UgheeJ C u i.c., with J S C, defines simplex if [ee)(U,) * 6. In this construction, each cover element U3 E U defines vertex.
Definition 2.4 (Steinhaus Nerve). The Steinhaus nerve of a cover U, denoted Nrv (44), is defined as the nerve of 2 with each simplex assigned their generalized Steinhaus distance weight:
We = ds:((UU E E Vo E..
Note that w, < 1 by definition for every simplex E U. We will use Nrv when the cover UI is evident from context. This can be thought of as a weighted nerve, but the weighting scheme satisfies the conditions of filtration (see Page 14 for the proof).
Theorem 2.5. The Steinhaus nerve of cover U is filtered simplicial complex.
Following this result, we refer to the construction as the Steinhaus filtration. The only cover filtra- tions use in this paper is Steinhaus filtrations,
will use the two terms interchangeably.
We could study an adaptation of cover filtration to an analog of the VR complex by building a weighted clique rank filtration from the 1-skeleton of the cover filtration (Petri et al. (013). This adaptation drastically reduces the number of intersection and union checks required for the construc- tion. The weight rank clique filtration is way of generating a flag filtration from weighted graph PPerr et al. 2013). We can apply this technique to build a VR analog of the cover filtration.
3 STABILITY
We consider notions of stability the cover filtration with respect to changes in the cover. We first modify the standard edit distance to define a bottleneck distance on the space of covers of a finite set that have the same cardinality. Under this setting, we show that the cover filtration is interleaved with respect to this distance.
Definition 3.1 (Bottleneck metric on covers). Let and 1 be two finite covers of finite set X with same cardinality, and let MM, V) be the set of possible matchings between them. Let A denote the symmetric difference. Then the bottleneck distance dn(.-) between two covers is defined as
d ()
min MEM((E)
max ((UAV)
(U
4

---

Under review as a conference paper at ICLR 2020
We can verify that dg is indeed metric (see Page 14 for the proof).
Proposition 3.2. Let U, V. and W be finite covers of finite set X with equal cardinalities, and let d be the bottleneck distance between any pair of these covers (Definition Then dp is a metric.
We now present two somewhat technical lemmas, which we subsequently employ in the proof of the main stability result. See Page 14 for proof of Corollary 3.4
Let a, b, c, d, e, f be real numbers with a bb <b [b] Then we have that (a-c)/(b+d) that we can distribute between decreasing the numerator of a proper fraction and increasing its denominator, the greatest decrease comes from decreasing the numerator by the entire weight.
Lemma 3.3.
[d], and [b] > [ > (a-e)/(b+ f) when < In words. for a weight
d
Q- > 0. b+d b+s
Proof. We will show that, with the given conditions,
c a - (a b + b (a- ebb (b+d)bb+
(a -c(0+)++ddc)) (b+
(b + fc) =
ab + ac + ad - ae - cb 2 - cd + ce ab ae as tf
d)(b
20c Zne + ad - aʃ + be + - 0² + tef cd
(b + (b
-2a(e- - c) + ald - f) + b(e c) + cc c) of
(b+d)(b+))
-2a(e - c) + a(e c) +ble - (e ce ef
db+d)(b++
since e c= f-
(-a+b) + b) - c) + ed - ef + od - of + ef - cd (-a+ b)(e c) + ed - ef
(b+ db + f)
(b+d)(b + +
< e, S
ed > cf and e c > 0. Also, since a/b is proper, < b, so -a+b > 0. Thus
(-a+b)(e-e)+ cf) 0. Since b+d, b+ O. we get that (-a + b)(e c) ed cf 0,
(b d) +
which in turn shows that a - C b+ d
a -
as desired.
b b+s
Corollary 3.4. Similar Lemma
3.3 the greatest increase possible such a scenario comes from assigning the negative of the total weight to the numerator.
We now present a theorem that provides basic stability guarantees for the constructed filtration, assuming that each element is not too small.
Theorem 3.5. Suppose that U (U,} and V = -V1) are covers of X with [ = |V such that d LI( S a. Given m = min minu (U)), minvev ((V)), Nrv and Nrv are a/m m interleaved filtrations.
Proof. Given two covers U {U+) and V (V,). we use the notation that Uj and Vi, for generic indices and j. are paired in matching that minimizes the bottleneck distance between the two covers. We assume that the bottleneck distance is a, positive integer.
We consider the following question: what is the largest change in generalized Steinhaus distance possible between collection Un and V,, where index sets I and J are paired elementwise in matching. To answer this question, we keep U, fixed and consider how large difference in gen- eralized Steinhaus distance can achieve by taking the symmetric difference with set S; with
5

---

Under review as a conference paper at ICLR 2020
measure up to for each U,. That is, want to maximize change in ((NU1)/ (((U))) To get the maximum increase in ((NU://((UU)) we must increase the numerator and/or decrease the denominator. Likewise, we must decrease the numerator and/or increase the denominator to get maximum decrease.
First, we note that St be partitioned into two sets: $1,1 U3 n S,, and 81.2 S $1,1, those not in U, n S.. ju($1,1 + s1,2) = ((,,) Σ a. Replacing U2 with U; $1,1 cannot increase the size of the intersection union, but can decrease the size of the intersection or union by up u(st.1), Likewise, replacing U; with U,U.A U4,2 cannot decrease the size of the intersection or union, but could increase the size of the intersection or union by up to p(st.2).
The greatest possible change would occur if it were possible to select an S; for each Ug in the cover such that replacing each U, turn with U,S., increases or decreases the numerator with p(s;,1) or (u(s;,), respectively, and does the opposite to the size of the denominator by (u(s;2) or p(sta), again respectively. Since (((Si.1 + 81,2) = v(S.) S a, follows that each change has weight of most which it could throw into increasing decreasing the size of the intersection and doing the opposite to the size the union.
Lemma 3.3 and Corollary 3.4 imply that the maximum possible change in those situations will be achieved when weight is directed toward increasing or decreasing the size of the intersection, since u((Ur)/ (UUU)) must be between 0 and 1. As we want to bound the possible change in the Steinhaus distance, it will suffice to use the observation that
m((V)) + Sa. S 1
M(NUT) ((UU))
S m(NV)) Sa
((UV))
((UV))
to obtain bounds on the change of Steinhaus distance between covers with maximum bottleneck distance of and with the cover cardinality.
Then we have
M(NV))+++++ S m(UV))
p(nU))
1 m(UUT)
((V)) Sa
((UV)) ((V))) S du:(Ur)
m(NV)) Sa
s dsc(UI), where is the size of the smallest set, since
m(UV)) Sm
p(NV)) Sa
1 p(nV))
Sa
m(VV)) Sm
p(UV))
M(VV))
dsi(V dsc(UI).
Similarly, since
(NVV)) - Sa
p(nU1)
we get ds:(Vi) + a dsi(Ur).
m(UVT) 2 M(UUT))
Hence ds: s ds:(Ur) S dsi(Vi) -..)++..gviin giving that 2 and V a/m interleaved. m
Remark 3.6. Consider the case when W # [V]. Assume without loss of generality that [ > [V]. Then there is vertex E Nrv (44) that is not present in Nrvs:(V). Hence Nrv (2/) and (V)) cannot be interleaved the current setting. We need to first generalize matchings and the bottleneck distance to allow covers with unequal cardinalities.
4 EQUIVALENCE
To situate the cover filtration, we wish to show that it is isomorphic to the Čech and VR filtrations under certain conditions. We conjecture that the Čech filtration on a finite set of points, i.e., the nerve of balls with radius around each point and over a sequence of r, and the Steinhaus Nerve constructed from the terminal cover of the Čech filtraiion are isomorphic.

---

Under review as a conference paper at ICLR 2020
More precisely, the insertion order of simplices is equivalent between the two cases, and there exists a continuous bijection between insertion times of the Steinhaus Nerve and insertion times of the Čech filtration. We prove this result for n = 1, i... when is drawn from the real line. We also provide experimental evidence for the 1-skeleton equivalence, and prove one direction of this equivalence (that the VR filtration completely determines the cover filtration).
Let (X) be the cover of X by balls of radius r centered on points in X. The Čech complex is nerve of this cover. The Čech filtration is the sequence of simplicial complexes for all values of r.
Conjecture 4.1 (Čech equivalence). Given a finite data set X C R" and some radius R > diam(X) the Čech filtration constructed from X isomorphic to the the cover filtration on X constructed from (x(X), given the Lebesgue (i.e. volume) measure.
A comprehensive proof for arbitrary order of intersections and arbitrary dimension is incomplete. We provide the proof for the case of n-skeleton in 1-dimension and provide a mapping from the Čech filtration to cover filtration for the 1-skeleton arbitrary dimension.
Proof. We will define C(t+))) as the birth radius of the simplex defined by the set {er). This can be computed as Ö({r:)) (m. min)(::))
(e:))/ /2 since in 1 I-dimensional space the associated simplex is born precisely when the balls around the two outermost points intersect.
Let {V:} be the set of balls of radius R centered on the set {u:}. Recall that we are using the Stein- haus distance for Lebesgue measure, so μ computes volume here. Then the generalized Steinhaus RR)
distance for those balls is given by ((V.t) = max(n; Riimmnnee; R since the mutual intersec- tion of all of the balls in this one dimensional space is the interval bounded by the minimum right endpoint of all the balls and the maximum of all left endpoints of all the balls and the union of all the balls has the minimum left endpoint amongst left endpoints and maximum right endpoint amongst right endpoints.
min (.) - max(u;) 2R
= 1 -2C((u:))+2R = R- C(&o)) 2C((u:)) +2 R + C(fu))
ds:((Vi)) =
max max(v;) mi;) + 2R
Solving for C(fu:)), we get C((u)) (d).) 2V)):((V)))- establishing bijection between birth times.
R-z decreases monotonically Now since R is the radius of X and U2 C 0 ((f+)) S R. Also, R+z over the range x E [o, R.. Thus 1 R-z increases monotonically on x E [0, R). Thus if we order R+r
the subsets of of X by increasing birth radius (8), 82, ... 8n)), (dse(s1), (sr(s2), ... dss(sn)) is also in increasing order. Thus the two filtrations are isomorphic.
We now address the case of 1-skeleton of the Čech and cover filtrations in arbitrary dimension. It is clear that if the 1-skeletons are isomorphic, then the cover filtration is isomorphic to the VR filtration. We prove one direction this isomorphism (see Pa the proof). Lemma 4.2. The VR filtration completely determines the cover filtration in arbitrary dimensions.
Hence one can derive the cover filtration from the Vietoris-Rips filtration. In Appendix B we present some experimental evidence suggesting that the I-skeleton of the Steinhaus filtration and the Vietoris-Rips filtration are isomorphic.
STABLE PATHS
We develop a theory of stable paths in the 1-skeleton of a cover filtration. We provide algorithm to find a maximally stable path from one vertex to another, with Steinhaus distances as edge weights. Note that maximally stable path might not be shortest path in terms of number of edges. Con- versely, a shortest path might not be highly stable. Since the two objectives are at odds with each other, provide algorithm to identify family of shortest paths we vary the stability level, similar in a loose sense to computing persistent homology.
We were studying shortest paths in Mapper constructed 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
machine learning model as ways to

---

Under review as a conference paper at ICLR 2020
desire to find stable paths, as they would intuitively be most representative of the data set and stable with respect to changing parameters in Mapper or changing data.
Definition 5.1 (p-Stable Path). Given Steinhaus distance p. a path P is defined be p-stable if
max(ds: E P) P.
In other words, the largest edge weight (Steinhaus distance) along the path is at most Note that a P1 -taabe path is also P2-stable for any P2 2 P1. Also, a #1 -tablee path P2-stable path P2 when P1 < P2. Hence we have higher confidence that edges in P1 do exist (are not due to noise) than those P2. We now define maximally stable paths between a pair vertices. Definition 5.2 (Maximally Stable Path). Given pair of vertices and t, maximally stable s-t path a p-stable path between & and t for the smallest value of p. If there are multiple s-t paths at the same minimum p value, shortest path among them is defined as maximally stable path.
more stable than a
The problem of finding the max- imally stable s-f path can be solved as minimax path prob- lem on an undirected graph, which can solved efficiently using, e.g., range minimum queries (Demaine) ct al. 2009).
Algorithm to identify the Pareto frontier between shortest and maximally stable paths.
Figure 3:
Input: I-skeleton G of cover filtration and vertices s,t
set LIST = [0.0] // stores [P.p] pairs while 8, are connected in G compute shortest path P between and find p= max(ds((e)
We are then left with two paths be- tween vertices and t, the short- est and the maximally stable. The shortest path is not necessarily stable and the stable path is not necessarily short. As these two notions, stable and short, are at odds with each other, we are in- terested in computing the entire Pareto frontier between the short and stable path. We present an algorithm to identify the Pareto frontier in Figure 3 and a visual- ization of the output from this al- gorithm in Figure
if LIST has no pair [P',p] |P|= |P' add [P.p] to LIST else if p< for replace [P with P.P.] in LIST
ELIST |P = PP
remove all edges e from G with dscle) 2 p
Return: LIST
We repeatedly compute the shortest path, while essentially sweeping over the Steinhaus Distance. This process results a Pareto fron- tier balancing the shortest paths with the sta- bility of those paths. The blue points in Figure 4 are the Pareto frontier, while the orange points are the pairs [P',p'] that get replaced from the LIST the course of the algorithm. We then visualize the paths on the Pareto fron- tier in Figure Continuing our analogy to per- sistence, the path corresponding to 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.
1000
0.00
0.52
22
25
24
Length of path
Figure 4: Pareto frontier between length and sta- bility of path.
23
28/0335
Figure 5: Visualization of paths on the Pareto frontier in Figure Length /p listed on top.
8

---

Under review as a conference paper at ICLR 2020
6 APPLICATIONS
We apply the cover filtration and stable paths two applications, recommendation systems and Mapper. We first show how recommendation systems can be modeled using the cover filtration and then show how stable paths within 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 (Singh al.] Carrièree & Oudot 2017) called the Steinhaus Mapper Filtration, and show how stable paths within this filtration can provide valuable explanations of populations in the Mapper. As a direct illustration, learning, where the Mapper is constructed with supervised machine learning model as the filter function, and address the question what can we learn about the model?
focus the case of explainable machine
Movie Recommendations: We illustrate how cover filtration framework could be used to find a sequence of movies to gently transition from Mulan to Moulin Rouge. It would be abrupt to switch directly from to the other movie, since they belong to completely different genres. We compute stable paths that identify such feasible gentle sequences, Two sequences corresponding to a shortest path and the most stable path are presented in Table See Appendix C.I for details.
Table Two sequences of movie transitions from Mulan Moulin Rouge.
Shortest Path
Most Stable Path
1. Mulan (1998)
1. Mulan (1998)
2. Dumbo (1941)
2. Robin Hood (1973)
3. Sound of Music, The (1965)
3. Dumbo (1941)
4. Moulin Rouge (2001)
4. Sound of Music, The (1965)
5. Gone with the Wind (1939)
6. Psycho (1960)
7. High Fidelity (2000)
8. Moulin Rouge (2001)
Explanations in a Machine Learning Model: With a goal to develop a method of model in- duction for inspecting machine learning model, build Mapper (Singh et al.) (007) from the predicted probability space of a logistic regression model built from the Fashion-MNISTT data set (Xiao et al. 2017). 'Th goal is understand the model structure by characterizing the relation- ship between the feature space and the prediction space. We extend the constructed Mapper to be Steinhaus Mapper Filtration and analyze the stable paths in that object.
See Appendix C.2 for details. We look at three regions of shoes (sneaker, ankle boot, and sandals) that are understandably confusing the machine learning model. We try to elucidate where these confusions arise by studying the stable paths connecting representative nodes for each type of shoe. Figure IT shows representatives from each vertex in the path for the shortest path and the stable path. In both paths, the vertices start predominately containing sneakers and sneaker-like sandals. They then transition containing a larger proportion of ankle boots, with all three classes showing higher cut tops or high heels.
Along each path we can see the relationships between nodes change. the most stable path on the right, we a slow transition from sneaker space to ankle boot space, with some amount of sandals spread throughout. Through the path, shoes from each of the three classes become taller. Near the middle of the path, the images from sneakers and ankle boots are nearly indistinguishable. And earlier in the path, we see how some white strips in the sneakers and boots might easily be confused with negative space in the sandals.

---

Under review as a conference paper at ICLR 2020
7 CONCLUSION
In this work, we established the cover filtration, a new kind of filtration that enables application of TDA to previously inaccessible types of data. We then developed theory of stable paths in the cover 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.
The results in this paper suggest many new questions. The application of recommendation systems leaves us curious if the cover filtration along with new results such as the one on predicting links in graphs using persistent homology (Bhatia et al.] (018) could provide methods for answering the main question in recommendation system research: what item to recommend to the user next? Proving Conjecture is highly desirable goal.
The applications of cover filtration and stable paths are not limited to ones we highlighted. Another possibility not explored is for sensor networks. Sensor coverage areas often not uniform balls, and the cover filtration is aptly suited for developing a filtration. In the context of communication networks, stable paths could be interpreted reliable routes. Yet another direct application could be finding driving directions that take not only short, but also "easy" routes.
While paths and connected components most amenable practical interpretations, could other structures in the cover filtration also suggest insights? What would holes and loops in the cover filtration for recommendation systems mean?
Our application for explanations in machine learning models raises the following question. What the implications of understanding a path in Figure I1] How could the predictive model be updated to account for such implications?
We showed that the cover filtration stable small changes within the cover. Does this result imply that the persistence diagram of the Steinhaus Mapper filtration is stable with respect to changes in the data, cover parameters, or filter functions?
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Henry Adams and Gunnar Carlsson. On the nonlinear statistics of range image patches. SIAM Journal on Imaging Sciences, 2(1):110-117, 2009.
Henry Adams, Tegan Emerson, Michael Kirby, Rachel Neville, Chris Peterson, Patrick Shipman, Sofya Chepushtanova, Eric Hanson, Francis Motta, and Lori Ziegelmeier. Persistence images: A stable vector representation of persistent homology. Journal of Machine Learning Research, 18 (8):1-35, 2017. URL CRRLhttp:/// /m1 wttpppapprs//1//11 337 .html
Paul Bendich, Peter Bubenik, and Alexander Wagner. Stabilizing the unstable output of per- sistent homology computations. Journal of Applied and Computational Topology, Nov 2019. ISSN 2367-1734, doi: 10.1007//41468-019-000444 URL htt.aats////i..rr/////// s41468 01 9-1--11 00044-3
Sumit Bhatia, Bapi Chatterjee, Deepak Nathani, and Manohar Kaul. Understanding and predicting links in graphs: A persistent homology perspective. arXiv preprint 1rXiv:1811.04449 2018.
Philip Bille, Anna Pagh, and Rasmus Pagh. Fast evaluation of union-intersection expressions. In
Takeshi Tokuyama (ed.), Algorithms and Computation, pp. 739-750, Berlin, Heidelberg, 2007.
Springer Berlin Heidelberg. ISBN 978-3-540-77122-3.
Gunnar Carlsson. Topology and data. Bulletin of the American Mathematical Society, 46(2):255- 308, January 2009. ISSN 0273-0979. doi: 10.1000/6227-099799-00001222
Mathieu Carrière and Steve Oudot. Structure and stability of the oin-dimnnsi mapper. Foundations of Computational Mathematics, Oct 2017. ISSN 1615-3383. doi: 10.1007/
-10208-017-9370-22 arXiv:1511.0588
Mathieu Carrière, Bertrand Michel, and Steve Oudot. Statistical analysis and parameter selection for mapper. Journal of Machine Learning Reseurch, 19(12):1-9, 2018. URL http::/mmlr. arXiv: Ttl::1706.002000
pre/papers/v19//1 291. html
Nicholas Cavanna and Donald R Sheehy. Persistent nerves revisited. Young Researchers Fo- rum Symposium of Computational Geometry, 2017. URL http:://donshehhy
Frédéric Chazal, David Cohen-Steiner Leonidas J. Guibas, Facundo Mémoli, and Steve Y. Oudot. Gromor-hausdorff stable signatures for shapes using persistence. Proceedings of the Sym- posium Geometry Processing, SGP '09, pp. 1393-1403, Aire-la- Mille,,, Switzerland. Switzer- land, 2009. Eurographics Association. URL kutpp:/ dl, acm. org/ citation. cfm?id=
17356033174558
Erik D. Demaine, Gad M. Landau, and Oren Weimann. On cartesian trees and range minimum queries. In Susanne Albers, Alberto prrchettiiSpaccamehh Yossi Matias, Sotiris Nikoletseas, and Wolfgang Thomas (eds.), Automata, Languages and Programming, pp. 341-353, Berlin, Heidelberg, 2009. Springer Berlin Heidelberg. ISBN 978-3-644--0222-11.
Tamal K. Dey, Facundo Mémoli, and Yusu Wang. Multiscale mapper: Topological summarization via codomain covers. In Proceedings of the Tweent-Sevennth Annual ACM-SIAM Symposium on Discrete Algorithmss, SODA '16, pp. 997-1013, Philadelphia, PA, USA, 2016. Society for Indus- trial and Applied Mathematics. ISBN 978-1-611974-33-1
arXiv: 150..053040333333
Herbert Edelsbrunner and John L. Harer. Computational Topology An Introduction. Mathematical Society, December 2009. ISBN 0821849255.
American
Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplifi- cation. Discrete and Computational Geometry. 28:51 18:511-5333 1-533, 2002.
Martin Ester, Hans-Peter Kriegel, Jörg Sander, and Xiaowei Xu. A density- based algorithm for discovering clusters censity-based algorithm for discovering clusters in large spatial databases with noise. In Proceedings of the Second International Conference on Knowledge Discovery and Data Mining, KDD'96, pp. 226-231. AAAI Press, 1996.
11

---

Under review as a conference paper at ICLR 2020
Robert Ghrist. Barcodes: The persistent topology of data. Bullerin of the American Mathematical Sociery, 45:61-75, 2008. doi: 10.1090/002730099-000000000 URL hhtp:: : //www ams
F Maxwell Harper and Joseph A Konstan. The MovieLens datasets: History and context. ACM transactions on interactive intelligent systems (TIIS), 5(4):19, 2016.
Ananth Kalyanaraman, Methun Kamruzzaman, and Bala Krishnamoorthy. Interesting Paths in the Mapper Complex. Journal of Computational Geometry, 2019. To appear; arXiv:
Methun Kamruzzaman, Ananth Kalyanaraman, and Bala Krishnamoorthy Detecting divergent subpopulations phenomics data using interesting flares. In Proceedings of the 2018 ACM International Conference Bioinformatics, Computational Biology, and Health Informatics, BCB '18. pp. 155-164, New York, NY, USA, 2018. ACM. ISBN 10.1 10.1145//23354..223999
doi:
Li Li, Wei-Yi Yi Cheng, Benjamin S. Glicksberg, Omri Gottesman, Ronald Tamler, Rong Chen, Er- win P. Bottinger, and Joel T. Dudley. Identification of type 2 diabetes subgroups through topolog- ical analysis of patient similarity. Science Translational Medicine, 7(311):31 Iral)33all 2015. ISSN 1946-6234, doi: 10. 126/scitranslmedd. 2423444
Li. Concise formulas for the area and volume of a hyperspherical cap. Asian Journal of Mathe- matics and Statistics, 4(1):66-70, 2011.
Pek Y. Lum, Gurjeet Singh, Alan Lehman, Tigran Ishkanov, Mikael. Vejdemo-Johannson, Muthi Alagappan, John G. Carlsson, and Gunnar Carlsson. Extracting insights from the shape of com- plex data using topology. Scientific Reports, 3(1236), 2013. doi: 10.1038//rep01236.
Edward Marczewski and Hugo Steinhaus. On a certain distance of sets and the corresponding distance of functions. Colloquium Mathematicum, 6(1):319-327, 1958. URL/tttp://eudm11
org/doc/ 2100///211778
L. McInnes and J. Healy. UMAP: Uniform Manifold Approximation and Projection for Dimension
Reduction. ArXiv e-prints, February 2018
Leland Mclnnes, John Healy. Nathaniel Saul, and Lukas Großberger. Umap: Uniform manifold approximation and projection. The Journal of Open Source Sofvware, 3(29):861, 2018. URL
https://joss: theoj. wwwpeoo.or/ppppprreee 10. 21 21105/ joss. 00861
Monica Nicolau, Arnold J. Levine, and Gunnar Carlsson. Topology based data analysis identifies subgroup of breast cancers with unique mutational profile and excellent survival. Proceedings of the National Academy of Sciences, 108(17):7265-727)) 2011. doi: 10.1073/pnas. 1t..77//paa.111022610000 1102826108.
Nina Otter, Mason A Porter, Ulrike Tillmann, Peter Grindrod, and Heather A Harrington. A roadmap for the computation of persistent homology. EPJ Data Science, 6(1):17, 2017.
Srinivasan Parthasarathy, David Sivakoff, Minghao Tian, and Yusu Wang. A quest to unravel the metric structure behind perturbed networks. In Proceedings of the thirty-three annual symposium on Computational geometry, pp. 123-445. ACM, 2017.
Giovanni Petri, Martina Scolamiero, Irene Donato, and Francesco Vaccarino. Topological strata of weighted complex networks. PloS one, 8(6)xe66566, 2013.
Emilie Purvine, Sinan Aksoy, Cliff Joslyn, Kathleen Nowak, Brenda Praggastis, and Michael Robin- son. topological approach to representational data models. In Sakae Yamamoto and Hirohiko Mori (eds.), Human Interface and the Management of Information. Interaction, Visualization, and Analytics, pp. 90-109, Cham, 2018. Springer International Publishing. ISBN 978-3-319-920443-
Nathaniel Saul and Dustin L. Arendt. Machine learning explanations with topological data analysis. Demo the Workshop Visualization for Al explainability (VISzAI), 2018
12

---

Under review as a conference paper at ICLR 2020
Gurjeet Singh, Facundo Memoli, and Gunnar Carlsson. Topological Methods for the Analysis of High Dimensional Data Sets and 3D Object Recognition. In M. Botsch, R. Pajarola, B. Chen, and M. Zwicker (eds.), Proceedings of the Symposium on Point Based Graphics, pp. 91-100, Prague, Czech Republic, 2007. Eurographics Association. ISBN 978-3-905673-51-7. doi: 10. 231 2112/SPBG/SPEC00/001--0000
Brenda Y. Torres, Jose Henrique M. Oliveira, Ann Thomas Tate, Poonam Rath, Katherine Cumnock, and David S. Schneider. Tracking resilience to infections by mapping disease space. PLoS Biol, 14(4):1-19, 04 2016. doi: 10. 1tt.7/////rall.ppp. phio. 1002436.
Katharine Turner, Yuriy Mileyko, Sayan Mukherjee, and John Harer. Fréchet means for distributions of persistence diagrams. Discrete & Computational Geometry, 52(1))44-70, Jul 2014. ISSN 1432-0444. doi: 10.10077/04455--44-604.
Hendrik Jacob van Veen and Nathaniel Saul. Kepler mapper: python library for visualization of high-dimensional data. 2017. http://wwww..cco/iiiitttaaaeeeee
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mmin a novel image dataset for benchmark- ing machine learning algorithms. 2017.
Afra J. Zomorodian. Topology for Computing. Cambridge Monographs on Applied and Com- putational Mathematics. Cambridge University Press, New York, NY, USA, 2005. ISBN 978- 0521 136099.
13

---

Under review as a conference paper at ICLR 2020
Appendix
A
MISSING PROOFS
We restate theorems and lemmas stated without proofs in the main paper, and present their proofs.
Theorem 2.5 The Steinhaus nerve of cover U is a filtered simplicial complex.
Proof. This proof makes use of standard set theory results. Let UI be an arbitrary cover of some set X and let Nrvst its Steinhaus nerve. We consider Nrv as filtration by assigning as the birth time of simplex E Nrv its weight wig To show this is indeed filtration, we focus on a single simplex a and a face 3 a to show that the face always appears in the filtration before the simplex.
Suppose is generated from cover elements {Ui)eer over some index set I. Let face 3 be generated by cover elements indexed by subset J C.
u(NieJUs) and m(iee(U))
The birth time of r is dss ((Ui)i)) =1
the birth time of a is ds ((U:)iE)) = u(NverU:)
m(UielU;)
Clearly, with (U))ee с (U:)ie,, we have that (((nie 2 U4)) and ((U)e)U,) s ((),erU;), It follows then that (T)(T) I dsr(o). With K, denoting the subcomplex that in- cludes all simplices in Nrvg. with birth time most a E [0, 1), for any a, B [0,1) with a B. we have Ka C Kg. Hence (t is monotonic filtration.
Proposition 3.2 U,, and W be finite covers of finite set X with equal cardinalities, and let
d denote the bottleneck distance between any pair of these covers as specified in Definition Then dg is metric.
Proof. We make the following observations.
1. d (2, 0, as matching each set in the cover to itself gives distance of 0 and the smallest cardinality symmetric distance is O, hence this matching gives the minimum possible symmetric difference. Likewise, if dp (24, V) = 0, there is a matching where the symmetric difference between each matched pair has cardinality O. Hence the sets are equal for each pair in the matching, and hence U = V.
2. de (U, V) O, since is the greatest lower bound for measures.
3. d dn,,)))
min (max (UU ((UAV)) min minMeM(vu)) (max(V,U)M (VVAU) dv(V,
4. Let dn(,, V)- = a and d (V, W) = 3. Then Uj and its matched set V, differ on set D with measure at most a, and V, and its matched set Wt differ on a set D2 with measure at most B. Then U; and W. differ on some subset of D2 U2. so their difference has measure at most μ(D; U D2) S {p(Di) + u(D2) I a + B. Since this result holds for all i, there is matching between 1/ and W with maximum symmetric difference measure of a + 3. Hence da (4, W) & a + 3 = dg (u, V) + (v W).
Hence dg is a metric with respect to covers of equal cardinality.
Corollary 3.4, Similar to Lemma 3.3 the greatest increase possible in such a scenario comes from assigning the negative of the total weight to the numerator.
Proof. Let a, b, d, e, be numbers as specified. Then -c -e, and -c d J, and
bb] >
[d) |6| > Ifl, so a, 6, -c, -d,- -e, -f fulfill the hypotheses of Lemma 3.3 Then we get that
a
a t
d b b-f
14

---

Under review as a conference paper at ICLR 2020
Lemma 4.2 The VR filtration completely determines the cover filtration in arbitrary dimensions.
Proof. The intersection of two hyperspheres was derived by Li (001). J. The volume of intersection of two hyperspheres of equal radius R in IK" with centers distance apart is defined
n/ VA (R,d) = r(2 +)
+ 1
Rd 1
2 '
where I is the gamma function and / the regularized incomplete beta function:
[a b) [(a + b) So ud u01 - - T(a)I(b)
We can reduce this equation to The volume of an n-sphere radius R is
Vn (R, d) 1n"n(n-11/22 11/2 So 2-(d/2)/1 ((n-1)/2(1 u) -1/2 du
T T(
T./22
(o(R)
R"
r( + 1)
and the volume of union of two n-spheres is
(R, = 2V (R) (R)
We then compute the Steinhaus distance with Lebesgue measure of two spheres in R" and radius with Euclidean distance d apart as
2V RR) - 2V (R, 2V R (R, d)
d.. d)
2 1n/2 R 2 (n-1)/2 (1 /2 ( (n- (n-2))/ 1/2
+[
r(=21)
r(++1) R
gn/2
R (n 1)/2 /24)/12 n
11/2 (1-))1111
1(222) )
2 - nI
(d(22)//1
11/21) - -1)-111 1/2 du
2( (T())= 1- (d/2)/12 11/21)/2(1 -1) du
This equation provides a mapping from the birth time of the edge in the Čech filtration to the birth time of the edge in the cover filtration. Once and R chosen, the equation readily reduces, producing the birth times of a simplex in the cover filtration.
B EQUIVALENCE
We detail experimental results suggesting that the 1-skeleton of the Steinhaus filtration and the I- skeleton the Čech filtration are isomorphic (i.e., the Vietoris-Rips filtration). To estimate the area of intersection of 1-spheres, in Figure [ shows the 50 landmark points along with 20,000 points uniformly sampled around the landmarks. The middle plot shows the persistence diagrams of dimension 0 and 1 for the Vietoris- Rips filtration on the landmarks. Finally, we show an approximated Steinhaus filtration on the landmarks, using the balls with radii 0.5 as the covers. We approximate the Steinhaus filtration similar how the Vietoris-Rips approximates Čech filtration, i.e., by only computing the 1-skeleton of the nerve, and including any higher order simplices for which all faces are already contained in the filtration, taking the maximum birth time of all faces. We note that the two persistence diagrams have only minor differences (only in dimension 1).
Monte Carlo integration with uniform sampling. The first plot
15

---

Under review as a conference paper at ICLR 2020
Rips filtration on landmarks
Cover-Fiag filtration R=0.5
1.0
0.35
0.30
0.25
0.0
0.0
0.3-
-025
-0.0
0.75
-1.00
-1.
-0.5
0.0
0.5
1.0
0.0
0.1
0.2
0.3
0.0
0.
0.1
0.6
Brth
Brth
Figure 6: Persistence diagrams for the Vietrois-Rip Rips filtration and the approximate Steinhaus filtra- tion of set of uniformly sampled points in the plane.
C APPLICATIONS
C.I RECOMMENDATION SYSTEMS
In this application, apply the cover filtration to a recommendation system data set and employ the stable paths analysis to compute sequences movies that ease viewers from one title to another title. Our viewpoint on recommendation systems is similar to work of graph-based recommendation systems. This is an active area of research and we believe our new perspective interpreting such systems covers and filtrations will yield useful tools for advancing the field. The general approach of graph-based recommendation systems is to model the data as a bipartite graph, with one set of nodes representing the recommendation items and the other set representing the recommendees. We can interpret a bipartite graph as a cover, either with elements being the recommendees covering the items, elements being the items covering the recommendees.
For an example that we will see more of shortly, suppose you have only ever seen the movie Mulan and your partner wants show you Moulin Rouge. It would be jarring to just watch the movie, so your partner might gently build to Moulin Rouge by showing you movies similar to both Mulan and Moulin Rouge. We compute stable paths that identify such feasible gentle sequence.
We use the MovieLens-20m data set (Harper & Konstan 2016). This data set is comprised of 20 million ratings by 138,493 users of 27, 27,278 movies. Often, these types of data sets are interpreted as bipartite graphs. Once we realize that a bipartite graph can be equivalently represented as a covering of one node set with the other, we can apply the cover filtration to build filtration. In our case, we interpret each movie as a cover element of the users who have rated the movie. To ensure the entire computation runs efficiently on a laptop, and to avoid noise, we remove all movies with less than 10 ratings and then sample 4000 movies at random from the remaining movies.
Figure 7 shows the computed Pareto frontier of stable paths for the case of Mulan and Moulin Rouge. In Table [ we show stable paths that might be chosen. The stable path with length 4 is found after a large drop in insta- bility. As the length and stability must be traded off, we think this would be a decent path choose if you want to optimize both. The second path shown is the most stable. For readers who have seen the movies in this path, the re- lationship between each edge is clear, even one might consider the path bit the longer side.
Pareto frontier
0.9
Nonoptimal Optimal paths
Instabiiity of path
0.85
084
083
Length path
Figure 7: Pareto frontier of stable paths between Mulan and Moulin Rouge.
16

---

Under review as a conference paper at ICLR 2020
Table 1: Two sequences of movie transitions.
Shortest Path
Most Stable Path
1. Mulan (1998)
1. Mulan (1998)
2. Dumbo (1941)
2. Robin Hood (1973)
3. Sound of Music, The (1965)
3. Dumbo (1941)
4. Moulin Rouge (2001)
4. Sound of Music, The (1965)
5. Gone with the Wind (1939)
6. Psycho (1960)
7. High Fidelity (2000)
8. Moulin Rouge (2001)
C.2 STEINHAUS MAPPER FILTRATION
As supervised learning has become powerful, the need for explanations is also grown. We develop method of model induction for inspecting a machine learning model. The goal to develop understanding of the model structure by characterizing the relationship between the feature space and the prediction space. The gleaned understanding can help non-experts make sense of algorithmic decisions and essential when models are too complex to fully understand in white-box fashion. The Mapper (Singh et al. 2007) is aptly suited for visualizing this functional structure.
Anide boot
Bag
Coat
Dress
Pullover
Sandal
Shirt
Sheaker
T-shirthtp
Trouser
Figure 8: Constructed Mapper from logistic regression model of Fashion-MNIST data set. The window marks the frame of Figure
17

---

Under review as a conference paper at ICLR 2020
This application is based the work of using paths in the Mapper to provide explanations for supervised machine learning models (Saul & Arendt 2018). We build a Mapper from the predicted probability space of logistic regression model. We then extend the constructed Mapper be Steinhaus Mapper Filtration and proceed to analyze the stable paths in that object.
Given topological spaces X,Y, Y, a function f: X - Y, and cover of Y, define Mapper to be the nerve of the refined pullback cover of f(Y). A refined cover is one such that each cover element split into its path-connected components.
Definition C.I (Steinhaus Mapper filtration). Given data X, function / X - Y, and cover U of Y. we define the Steinhaus Mapper the Steinhaus nerve (Definition 2.4) of the refined pullback cover of f(U):
Nrv
By incorporating information about the amount of overlap between the cover produced by the Map- per, our analysis is robust to noise and largely insensitive to the chosen parameters of the Mapper construction.
9.999
0.0.88
10/0.
11/20.921
21.06.67
12/0..0
Figure Depiction of stable paths found along Pareto frontier in Figure 10
Figure 8 shows the Steinhaus Mapper filtration constructed from logistic regression model built data set (Xiao et al.] 2017). This data set consists of 70,000 images of clothing items from 10 classes. Each image Is 28 pixels. It is widely regarded as a more difficult drop-in replacement for the ubiquitous MNIST handwritten digits data set.
from the Fashion-M
The dimensionality of the data set first reduced to 100 di- mensions using Principal Com- ponents Analysis, and then a logistic regression classi- fier with I regularization is trained on the reduced data us-
0.98
Parek: fronde Nonoplina
C3M
Inoabbitt of peet
C.22
2.00
ing 5-fold cross validation on
training set of 60,000 im-
6.85
ages. The model is evaluated
at 93% accuracy on the re- maining 10,000 images. We then extract the 10-dimensional predicted probability space and use UMAP (McInnes & Healy] 2018 MeInnes al., (2018) to reduce the space to 2 dimen-
0.06
0.44
12
19
16
18
17
18
28
Longth
Figure 10: Pareto frontier of stable paths between predominately sneaker vertex and predominately ankle boot vertex.
sions. This 2-dimensional space is taken as the filter function of the Mapper, using a cover consisting of 40 bins along each dimension with 50% overlap between each bin. We explored ranges of values for the number of bins (10-50) and the overlap percentage 20-60%), and observed variabilities in the constructed Mappers. The final choice of parameters (40 bins, 50% overlap) were chosen as the Mappers showed least variability over subsets of values centered at these parameter values. DB- SCAN is used as the clustering algorithm in the refinement step (Ester et al. 1996). KeplerMapper is used for constructing the Mapper (van Veen & Saul, 2017). Finally, the cover is extracted and the Steinhaus Mapper filtration is constructed.
To illustrate the power of the path explanations, we start with two vertices selected from the sneaker and ankle boot regions of the resulting graph. The three regions of shoes (sneaker, ankle boot, and sandals) are understandably confusing to the machine learning model, and we are interested in where these confusions arise. Figure shows the paths associated with the Pareto frontier (Figure TO
18

---

Under review as a conference paper at ICLR 2020
Ankle boot
Sneaker
Sandal
X'0
x
id: 627
152
x
x
id: 627
id: 5899
149
x
725
id: 2875
415
Ankle boot
Sneaker
Sandal
x 7
257
id: 5858
415
x 38 id: 627
id: 180
732
id: 32368
x
11 5000
91
x 48
1452
id: 916
id: 6170
id: 358
x 26
243
7
28
id: 902
id: 916
id: 1514
id: 301
2007
x 7
L 10
175
10
74
id: 4895
id: 2463
id: 2412
id: 301
id: 2007
1234
5
82
6
id:
id: 407
id: 442
8668
id: 367
id: 14156
id: 29421
213
id: 2492
28
8668
Id: 96
237
20090
2
id: 56
id: 5597
id: 96
335
id: 6222
Id. 32488
id: 190
383
id:
Id: 32488
id: 190
383
Figure 11: Path visualizations for shortest path (left) and stable path with length (right). Columns in the visualization are based on the class and each row represents node in the Mapper. We show one representative for each node each column. Columns with no shoes shown no representative of that class in the node.
19

---

Under review as a conference paper at ICLR 2020
show the Pareto frontier between the two chosen vertices. This frontier shows large decrease in instability value (thus increase stability) when moving to a path length of 12. As noted in Section [ paths found after large increase in stability correspond to highly stable paths, i.e, the path remains the shortest path while sweeping the instability value over a comparatively large range.
In Figure 10
Figure shows representatives from each vertex the path for the shortest path and the stable path with length 12. Each row corresponds one vertex and the columns show representative from each class represented in the vertex. Each image shows the multiplicity of that type of shoe in the vertex.
In both paths, the vertices start predominately containing sneakers and sneaker-like sandals. They then transition to containing a larger proportion of ankle boots, with all three classes showing higher cut tops or high heels.
Along each path we can see the relationships between nodes change. the most stable path on the right, we a slow transition from sneaker space to ankle boot space, with some amount of sandals spread throughout. Through the path, shoes from each of the three classes become taller. Near the middle of the path, the images from sneakers and ankle boots are nearly indistinguishable. And earlier in the path, we see how some white strips the sneakers and boots might easily confused with negative space in the sandals.
These two paths provide holistic representation how the trained logistic model interprets the data. By exploring these paths, we gain valuable insight into why model is making decision. This can help either reinforce our trust the model or reject the prediction. In either outcome, these explanations can strengthen the results of the predictions by including humans in the loop. Even though the case of predicting clothing types is a low stakes application, this framework is readily applicable to much more important data sets.
D NOTE ON COMPLEXITY OF COVER FILTRATIONS
The complexity of constructing the cover filtration is by and large inherited directly from the com- putational complexity of the nerve. Given cover U, the nerve could have most 2 - simplices and dimension at most [ - Otter et al. (2017). These bounds are equivalent to the corresponding worst case bounds for VR and Cech complexes.
The work involved for each simplex in constructing Nrvs: includes computing the volume of inter- section and volume of union the elements in the simplex. The complexity union and intersec- tion operations is largely dependent the type of data being used. Let (V)))) and Ein (V) be the costs of computing the union and intersection, respectively, of a set of cover elements V C U. In the worst case, we have do Eunn (2)) + (in((1) operations per simplex, leading an overall worst case computational complexity of (LEun (24) + inm (2 1). For instance, if we assume that a hashing-bass based dictionary could be produced for each set in U, both Gunn and Ei (V) will be most linear in |/] Bille et al. (2007).
20


Reviews:
[{"review_id": "SylLQHX9tH", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "1. Paper summary\n\nThis paper develops a novel filtration for the analysis of based on the\nidea of *covers* of data sets. The filtration employs the notion of\na generalised Jaccard distance to define stable paths within the nerve\nof the cover. These stable paths are then shown to be useful for the\ncreation of 'gentler' transitions for recommendation systems, as well\nas the development of explainable supervised machine learning models.\n\n2. Review summary\n\nI found this paper to be very interesting in terms of its new\nperspective on filtrations and its idea of the introducing a\n'stability' concept inspired by topological persistence.\nHowever, I recommend rejecting the paper in its current form due to the\nfollowing issues:\n\nA. Missing clarity: the paper requires readers to be familiar with the\n   Mapper algorithm and glosses over important details. Several results\n   that are mentioned as core contributions in the main texts are only\n   stated in the supplementary materials.\n\nB. Missing experimental depth: the experiments shown in the paper are\n   interesting, but only scratch the surface. To have a convincing case\n   study, a more quantitative analysis is required. At present, the\n   selection and depiction of results seems ad-hoc. I realise that,\n   when the foremost goal is interpretability, providing a quantitative\n   analysis is not always easily possible. Nevertheless, each data set\n   should be used for more than one case study; ideally, multiple\n   results that are 'surprising' can be reported. For example, are\n   there paths that do not match our intuition? What do they tell us\n   about the data set?\n\nC. Doubts about the technical correctness: the supervised learning\n   example requires an elaborate setup (dimensionality reduction,\n   UMAP for further reductions, setting up Mapper with additional\n   parameters). I am wondering how trustworthy any result obtained\n   from such an analysis can be. I would suggest discussing the\n   parameter selection process in more detail and ideally providing more\n   information about the impact of these choices.\n\nIn the following, I will comment on these issues in more detail.\n\n3. Clarity\n\n- Concepts such as 'cover' should be briefly introduced; already the\n  abstract presumes that readers are familiar with several TDA concepts\n\n- I would shorten the abstract to improve its flow; the paragraphs 'We\n  demonstrate...' and 'For explainable...' could also be added to the\n  introduction to improve the exposition of the paper.\n\n- The introduction already starts with TDA concepts; a brief motivation\n  would make the paper more accessible\n\n- I disagree with the statement that the existence of a metric on the\n  data is an implicit assumption of TDA. My perspective is quite the\n  opposite: TDA is rather flexible *because* of its support for\n  different metrics; Vietoris--Rips complex calculation, for example,\n  only requires a matrix of pairwise distances. Hence, I would rewrite this\n  sentence.\n\n- To add to the previous point: the paper itself introduces a new\n  metric based on a generalised Jaccard distance. I feel that the\n  discussion of 'ill-fit or incomplete' metrics detracts from the\n  main message of the paper.\n\n- The first explanation/definition of Mapper in the introduction is\n  rather complicated ('nerve of a refined pullback cover'); I would\n  suggest rephrasing this.\n\n- The point about the $1$-skeleton warrants more explanation: it is my\n  understanding that the paper uses paths that are defined using this\n  skeleton as well. My first pass of the paper slightly confused me\n  because I figured that the described paths would be generalised over\n  high-dimensional simplices as well. I would suggest making this\n  'restriction' (it is not a proper restriction because paths can be\n  defined for arbitrary simplices, but it is a restriction in terms of\n  the dimensionality) or property clear from the beginning.\n\n- The discussion of hypercube covers is repeated multiple times in the\n  introduction and the related work section; I would suggest mentioning\n  this only once as it does not have to a large bearing on the methods\n  described in the paper anyway.\n\n- Discussing stability of the paths/cover in the introduction is\n  misleading because these aspects are only discussed in the appendix.\n  Same goes for some of the contributions in Section 1.1; the\n  conjectures or connection to other filtrations are only mentioned in\n  the appendix.\n\n  This needs to be rewritten; I would pick a few contributions that the\n  main text can focus on and mention the rest in passing.\n\n  The paper lacks this structure at present and for a conference\n  submission, all main contributions should also be a part of the main\n  text.\n\n- Stability is meant to reflect a property of a cover; this could be\n  clarified by means of extending Figure 1, for example. During my\n  first pass of the paper, some of the subsequent definitions were\n  lacking a clear motivation. I would suggest to _clearly_ state that\n  the goal is to circumvent issues with paths in a cover that only\n  depend on a few data points.\n\n- Moreover, it would be interesting to point out to what extent the\n  method presented here is the _only_ one capable of doing this. It\n  occurred to me that there's a preprint that discusses how to stabilise\n  the calculations of persistent homology (with respect to picking the\n  _same_ creator simplex for a feature, for example):\n\n    Bendich, Paul et al.\n    Stabilizing the unstable output of persistent homology computations\n    https://arxiv.org/abs/1512.01700\n\n  It seems that one of the unique features of the method in this paper\n  is that the definition of path stability aligns exactly with the other\n  stability concept---the paths are thus indeed stable with respect to\n  perturbations of the underlying data set.\n\n  Maybe this could be mentioned as an interesting feature.\n\n- The paragraph 'In Section 4.1 [...]' in the related work section is\n  somewhat redundant; I would suggest putting it at the beginning of the\n  respective experimental section and merging it with the existing\n  description there.\n\n- The definition of the Steinhaus distance strikes me as unnecessary\n  complex; while it is mathematically pleasing to know that arbitrary\n  measures could be used, it seems that this is never exploited anywhere\n  in the paper.\n\n- In the interest of clarity, maybe it would make sense to refer to the\n  distance as a 'generalised Jaccard distance' instead.\n\n- The proof of Theorem 2.5 could be moved to the appendix. Moreover,\n  I think it could be simplified by mentioning that the nerve is\n  constructed from the cover and that weights are assigned based on\n  the number of intersections; then the main result would follow from\n  monotonicity. (the current proof is of course fully correct, I just\n  had to rephrase this result in terms of concepts that I found easier\n  to grasp)\n\n- Concerning the terminology, I find 'a most stable path' to be somewhat\n  confusing at the first read. I now understand what is meant by it, but\n  maybe 'highly stable' or 'maximally stable' would be better.\n\n- In Section 3, the 1-skeleton should be explicitly mentioned.\n\n- Moreover, the notion of 'shortest path', which _could_ also employ\n  distances, should be distinguished from stable paths; if I understand\n  the argumentation correctly, shortest paths are defined in terms of\n  the number of edges, while stable paths are defined in terms of the\n  weights along those edges. I would suggest spelling this out directly\n  to make the concepts non-ambiguous.\n\n- In Definition 3.1, it should be $d_{St}$, not $D_{St}$, I think.\n\n- Definition 3.1 could also be intuitively summarised as 'the largest\n  edge weight along a path', right?\n\n- The algorithm in Figure 2 should include some comments that make the\n  procedure  more understandable. I found the conceptual leap to Pareto\n  frontiers confusing at first; maybe this could be motivated better.\n\n- Figure 3 needs more explanations. In particular the connection to\n  persistence could be elucidated---I get that there's an immediate\n  connection (see the paper above) but this concept needs at least\n  a brief introduction. Moreover, if this connection is relevant, it\n  deserves to be elucidated in the paper explicitly.\n\n- Figure 4 needs additional labels; I expect that 'distance/stability'\n  are shown in the caption. Is this correct?\n\n  In general, I found the path visualisation not so helpful; maybe it\n  would be better to show the full 1-skeleton (or an excerpt) and\n  highlight the corresponding paths?\n\n- The language and motivation in Section 4 is somewhat informal; this is\n  not an issue for me, but I wanted to mention it as a something that\n  could potentially be rephrased.\n\n- The additional application domains should be moved from Section 4 to\n  a discussion section.\n\n- The cover generation strategy could be understood more rapidly if\n  a small illustration was provided. Do I get it correctly that every\n  *cover set* constitutes a film, while the overlap between them is\n  based on whether the same user also rated another film?\n\n- The path selection procedure for the experiment in Section 4.1 needs\n  to be explained formally. I get that it is akin to selecting a point\n  on the 'elbow' of a curve, but this should be briefly explained.\n\n- Figure 5 needs to be referenced more prominently in the text.\n\n- Section 4.2 is glossing over many important details of the definition\n  of Mapper. These are absolutely required, though, and any parameters\n  selected here should also be analysed to learn whether they affect the\n  results.\n\n- I am not sure about the utility of the paths in Figure 7\n\n- Figure 9 needs more explanations; as mentioned below, why not compare\n  this path with a geometry-based path in the embedding? Moreover, why\n  are there not the same number of images for all classes?\n\n- The conclusion needs to be rewritten; the paper does *not* show\n  stability properties in the main text\n\n4. Experiments\n\n- As a general question, I would like to see how stable the\n  interpretations of the different sections are. There is always\n  a degree of stochasticity when training a neural network, so does\n  the output of Mapper stay stable?\n\n- I am not sure about the relevance of experiment in Section 4.1; it\n  does not really provide a link to an explainable model for me, but\n  instead is more along the lines of 'gentle interpolation in a latent\n  space'. I could see that this has its uses, but an evaluation requires\n  more than one example. I would be particularly interested in knowing\n  about cases in which result is unexpected. Do such cases exist?\n\n- Please comment on the stability of the sampling procedure in Section 4.1\n\n- I understand that Section 4.2 wants to show how algorithms like Mapper can\n  act as a middle ground between black-box and white-box models. Is this\n  correct? If so, the chosen example is _not_ sufficiently complex to be\n  compelling. Would it not be equally appropriate to rewrite this\n  experiment in terms of explaining paths in the latent space of\n  autoencoders? In this context, I see more of a need for these paths as\n  an alternative to paths that purely employ latent space geometry.\n\n- Adding to this, the autoencoder context would it also make possible to\n  compare paths generated using Mapper and the proposed as well as the\n  paths generated by the model. Such an experiment would be more\n  compelling, I think.\n\n- In general, what are the implications of understanding a path as in\n  Figure 9? How could the model updated to account for this? If the\n  paper were to include an example of how to *fix* a model based on such\n  information, it would a highly compelling use case.\n\n- Moreover, would it be possible to detect 'problematic' regions such as\n  the one shown in Figure 9 automatically? If so, it would again provide\n  a highly compelling example. Otherwise, I think that the\n  interpretation of a model depends again on humans and are thus\n  restricted based on model complexity.\n\n5. Minor style issues\n\n- Mapper should be capitalised consistently\n- I suggest removing the paragraph 'Organization' as it is redundant\n- 'mod differences' --> 'modulo differences' (?)\n- 'distanceof' --> distance of'\n- 'on undirected graph' --> 'on an undirected graph'\n- 'Principle component analysis' --> 'Principal component analysis'", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I carefully checked the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Skl0rFWi9B", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper presents an interesting filtration method to find staple maps, which proves effective in the recommendation system and explainable machine learning. The new framework is built upon a new concept termed cover filtration based on the generalized Steinhaus distance derived from Jaccard distance. A staple path discovery mechanism is then developed using this filtration based on persistent homology. Experiments on Movielense and FashionMNIST has quantitatively and qualitatively demonstrated the effectiveness of the new model. It also showcases the explainable factors with visualized samples from FashionMNIST dataset. In addition, theoretical discussion in the appendix makes the theory part of this work solid and convincing.\n\n* The method introduced in this paper is intuitive and demonstrates with meaningful outcomes.\n\n* The method itself is built upon the SOTA method “Mapper”. Authors may want to clearly state the difference between the new method and Mapper in writing.\n\n* The overall structure of this paper needs some improvement. Authors attempt to introduce a new distance metric as an intermediate level representation. This is not very clear at the beginning; instead, most of the introduction is related to TDA and mapper, which may confuse people not from this particular field.\n\n* What is the meaning of D_St under definition 3.1? Is this the same as d_St or not?\n\n* It seems the restrictions in the experiments are strong, which can be found from a few settings in the experiments. For example, the authors claim that “To reduce computational expenses and noise, we remove all movies with less than 10 ratings and then sample 4000 movies at random from the remaining movies.” It seems the model may not work well in a more general case...\n\n* The pre-processing steps for filtration cover seem verbose on FashionMNIST “The model is evaluated at 93% accuracy on the remaining 10,000 images. We then extract the 10-dimensional predicted probability space and use UMAP (McInnes & Healy, 2018) to reduce the space to 2 dimensions. This 2-dimensional space is taken as the filter function of the Mapper, using a cover consisting of 40 bins along each dimension with 50% overlap between each bin.” Not sure if this method will work well without fine-tuning or feature selection like this.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper proposes a filtration based on the covers of data sets and demonstrates its effectiveness in recommendation systems and explainable machine learning. The paper is theory focused, and the discussion was mainly centered around one very detailed and thorough review. The main concerns raised in the reviews and reiterated at the end of the rebuttal cycle was lack of clarity, relatively incremental contribution, and limited experimental evaluation. Due to my limited knowledge of this particular field, I base my recommendation mostly on R1's assessment and recommend rejecting this submission.
Decision: Reject