# «Bei Wang School of Computing Scientiﬁc Computing and Imaging Institute (SCI) University of Utah May 18, 2016 Joint work with Liz Munch (University ...»

Category Representations and Convergence

Reeb Space and Mapper

Bei Wang

School of Computing

Scientiﬁc Computing and Imaging Institute (SCI)

University of Utah

May 18, 2016

Joint work with Liz Munch (University at Albany - SUNY)

Motivation

Multivariate data and atmospheric science

Multivariate: data points with vector values

Domain applications: weather ensembles from atmospheric science

with large societal impacts, windstorms, smoke transport from

wildﬁres, winter season precipitation, and hurricane forecasting Explore multivariate topological data analysis tools Multivariate analysis and vis: Jacobi sets, Reeb spaces and mapper Study relations among level sets and critical pts of multiple functions [Bhatia, Wang, Norgard, Pascucci, Bremer (CGTA) 2015] [Munch, Wang (FWCG) 2015] [Munch, Wang (SoCG) 2016] Reeb space Generalization of Reeb graph Compresses the contours of a multivariate mapping and obtains a summary representation of their relationships Fundamental to the study of multivariate scientiﬁc data Multivariate analysis within in an end-to-end view Multivariate analysis within in an end-to-end view High-Level Question Original Reeb graph construction Original Reeb graph construction Mapper Image: Nicolau Levine Carlsson 2011 Mapper Image: Nicolau, Levine, Carlsson, PNAS 2011 Joint Contour Net Image: Duke, Carr, 2013 Intuition Mapper is an approximation of the Reeb space.

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Goal Develop some theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis.

Intuition Mapper is an approximation of the Reeb space.

Question How do we formalize this?

Goal Develop some theoretical understanding of the relationship between the Reeb space and its discrete approximations to support its use in practical data analysis.

Result Prove the convergence between the Reeb space and mapper in terms of an interleaving distance between their categorical representations (Partially) address some open questions [Carri´re, Oudot, 2016]: is it possible to describe the mapper as a e particular constructible cosheaf? Yes, d = 1; hopefully d 1.

[Dey, M´moli, and Wang]: does the mapper construction converges e to the Reeb space in the limit? Yes, in the categorical representations; hopefully geometrically on the space level.

Sheaves make baby cry.

During a talk given by: Amit Patel Baby: Stanley Michael Phillips Quote contributed to (possibly): Dmitriy Morozov SIAM Conference on Applied Algebraic Geometry, August 2, 2013 Category Theory Basics Category and opposite category Data of a category: the objects and the arrows A “generalization” of set theory: set and relationships between elements of a set Arrows: morphisms between the objects Arrows can be composed associatively; identity arrow for each object Intuitively, a big (probably inﬁnite) directed multi-graph with extra underlying structures: objects – nodes, each possible arrow between the nodes – directed edge Examples of categories Top: the category of topological spaces with continuous functions between them Set: the category of sets with set maps Open(Rd ): the category of open sets in Rd with inclusion maps Vect: the category of vector spaces with linear maps R: the category of real numbers with inequalities connecting them Cell(K): the category induced by any simplicial complex K, where the objects are the simplices of K, and there is a arrow σ → τ if σ is a face of τ Poset category A category P in which any pair of elements x, y ∈ P has at most one arrow x → y.

