March 12 (Saturday), 2022
Algebraic Combinatorics and Category Theory in Topological Data Analysis
Topological Data Analysis (TDA) -- an emerging field at the intersection of Mathematics, Statistics and Computer Science -- deploys ideas from topology and geometry for identifying and quantifying the structure of complex data. Recently, algebraic combinatorics and category theory are playing an increasingly important role in the foundations of TDA. Instances of this include the overcoming of algebraic challenges in the development of multiparameter persistent homology and the study of broader types of data. In this workshop, we bring together researchers interested in these topics to share recent advances and discuss open questions.
Organizers: Woojin Kim, Alex McCleary, Facundo Mémoli, Amit Patel
Tamal Dey (Purdue)
Parker Edwards (Notre Dame)
Alex Elchesen (U of Florida)
Robert Ghrist (U of Pennsylvania)
Woojin Kim (Duke)
Sanjeevi Krishnan (Ohio State)
Alex McCleary (Ohio State)
Samantha Moore (U of North Carolina at Chapel Hill)
Amit Patel (Colorado State)
Tatum Rask (Colorado State)
Hans Riess (U of Pennsylvania)
Anna Schenfisch (Montana State)
Luis Scoccola (Northeastern)
Bei Wang (U of Utah)
Schedule (March 12, Saturday)
8:55 AM Opening remarks
Chair: Facundo Mémoli
9:00 AM Amit Patel Persistence Diagrams as Möbius Inversions Video
9:30 AM Alex McCleary Diagrams of Persistence Modules Over Finite Posets Video
10:00 AM Woojin Kim Extracting Persistent Clusters in Dynamic Data via Möbius inversion Video
10:30 AM Bei Wang Hypergraph Co-Optimal Transport: Metric and Categorical Properties Video
11-11:20 AM Break (20 mins)
Chair: Amit Patel
11:20 AM Sanjeevi Krishnan Invertibility in Category Representations
11:50 AM Samantha Moore The Generalized Persistence Diagram Encodes the Bigraded Betti Numbers Video
12:20 PM Tamal Dey Computing Generalized Rank Invariant for 2-parameter Persistence Modules via Zigzag Persistence Video
12:50- 14:00 PM Lunch Break (70 mins)
Chair: Woojin Kim
14:00 PM Robert Ghrist The Tarski Laplacian
14:30 PM Hans Riess Lattice Theory in Multi-Agent Systems
15:00 PM Alex Elchesen Relative Optimal Transport Video
15:30 PM Parker Edwards Graded Persistence Diagrams and Stability Video
16:00-16:20 PM Break (20 mins)
Chair: Alex McCleary
16:20 PM Tatum Rask Towards Characteristic Classes for Persistence Diagram Bundles Video
16:50 PM Anna Schenfisch Posets of Topological Descriptors Video
17:20 PM Luis Scoccola Bottleneck stability of multigraded Betti numbers and Hilbert functions
17:50 ET (15:50 MT) Closing remarks
Title Computing Generalized Rank Invariant for 2-parameter Persistence Modules via Zigzag Persistence
Abstract The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently.
We show that the generalized rank over a finite interval I of a Z^2-indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If I has t points, this computation takes O(t^\omega) time where \omega\in[2,2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.
Title Graded Persistence Diagrams and Stability
Abstract In the combinatorial framework introduced to persistence theory by Patel, a persistence module's persistence diagram is the function obtained via Möbius inversion of the persistence module's rank function. For settings where persistence diagrams give non-negative values as output, recent results (e.g. on bottleneck stability by McCleary and Patel, amongst others) generalize the metric theory of persistence diagrams . When one relaxes the non-negativity assumption the story is less settled. In this talk, I will discuss a refinement of persistence diagrams, graded persistence diagrams, and a metric theory for them. Whereas persistence diagrams take non-negative values, graded persistence diagrams take values of 0, 1, or -1. There is a strong correspondence between a persistence module's graded persistence diagram and its persistence landscape. I will give some idea of how to exploit this correspondence, as the constraints it imposes are critical for proving stability results. Our theory focuses on an analog of the 1-Wasserstein distance. Other Wasserstein distances are not well-defined. In fact, the 1-Wasserstein distance between graded persistence diagrams is at most twice the 1-Wasserstein distance between corresponding persistence diagrams and is more discriminative.
Title Relative Optimal Transport
Abstract The Wasserstein distances between persistence diagrams are widely used for quantifying topological dissimilarity of filtered topological spaces. While these distances were inspired by and named for the classical Wasserstein distances between probability measures arising in optimal transport, only recently has the precise connection to the classical theory been studied. Expanding on recent work by Divol and Lacombe, I will describe a general theory of "relative" optimal transport.
The relative optimal transport problem asks, given two Radon measures \mu and \nu on a pointed metric space (X,d,x_0), what is the most efficient way to transport the mass of \mu to that of \nu, allowing mass to be transported to and from the basepoint x_0? The relative Wasserstein distance is the cost of the most efficient transport plan. This generalizes the classical optimal transport theory by allowing comparison of measures of different total mass. The Wasserstein distances between persistence diagrams are then examples of the relative Wasserstein distances. I will also discuss connections to linear functionals on spaces of Lipschitz functions and state a Riesz representation-type theorem relating such functionals to the relative Wasserstein distance.
Title The Tarski Laplacian
Abstract Lattice theory is a tool of great potential use in topological data analysis, machine learning, and more. Categories of lattices and lattice morphisms are not abelian, and this presents some challenges in using lattices as data categories for systems. This talk, representing joint work with Hans Riess, describes a novel operator -- the Tarski Laplacian -- which can be used to define a Hodge theory on cellular sheaves of lattices. The main results focus on the dynamics of diffusion on such sheaves. Applications range from distributed consensus algorithms to novel approaches to cohomology.
Title Extracting Persistent Clusters in Dynamic Data via Möbius inversion
Abstract Identifying and representing clusters in time-varying network data is of particular importance when studying collective behaviors emerging in nature, in mobile device networks or in social networks. Based on combinatorial, categorical, and persistence theoretic viewpoints, we establish a stable functorial pipeline for the summarization of the evolution of clusters in a time-varying network. We first construct a complete summary of the evolution of clusters in a given time-varying network over a set of entities X of which takes the form of a formigram. This formigram can be understood as a certain Reeb graph R which is labeled by subsets of X. By applying Möbius inversion to the formigram in two different manners, we obtain two dual notions of diagram: the maximal group diagram and the persistence clustergram, both of which are in the form of an `annotated' barcode. The maximal group diagram consists of time intervals annotated by their corresponding maximal groups -- a notion due to Buchin et al., implying that we recognize the notion of maximal groups as a special instance of generalized persistence diagram by Patel. On the other hand, the persistence clustergram is mostly obtained by annotating the intervals in the zigzag barcode of the Reeb graph R with certain merging/disbanding events in the given time-varying network. We show that both diagrams are complete invariants of formigrams (or equivalently of trajectory grouping structure by Buchin et al.) and thus contain more information than the Reeb graph R. Joint work with Facundo Mémoli; https://arxiv.org/abs/1712.04064
Title Invertibility in Category Representations (joint with Crichton Ogle)
Abstract This talk is about some joint work with Crichton Ogle on characterizing when a diagram of vector spaces extends to a diagram indexed by a small inverse category, a small category whose morphisms f are equipped with unique choices of generalized inverses g in the sense that fgf=f and gfg=g. Motivating examples of such extendable diagrams include diagrams of Hilbert spaces and partial isometries and multidimensional persistence diagrams that decompose into direct sums of diagrams whose non-zero morphisms are isomorphisms. Time-permitting, we describe how this extendability result is interpretable as a reduction of a structure semigroup in a nascent theory of principle S-bundles for inverse semigroups S [Hofstra], and some open questions on some subsequent characteristic classes for persistence diagrams.
Title Diagrams of Persistence Modules Over Finite Posets
Abstract We extend the construction of persistence diagrams over finite lattices from the setting of filtrations over finite lattices to persistence modules over finite posets. This is done by defining the birth-death function using free presentations of a persistence module. We relate the persistence diagrams obtained from the birth-death function and the rank function by introducing a new function: the kernel function. The diagrams obtained from the birth-death function and the kernel function differ only along the diagonal. The diagram of the rank function is related to that of the kernel function by a linear isomorphism.
Title The Generalized Persistence Diagram Encodes the Bigraded Betti Numbers
Abstract For finite 2-parameter persistence modules, we have proven that the generalized persistence diagram (introduced by Kim and Mémoli) encodes the bigraded Betti numbers. More interestingly, the bigraded Betti numbers can be visually read off from the generalized persistence diagram in a manner parallel to how the bigraded Betti numbers are extracted from interval decomposable modules. Our results imply that all of the invariants of 2-parameter persistence modules that are computed by the software RIVET are encoded in the generalized persistence diagram.
Title Persistence Diagrams as Möbius Inversions
Abstract The persistence diagram as a Möbius inversion is a relatively new discovery that has enabled the generalization of persistent homology to previously unthinkable settings. Although much progress has been made, there are plenty of open problems remaining. In this talk, I will describe what I feel are the top three or four open problems in this area.
Title Towards Characteristic Classes for Persistence Diagram Bundles
Abstract Given a fixed simplicial complex K, there is a functor PH_\ast : Fil(K) \to Dgm that takes a filtration of K indexed over any finite lattice to its generalized persistence diagram. With functoriality established, the next step is to study cellular cosheaves valued in Fil(K) to which we apply the functor PH_\ast, giving us a cellular cosheaf of generalized persistence diagrams. For example, the persistent homology transform is a cellular cosheaf of persistence diagrams. The goal is to extract interesting invariants from these cellular cosheaves. Since neither category is abelian, a theory of cosheaf homology is unlikely. However, there is an interesting classifying space associated to subcategories of both Fil(K) and Dgm suggesting that, if we think of these cosheaves as bundles, there is an interesting theory of characteristic classes. I will discuss ongoing preliminary work in this direction.
Title Lattice Theory in Multi-Agent Systems
Abstract As evidenced by the existence of this workshop, lattice theory has become increasingly relevant to the foundations of topological data analysis (TDA) (McCleary/Patel 2020, Ghrist/Henselman-Petrusek 2021). Meanwhile, sheaf Laplacians (Ghrist/Hansen, 2019), generalizing the graph Laplacian, a tried-and-true network diffusion operator, have gained popularity inside and outside the TDA community. We report efforts to understand multi-agent systems from a lattice-theoretic point of view. Our focus is the recently introduced Tarski Laplacian. We will survey the development of engineering applications ranging from synchronization of concurrent systems to multi-agent Kripke semantics, as well as suggest open problems.
Title Posets of Topological Descriptors
Abstract Given a general simplicial complex embedded in R^d, there exist finite sets of topological descriptors generated by lower-star filtrations in various directions that, together, faithfully represent the complex, a fact that is the foundation of many recent developments in shape comparison. We build a framework through which descriptor types---persistence diagrams, Euler characteristic curves, etc---can be ordered by their ability to represent shapes. Specifically, we use the size of faithful sets of parameterized descriptors to define this ordering. We then partially order six common descriptor types and discuss the benefits of viewing this work through the lens of constructible cosheaves over a stratified "sphere of directions." Throughout, we will pause to note research highlights as well as proposed work and conjectures.
Title Bottleneck Stability for multigraded Betti numbers and Hilbert functions
Abstract Unlike one-parameter persistence modules, for which we have the barcode, persistence modules with two or more parameters do not admit a complete discrete invariant, and thus incomplete invariants must be used to study the structure of such modules in practice. The Hilbert function and the multigraded Betti numbers are among the simplest such incomplete invariants, and, although these invariants are already being used in applications, it is a priori unclear whether they satisfy a stability result analogous to the stability of the one-parameter barcode. Stability results are essential for the interpretability and consistency of practical methods. I will present joint work with Steve Oudot in which we prove stability results for multigraded Betti numbers and for the Hilbert function. I will also discuss ongoing work in which we prove the stability of finer invariants coming from different exact structures on the category of representations of a poset.
Title Hypergraph Co-Optimal Transport: Metric and Categorical Properties
Abstract We develop a theoretical foundation in studying the space of hypergraphs using ingredients from optimal transport. By enriching a hypergraph with probability measures on its nodes and hyperedges, as well as relational information capturing local and global structure, we obtain a general and robust framework for studying the collection of all hypergraphs. We first introduce a hypergraph distance based on the co-optimal transport framework of Redko et al. and study its theoretical properties. We then formalize common methods for transforming a hypergraph into a graph as maps from the space of hypergraphs to the space of graphs and study their functorial properties and Lipschitz bounds. Finally, we demonstrate the versatility of our Hypergraph Co-Optimal Transport (HyperCOT) framework through various examples. This talk is based on joint works with Youjia Zhou, Samir Chowdhury, Tom Needham, and Ethan Semrad. See https://arxiv.org/abs/2112.03904.