Document Open Access Logo

Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams

Authors Samantha Chen, Yusu Wang

PDF
Thumbnail PDF

File

LIPIcs.SEA.2021.14.pdf
  • Filesize: 1.19 MB
  • 19 pages

Document Identifiers

Author Details

Samantha Chen
  • University of California at San Diego, La Jolla, CA, USA
Yusu Wang
  • University of California at San Diego, La Jolla, CA, USA

Funding

This work is partially supported by National Science Foundation (NSF) via grants OAC-2039794 and IIS- 2050360.

Acknowledgements

We want to thank Chen Cai for providing the reddit-binary and ModelNet10 datasets used in the experiments.

Cite As Get BibTex

Samantha Chen and Yusu Wang. Approximation Algorithms for 1-Wasserstein Distance Between Persistence Diagrams. In 19th International Symposium on Experimental Algorithms (SEA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 190, pp. 14:1-14:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021) https://doi.org/10.4230/LIPIcs.SEA.2021.14

Abstract

Recent years have witnessed a tremendous growth using topological summaries, especially the persistence diagrams (encoding the so-called persistent homology) for analyzing complex shapes. Intuitively, persistent homology maps a potentially complex input object (be it a graph, an image, or a point set and so on) to a unified type of feature summary, called the persistence diagrams. One can then carry out downstream data analysis tasks using such persistence diagram representations. A key problem is to compute the distance between two persistence diagrams efficiently. In particular, a persistence diagram is essentially a multiset of points in the plane, and one popular distance is the so-called 1-Wasserstein distance between persistence diagrams. In this paper, we present two algorithms to approximate the 1-Wasserstein distance for persistence diagrams in near-linear time. These algorithms primarily follow the same ideas as two existing algorithms to approximate optimal transport between two finite point-sets in Euclidean spaces via randomly shifted quadtrees. We show how these algorithms can be effectively adapted for the case of persistence diagrams. Our algorithms are much more efficient than previous exact and approximate algorithms, both in theory and in practice, and we demonstrate its efficiency via extensive experiments. They are conceptually simple and easy to implement, and the code is publicly available in github.

Subject Classification

ACM Subject Classification
  • Theory of computation → Approximation algorithms analysis
Keywords
  • persistence diagrams
  • approximation algorithms
  • Wasserstein distance
  • optimal transport

Metrics

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

Supplementary Materials