Open(Rd ): exactly one arrow I → J between open sets if I ⊆ J R: exactly one arrow a → b between real numbers if a ≤ b Intuitively, a poset category can be thought of as a directed graph which is not a multigraph Opposite category The opposite category C op of a given category C is formed by interchanging the source and target of each arrow Functor A functor is a map between categories that maps objects to objects and arrows to arrows Functor F : C → D maps an object x in C to an object F (x) in D, and maps an arrow f : x → y of C to an arrow F [f ] : F (x) → F (y) of D in a way that respects the identity and composition laws Intuitively, a functor is a map between graphs which sends nodes (objects) to nodes and edges (arrows) to edges in a way that is compatible with the structure of the graphs Examples of functors Hp : Top → Vect, sends a topological space X to its p-th singular homology group Hp (X), and sends any continuous map f : X → Y to the linear map between homology groups, Hp [f ] := f∗ : Hp (X) → Hp (Y) π0 : Top → Set, sends a topological space X to a set π0 (X) where each element represents a path connected component of X, and sends a map f : X → Y to a set map π0 [f ] := f∗ : π0 (X) → π0 (Y) Natural Transformation A natural transformation ϕ : F ⇒ G between functors F, G : C → D is a family of arrows ϕ in D such that (a) for each object x of C, we have ϕx : F (x) → G(x), an arrow of D; and (b) for any arrow f : x → y in C, G[f ] ◦ ϕx = ϕy ◦ F [f ] Any collection of functors F : C → D can be turned into a category, with the functors themselves as objects and the natural transformations as arrows, notated as DC Our case: D = Set Colimit The cocone (N, ψ) of a functor F : C → D is an object N of D along with a family of ψ of arrows ψx : F (x) → N for every object x of C, such that for every arrow f : x → y in C, we have ψy ◦ F [f ] = ϕx A cocone (N, ψ) factors through another cocone (L, ϕ) if there exists an arrow u : L → N such that u ◦ ϕx = ψx for every x in C The colimit of F : C → D, denoted as colim F, is a cocone (L, ϕ) of F such that for any other cocone (N, ψ) of F, there exists a unique arrow u : L → N such that (N, ψ) factors through (L, ϕ).

Topological Notions Reeb space

The Point The Reeb space of a (nice enough) Image: [de Silva, Munch, Patel, 2015] (X, f ) is a stratiﬁed space.

[Edelsbrunner, Harer, Patel 2008] A Reeb space comes with a space and a function Data Data (X, f ) A compact topological space X with a function f : X → Rd

Mapper M (U, f ) Given f : X → Rd Fix a good cover U = {Uα } of Rd f ∗ (U): the cover of X obtained by considering the path connected components of {f −1 (Uα )} Mapper is the nerve of this cover M (U, f ) := Nrv(f ∗ (U)) [Singh, M´moli, Carlsson 2007] e A Road Map Connecting categorical representations Measures the amount the above diagram deviates from being commutative.

Results Overview Convergence result Theorem Given a multivariate function f : X → Rd deﬁned on a compact topological space, the data is represented as an object (X, f ) in Rd -Top. Let U = {Uα }α∈A be a good cover of f (X) ⊆ Rd, K be the nerve of the cover and res(U) be the resolution of the cover, res(U) = sup{diam(Uα ) | Uα ∈ U}. Then

Convergence between continuous Reeb Space and discrete Mapper Distance between their categorical reps. requires only the knowledge of the cover Interleaving distance is an extended pseudometric.

Geometric convergence (d = 1) Corollary Given a constructible R-space (X, f ) with f : X → R, let U = {Uα }α∈A be a good cover of f (X) ⊆ R, and let K be the nerve of the cover. Then

In particular, a sequence of mappers for increasingly reﬁned covers converges to the Reeb graph.

Interleaving distance is an extended metric when d = 1 [de Silva, Munch, Patel, 2015].

d = 1: convergence geometrically (i.e. on the space level).

Categorical Notions Data Data is stored in the category Rd -Top Object: Rd -space, a pair consisting of a topological space X with a continuous map f : X → Rd, (X, f ) Arrow: ν : (X, f ) → (Y, g), a function-preserving map, i.e., a continuous map on the underlying spaces ν : X → Y such that g ◦ ν(x) = f (x) for all x ∈ X Examples: PL functions on simplicial complexes or Morse functions on manifolds are objects in Rd -Top Function preserving maps

Interleaving Distance Perturb each Reeb graph/Reeb space by ε (Smoothing) Determine if there is an almost isomorphism (ε-interleaving) Interleaving between categorical Reeb spaces Deﬁnition (Interleaving distance between Categorical Reeb spaces) An ε-interleaving between functors F, G : Open(Rd ) → Set is a pair of natural transformations, ϕ : F ⇒ Sε (G) and ψ : G ⇒ Sε (F) such that the diagrams below commute.

Interleaving between categorical Reeb spaces Deﬁnition Given two functors F, G : Open(Rd ) → Set, the interleaving distance is deﬁned to be dI (F, G) = inf{ε ∈ R≥0 | F, G are ε-interleaved} Interleaving between categorical Reeb spaces Deﬁnition Given two functors F, G : Open(Rd ) → Set, the interleaving distance is deﬁned to be

Idea The interleaving is a metric on Reeb spaces which takes into account both the space and the function Categorical Mapper: data over nerve of cover

