Document Open Access Logo

The Universal 𝓁^p-Metric on Merge Trees

Authors Robert Cardona, Justin Curry , Tung Lam, Michael Lesnick

PDF
Thumbnail PDF

File

LIPIcs.SoCG.2022.24.pdf
  • Filesize: 0.84 MB
  • 20 pages

Document Identifiers

Author Details

Robert Cardona
  • University at Albany, State University of New York (SUNY), NY, USA
Justin Curry
  • University at Albany, State University of New York (SUNY), NY, USA
Tung Lam
  • University at Albany, State University of New York (SUNY), NY, USA
Michael Lesnick
  • University at Albany, State University of New York (SUNY), NY, USA

Funding

  • Curry, Justin: Supported by NSF CCF-1850052 and NASA 80GRC020C0016.

Acknowledgements

While Håvard Bjerkevik was not directly involved in this project, he has had a major influence on it, via his collaboration with ML on presentation distances for multiparameter persistence modules [Bjerkevik and Lesnick, 2021]. In particular, Håvard kindly agreed to share an early draft of [Bjerkevik and Lesnick, 2021] with our group in July 2020, which inspired many of the ideas in our paper.

Cite AsGet BibTex

Robert Cardona, Justin Curry, Tung Lam, and Michael Lesnick. The Universal 𝓁^p-Metric on Merge Trees. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 24:1-24:20, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.SoCG.2022.24

Abstract

Adapting a definition given by Bjerkevik and Lesnick for multiparameter persistence modules, we introduce an 𝓁^p-type extension of the interleaving distance on merge trees. We show that our distance is a metric, and that it upper-bounds the p-Wasserstein distance between the associated barcodes. For each p ∈ [1,∞], we prove that this distance is stable with respect to cellular sublevel filtrations and that it is the universal (i.e., largest) distance satisfying this stability property. In the p = ∞ case, this gives a novel proof of universality for the interleaving distance on merge trees.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Algebraic topology
  • Theory of computation → Unsupervised learning and clustering
  • Theory of computation → Computational geometry
