10:00 (EDT) / 15:00 (CET): Steve Oudot

Title: Signed barcodes for multi-parameter persistence --- part 1

Abstract: This talk will introduce the signed barcode, a new visual representation of the global structure of the rank invariant of a multi-parameter persistence module. Like its unsigned counterpart in one-parameter persistence, the signed barcode derives from a decomposition of the rank invariant as a Z-linear combination of rank invariants of indicator modules supported on segments in the indexing poset. The talk will exhibit sufficient conditions under which such rank decompositions exist and are unique, and describe the ensuing construction of the signed barcode. It will also provide insight into the structure of the signed barcode and its interpretation in the context of data analysis.

10:30 (EDT) / 15:30 (CET): Magnus Botnan

Title: Signed barcodes for multi-parameter persistence --- part 2

Abstract: In the first part of the talk, I will discuss computational aspects of the rank invariant and the associated signed barcode. The second part will be devoted to extending the material from part 1 to the generalized rank invariant as introduced by Kim and Memoli.

11:00 (EDT) / 16:00 (CET): Alex Rolle

Title: Computing minimal presentations of 2-parameter persistence modules

Abstract: This talk will survey recent approaches for computing minimal presentations of 2-parameter persistence modules. In particular, we will discuss an algorithm of Lesnick--Wright, some modifications of this algorithm that are joint work with Michael Kerber, and the "chunk" algorithm of Fugacci--Kerber. Combining all these ideas, one has an algorithm that scales linearly in terms of time and memory size on many classes of input data.

12:00 (EDT) / 17:00 (CET): Amit Patel

Title: Algorithms for Generalized Persistence Diagrams

Abstract: The conventional interpretation of a persistence diagram as a list of indecomposable is limited to 1D persistence modules of vector spaces. However, if one interprets a persistence diagram as the Möbius inversion of a rank or a birth-death function, then all sorts of new possibilities emerge. First, the generalized persistence diagram is well defined for filtrations indexed over any finite metric lattice and it is stable. Second, the generalized persistence diagram is well defined for functors from any finite metric lattice into any abelian category and it is stable. Thirdly, the construction of the generalized persistence diagram is functorial, which is new even to classical persistent homology. Now that the basic theory is established, it is time to develop efficient algorithms. I will describe three ongoing projects that aims to bring this theory into practice: 1) develop an efficient algorithm to construct the generalized persistence diagram of a 1D filtration using coefficients in a finite abelian group, 2) develop an efficient algorithm to construct the generalized persistence diagram of a filtration indexed by a finite lattice using field coefficients, 3) develop an efficient algorithm to compute the edit distance between two generalized persistence diagrams over two finite metric lattices.

12:30 (EDT) / 17:30 (CET): Peter Bubenik

Title: A topological heat map for persistence

Abstract: Topological data analysis (TDA) is often able quantify the "shape" of data and perform learning tasks such as classification. In such cases, users of TDA often want to locate the part of their data responsible for these decisions. While persistence algorithms can compute representative cycles for the dots in the persistence diagram, unlike the persistence diagram itself, these representative cycles are not stable. I will present an approach to using persistence diagrams and representative cycles to produce a stable topological heat map and discuss connections with machine learning.

This is joint work with Alex Wagner (Duke).

13:00 (EDT) / 18:00 (CET): Hubert Wagner

Title: Capturing higher-order interactions using topological constructions.

Abstract: A significant proportion of work in TDA is on computing and using concise topological descriptors, such as persistence modules. In this talk I would like to focus on the information contained in what is usually considered an intermediate representation, namely on the simplicial complex derived from data. I will show constructions in which the filtration value of each simplex has a clear information-theoretical interpretation and captures a higher-order interaction present in data. Stressing that this information cannot be reconstructed solely from the graph of pairwise interactions, I would like to start a discussion about efficient tools that go beyond the standard Vietoris--Rips construction.

10:00 (EDT) / 15:00 (CET): Michael Kerber

Title: Average complexity of matrix reduction for clique filtrations

Abstract: We study the algorithmic complexity of computing persistent homology of a randomly chosen filtration. Specifically, we prove upper bounds for the average fill-up of the boundary matrix on Erd\"os-Renyi complexes and Vietoris-Rips complexes after matrix reduction. Our bounds show that in both cases, the reduced matrix is expected to be significantly sparser than what the general worst-case predicts. Our bounds are based on previous results on the expected first Betti numbers of corresponding complexes. We establish a link of these results to the sparsity of the boundary matrix. We also show experimentally that the empirically observed fill-up for Vietoris-Rips complexes agrees with our asymptotic upper bound.

