Probabilistic convergence and stability of random mapper graphs

DOI10.1007/S41468-020-00063-XMaRDI QIDQ2240090zbMATH OpenOpenAlexFDO

Authors Adam Brown, Omer Bobrowski, Elizabeth Munch, Bei Wang

Publication date 5 November 2021

Published in Journal of Applied and Computational Topology (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1909.03488

zbMATH Keywords

computational topologytopological data analysisReeb graphReeb spacemapperconstructible cosheaves

Mathematics Subject Classification ID

Persistent homology and applications, topological data analysis (55N31) Topological data analysis (62R40)

Abstract: We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space $mathbbX$ equipped with a continuous function $f:mathbbXightarrowmathbbR$. We first give a categorification of the mapper graph and the Reeb graph by interpreting them in terms of cosheaves and stratified covers of the real line $mathbbR$. We then introduce a variant of the classic mapper graph of Singh et al.~(2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of $(mathbbX,f)$ when it is applied to points randomly sampled from a probability density function concentrated on $(mathbbX,f)$. Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (2018), we first show that the mapper graph of $(mathbbX,f)$, a constructible $mathbbR$-space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of $(mathbbX,f)$ to the mapper of a super-level set of a probability density function concentrated on $(mathbbX,f)$. Finally, building on the approach of Bobrowski et al.~(2017), we show that, with high probability, we can recover the mapper of the super-level set given a sufficiently large sample. Our work is the first to consider the mapper construction using the theory of cosheaves in a probabilistic setting. It is part of an ongoing effort to combine sheaf theory, probability, and statistics, to support topological data analysis with random data.

Recommendations

• Structure and stability of the 1-dimensional mapper
• Convergence between categorical representations of Reeb space and mapper
• Structure and stability of the one-dimensional Mapper
• Statistical analysis of Mapper for stochastic and multivariate filters
• Statistical analysis and parameter selection for Mapper

Cites work

• scientific article; zbMATH DE number 753667 (Why is no real title available?)
• scientific article; zbMATH DE number 3106699 (Why is no real title available?)
• A complete characterization of the one-dimensional intrinsic Čech persistence diagrams for metric graphs
• A topological view of unsupervised learning from noisy data
• Barcodes: The persistent topology of data
• Categorified Reeb graphs
• Computing contour trees in all dimensions
• Confidence sets for persistence diagrams
• Convergence between categorical representations of Reeb space and mapper
• Convergence rates for persistence diagram estimation in topological data analysis
• Extending persistence using Poincaré and Lefschetz duality
• Finding the homology of submanifolds with high confidence from random samples
• Gromov-Hausdorff approximation of filament structure using Reeb-type graph (extended abstract)
• Hierarchical Morse-Smale complexes for piecewise linear 2-manifolds
• Limit theorems for Betti numbers of random simplicial complexes
• Limit theorems for persistence diagrams
• Limit theorems for point processes under geometric constraints (and topological crackle)
• Maximally persistent cycles in random geometric complexes
• Measuring distance between Reeb graphs (extended abstract)
• Measuring the distance between merge trees
• Morse-Smale complexes for piecewise linear 3-manifolds
• Multinerves and Helly numbers of acyclic families
• Multiscale mapper: topological summarization via codomain covers
• PERSISTENCE BARCODES FOR SHAPES
• Random geometric complexes in the thermodynamic regime
• Reeb graphs for shape analysis and applications
• Reeb spaces of piecewise linear mappings
• Robust topological inference: distance to a measure and kernel distance
• Scalar field analysis over point cloud data
• Statistical analysis and parameter selection for Mapper
• Structure and stability of the one-dimensional Mapper
• The fundamental category of a stratified space
• Topological analysis of nerves, Reeb spaces, mappers, and multiscale mappers
• Topological consistency via kernel estimation
• Topological persistence and simplification

Cited in

(17)

• Statistical analysis and parameter selection for Mapper
• scientific article; zbMATH DE number 7307480 (Why is no real title available?)
• Mapper–Type Algorithms for Complex Data and Relations
• Structure and stability of the 1-dimensional mapper
• Structure and stability of the one-dimensional Mapper
• Convergence between categorical representations of Reeb space and mapper
• Multiscale mapper: topological summarization via codomain covers
• Functorial manifold learning
• A family of metrics from the truncated smoothing of Reeb graphs
• scientific article; zbMATH DE number 1245629 (Why is no real title available?)
• A fast algorithm for constructing topological structure in large data
• Certified mapper: repeated testing for acyclicity and obstructions to the nerve lemma
• Measure-theoretic Reeb graphs and Reeb spaces
• Topological mapper for 3D volumetric images
• Stitch fix for mapper and topological gains
• Statistical analysis of Mapper for stochastic and multivariate filters
• Bounding the interleaving distance for mapper graphs with a loss function

Describes a project that uses

Uses Software

• msr

This page was built for publication: Probabilistic convergence and stability of random mapper graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2240090)