Computing Zigzag Persistence on Graphs in Near-Linear Time

Authors Tamal K. Dey, Tao Hou



PDF
Thumbnail PDF

File

LIPIcs.SoCG.2021.30.pdf
  • Filesize: 0.76 MB
  • 15 pages

Document Identifiers

Author Details

Tamal K. Dey
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA
Tao Hou
  • Department of Computer Science, Purdue University, West Lafayette, IN, USA

Cite AsGet BibTex

Tamal K. Dey and Tao Hou. Computing Zigzag Persistence on Graphs in Near-Linear Time. In 37th International Symposium on Computational Geometry (SoCG 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 189, pp. 30:1-30:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.SoCG.2021.30

Abstract

Graphs model real-world circumstances in many applications where they may constantly change to capture the dynamic behavior of the phenomena. Topological persistence which provides a set of birth and death pairs for the topological features is one instrument for analyzing such changing graph data. However, standard persistent homology defined over a growing space cannot always capture such a dynamic process unless shrinking with deletions is also allowed. Hence, zigzag persistence which incorporates both insertions and deletions of simplices is more appropriate in such a setting. Unlike standard persistence which admits nearly linear-time algorithms for graphs, such results for the zigzag version improving the general O(m^ω) time complexity are not known, where ω < 2.37286 is the matrix multiplication exponent. In this paper, we propose algorithms for zigzag persistence on graphs which run in near-linear time. Specifically, given a filtration with m additions and deletions on a graph with n vertices and edges, the algorithm for 0-dimension runs in O(mlog² n+mlog m) time and the algorithm for 1-dimension runs in O(mlog⁴ n) time. The algorithm for 0-dimension draws upon another algorithm designed originally for pairing critical points of Morse functions on 2-manifolds. The algorithm for 1-dimension pairs a negative edge with the earliest positive edge so that a 1-cycle containing both edges resides in all intermediate graphs. Both algorithms achieve the claimed time complexity via dynamic graph data structures proposed by Holm et al. In the end, using Alexander duality, we extend the algorithm for 0-dimension to compute the (p-1)-dimensional zigzag persistence for ℝ^p-embedded complexes in O(mlog² n+mlog m+nlog n) time.

Subject Classification

ACM Subject Classification
  • Theory of computation → Computational geometry
  • Mathematics of computing → Algebraic topology
Keywords
  • persistent homology
  • zigzag persistence
  • graph filtration
  • dynamic networks

Metrics

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

References

  1. Pankaj K. Agarwal, Herbert Edelsbrunner, John Harer, and Yusu Wang. Extreme elevation on a 2-manifold. Discrete & Computational Geometry, 36(4):553-572, 2006. Google Scholar
  2. Josh Alman and Virginia Vassilevska Williams. A refined laser method and faster matrix multiplication. In Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 522-539. SIAM, 2021. Google Scholar
  3. Gunnar Carlsson and Vin de Silva. Zigzag persistence. Foundations of Computational Mathematics, 10(4):367-405, 2010. Google Scholar
  4. Gunnar Carlsson, Vin de Silva, and Dmitriy Morozov. Zigzag persistent homology and real-valued functions. In Proceedings of the Twenty-Fifth Annual Symposium on Computational Geometry, pages 247-256, 2009. Google Scholar
  5. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, 3rd Edition. MIT Press, 2009. URL: http://mitpress.mit.edu/books/introduction-algorithms.
  6. Tamal K. Dey. Computing height persistence and homology generators in ℝ³ efficiently. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2649-2662. SIAM, 2019. Google Scholar
  7. Tamal K. Dey and Tao Hou. Computing zigzag persistence on graphs in near-linear time. arXiv preprint, 2021. URL: http://arxiv.org/abs/2103.07353.
  8. Tamal K. Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In Proceedings of the Fourteenth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 2587-2606. SIAM, 2020. Google Scholar
  9. Herbert Edelsbrunner and Michael Kerber. Alexander duality for functions: the persistent behavior of land and water and shore. In Proceedings of the Twenty-Eighth Annual Symposium on Computational Geometry, pages 249-258, 2012. Google Scholar
  10. Herbert Edelsbrunner, David Letscher, and Afra Zomorodian. Topological persistence and simplification. In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 454-463. IEEE, 2000. Google Scholar
  11. Loukas Georgiadis, Haim Kaplan, Nira Shafrir, Robert E. Tarjan, and Renato F. Werneck. Data structures for mergeable trees. ACM Transactions on Algorithms (TALG), 7(2):1-30, 2011. Google Scholar
  12. Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup. Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity. Journal of the ACM (JACM), 48(4):723-760, 2001. Google Scholar
  13. Petter Holme and Jari Saramäki. Temporal networks. Physics Reports, 519(3):97-125, 2012. Google Scholar
  14. Woojin Kim and Facundo Memoli. Stable signatures for dynamic graphs and dynamic metric spaces via zigzag persistence. arXiv preprint, 2017. URL: http://arxiv.org/abs/1712.04064.
  15. Clément Maria and Steve Y. Oudot. Zigzag persistence via reflections and transpositions. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, pages 181-199. SIAM, 2014. Google Scholar
  16. Nikola Milosavljević, Dmitriy Morozov, and Primoz Skraba. Zigzag persistent homology in matrix multiplication time. In Proceedings of the Twenty-Seventh Annual Symposium on Computational Geometry, pages 216-225, 2011. Google Scholar
  17. James R. Munkres. Elements of Algebraic Topology. CRC Press, 2018. Google Scholar
  18. Benjamin Schweinhart. Statistical Topology of Embedded Graphs. PhD thesis, Princeton University Press, 2015. Google Scholar
  19. Joakim Skarding, Bogdan Gabrys, and Katarzyna Musial. Foundations and modelling of dynamic networks using dynamic graph neural networks: A survey. arXiv preprint, 2020. URL: http://arxiv.org/abs/2005.07496.
  20. Afra Zomorodian and Gunnar Carlsson. Computing persistent homology. Discrete & Computational Geometry, 33(2):249-274, 2005. 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