Computational Persistence 2023
Sep 25 - 29, Purdue University, Indiana

Session 1, Monday (Sep 25)

  • 10:00 EDT (4:00 CET):

    Peter Bubenik (Invited Talk). Persistence: from Algebra to Analysis

    Abstract: Consider the following view of topological data analysis. The first and most difficult step consists of the computation of useful invariants from data. The theoretical foundation for these computations is algebra. The second step is the computation of vector summaries of these invariants, which may then be used in statistics and machine learning. The theoretical foundation for these computations is functional analysis. As the algebraic invariants being computed are increasing in sophistication, we need a better analytic theory for persistence.

    This is joint work with Alex Elchesen.

  • 10:30 EDT (4:30 CET):

    Jiajie Luo and Gregory Henselman-Petrusek. Algorithmic Interval Decomposition for Persistence Modules of Free Abelian Groups

    Abstract: The theory of single-parameter persistence is intimately tied to Gabriel’s Theorem, which states that any functor F from the poset category of finite totally-ordered set I into a category of finitedimensional vector spaces admits an interval decomposition – that is, a decomposition as a direct sum of interval modules.
    This theorem typically fails when one loosens the restriction on the target category. In this talk, we introduce a necessary and sufficient condition for the existence of interval decompositions in singleparameter persistence modules valued in the category of finitely-generated free abelian groups, and group homomorphisms. This work complements and informs earlier work characterizing filtered topological spaces whose persistence diagrams are independent of the choice of ground field.
    We also provide a polynomial-time algorithm to either (a) compute an interval decomposition of a module of free abelian groups, or (b) certify that no such decomposition exists.

  • 11:00 EDT (5:00 CET):

    Isaac Ren. Computing relative Betti diagrams of multipersistence modules using Koszul complexes

    Abstract: Relative homological algebra is a fruitful source of numerical invariants for multidimensional persistence modules and modules over arbitrary posets. In this talk, we focus on relative resolutions, which are exact sequences of persistence modules that are projective, in some sense, relative to a given family of “simple” modules. Under certain conditions on this family, these resolutions consist of direct sums of simple modules, whose multiplicities we can then collect in the so-called relative Betti diagrams. We can then compute the these relative Betti diagrams using Koszul complexes, which is simpler than directly computing the full relative resolutions.

    This is a joint work with Wojciech Chachólski, Andrea Guidolin, Martina Scolamiero, and Francesca Tombari.

Session 2, Monday (Sep 25)

  • 12:30 EDT (6:30 CET):

    Guo-Wei Wei (Invited Talk). Persistent Topological Laplacians

    Abstract: In recent years, the impact of topological data analysis (TDA) in sciences and engineering has grown exponentially. The main tool of TDA, persistent homology (PH), helps bridge the gap between complex geometry and abstract topology through filtration. PH has been incredibly successful in handling intricately complex, high-dimensional, nonlinear, and multiscale data. However, it has some limitations, including its inability to handle heterogeneous information (i.e., different types of objects in the point cloud), its qualitative nature (e.g., a 5-member ring is counted the same as a 6-member ring), its lack of description of non-topological changes (i.e., homotopic shape evolution), its incapable of coping with directed networks and digraphs, and its inability to characterize structured data (e.g., self-organizations in data). To address these challenges, we introduce persistent topological Laplacians (PTLs), including persistent Laplacians, persistent path Laplacians, persistent sheaf Laplacians, persistent hypergraph Laplacians, persistent hyperdigraph Laplacians, and evolutionary de Rham-Hodge theory. By combining these tools with state-of-the-art artificial intelligence (AI) algorithms, we have uncovered the mechanisms of SARS-CoV-2 evolution and accurately forecast emerging dominant SARS-CoV-2 variants.

  • 1:00 EDT (7:00 CET):

    Barbara Giunti and Jānis Lazovskis. Pruning vineyards: updating barcodes by removing simplices

    Abstract: The barcode computation of a filtration can be computationally expensive. Therefore, it is useful to have methods to update a barcode if its filtration undergoes small changes, such as the addition, swap, and removal of some simplices. There is already a rich literature on how to efficiently update a barcode in the first two cases, but the latter has not been investigated yet. In this work, we provide an algorithm to update a reduced boundary matrix when simplices are removed. We show that in many cases the complexity is much lower than recomputing the reduction from scratch, with both theoretical and experimental methods.