This is joint work with Barbara Giunti (TU Graz) and Guillaume Houry (Ecole Polytechnique)

10:30 (EDT) / 15:30 (CET): Claudia Landi

Title: Morse-based Fibering of the Persistence Rank Invariant

Abstract: Although there is no doubt that multi-parameter persistent homology is a useful tool to analyze multi-variate data, efficient ways to compute these modules are still lacking in the available topological data analysis toolboxes. Other issues such as interpretation and visualization of the output remain difficult to solve. One of the simplest invariants for a multi-parameter persistence module is its rank invariant, defined as the function that counts the number of linearly independent homology classes that live in the filtration through a given pair of values of the multi-parameter. We show how discrete Morse theory may be used to compute the rank invariant, proving that it is completely determined by its values at points whose coordinates are critical with respect to a discrete Morse gradient vector field. These critical points partition the set of all lines of positive slope in the parameter space into equivalence classes, such that the rank invariant along lines in the same class are also equivalent. We show that we can deduce all persistence diagrams of the restrictions to the lines in a given class from the persistence diagram of the restriction to a representative in that class. An algorithm that chooses a representative line for each equivalence class in the case of 2-parameter persistence modules is presented.

This is joint work with Asilata Bapat, Robyn Brooks, Celia Hacker, Barbara I. Mahler.

11:00 (EDT) / 16:00 (CET): Mickaël Buchet

Title: Computing multiplicities of indecomposable in multi-persistence modules.

Abstract: I will present an algorithm to compute the multiplicity of an indecomposable module within a more general persistence module, without computing the full decomposition. In the specific case of interval modules as indecomposable and 2D-persistence module as the containing module, it provides a way to test for interval decomposability without the need of computing the whole decomposition. The algorithm is general and can be used without extra assumptions for any module.

12:00 (EDT) / 17:00 (CET): Don Sheehy

Title: Discrete Voronoi Refinement

Abstract: If one views topological data analysis using persistent homology as the attempt to compute topological invariants of an unknown function over an unknown space subject to unknown continuous transformations, it becomes clear that a first step is to have a reasonable reconstruction of the underlying space. For non-Euclidean data sets, the Witness complex has been proposed as a way to reconstruct a space and capture some of the intrinsic geometry and topology of the underlying shape or distribution. In this talk, I will present an alternative variation of the witness complex that is a generalization of the Delaunay/Voronoi refinement schemes that have been so successful in the Euclidean setting for mesh generation and surface reconstruction. The advantages of this approach are that it allows for strong guarantees on the number of simplices incident to any point and it also naturally adapts to local changes of scale. Thus, the resulting complex can have large simplices in areas of low density and small simplices in areas of high density. I will also discuss efficient algorithms as well as a theory of optimal size complexes of this form.

12:30 (EDT) / 17:30 (CET): Tao Hou

Title: Computing zigzag persistence on graphs in near-linear time

Abstract: Zigzag persistence which incorporates both additions and deletions of simplices is a more powerful tool than standard persistence. For example, dynamic networks (a dynamic sequence of graphs where vertices and edges can be both added and deleted) cannot be treated as a standard filtration but can be treated as a zigzag filtration. However, unlike standard persistence which admits a near-linear algorithm on graphs, such a result for the zigzag version improving the general $O(m^\omega)$ time complexity is not known ($\omega< 2.37286$ is the matrix multiplication exponent). In this talk, I will describe our recent work on computing zigzag persistence on graphs in near-linear time. Given a filtration of length $m$ on a graph of size $n$, our algorithm for 0-dimension runs in $O(m\log^2 n+m\log m)$ time and our algorithm for 1-dimension runs in $O(m\log^4 n)$ time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a 1-cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al.

This is joint work with Tamal K. Dey.

13:00 (EDT) / 18:00 (CET): Dmitriy Morozov

Title: Towards Lockfree Persistent Homology

Abstract: Most of the existing algorithms that compute persistence in parallel rely on the algebraic structure of the problem to subdivide the computation, either by partitioning the range, or the domain of the underlying scalar measurement. After briefly surveying these, we will describe a way to exploit the inherent parallelism of the original reduction algorithm. Using hardware synchronization primitives, namely compare-and-swap operations, we develop a lockfree shared-memory algorithm that avoids having to decide how to partition the underlying data set. We demonstrate the algorithm’s performance and scaling using a set of computational experiments. (Joint work with Arnur Nigmetov.)

10:00 (EDT) / 15:00 (CET): Clément Maria

Title: Computational Aspects of Zigzag Persistence

