Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher.
Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?
Some links on this page may take you to nonfederal websites. Their policies may differ from this site.

1parameter persistent homology, a cornerstone in Topological Data Analysis (TDA), studies the evolution of topological features such as connected components and cycles hidden in data. It has been applied to enhance the representation power of deep learning models, such as Graph Neural Networks (GNNs). To enrich the representations of topological features, here we propose to study 2parameter persistence modules induced by bifiltration functions. In order to incorporate these representations into machine learning models, we introduce a novel vector representation called Generalized Rank Invariant Landscape (GRIL) for 2parameter persistence modules. We show that this vector representation is 1Lipschitz stable and differentiable with respect to underlying filtration functions and can be easily integrated into machine learning models to augment encoding topological features. We present an algorithm to compute the vector representation efficiently. We also test our methods on synthetic and benchmark graph datasets, and compare the results with previous vector representations of 1parameter and 2parameter persistence modules. Further, we augment GNNs with GRIL features and observe an increase in performance indicating that GRIL can capture additional features enriching GNNs. We make the complete code for the proposed method available at https://github.com/soham0209/mpmlgraph.more » « less

We first introduce the notion of metarank for a 2parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the metadiagram of a 2parameter persistence module to be the Möbius inversion of the metarank, resulting in a function that takes values from signed 1parameter persistence modules. We show that the metarank and metadiagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the metarank and metadiagram of a 2parameter module M indexed by a bifiltration of n simplices in O(n^3) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n^4) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n^4) to O(n^3). In addition, we define notions of erosion distance between metaranks and between metadiagrams, and show that under these distances, metaranks and metadiagrams are stable with respect to the interleaving distance. Lastly, the metadiagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the wellunderstood persistent diagram in the 1parameter setting.more » « less

Zigzag persistence is a powerful extension of the standard persistence which allows deletions of simplices besides insertions. However, computing zigzag persistence usually takes considerably more time than the standard persistence. We propose an algorithm called FastZigzag which narrows this efficiency gap. Our main result is that an input simplexwise zigzag filtration can be converted to a cellwise nonzigzag filtration of a ∆complex with the same length, where the cells are copies of the input simplices. This conversion step in FastZigzag incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cellwise filtration because the conversion embodies a series of diamond switches known in topological data analysis. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain over the existing stateoftheart softwares.more » « less

Xavier Goaoc ; Michael Kerber (Ed.)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 𝐙²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 the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^ω) time where ω ∈ [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.more » « less

Xavier Goaoc ; Michael Kerber (Ed.)Multivector fields and combinatorial dynamical systems have recently become a subject of interest due to their potential for use in computational methods. In this paper, we develop a method to track an isolated invariant set  a salient feature of a combinatorial dynamical system  across a sequence of multivector fields. This goal is attained by placing the classical notion of the "continuation" of an isolated invariant set in the combinatorial setting. In particular, we give a "Tracking Protocol" that, when given a seed isolated invariant set, finds a canonical continuation of the seed across a sequence of multivector fields. In cases where it is not possible to continue, we show how to use zigzag persistence to track homological features associated with the isolated invariant sets. This construction permits viewing continuation as a special case of persistence.more » « less

null (Ed.)Graphs model realworld circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly lineartime algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in nearlinear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0dimension runs in O(mlog² n+mlog m) time and the algorithm for 1dimension runs in O(mlog⁴ n) time. The algorithm for 0dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2manifolds. The algorithm for 1dimension pairs a negative edge with the earliest positive edge so that a 1cycle 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. In the end, using Alexander duality, we extend the algorithm for 0dimension to compute the (p1)dimensional zigzag persistence for ℝ^pembedded complexes in O(mlog² n+mlog m+nlog n) time.more » « less

null (Ed.)A combinatorial framework for dynamical systems provides an avenue for connecting classical dynamics with dataoriented, algorithmic methods. Combinatorial vector fields introduced by Forman [R. Forman, 1998; R. Forman, 1998] and their recent generalization to multivector fields [Mrozek, 2017] have provided a starting point for building such a connection. In this work, we strengthen this relationship by placing the Conley index in the persistent homology setting. Conley indices are homological features associated with socalled isolated invariant sets, so a change in the Conley index is a response to perturbation in an underlying multivector field. We show how one can use zigzag persistence to summarize changes to the Conley index, and we develop techniques to capture such changes in the presence of noise. We conclude by developing an algorithm to "track" features in a changing multivector field.more » « less