Session 1, Tuesday (Sep 26)

  • 10:00 EDT (4:00 CET):

    Teressa Heiss (Invited Talk). Merge Trees of Periodic Filtrations: Definition and Computation

    Abstract: We study merge trees of periodic filtrations in three-dimensional euclidean space, i.e. the filtration is invariant under three linearly independent translations. Such periodic filtrations are used for studying crystalline materials. The merge tree of a periodic filtration has infinitely many branches, which we refer to as twigs. To reduce the redundant information into a finite object, we group twigs that represent periodic copies of each other into branches, and describe for each branch how many twigs it consists of. If it consists of infinitely many twigs, we quantify how fast the number of twigs tends to infinity with increasing window size. Contrary to related work, we achieve this in a way that is stable under perturbations and invariant under different finite representations of the infinite periodic filtration. From the resulting Periodic Merge Tree, it is easy to read off the 0-dimensional persistent homology. Apart from defining the Periodic Merge Tree, I will also sketch the algorithm.

  • 10:30 EDT (4:30 CET):

    Matt Piekenbrock and Jose A. Perea. Spectral families of persistent rank invariants

    Abstract: Using a duality result between persistence diagrams and persistence measures, we introduce a framework for constructing families of continuous relaxations of the persistent rank invariant for parametrized families of persistence vector spaces indexed over the real line. Like the rank invariant, these families obey inclusion-exclusion, are derived from simplicial boundary operators, and encode all the information needed to construct a persistence diagram. Unlike the rank invariant, these spectrallyderived families enjoy a number of stability and continuity properties typically reserved for persistence diagrams, such as smoothness and di↵erentiability over the positive semi-definite cone. Leveraging a connection to combinatorial Laplacian operators, we find the non-harmonic spectra of our proposed relaxation encode valuable geometric information about the underlying space, prompting several avenues for geometric data analysis.

  • 11:00 EDT (5:00 CET):

    Tamal Dey and Abhishek Rathod. Cup Product Persistence and Its Efficient Computation

    Abstract: It is well-known that cohomology has a richer structure than homology. However, so far, in practice, the use of cohomology in persistence setting has been limited to speeding up of barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an O(dn^4) algorithm for computing the persistent k-cup modules for all k ∈ {2, ... , d}, where d denotes the dimension of the filtered complex, and n denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it.

Session 2, Tuesday (Sep 26)

  • 12:30 EDT (6:30 CET):

    Brittany Fasy (Invited Talk). (Cancelled)

    Tamal K. Dey. A Persistence-like Algorithm for Computing Connection Matrices Efficiently

    Abstract: Connection matrices are a generalization of Morse boundary operators from the classical Morse theory for gradient vector fields. Developing an efficient computational framework for connection matrices is particularly important in the context of a rapidly growing data science that requires new mathematical tools for discrete data. Toward this goal, the classical theory for connection matrices has been adapted to combinatorial frameworks that facilitate computation. We develop an efficient persistence-like algorithm to compute a connection matrix from a given combinatorial (multi) vector field on a simplicial complex. This algorithm requires a single-pass, improving upon a known algorithm that runs an implicit recursion executing two-passes at each level. Overall, the new algorithm is more simple, direct, and efficient than the state-of-the-art. Because of the algorithm's similarity to the persistence algorithm, one may take advantage of various software optimizations from topological data analysis.

  • 1:00 EDT (7:00 CET):

    Marc Ethier, Patrizio Frosini, Nicola Quercioli and Francesca Tombari. Geometry of the matching distance for 2D filtering functions

    Abstract: The matching distance is a metric studied in multiparameter persistence theory. Its computation, in the context of biparameter persistence, has produced several successful efforts turning into more and more efficient algorithms. In this talk, we will explore the geometry of the matching distance and its dependence on the differential structure of the filtering functions from which the persistence invariants are extracted. We will introduce the extended Pareto grid associated with a smooth function from a closed Riemannian manifold to the real plane, explain how this grid can be used to find persistence features and use this information to deepen our understanding of the matching distance.