Abstract: In this talk, we discuss several computational aspects of zigzag persistent homology of general filtrations. After introducing a general framework for presenting existing algorithms for zigzag persistence, we will highlight some difficulties posed by the zigzag framework compared to standard persistent homology. Finally, we will draw directions along which the computation of zigzag persistence may be improved, notably by the simplification of zigzag filtrations.

10:30 (EDT) / 15:30 (CET): Marian Mrozek

Title: Persistence in combinatorial topological dynamics

Abstract: Forman's work on discrete Morse theory has found applications in the study of the topological shape of data. To make this approach successful in describing the dynamics encoded in data a proper understanding of dynamical concepts in the combinatorial setting of finite topological spaces is needed. In an attempt to go in this direction I will define the broader concept of a combinatorial multivector field and a time-discrete dynamical system on a finite topological space. I will introduce some topological invariants for combinatorial dynamical systems and I will present some results on the persistence of Morse decompositions for such systems.

11:00 (EDT) / 16:00 (CET): Abhishek Rathod

Title: The complexity of computing single parameter persistence: Is there more to say?

Abstract: It is well-known that the persistent homology of a filtered simplicial complex can be computed in matrix multiplication time in the worst case. Additionally, Chen and Kerber devised algorithms for computing persistence with output-sensitive complexity bounds. In this talk, we will introduce two output-sensitive algorithms for computing persistence with bounds that are more refined compared to bounds given by Chen and Kerber. We believe that similar bounds also hold for the compressed annotation matrix algorithm. Time permitting, we will discuss how the new algorithms can be viewed in the light of algebraic Morse theory.

The talk is based on joint work with Uli Bauer and Talha Bin Masood.

12:00 (EDT) / 17:00 (CET): Facundo Memoli

Title: Curvature sets over persistence diagrams

Abstract: We study an invariant of compact metric spaces which combines the notion of curvature sets introduced by Gromov in the 1980s together with the notion of Vietoris-Rips persistent homology. For given integers k≥0 and n≥1 these invariants arise by considering the degree k Vietoris-Rips persistence diagrams of all subsets of a given metric space with cardinality at most n. We call these invariants (n,k)-persistence sets. We argue that due to their inherently parallelizable nature, computing these invariants could be significantly easier than computing the usual Vietoris-Rips persistence diagrams. We establish stability results for these invariants and we also precisely characterize some of them in the case of spheres with geodesic and Euclidean distances. We also identify a rich family of metric graphs for which the (4,1)-persistence sets fully recover their homotopy type. Along the way we prove some useful properties of Vietoris-Rips persistence diagrams.

This is joint work with Mario Gómez.

12:30 (EDT) / 17:30 (CET): Yusu Wang

Title: Persistent Laplacian: properties and algorithms

Abstract: The combinatorial graph Laplacian, as an operator on functions defined on the vertex set of a graph, is a fundamental object in the analysis of and optimization on graphs. There is also an algebraic topology view of the graph Laplacian which arises through considering boundary operators and specific inner products defined on simplicial (co)chain groups. This permits extending the graph Laplacian to a more general operator, the q-th combinatorial Laplacian to a given simplicial complex. An extension of this combinatorial Laplacian to the setting of pairs (or more generally, a sequence of) simplicial complexes was recently introduced by (R.) Wang, Nguyen and Wei. In this talk, I will present several results from our recent study of the properties for the persistence Laplacian, as well as efficient algorithms to compute it.

This is joint work with Facundo Memoli and Zhengchao Wan.

13:00 (EDT) / 18:00 (CET): Bala Krishnamoorthy

Title: Box Filtration

Abstract: We propose a new filtration for the topological data analysis of points in high-dimensional Euclidean space where the convex sets are hyperrectangles or boxes. Rather than center them at each point, we grow the boxes non-uniformly in each dimension or direction based on the distribution of points so as to better capture the topology of the point set. We present efficient algorithms to construct the box filtration. We also prove stability results for the boxes constructed in the filtration under small changes of input parameters. We compare topological summaries of standard data sets in the form of persistence diagrams produced by box filtration to those produced by the standard distance-to-measure (DTM) filtration.

This is joint work with Enrique Alvarado and Prashant Gupta.

10:00 (EDT) / 15:00 (CET): Ulrich Bauer

Title: Gromov hyperbolicity, geodesic defect, and apparent pairs in Rips filtrations

Abstract: Motivated by performance gains observed in large-scale computations of Vietoris–Rips persistence for viral evolution data, we revisit Eliyahu Rips‘ result on the contractibility of Rips complexes for a suitable parameter, depending on the hyperbolicity of the space. We introduce the notion of geodesic defect to extend this result to general metric spaces in a way that is also compatible with the Rips filtration. Finally, we show that for finite metric trees this result is obtained through the apparent pairs gradient, which is used as a computational optimization in Ripser, providing an explanation for its particularly good performance on evolution data.

