The degree-Rips bifiltration is a simplicial filtration used in topological data analysis for analyzing the shape of point cloud data. It is a multiparameter extension of the Vietoris–Rips filtration that possesses greater stability to data outliers than single-parameter filtrations, and which is more amenable to practical computation than other multiparameter constructions. Introduced in 2015 by Lesnick and Wright, the degree-Rips bifiltration is a parameter-free and density-sensitive vehicle for performing persistent homology computations on point cloud data.[1]
Definition
editIt is standard practice in topological data analysis (TDA) to associate a sequence of nested simplicial complexes to a finite data set in order to detect the persistence of topological features over a range of scale parameters. One way to do this is by considering the sequence of Vietoris–Rips complexes of a finite set in a metric space indexed over all scale parameters.
If is a finite set in a metric space, then this construction is known as the Vietoris–Rips (or simply "Rips") filtration on , commonly denoted or .[2][3][4] The Rips filtration can be expressed as a functor from the real numbers (viewed as a poset category) to the category of simplicial complexes and simplicial maps, a subcategory of the category of topological spaces and continuous maps via the geometric realization functor.[5]
The Rips filtration is indexed over a single parameter, but we can capture more information (e.g., density) about the underlying data set by considering multiparameter filtrations. A filtration indexed by the product of two totally-ordered sets is known as a bifiltration, first introduced by Gunnar Carlsson and Afra Zomorodian in 2009.[6]
The degree-Rips bifiltration filters each simplicial complex in the Rips filtration by the degree of each vertex in the graph isomorphic to the 1-skeleton at each index. More formally, let be an element of and define to be the subgraph of the 1-skeleton of containing all vertices whose degree is at least . Subsequently building the maximal simplicial complex possible on this 1-skeleton, we obtain a complex . By doing this for all possible vertex degrees, and across all scale parameters in the Rips filtration, we extend the Rips construction to a bifiltration .[1]
Note that since the size of each complex will decrease as increases, we should identify the indexing set with , where is the opposite poset category of . Therefore the degree-Rips bifiltration can be viewed as a functor .[7]
The idea behind the degree-Rips bifiltration is that vertices of higher degree will correspond to higher density regions of the underlying data set. However, since degree-Rips does not depend on an arbitrary choice of a parameter (such as a pre-selected density parameter, which is a priori difficult to determine), it is a convenient tool for analyzing data.[8]
Applications to data analysis
editThe degree-Rips bifiltration possesses several properties that make it a useful tool in data analysis. For example, each of its skeleta has polynomial size; the k-dimensional skeleton of has simplices, where denotes an asymptotic upper bound.[7] Moreover, it has been shown that the degree-Rips bifiltration possesses reasonably strong stability properties with respect to perturbations of the underlying data set.[7] Further work has also been done examining the stable components and homotopy types of degree-Rips complexes.[9][10][11]
The software RIVET was created in order to visualize several multiparameter invariants (i.e., data structures that attempt to capture underlying geometric information of the data) of 2-parameter persistence modules, including the persistent homology modules of the degree-Rips bifiltration. These invariants include the Hilbert function, rank invariant, and fibered barcode.[1]
As a follow-up to the introduction of degree-Rips in their original 2015 paper, Lesnick and Wright showed in 2022 that a primary component of persistent homology computations (namely, computing minimal presentations and bigraded Betti numbers) can be achieved efficiently in a way that outperforms other persistent homology software.[12] Methods of improving algorithmic efficiency of multiparameter persistent homology have also been explored that suggest the possibility of substantial speed increases for data analysis tools such as RIVET.[13]
The degree-Rips bifiltration has been used for data analysis on random point clouds,[14] as well as for analyzing data clusters with respect to variations in density.[15][16][17] There has been some preliminary experimental analysis of the performance of degree-Rips with respect to outliers in particular, but this is an ongoing area of research as of February 2023.[18]
References
edit- ^ a b c Lesnick, Michael; Wright, Matthew (2015-12-01). "Interactive Visualization of 2-D Persistence Modules". arXiv:1512.00180 [math.AT].
- ^ Rabadan, Raul; Blumberg, Andrew J. (2019). Topological Data Analysis for Genomics and Evolution: Topology in Biology. Cambridge: Cambridge University Press. pp. 135–139. doi:10.1017/9781316671665. ISBN 978-1-107-15954-9. S2CID 242498045.
- ^ Oudot, Steve Y. (2015). Persistence theory : from quiver representations to data analysis. Providence, Rhode Island. p. 104. ISBN 978-1-4704-2545-6. OCLC 918149730.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ The structure and stability of persistence modules. Frédéric Chazal, Vin De Silva, Marc Glisse, Steve Y. Oudot. Switzerland. 2016. p. 66. ISBN 978-3-319-42545-0. OCLC 960458101.
{{cite book}}: CS1 maint: location missing publisher (link) CS1 maint: others (link) - ^ Botnan, Magnus Bakke; Lesnick, Michael (2022-03-27). "An Introduction to Multiparameter Persistence". p. 8. arXiv:2203.14289 [math.AT].
- ^ Carlsson, Gunnar; Zomorodian, Afra (2009-07-01). "The Theory of Multidimensional Persistence". Discrete & Computational Geometry. 42 (1): 71–93. doi:10.1007/s00454-009-9176-0. ISSN 1432-0444.
- ^ a b c Blumberg, Andrew J.; Lesnick, Michael (2022-10-17). "Stability of 2-Parameter Persistent Homology". Foundations of Computational Mathematics: 3, 8. arXiv:2010.09628. doi:10.1007/s10208-022-09576-6. ISSN 1615-3375. S2CID 224705357.
- ^ Schenck, Hal (2022). Algebraic foundations for applied topology and data analysis. Cham. p. 183. ISBN 978-3-031-06664-1. OCLC 1351750760.
{{cite book}}: CS1 maint: location missing publisher (link) - ^ Jardine, J. F. (September 2020). "Stable Components and Layers". Canadian Mathematical Bulletin. 63 (3): 562–576. arXiv:1905.05788. doi:10.4153/S000843951900064X. ISSN 0008-4395. S2CID 155092981.
- ^ Jardine, J. F. (2019). "Data and homotopy types". arXiv:1908.06323.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Jardine, J. F. (2020-10-26). "Persistent homotopy theory". arXiv:2002.10013 [math.AT].
- ^ Lesnick, Michael; Wright, Matthew (2022). "Computing Minimal Presentations and Bigraded Betti Numbers of 2-Parameter Persistent Homology". SIAM Journal on Applied Algebra and Geometry. 6 (2): 267–298. arXiv:1902.05708. doi:10.1137/20M1388425. S2CID 85499980.
- ^ Alonso; Kerber; Pritam (2023). "Filtration-Domination in Bifiltered Graphs". 2023 Proceedings of the Symposium on Algorithm Engineering and Experiments (ALENEX): 27–38. arXiv:2211.05574. doi:10.1137/1.9781611977561.ch3. ISBN 978-1-61197-756-1. S2CID 253447256.
- ^ Prabesh Paudel; Wang, Ken; Yuldasheva, Julie (2021). "Characteristics of Degree-Rips Bifiltrations from Random Geometric Point Clouds". doi:10.13140/RG.2.2.34156.28809.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Rolle, Alexander; Scoccola, Luis (2021-07-16). "Stable and consistent density-based clustering". arXiv:2005.09048 [math.ST].
- ^ Rolle, Alexander (2020). "Multi-parameter hierarchical clustering and beyond". Topological Data Analysis and Beyond Workshop at the 34th Conference on Neural Information Processing Systems.
- ^ Adamyk, Katharine L. M. (2021). "Stability for layer points". arXiv:2109.01701.
{{cite journal}}: Cite journal requires|journal=(help) - ^ Rolle, Alexander (2022-03-16). "The Degree-Rips Complexes of an Annulus with Outliers". arXiv:2203.08767 [math.AT].