Session 1, Wednesday (Sep 27)

  • 10:00 EDT (4:00 CET):

    Andrew Blumberg (Invited Talk). An Intrinsic Approach to Scalar-Curvature Estimation for Point Clouds

    Abstract: I will discuss joint work with Hickok in which we develop an intrinsic estimator for scalar curvature of a point cloud; our estimator does not depend on an embedding into R^n but only on the metric structure. I will explain stability properties of the estimator as well as empirical results on synthetic data sets and on genomic data.

  • 10:30 EDT (4:30 CET):

    Håvard Bakke Bjerkevik. Stabilizing decomposition of multiparameter persistence modules

    Abstract: While decomposition of one-parameter persistence modules behaves nicely, as demonstrated by the algebraic stability theorem, decomposition of multiparameter modules is well known to be unstable in a certain precise sense. I will explain why naive attempts to build a meaningful stability theory for multiparameter module decomposition tend to fail, and then present recent work showing that decomposition stability theorems can be proved despite these difficulties.
    If time allows, I will also talk about a conjecture that would strengthen the main stability result for staircase decomposable modules, is relevant for other areas of multipersistence, and can be understood without knowing anything about persistence.
    The talk is based on the arXiv preprint

  • 11:00 EDT (5:00 CET):

    Elizabeth Munch, Erin Chambers, Sarah Percival and Bei Wang. Bounding the Interleaving Distance for Geometric Graphs with a Loss Function

    Abstract: A geometric graph is generally defined as an abstract graph along with a well behaved embedding of the graph into the Euclidean plane. Such graphs are a fundamental object used to model a wide range of data sets, ranging from maps and trajectories to commodity networks (i.e. electrical grids) to skeletons for shape recognition. The ability to compare and cluster such objects is required in a data analysis pipeline, leading to a need for distances or metrics on these objects. In this work, we utilize the idea of the interleaving distance, where functor representations of data can be compared by finding pairs of natural transformations between them. However, in many cases, particularly those of the set-valued functor variety, computation of the interleaving distance is NP-hard. For this reason, we take inspiration from the work of Robinson to find quality measures for families of maps that do not rise to the level of a natural transformation. Using the structure of the embedded graphs, we define a loss function which measures how far the required diagrams of an interleaving are from commuting. We can use this loss function to determine a bound on the interleaving distance as follows, as well as begin to develop an algorithmic approach to finding locally optimal interleavings. We expect these ideas are not only useful in our particular use case of embedded graphs, but can be extended to a larger class of interleaving distance problems where computational complexity creates a barrier to use in practice.

Session 2, Wednesday (Sep 27)

  • 12:30 EDT (6:30 CET):

    Sarah Tymochko (Invited Talk). Time Series Analysis using Zigzag Persistent Homology

    Abstract: Persistent homology, one of the most popular tools in topological data analysis, has proven useful in applications to time series data, quantifying features like periodicity. We consider a problem inspired by bifurcation detection in dynamical systems where a time series changes depending on some choice of input parameter. While standard persistent homology has been used in this type of setting, it usually requires analyzing a collection of persistence diagrams, which in turn drives up the computational cost. Using zigzag persistence, we can capture topological changes in the data in only one persistence diagram. From this zigzag persistence diagram, we can translate back to the original input system and identify parameter values where the time series behavior changed significantly.

  • 1:00 EDT (7:00 CET):

    Hana Dal Poz Kourimska, Mathijs Wintraecken, Dominique Attali, Andre Lieutier, Christopher Fillmore, Ishika Ghosh and Elizabeth Stephenso. Tight bounds for the learning of homotopy a la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds

    Abstract: Can we infer the topology of a set if we are only given a partial geometric information about it? Under which conditions is such inference possible? Niyogi, Smale, and Weinberger showed that, given a C^2 manifold of positive reach embedded in the Euclidean space and a sufficiently dense point sample on — or near — the manifold, the union of balls of certain radii centred on the point sample captures the homotopy type of the manifold. Their work has quickly gained recognition in the computational geometry society, since the homotopy groups of the aforementioned union of balls are easy to calculate.
    We have expanded this seminal work in several directions. Instead of a C^2 manifold, we consider general closed sets of positive reach, and establish tight bounds on the quality of the sample, that guarantee a successful reconstruction. We achieve the same result for closed sets of positive reach embedded not only in the Euclidean space, but in any Riemannian manifold. In this case, we compare the manifold to spaces of constant curvature, and our bounds depend on the curvature of these spaces.