This is joint work with Fabian Roll.

10:30 (EDT) / 15:30 (CET): Francesco Vaccarino

Title: Parallel decomposition of persistence modules through interval bases

Abstract: We introduce an algorithm to decompose any finite-type persistence module with coefficients in a field into what we call an "interval basis". This construction yields both the standard persistence pairs of Topological Data Analysis (TDA), as well as a special set of generators inducing the interval decomposition of the Structure theorem. The computation of this basis can be distributed over the steps in the persistence module. This construction works for general persistence modules on a field, not necessarily deriving from persistent homology. We subsequently provide a parallel algorithm to build a persistent homology module over by leveraging the Hodge decomposition, thus providing new motivation to explore the interplay between TDA and the Hodge Laplacian.

Joint work with: Alessandro De Gregorio, Marco Guerra, and Sara Scaramuccia

11:00 (EDT) / 16:00 (CET): Saugata Basu

Title: Efficient simplicial replacement of semi-algebraic sets and applications

Abstract: In the talk I will describe a new algorithm that for any $\ell \geq 0$ , takes as input a description of a semi-algebraic set $S$ given by a quantifier-free first order formula in the language of the reals, and produces as output a simplicial complex, whose geometric realization, $\ell$ -equivalent to S. The complexity of our algorithm is bounded singly exponentially in the dimension of the ambient space for fixed $\ell$. In particular, we obtain a reduction (having singly exponential complexity) of the problem of computing the first $\ell$ homotopy groups of $S$ to the combinatorial problem of computing the first $\ell$ homotopy groups of a finite simplicial complex of singly exponetially bounded size. As an application we give an algorithm with singly exponential complexity for computing the \emph{persistence barcodes} up to dimension $\ell$ (for any fixed $\ell \geq 0$), of the filtration of a given semi-algebraic set by the sub-level sets of a given polynomial. Our algorithm is the first algorithm for this problem with singly exponential complexity, and generalizes the corresponding results for computing the Betti numbers up to dimension $\ell$ of semi-algebraic sets with no filtration present.

(Joint work with Negin Karisani).

12:00 (EDT) / 17:00 (CET): Michael Lesnick

Title: ℓ^p-Metrics on Multiparameter Persistence Modules

Motivated both by theoretical and practical considerations in topological data analysis, we generalize the p-Wasserstein distance on barcodes to multiparameter persistence modules. For each p ∈ [1,∞], we in fact introduce two such generalizations d_I^p and d_M^p, such that d_I^∞ equals the interleaving distance and d_M^∞ equals the matching distance. We show that d_M^p ≤ d_I^p for all p ∈ [1,∞], extending an observation of Landi in the p = ∞ case. We observe that the distances d_M^p can be efficiently approximated. Finally, we show that on 1- or 2-parameter persistence modules over prime fields, d_I^p is the universal (i.e., largest) metric satisfying a natural stability property; this result extends a stability theorem of Skraba and Turner for the p-Wasserstein distance on barcodes in the 1-parameter case, and is also a close analogue of a universality property for the interleaving distance given by the second author. In a forthcoming paper, we apply some of these results to study the stability of (2-parameter) multicover persistent homology.

Joint work with Håvard Bjerkevik

12:30 (EDT) / 17:30 (CET): Henry Adams

Title: Open problems in need of computer simulation

Abstract: Though math papers are sometimes presented as "definition, lemma, theorem, proof", the ideas instead often arise via a computational experiment, which leads to a conjecture, which only later perhaps becomes a theorem. Such computations should be explained, advertised, acknowledged, and celebrated. I will share open problems where more computational experiments are needed, and where there is plenty of room for folks with algorithmic expertise to get involved. These open problems are related (for example) to nerve complexes, to Vietoris-Rips complexes, and to the persistent homology of fractals.

13:00 (EDT) / 18:00 (CET): Bei Wang

Title: Adaptive Covers for Mapper Graphs Using Information Criteria

The mapper construction is a widely used tool from topological data analysis in obtaining topological summaries of large, high-dimensional point cloud data. It has enjoyed great success in data science, including cancer research, sports analytics, and visualization. However, developing practical and automatic parameter selection for the mapper construction remains a challenging open problem for both the topological analysis and visualization communities. In this paper, we focus on parameter selection for the 1-dimensional skeleton of the mapper construction, called the mapper graph. Specifically, we explore how information criteria used in the X-means clustering algorithm can inform and generate adaptive covers for mapper graphs. Our approach thus makes novel progress towards automatic parameter selection for the mapper construction using information theory.

