Probabilistic convergence and stability of random mapper graphs

A. Brown, O. Bobrowski, E. Munch, B. Wang, Journal of Applied and Computational Topology (2020).

Download
OA 2020_JourApplCompTopology_Brown.pdf 2.09 MB

Journal Article | Epub ahead of print | English
Author
Brown, AdamIST Austria; Bobrowski, Omer; Munch, Elizabeth; Wang, Bei
Department
Abstract
We study the probabilistic convergence between the mapper graph and the Reeb graph of a topological space X equipped with a continuous function f:X→R. 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 R. We then introduce a variant of the classic mapper graph of Singh et al. (in: Eurographics symposium on point-based graphics, 2007), referred to as the enhanced mapper graph, and demonstrate that such a construction approximates the Reeb graph of (X,f) when it is applied to points randomly sampled from a probability density function concentrated on (X,f). Our techniques are based on the interleaving distance of constructible cosheaves and topological estimation via kernel density estimates. Following Munch and Wang (In: 32nd international symposium on computational geometry, volume 51 of Leibniz international proceedings in informatics (LIPIcs), Dagstuhl, Germany, pp 53:1–53:16, 2016), we first show that the mapper graph of (X,f), a constructible R-space (with a fixed open cover), approximates the Reeb graph of the same space. We then construct an isomorphism between the mapper of (X,f) to the mapper of a super-level set of a probability density function concentrated on (X,f). Finally, building on the approach of Bobrowski et al. (Bernoulli 23(1):288–328, 2017b), 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.
Publishing Year
Date Published
2020-12-17
Journal Title
Journal of Applied and Computational Topology
Acknowledgement
AB was supported in part by the European Union’s Horizon 2020 research and innovation programme under the Marie Sklodowska-Curie GrantAgreement No. 754411 and NSF IIS-1513616. OB was supported in part by the Israel Science Foundation, Grant 1965/19. BW was supported in part by NSF IIS-1513616 and DBI-1661375. EM was supported in part by NSF CMMI-1800466, DMS-1800446, and CCF-1907591.We would like to thank the Institute for Mathematics and its Applications for hosting a workshop titled Bridging Statistics and Sheaves in May 2018, where this work was conceived. Open Access funding provided by Institute of Science and Technology (IST Austria).
IST-REx-ID

Cite this

Brown A, Bobrowski O, Munch E, Wang B. Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology. 2020. doi:10.1007/s41468-020-00063-x
Brown, A., Bobrowski, O., Munch, E., & Wang, B. (2020). Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology. Springer Nature. https://doi.org/10.1007/s41468-020-00063-x
Brown, Adam, Omer Bobrowski, Elizabeth Munch, and Bei Wang. “Probabilistic Convergence and Stability of Random Mapper Graphs.” Journal of Applied and Computational Topology. Springer Nature, 2020. https://doi.org/10.1007/s41468-020-00063-x.
A. Brown, O. Bobrowski, E. Munch, and B. Wang, “Probabilistic convergence and stability of random mapper graphs,” Journal of Applied and Computational Topology. Springer Nature, 2020.
Brown A, Bobrowski O, Munch E, Wang B. 2020. Probabilistic convergence and stability of random mapper graphs. Journal of Applied and Computational Topology.
Brown, Adam, et al. “Probabilistic Convergence and Stability of Random Mapper Graphs.” Journal of Applied and Computational Topology, Springer Nature, 2020, doi:10.1007/s41468-020-00063-x.
All files available under the following license(s):
Creative Commons Attribution 4.0 International Public License (CC-BY 4.0):
Main File(s)
Access Level
OA Open Access
Date Uploaded
2021-02-11
MD5 Checksum
3f02e9d47c428484733da0f588a3c069


Export

Marked Publications

Open Data IST Research Explorer

Sources

arXiv 1909.03488

Search this title in

Google Scholar