Session 1, Thursday (Sep 28)

  • 10:00 EDT (4:00 CET):

    Michael Lesnick (Invited Talk). Tension Between Robustness and Computability in 2-Parameter Persistence

    Abstract: In this talk, I'll discuss recent results about the robustness and computation of density-sensitive bilftrations of point cloud and metric data. Together, the results reveal a tension: The more robust a bifiltration, the less computable it is with current techniques. The question of whether this tension can be resolved is largely open.

  • 10:30 EDT (4:30 CET):

    Wenwen Li. Multiparameter persistence homology and topological robotics

    Abstract: Multiparameter persistence modules come up naturally in the areas of topological data analysis and topological robotics. Given multiple robots moving on a rail X, the configuration space of X consists of all possible positions that the robots may attain in X. In this talk, we discuss the homology of the second configuration space of metric graphs with the proximity parameter r and the edge length parameter L. These configuration spaces are naturally filtered by the poset (R,≤)^op × (R,≤), and we obtain a 2-parameter persistence module after applying the homology functor to the filtration. We then focus on the persistence modules associated with the star graph and the generalized H-shaped graph with parameters r and L. Moreover, we provide the direct sum decomposition for each persistence module, where each direct summand is indecomposable.

  • 11:00 EDT (5:00 CET):

    Xinyi Wang, Elizabeth Munch, Erin Wolf Chambers and Sarah Percival. A Distance for Geometric Graphs via the Labeled Merge Tree Interleaving Distance

    Abstract: Geometric graphs appear in many real-world datasets, such as road networks, sensor networks, and molecules. We investigate the notion of distance between graphs and present a semi-metric to measure the distance between two geometric graphs via the directional transform combined with the labeled merge tree distance. We introduce a way of rotating the sub-level set to obtain the merge trees via the idea of the directional transform. We represent the merge trees using a surjective multi-labeling scheme and then compute the distance between two representative matrices. Our distance is not only reflective of the information from the input graphs, but also can be computed in polynomial time. We illustrate its utility by implementation on a Passiflora leaf dataset.

Session 2, Thursday (Sep 28)

  • 12:30 EDT (6:30 CET):

    Tim Downing and Alexander D. Rahm. New tools for studying the topology of bacterial protein interaction networks

    Abstract: On the genome of bacteria, Protein-Protein Interaction Networks (PPINs) are recorded as weighted graphs, where proteins represent the genes which code them. We introduce a topological measure on PPINs, the Persistant Maximum of Non-trivial Loops per Edge (PMNLE), where an edge is a protein-protein interaction of sufficient weight, and we look at non-trivial loops in the Vietoris-Rips complex with respect to that weight. The weight combines several biological measurements, and the PMNLE allows to measure across its scale.
    The genome of bacteria is made of a chromosome and a collection of plasmids, the latter ones containing exchangeable information, for instance on how to survive a specific antibiotic. On a large database of bacteria, we measured the PMNLE separately on the chromosome and on the full genome. Bacteria which showed a significantly higher PMNLE on their full genome than on their chromosome, did show a crumbling of their PPIN when removing plasmid proteins, and hence appeared to be likely to be "co-evolutive": eager to integrate plasmids into their chromosome.

  • 1:00 EDT (7:00 CET):

    Audun Myers, David Munoz, Firas Khasawneh and Elizabeth Munch. Temporal Network Analysis Using Zigzag Persistence

    Abstract: We present a framework for studying temporal networks using zigzag persistence, a tool from the field of Topological Data Analysis (TDA). The resulting approach is general and applicable to a wide variety of time-varying graphs. For example, these graphs may correspond to a system modeled as a network with edges whose weights are functions of time, or they may represent a time series of a complex dynamical system. We use simplicial complexes to represent snapshots of the temporal networks that can then be analyzed using zigzag persistence. We show two applications of our method to dynamic networks: an analysis of commuting trends on multiple temporal scales, e.g., daily and weekly, in the Great Britain transportation network, and the detection of periodic/chaotic transitions due to intermittency in dynamical systems represented by temporal ordinal partition networks. Our findings show that the resulting zero- and one-dimensional zigzag persistence diagrams can detect changes in the networks' shapes that are missed by traditional connectivity and centrality graph statistics.