This is joint work with Nithin Chalapathi and Youjia Zhou.

10:00 (EDT) / 15:00 (CET): Mathieu Carrière

Title: Statistical analysis of Mapper for stochastic and multivariate filters

Abstract: Reeb spaces, as well as their discretized versions called Mappers, are common descriptors used in Topological Data Analysis, with plenty of applications in various fields of science, such as computational biology and data visualization, among others. The stability and quantification of the rate of convergence of the Mapper to the Reeb space has been studied a lot in recent works, focusing on the case where a scalar-valued filter is used for the computation of Mapper. On the other hand, much less is known in the multivariate case, when the codomain of the filter is Rp, and in the general case, when it is a general metric space (Z, dZ), instead of R. In this talk, I will introduce a slight modification of the usual Mapper construction and give risk bounds for estimating the Reeb space using this estimator. Our approach applies in particular to the setting where the filter function used to compute Mapper is also estimated from data, such as the eigenfunctions of PCA. I will also provide preliminary applications of this estimator in statistics and machine learning for different kinds of target filters.

This is joint work with Bertrand Michel.

10:30 (EDT) / 15:30 (CET): Adam Brown

Title: Computing Injective Resolutions of Cellular Sheaves

Sheaf theory models relationships between local and global properties of a topological space. When combined with homological algebra, sheaf theory generalizes many forms of cohomology (such as simplicial cohomology, local cohomology, persistent (co)homology). To apply this theory to data, it is necessary to describe theoretical concepts in a computationally tractable form. In this talk we will discuss methods for computing injective resolutions of sheaves on simplicial complexes. Injective resolutions, a fundamental ingredient of homological algebra, are used to study sheaves from the ‘derived’ perspective, i.e. as objects in a derived category. Explicitly (and efficiently) constructed injective resolutions allow for new applications of homological algebra in computational topology. We will discuss the existence and uniqueness of ‘minimal’ injective resolutions and outline an algorithm for their construction. We will illustrate these calculations through examples and show applications to level-set persistence.

This is joint work with Ondrej Draganov.

11:00 (EDT) / 16:00 (CET): Chao Chen

Title: Cycle-Basis Graph Neural Networks

Abstract: Topological information has shown strong discriminative power for learning methods on graphs. Existing approaches focus on directly using persistent-homology-based features. We stipulate that cycles can be essential in some graph learning tasks. We propose a new cycle-centric graph neural network which efficiently exploits the space of cycles and learns the cycle representation for the learning tasks. Under the hood there is a need to compute cycle bases that are short and also cover the graph well. The method is applied to a knowledge-graph-completion task and achieves state-of-the-art performance. I will also briefly mention our recent NeurIPS paper in which we use persistent homology to identify backdoor-attacked neural networks.

12:00 (EDT) / 17:00 (CET): Elizabeth Munch

Title: On the inter-level-set persistence bottleneck distance for Reeb graphs

The Reeb graph is a skeletonization of an input function which provides information about the connected components of level-sets. While many distances for comparing these objects have been proposed, one of the computationally simplest options is to convert the Reeb graph data into some flavor of persistence and compute bottleneck distance accordingly. While this does not give a metric in general (many Reeb graphs will have the same algebraic representation), it is often discriminative enough for many representations. Further, there are many known relationships between the bottleneck option and other, more computationally complex but also more discriminative options for distances. In this talk, we discuss the use and differences between using the inter-level-set persistence representation and the extended persistence representation, and how these distances relate to other Reeb graph metrics.

12:30 (EDT) / 17:30 (CET): Ryan Slechta

Title: Persistence of Conley-Morse Graphs in Combinatorial Dynamical Systems

Abstract: Multivector fields provide an avenue for studying continuous dynamical systems in a combinatorial framework. There are currently two approaches in the literature which use persistent homology to capture changes in combinatorial dynamical systems. The first captures changes in the Conley index, while the second captures changes in the Morse decomposition. However, such approaches have limitations. The former approach only describes how the Conley index changes across a selected isolated invariant set though the dynamics can be much more complicated than the behavior of a single isolated invariant set. Likewise, considering a Morse decomposition omits much information about the individual Morse sets. In this paper, we propose a method to summarize changes in combinatorial dynamical systems by capturing changes in the so-called Conley-Morse graphs. A Conley-Morse graph contains information about both the structure of a selected Morse decomposition and about the Conley index at each Morse set in the decomposition. Hence, our method summarizes the changing structure of a sequence of dynamical systems at a finer granularity than previous approaches.

Joint work with Tamal K. Dey and Marian Mrozek.