References

  1. Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. Scalable nearest neighbor search for optimal transport. arXiv preprint arXiv:1910.04126, 2019. Google Scholar
  2. Yair Bartal. Probabilistic approximation of metric spaces and its algorithmic applications. In Proceedings of 37th Conference on Foundations of Computer Science, pages 184-193. IEEE, 1996. Google Scholar
  3. Yair Bartal. On approximating arbitrary metrices by tree metrics. STOC, 98:161-168, 1998. Google Scholar
  4. Dimitri Bertsekas. The auction algorithm: A distributed relaxation method for the assignment problem. Annals of Operations Research, 14(1):105-123, 1988. Google Scholar
  5. Mickaël Buchet, Yasuaki Hiraoka, and Ippei Obayashi. Persistence homology and material and informatics. In Isao Tanaka, editor, Nanoinformatics, pages 75-95. Spring Singapore, Singapore, 2018. URL: https://doi.org/10.1007/978-981-10-7617-6_5.
  6. Chen Cai and Yusu Wang. Understanding the power of persistence pairing via permutation test. arXiv preprint arXiv:2001.06058, 2020. Google Scholar
  7. Moses Charikar. Similarity estimation techniques from rounding algorithms. In Proceedings of the thirty-fourth annual ACM symposium on theory of computing, pages 2292-2300. ACM, 2002. Google Scholar
  8. Frédéric Chazal, David Cohen-Steiner, Leonidas J. Guibas, Facundo Mémoli, and Steve Y. Oudot. Gromov-hausdorff stable signatures for shapes using persistence. Computer Graphics Forum, 28(5):1393-1403, 2009. Google Scholar
  9. David Cohen-Steiner, Herbert Edelsbrunner, and John Harer. Stability of persistence diagrams. Discrete Comput. Geom., 37(1):103-120, 2007. Google Scholar
  10. Herbert Edelsbrunner and John Harer. Computational topology: an introduction. American Mathematical Society, 2010. Google Scholar
  11. Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. Discrete Comput. Gemo., 28:511-533, 2002. Google Scholar
  12. Rémi Flamary and Nicolas Courty. Pot: Python optimal transport library, 2017. URL: https://pythonot.github.io/.
  13. Jennifer Gamble and Giseon Ho. Exploring uses of persistence homology for statistical analysis of landmark-based shape data. Journal of Multivariate Analysis, 101(9):2184-2199, 2010. Google Scholar
  14. Yasuaki Hiraoka, Takenobu Nakamura, Akihiko Hirata, Emerson G. Escolar, Kaname Matsue, and Yasumasa Nishiura. Hierarchical structures of amorphous solids characterized by persistent homology. Proceedings of the National Academy of Sciences, 113(26):7035-7040, 2016. URL: https://doi.org/10.1073/pnas.1520877113.
  15. Piotr Indyk and Nitin Thaper. Fast image retrieval via embeddings. In 3rd international workshop on statistical and computational theories of vision, volume 2, page 5, 2003. Google Scholar
  16. Bahman Kalantari and Iraj Kalantari. A linear-time algorithm for minimum cost flow on undirected one-trees. Combinatorics Advances, pages 217-223, 1995. Google Scholar
  17. Lida Kanari, Paweł Dłotko, Martina Scolamiero, Ran Levi, Julian Shillcock, Kathryn Hess, and Henry Markram. A topological representation of branching neuronal morphologies. Neuroinformatics, 16(1):3-13, 2018. URL: https://doi.org/10.1007/s12021-017-9341-1.
  18. Michael Kerber, Dimitriy Morozov, and Arnur Nigmetov. Geometry helps to compare persistence diagrams. Journal of Experimental Algorithmics(JEA), 22:1-20, 2017. Google Scholar
  19. Jon Kleinberg and Eva Tardos. Approximation algorithms for classification problems with pairwise relationships: Metric labeling and markov random fields. Journal of the ACM (JACM), 49(5):616-639, 2002. Google Scholar
  20. Harold Kuhn. The hungarian method for the assignment problem. Naval research logistics quarterly, 2(1-2):83-97, 1955. Google Scholar
  21. Théo Lacombe, Marco Cuturi, and Steve Oudot. Large scale computation of means and clusters for persistence diagrams using optimal transport, 2018. URL: http://arxiv.org/abs/1805.08331.
  22. Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. Tree-sliced approximation of wasserstein distances. arXiv preprint arXiv:1902.00342, 2019. Google Scholar
  23. Yongjin Lee, Senja D. Barthel, Paweł Dłotko, S. Mohamad Moosavi, Kathryn Hess, and Berend Smit. Quantifying similarity of pore-geometry in nanoporous materials. Nat Commun., 8:15396, 2017. URL: https://doi.org/10.1038/ncomms15396.
  24. Yanjie Li, Dingkang Wang, Giorgio Ascoli, Partha Mitra, and Yusu Wang. Metrics for comparing neuronal tree shapes based on persistent homology. PLOS One, 12(8):1-24, 2017. URL: https://doi.org/10.1371/journal.pone.0182184.
  25. Clément Maria, Jean-Daniel Boissonat, Marc Glisse, and Mariette Yvinec. The gudhi library: simplicial complexes and persistent homology, 2014. URL: http://gudhi.gforge.inria.fr/python/latest/index.html.
  26. Dimitriy Morozov. Dionysus, 2010. URL: https://mrzv.org/software/dionysus.
  27. Ahmet Sacan, Ozgur Ozturk, Hakan Ferhatosmanoglu, and Yusu Wang. Lfm-pro: a tool for detecting significant local structural sites in proteins. Bioinformatics, 23(6):709-716, 2007. Google Scholar
  28. Ryoma Sato, Makoto Yamada, and Hisashi Kashima. Fast unbalanced optimal transport on tree. arXiv preprint arXiv:2006.02703, 2020. Google Scholar
  29. Primoz Skraba, Maks Ovsjanikov, Frédéric Chazal, and Leonidas Guibas. Persistence-based segmentation of deformable shapes. In 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition - Workshops, pages 45-52, 2010. URL: https://doi.org/10.1109/CVPRW.2010.5543285.
  30. Zhirong Wu, Shuran Song, Aditya Khosla, Fisher Yu, Linguang Zhang, Xiaoou Tang, and Jianxiong Xiao. 3d shapenets: A deep representation for volumentric shapes. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 1912-1920, 2015. Google Scholar
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 About DROPS Imprint Privacy Contact