Session 1, Friday (Sep 29)

  • 10:00 EDT (4:00 CET):

    Omer Bobrowski. Universality in Random Persistence Diagrams - Weak, Strong and Extremal

    Abstract: In this talk we will present a series of new statements regarding the behavior of persistence diagrams arising from random point-clouds. We claim that, viewed in the right way, persistence values obey a universal probability law, that depends on neither the underlying space nor the original distribution of the point-cloud. We will present three notions of such universality. The “weak” and “strong” notions characterize the distribution of values across the entire persistence diagram. We will also discuss the “extremal” notion, referring to the largest cycles formed in random diagrams.

  • 10:30 EDT (4:30 CET):

    Sunia Tanweer, Firas Khasawneh, Elizabeth Munch and Joshua Templeman. A Topological Framework for Identifying Phenomenological Bifurcations in Stochastic Dynamical Systems

    Abstract: The state of many engineered and natural systems can transition between several, qualitatively different regimes over time. These transitions (called bifurcations) are important as they can signal harmful transitions in the system's response. In presence of randomness, there is interest in tracking stochastic bifurcations referred to as P-type (Phenomenological) bifurcations. These include transitions from mono-stability to bi-stability, and the emergence of stochastic limit cycles in the probability distributions of the state space. Identifying and analyzing P-type bifurcations is more challenging than their deterministic counterparts. For P-type bifurcations, the prominent practice is to visually inspect the probability density function to judge the type of the bifurcation. This limits the feasibility of this approach to experienced users, and to systems with a small state space (no larger than 2). In contrast, we present an approach based on Topological Data Analysis (TDA) for quantifying P-type bifurcations in stochastic systems. We show examples that demonstrate how measuring the 0- and 1-dimensional sublevel persistence of the probability density function can provide information for inferring P-type bifurcations. We also discuss future work for extending this approach to a wider class of stochastic equations.

  • 11:00 EDT (5:00 CET):

    Chunyin Siu, Gennady Samorodnitsky, Christina Lee Yu and Rongyi He. The Asymptotics of the Expected Betti Numbers of Preferential Attachment Clique Complexes -- Theory and Computational Challenges

    Abstract: Random models of simplicial complexes are important for isolating topological signals from statistical noise. However, the need to compute topological invariants for a large number of samples presents significant computational challenges. This is especially so for heavy-tailed statistics, whose estimation requires a large sample size so as to mitigate the effect of outliers.
    We focus on the case of the expected Betti numbers of the preferential attachment clique complex. Preferential attachment graphs are popular models for scale-free networks, and its degree distribution is known to be heavy-tailed. We have shown analytically that the expected Betti numbers grow sublinearly with the number of nodes (with the exceptions that the expected first Betti number grows linearly, and the zeroth Betti number is 1 by construction), but the convergence to the asymptotical growth rate is observed to be slow. In this talk, we will discuss our analytical result on the expected Betti numbers, and we will present numerical results that are within our computational capacity. We discuss the computational challenges to obtaining numerical results that better illustrate the theoretical growth rates.
    This talk is based on the results in the preprint

Session 2, Friday (Sep 29)

  • 12:30 EDT (6:30 CET):

    Sarah McGuire, Elizabeth Munch and Matthew Hirn. NervePool: a simplicial pooling layer

    Abstract: For deep learning problems on graph-structured data, pooling layers are important for down sampling, reducing computational cost, and minimizing overfitting. In this talk, I will discuss a pooling layer for data structured as simplicial complexes, which are generalizations of graphs that include of higher-dimensional simplices beyond vertices and edges; this structure allows for greater flexibility in modeling higher-order relationships. We propose a simplicial coarsening scheme built upon soft partitions of vertices, which allows us to generate hierarchical representations of simplicial complexes, collapsing information in a learned fashion. The simplicial pooling method builds on the learned vertex cluster assignments and extends to coarsening of higher dimensional simplices in a deterministic fashion. While in practice, the pooling operations are computed via a series of matrix operations, its topological motivation is based on unions of stars of simplices and the nerve complex.