Mapper doesn’t have an obvious Rd function.

Mapper and Reeb are not represented in the same category.

Compare Reeb space and mapper

PK (F )(I) = colimσ∈KI F (σ) for every I in Open(Rd ) Colimit: “gluing”, push discrete entities to continuous entities Lemma Let F : Open(Rd ) → Set be a functor which maps an open set I, to a set π0 f −1 ( σ∈KI Uσ ) with morphisms induced by π0 on the inclusions. Then, the functor PK CK (X, f ) is equivalent to F.

Convergence result revisited Theorem Given a multivariate function f : X → Rd deﬁned on a compact topological space, the data is represented as an object (X, f ) in Rd -Top. Let U = {Uα }α∈A be a good cover of f (X) ⊆ Rd, K be the nerve of the cover and res(U) be the resolution of the cover, res(U) = sup{diam(Uα ) | Uα ∈ U}. Then

If we have a sequence of covers Ui such that res(Ui ) → 0, then the categorical representations of the mapper converge to the Reeb space in the interleaving distance Connecting categorical rep. with geometric rep. (d = 1) Deﬁne a mapping that recovers the geometric rep. of mapper from its categorical rep.

Convergence between mapper and Reeb graph geometrically (on the space level).

Highlight Constructing the (geometric) Reeb graph from well behaved data is the same as creating its categorical representation, and then turning it back into a geometric object.

Well behaved data Requiring the data to be constructible R-spaces [de Silva, Munch, Patel, 2015], [Patel, Curry, 2016] R-Topc : full subcategory of R-Top, objects are constructible R-spaces Reeb: full subcategory of R-Topc, category of (geometric) Reeb graphs The construction of a (geometric) Reeb graph from well behaved data (a constructible R-space) is captured by the functor R : R-Topc → Reeb.

Well behaved data Further restrict our objects of interest in SetOpen(R) to be well behaved A cosheaf is a functor F : Open(R) → Set such that for any open cover U of a set U, the unique map colimUα ∈U F (Uα ) → F (U ) is an isomorphism.

A cosheaf is constructible if there is a ﬁnite set S ⊂ R such that if A, B ∈ Open(R) with A ⊆ B and S ∩ A = S ∩ B, then F (A) → F (B) is an isomorphism. In addition, we require that if A ∩ S = ∅ then F (A) = ∅.

The category of constructible cosheaves with natural transformations is denoted Cshc.

Equivalence of categories [de Silva, Munch, Patel, 2015] Reeb ≡ Cshc C has an “inverse” functor D : Cshc → Reeb which can turn a constructible cosheaf back into a geometric object Commutativity of the upper right triangle: R = DC Our geometric result

Corollary Given a constructible R-space (X, f ) with f : X → R, let U = {Uα }α∈A be a good cover of f (X) ⊆ R, and let K be the nerve of the cover. Then

Glue a collection of disjoint edges along equivalent vertices deﬁned by the cover Summary [Carri´re, Oudot, 2016]: is it possible to describe the mapper as a e particular constructible cosheaf? Yes, d = 1 with our geometric results: we described the mapper as a constructible cosheaf when it is passed to the continuous version.

Suspect that our geometric results may hold in the case d 1.

**Require proper notion of constructibility for Rd -spaces and cosheaves:**

want an equivalence of categories, and a proof that the interleaving distance is an extended metric, not just a pseudometric; and therefore the mapper converges to the Reeb space on the space level.

Algorithm strategy for building the associated geometric mapper may be generalized by considering k-dimensional cover elements and their intersections.

First steps towards providing a theoretical justiﬁcation for the use of discrete objects (mapper and JCN) as approximations to the Reeb space with guarantees.

On-going/future directions Categorical interpretations of Jacobi sets and their distances Categorical interpretations of multiscale mapper Geometric graphs Take home message Category theory provides a simple, beautiful language that could potentially give us cleaner interpretation of some commonly used TDA constructs Simple language for convergence proofs that connect discrete with continuous entities (hard to prove otherwise) New interpretations for studying topological structures, and for multivariate data analysis Thank you!

Liz Munch Vin de Silva, Justin Curry, Amit Patel, Robert Ghrist...

All the TDA researchers who make category theory less scary arXiv:1512.04108, SoCG 2016 NSF-IIS-1513616