Keywords
  • merge trees
  • hierarchical clustering
  • persistent homology
  • Wasserstein distances
  • interleavings

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Pankaj K Agarwal, Kyle Fox, Abhinandan Nath, Anastasios Sidiropoulos, and Yusu Wang. Computing the Gromov-Hausdorff distance for metric trees. ACM Transactions on Algorithms (TALG), 14(2):1-20, 2018. URL: https://doi.org/10.1145/3185466.
  2. Ulrich Bauer. The space of Reeb graphs. Workshop on Topology, Computation, and Data Analysis, Schloss Dagstuhl, 2019. Google Scholar
  3. Ulrich Bauer, Magnus Bakke Botnan, and Benedikt Fluhr. Universality of the bottleneck distance for extended persistence diagrams. arXiv preprint, 2020. URL: http://arxiv.org/abs/2007.01834.
  4. Ulrich Bauer, Xiaoyin Ge, and Yusu Wang. Measuring distance between Reeb graphs. In Proceedings of the thirtieth annual symposium on Computational geometry, pages 464-473, 2014. URL: https://doi.org/10.1145/2582112.2582169.
  5. Ulrich Bauer, Claudia Landi, and Facundo Mémoli. The Reeb graph edit distance is universal. Foundations of Computational Mathematics, pages 1-24, 2020. URL: https://doi.org/10.1007/s10208-020-09488-3.
  6. Ulrich Bauer and Michael Lesnick. Persistence diagrams as diagrams: A categorification of the stability theorem. In Topological Data Analysis, pages 67-96. Springer International Publishing, 2020. URL: https://doi.org/10.1007/978-3-030-43408-3_3.
  7. Ulrich Bauer, Elizabeth Munch, and Yusu Wang. Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs. In 31st International Symposium on Computational Geometry (SoCG 2015). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2015. URL: https://doi.org/10.4230/LIPIcs.SOCG.2015.461.
  8. Ulrich J Bauer, Håvard Bakke Bjerkevik, and Benedikt Fluhr. Quasi-universality of Reeb graph distances. arXiv preprint, 2021. URL: http://arxiv.org/abs/1705.01690.
  9. Håvard Bakke Bjerkevik and Michael Lesnick. 𝓁^p-distances on multiparameter persistence modules. arXiv preprint, 2021. URL: http://arxiv.org/abs/2106.13589.
  10. Andrew J Blumberg and Michael Lesnick. Universality of the homotopy interleaving distance. arXiv preprint, 2017. URL: http://arxiv.org/abs/1705.01690.
  11. Brian Bollen, Erin W. Chambers, Joshua A. Levine, and Elizabeth Munch. Reeb graph metrics from the ground up. arXiv preprint, 2021. URL: http://arxiv.org/abs/2110.05631.
  12. Peter Bubenik, Vin de Silva, and Jonathan Scott. Metrics for generalized persistence modules. Foundations of Computational Mathematics, 15(6):1501-1531, 2015. URL: https://doi.org/10.1007/s10208-014-9229-5.
  13. Peter Bubenik, Jonathan Scott, and Donald Stanley. Exact weights, path metrics, and algebraic Wasserstein distances. arXiv preprint, 2018. URL: http://arxiv.org/abs/1809.09654.
  14. Peter Bubenik and Jonathan A Scott. Categorification of persistent homology. Discrete & Computational Geometry, 51(3):600-627, 2014. URL: https://doi.org/10.1007/s00454-014-9573-x.
  15. Gabriel Cardona, Arnau Mir, Francesc Rosselló, Lucia Rotger, and David Sánchez. Cophenetic metrics for phylogenetic trees, after Sokal and Rohlf. BMC bioinformatics, 14(1):1-13, 2013. URL: https://doi.org/10.1186/1471-2105-14-3.
  16. Robert Cardona, Justin Curry, Tung Lam, and Michael Lesnick. The universal 𝓁^p-metric on merge trees. arXiv preprint, 2021. URL: http://arxiv.org/abs/2112.12165.
  17. Gunnar Carlsson and Facundo Mémoli. Characterization, stability and convergence of hierarchical clustering methods. Journal of Machine Learning Research, 11(47):1425-1470, 2010. URL: http://jmlr.org/papers/v11/carlsson10a.html.
  18. Hamish Carr, Jack Snoeyink, and Ulrike Axen. Computing contour trees in all dimensions. Computational Geometry, 24(2):75-94, 2003. URL: https://doi.org/10.1016/S0925-7721(02)00093-7.
  19. Hamish Carr, Jack Snoeyink, and Michiel van de Panne. Simplifying flexible isosurfaces using local geometric measures. In IEEE Visualization 2004, pages 497-504, 2004. URL: https://doi.org/10.1109/VISUAL.2004.96.
  20. Erin Wolf Chambers, Elizabeth Munch, and Tim Ophelders. A family of metrics from the truncated smoothing of Reeb graphs. In 37th International Symposium on Computational Geometry, 2021. URL: https://doi.org/10.4230/LIPIcs.SoCG.2021.22.
  21. Frédéric Chazal, David Cohen-Steiner, Marc Glisse, Leonidas J Guibas, and Steve Y Oudot. Proximity of persistence modules and their diagrams. In Proceedings of the twenty-fifth annual symposium on Computational geometry, pages 237-246, 2009. URL: https://doi.org/10.1145/1542362.1542407.
  22. Yen-Chi Chen. Generalized cluster trees and singular measures. The Annals of Statistics, 47(4):2174-2203, 2019. URL: https://doi.org/10.1214/18-AOS1744.
  23. David Cohen-Steiner, Herbert Edelsbrunner, John Harer, and Yuriy Mileyko. Lipschitz functions have L^p-stable persistence. Foundations of computational mathematics, 10(2):127-139, 2010. URL: https://doi.org/10.1007/s10208-010-9060-6.
  24. William Crawley-Boevey. Decomposition of pointwise finite-dimensional persistence modules. Journal of Algebra and its Applications, 14(05):1550066, 2015. URL: https://doi.org/10.1142/S0219498815500668.
  25. Justin Curry. The fiber of the persistence map for functions on the interval. Journal of Applied and Computational Topology, 2(3):301-321, 2018. URL: https://doi.org/10.1007/s41468-019-00024-z.
  26. Justin Curry, Haibin Hang, Washington Mio, Tom Needham, and Osman Berat Okutan. Decorated merge trees for persistent topology. To Appear in the Journal of Applied and Computational Topology, 2022. URL: http://arxiv.org/abs/2103.15804.
  27. Justin Michael Curry. Sheaves, Cosheaves and Applications. PhD thesis, University of Pennsylvania, 2014. Google Scholar
  28. Vin de Silva, Elizabeth Munch, and Amit Patel. Categorified Reeb graphs. Discrete & Computational Geometry, 55(4):854-906, 2016. URL: https://doi.org/10.1007/s00454-016-9763-9.
  29. Vin de Silva, Elizabeth Munch, and Anastasios Stefanou. Theory of interleavings on categories with a flow. Theory and Applications of Categories, 33(21):583-607, 2018. URL: http://www.tac.mta.ca/tac/volumes/33/21/33-21.pdf.
  30. Barbara Di Fabio and Claudia Landi. The edit distance for Reeb graphs of surfaces. Discrete & Computational Geometry, 55(2):423-461, 2016. URL: https://doi.org/10.1007/s00454-016-9758-6.
  31. Thomas Duquesne and Jean-François Le Gall. Random trees, Lévy processes and spatial branching processes. Number 281 in Astérisque. Société mathématique de France, 2002. URL: http://www.numdam.org/item/AST_2002__281__R1_0/.
  32. Elena Farahbakhsh Touli. Fréchet-like distances between two rooted trees. Journal of Algorithms and Computation, 53(1):1-12, 2021. URL: https://doi.org/10.22059/JAC.2021.81145.
  33. Elena Farahbakhsh Touli and Yusu Wang. FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees. In European Symposium on Algorithms, 2019. URL: https://doi.org/10.4230/LIPIcs.ESA.2019.83.
  34. Christoph Flamm, Ivo L. Hofacker, Peter F. Stadler, and Michael T. Wolfinger. Barrier trees of degenerate landscapes. Zeitschrift für Physikalische Chemie, 2002. URL: https://doi.org/10.1524/zpch.2002.216.2.155.
  35. Ellen Gasparovic, Elizabeth Munch, Steve Oudot, Katharine Turner, Bei Wang, and Yusu Wang. Intrinsic interleaving distance for merge trees. arXiv preprint, July 2019. URL: http://arxiv.org/abs/1908.00063.
  36. Christopher Gold and Sean Cormack. Spatially ordered networks and topographic reconstructions. International Journal of Geographical Information Systems, 1(2):137-148, 1987. URL: https://doi.org/10.1080/02693798708927800.
  37. John A. Hartigan . Consistency of single linkage for high-density clusters. Journal of the American Statistical Association, 76(374):388-394, 1981. URL: https://doi.org/10.1080/01621459.1981.10477658.
  38. Masaki Kashiwara and Pierre Schapira. Persistent homology and microlocal sheaf theory. Journal of Applied and Computational Topology, 2(1):83-113, 2018. URL: https://doi.org/10.1007/s41468-018-0019-z.
  39. In So Kweon and Takeo Kanade . Extracting topographic terrain features from elevation maps. CVGIP: Image Understanding, 59(2):171-182, 1994. URL: https://doi.org/10.1006/ciun.1994.1011.
  40. Michael Lesnick. The theory of the interleaving distance on multidimensional persistence modules. Foundations of Computational Mathematics, 15(3):613-650, 2015. URL: https://doi.org/10.1007/s10208-015-9255-y.
  41. Dmitriy Morozov, Kenes Beketayev, and Gunther Weber. Interleaving distance between merge trees. Proceedings of Topology-Based Methods in Visualization, 2013. Google Scholar
  42. Elizabeth Munch and Anastasios Stefanou. The l^∞-cophenetic metric for phylogenetic trees as an interleaving distance. In Research in Data Science, pages 109-127. Springer International Publishing, 2019. URL: https://doi.org/10.1007/978-3-030-11566-1_5.
  43. Amit Patel. Generalized persistence diagrams. Journal of Applied and Computational Topology, 1(3):397-419, 2018. URL: https://doi.org/10.1007/s41468-018-0012-6.
  44. Daniel Perez. On C⁰-persistent homology and trees. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.02634.
  45. Daniel Perez. On the persistent homology of almost surely C⁰ stochastic processes. arXiv preprint, 2020. URL: http://arxiv.org/abs/2012.09459.
  46. Mathieu Pont, Jules Vidal, Julie Delon, and Julien Tierny. Wasserstein distances, geodesics and barycenters of merge trees. IEEE Transactions on Visualization and Computer Graphics, 28(1):291-301, 2021. URL: https://doi.org/10.1109/TVCG.2021.3114839.
  47. Andrew Robinson and Katharine Turner. Hypothesis testing for topological data analysis. Journal of Applied and Computational Topology, 1(2):241-261, December 2017. URL: https://doi.org/10.1007/s41468-017-0008-7.
  48. Luis N Scoccola. Locally persistent categories and metric properties of interleaving distances. PhD thesis, The University of Western Ontario, 2020. Google Scholar
  49. Primoz Skraba and Katharine Turner. Wasserstein stability for persistence diagrams. arXiv preprint, 2021. URL: http://arxiv.org/abs/2006.16824.
  50. Raghavendra Sridharamurthy, Talha Bin Masood, Adhitya Kamakshidasan, and Vijay Natarajan. Edit distance between merge trees. IEEE Transactions on Visualization and Computer Graphics, 26(3):1518-1531, 2020. URL: https://doi.org/10.1109/TVCG.2018.2873612.
  51. Raghavendra Sridharamurthy and Vijay Natarajan. Comparative analysis of merge trees using local tree edit distance. IEEE Transactions on Visualization and Computer Graphics, 2021. Google Scholar
  52. Katharine Turner. Medians of populations of persistence diagrams. Homology, Homotopy and Applications, 22(1):255-282, 2020. URL: https://doi.org/10.4310/HHA.2020.v22.n1.a15.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact