Search Results

Documents authored by Dey, Tamal K.

Document
DOI: 10.4230/LIPIcs.SoCG.2024.49
Computing Zigzag Vineyard Efficiently Including Expansions and Contractions

Authors: Tamal K. Dey and Tao Hou

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
Vines and vineyard connecting a stack of persistence diagrams have been introduced in the non-zigzag setting by Cohen-Steiner et al. [Cohen-Steiner et al., 2006]. We consider computing these vines over changing filtrations for zigzag persistence while incorporating two more operations: expansions and contractions in addition to the transpositions considered in the non-zigzag setting. Although expansions and contractions can be implemented in quadratic time in the non-zigzag case by utilizing the linear-time transpositions, it is not obvious how they can be carried out under the zigzag framework with the same complexity. While transpositions alone can be easily conducted in linear time using the recent FastZigzag algorithm [Tamal K. Dey and Tao Hou, 2022], expansions and contractions pose difficulty in breaking the barrier of cubic complexity [Dey and Hou, 2022]. Our main result is that, the half-way constructed up-down filtration in the FastZigzag algorithm indeed can be used to achieve linear time complexity for transpositions and quadratic time complexity for expansions and contractions, matching the time complexity of all corresponding operations in the non-zigzag case.
Cite as

Tamal K. Dey and Tao Hou. Computing Zigzag Vineyard Efficiently Including Expansions and Contractions. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 49:1-49:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.49,
  author =	{Dey, Tamal K. and Hou, Tao},
  title =	{{Computing Zigzag Vineyard Efficiently Including Expansions and Contractions}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{49:1--49:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.49},
  URN =		{urn:nbn:de:0030-drops-199942},
  doi =		{10.4230/LIPIcs.SoCG.2024.49},
  annote =	{Keywords: zigzag persistence, vines and vineyard, update operations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.50
Cup Product Persistence and Its Efficient Computation

Authors: Tamal K. Dey and Abhishek Rathod

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
It is well-known that the cohomology ring has a richer structure than homology groups. However, until recently, the use of cohomology in persistence setting has been limited to speeding up of barcode computations. Some of the recently introduced invariants, namely, persistent cup-length, persistent cup modules and persistent Steenrod modules, to some extent, fill this gap. When added to the standard persistence barcode, they lead to invariants that are more discriminative than the standard persistence barcode. In this work, we devise an O(d n⁴) algorithm for computing the persistent k-cup modules for all k ∈ {2, … , d}, where d denotes the dimension of the filtered complex, and n denotes its size. Moreover, we note that since the persistent cup length can be obtained as a byproduct of our computations, this leads to a faster algorithm for computing it for d ≥ 3. Finally, we introduce a new stable invariant called partition modules of cup product that is more discriminative than persistent cup modules and devise an O(c(d)n⁴) algorithm for computing it, where c(d) is subexponential in d.
Cite as

Tamal K. Dey and Abhishek Rathod. Cup Product Persistence and Its Efficient Computation. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 50:1-50:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.50,
  author =	{Dey, Tamal K. and Rathod, Abhishek},
  title =	{{Cup Product Persistence and Its Efficient Computation}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{50:1--50:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.50},
  URN =		{urn:nbn:de:0030-drops-199958},
  doi =		{10.4230/LIPIcs.SoCG.2024.50},
  annote =	{Keywords: Persistent cohomology, cup product, image persistence, persistent cup module}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2024.51
Efficient Algorithms for Complexes of Persistence Modules with Applications

Authors: Tamal K. Dey, Florian Russold, and Shreyas N. Samaga

Published in: LIPIcs, Volume 293, 40th International Symposium on Computational Geometry (SoCG 2024)

Abstract
We extend the persistence algorithm, viewed as an algorithm computing the homology of a complex of free persistence or graded modules, to complexes of modules that are not free. We replace persistence modules by their presentations and develop an efficient algorithm to compute the homology of a complex of presentations. To deal with inputs that are not given in terms of presentations, we give an efficient algorithm to compute a presentation of a morphism of persistence modules. This allows us to compute persistent (co)homology of instances giving rise to complexes of non-free modules. Our methods lead to a new efficient algorithm for computing the persistent homology of simplicial towers and they enable efficient algorithms to compute the persistent homology of cosheaves over simplicial towers and cohomology of persistent sheaves on simplicial complexes. We also show that we can compute the cohomology of persistent sheaves over arbitrary finite posets by reducing the computation to a computation over simplicial complexes.
Cite as

Tamal K. Dey, Florian Russold, and Shreyas N. Samaga. Efficient Algorithms for Complexes of Persistence Modules with Applications. In 40th International Symposium on Computational Geometry (SoCG 2024). Leibniz International Proceedings in Informatics (LIPIcs), Volume 293, pp. 51:1-51:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2024)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2024.51,
  author =	{Dey, Tamal K. and Russold, Florian and Samaga, Shreyas N.},
  title =	{{Efficient Algorithms for Complexes of Persistence Modules with Applications}},
  booktitle =	{40th International Symposium on Computational Geometry (SoCG 2024)},
  pages =	{51:1--51:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-316-4},
  ISSN =	{1868-8969},
  year =	{2024},
  volume =	{293},
  editor =	{Mulzer, Wolfgang and Phillips, Jeff M.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2024.51},
  URN =		{urn:nbn:de:0030-drops-199969},
  doi =		{10.4230/LIPIcs.SoCG.2024.51},
  annote =	{Keywords: Persistent (co)homology, Persistence modules, Sheaves, Presentations}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2023.25
Meta-Diagrams for 2-Parameter Persistence

Authors: Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang

Published in: LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023)

Abstract
We first introduce the notion of meta-rank for a 2-parameter persistence module, an invariant that captures the information behind images of morphisms between 1D slices of the module. We then define the meta-diagram of a 2-parameter persistence module to be the Möbius inversion of the meta-rank, resulting in a function that takes values from signed 1-parameter persistence modules. We show that the meta-rank and meta-diagram contain information equivalent to the rank invariant and the signed barcode. This equivalence leads to computational benefits, as we introduce an algorithm for computing the meta-rank and meta-diagram of a 2-parameter module M indexed by a bifiltration of n simplices in O(n³) time. This implies an improvement upon the existing algorithm for computing the signed barcode, which has O(n⁴) time complexity. This also allows us to improve the existing upper bound on the number of rectangles in the rank decomposition of M from O(n⁴) to O(n³). In addition, we define notions of erosion distance between meta-ranks and between meta-diagrams, and show that under these distances, meta-ranks and meta-diagrams are stable with respect to the interleaving distance. Lastly, the meta-diagram can be visualized in an intuitive fashion as a persistence diagram of diagrams, which generalizes the well-understood persistence diagram in the 1-parameter setting.
Cite as

Nate Clause, Tamal K. Dey, Facundo Mémoli, and Bei Wang. Meta-Diagrams for 2-Parameter Persistence. In 39th International Symposium on Computational Geometry (SoCG 2023). Leibniz International Proceedings in Informatics (LIPIcs), Volume 258, pp. 25:1-25:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{clause_et_al:LIPIcs.SoCG.2023.25,
  author =	{Clause, Nate and Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Bei},
  title =	{{Meta-Diagrams for 2-Parameter Persistence}},
  booktitle =	{39th International Symposium on Computational Geometry (SoCG 2023)},
  pages =	{25:1--25:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-273-0},
  ISSN =	{1868-8969},
  year =	{2023},
  volume =	{258},
  editor =	{Chambers, Erin W. and Gudmundsson, Joachim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.25},
  URN =		{urn:nbn:de:0030-drops-178754},
  doi =		{10.4230/LIPIcs.SoCG.2023.25},
  annote =	{Keywords: Multiparameter persistence modules, persistent homology, M\"{o}bius inversion, barcodes, computational topology, topological data analysis}
}
Document
DOI: 10.4230/LIPIcs.ESA.2022.43
Fast Computation of Zigzag Persistence

Authors: Tamal K. Dey and Tao Hou

Published in: LIPIcs, Volume 244, 30th Annual European Symposium on Algorithms (ESA 2022)

Abstract
Zigzag persistence is a powerful extension of the standard persistence which allows deletions of simplices besides insertions. However, computing zigzag persistence usually takes considerably more time than the standard persistence. We propose an algorithm called FastZigzag which narrows this efficiency gap. Our main result is that an input simplex-wise zigzag filtration can be converted to a cell-wise non-zigzag filtration of a Δ-complex with the same length, where the cells are copies of the input simplices. This conversion step in FastZigzag incurs very little cost. Furthermore, the barcode of the original filtration can be easily read from the barcode of the new cell-wise filtration because the conversion embodies a series of diamond switches known in topological data analysis. This seemingly simple observation opens up the vast possibilities for improving the computation of zigzag persistence because any efficient algorithm/software for standard persistence can now be applied to computing zigzag persistence. Our experiment shows that this indeed achieves substantial performance gain over the existing state-of-the-art softwares.
Cite as

Tamal K. Dey and Tao Hou. Fast Computation of Zigzag Persistence. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 43:1-43:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2022.43,
  author =	{Dey, Tamal K. and Hou, Tao},
  title =	{{Fast Computation of Zigzag Persistence}},
  booktitle =	{30th Annual European Symposium on Algorithms (ESA 2022)},
  pages =	{43:1--43:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-247-1},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{244},
  editor =	{Chechik, Shiri and Navarro, Gonzalo and Rotenberg, Eva and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2022.43},
  URN =		{urn:nbn:de:0030-drops-169813},
  doi =		{10.4230/LIPIcs.ESA.2022.43},
  annote =	{Keywords: zigzag persistence, persistent homology, fast computation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.34
Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications

Authors: Tamal K. Dey, Woojin Kim, and Facundo Mémoli

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
The notion of generalized rank invariant in the context of multiparameter persistence has become an important ingredient for defining interesting homological structures such as generalized persistence diagrams. Naturally, computing these rank invariants efficiently is a prelude to computing any of these derived structures efficiently. We show that the generalized rank over a finite interval I of a 𝐙²-indexed persistence module M is equal to the generalized rank of the zigzag module that is induced on a certain path in I tracing mostly its boundary. Hence, we can compute the generalized rank over I by computing the barcode of the zigzag module obtained by restricting the bifiltration inducing M to that path. If the bifiltration and I have at most t simplices and points respectively, this computation takes O(t^ω) time where ω ∈ [2,2.373) is the exponent of matrix multiplication. Among others, we apply this result to obtain an improved algorithm for the following problem. Given a bifiltration inducing a module M, determine whether M is interval decomposable and, if so, compute all intervals supporting its summands.
Cite as

Tamal K. Dey, Woojin Kim, and Facundo Mémoli. Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 34:1-34:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2022.34,
  author =	{Dey, Tamal K. and Kim, Woojin and M\'{e}moli, Facundo},
  title =	{{Computing Generalized Rank Invariant for 2-Parameter Persistence Modules via Zigzag Persistence and Its Applications}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{34:1--34:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.34},
  URN =		{urn:nbn:de:0030-drops-160420},
  doi =		{10.4230/LIPIcs.SoCG.2022.34},
  annote =	{Keywords: Multiparameter persistent homology, Zigzag persistent homology, Generalized Persistence Diagrams, M\"{o}bius inversion}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.35
Tracking Dynamical Features via Continuation and Persistence

Authors: Tamal K. Dey, Michał Lipiński, Marian Mrozek, and Ryan Slechta

Published in: LIPIcs, Volume 224, 38th International Symposium on Computational Geometry (SoCG 2022)

Abstract
Multivector fields and combinatorial dynamical systems have recently become a subject of interest due to their potential for use in computational methods. In this paper, we develop a method to track an isolated invariant set - a salient feature of a combinatorial dynamical system - across a sequence of multivector fields. This goal is attained by placing the classical notion of the "continuation" of an isolated invariant set in the combinatorial setting. In particular, we give a "Tracking Protocol" that, when given a seed isolated invariant set, finds a canonical continuation of the seed across a sequence of multivector fields. In cases where it is not possible to continue, we show how to use zigzag persistence to track homological features associated with the isolated invariant sets. This construction permits viewing continuation as a special case of persistence.
Cite as

Tamal K. Dey, Michał Lipiński, Marian Mrozek, and Ryan Slechta. Tracking Dynamical Features via Continuation and Persistence. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 35:1-35:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2022.35,
  author =	{Dey, Tamal K. and Lipi\'{n}ski, Micha{\l} and Mrozek, Marian and Slechta, Ryan},
  title =	{{Tracking Dynamical Features via Continuation and Persistence}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{35:1--35:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-227-3},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{224},
  editor =	{Goaoc, Xavier and Kerber, Michael},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2022.35},
  URN =		{urn:nbn:de:0030-drops-160439},
  doi =		{10.4230/LIPIcs.SoCG.2022.35},
  annote =	{Keywords: combinatorial dynamical systems, continuation, index pair, Conley index, persistent homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2021.30
Computing Zigzag Persistence on Graphs in Near-Linear Time

Authors: Tamal K. Dey and Tao Hou

Published in: LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021)

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.
Cite as

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)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2021.30,
  author =	{Dey, Tamal K. and Hou, Tao},
  title =	{{Computing Zigzag Persistence on Graphs in Near-Linear Time}},
  booktitle =	{37th International Symposium on Computational Geometry (SoCG 2021)},
  pages =	{30:1--30:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-184-9},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{189},
  editor =	{Buchin, Kevin and Colin de Verdi\`{e}re, \'{E}ric},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.30},
  URN =		{urn:nbn:de:0030-drops-138292},
  doi =		{10.4230/LIPIcs.SoCG.2021.30},
  annote =	{Keywords: persistent homology, zigzag persistence, graph filtration, dynamic networks}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.36
An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology

Authors: Tamal K. Dey, Tianqi Li, and Yusu Wang

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
This paper focuses on developing an efficient algorithm for analyzing a directed network (graph) from a topological viewpoint. A prevalent technique for such topological analysis involves computation of homology groups and their persistence. These concepts are well suited for spaces that are not directed. As a result, one needs a concept of homology that accommodates orientations in input space. Path-homology developed for directed graphs by Grigoryan, Lin, Muranov and Yau has been effectively adapted for this purpose recently by Chowdhury and Mémoli. They also give an algorithm to compute this path-homology. Our main contribution in this paper is an algorithm that computes this path-homology and its persistence more efficiently for the 1-dimensional (H₁) case. In developing such an algorithm, we discover various structures and their efficient computations that aid computing the 1-dimensional path-homology. We implement our algorithm and present some preliminary experimental results.
Cite as

Tamal K. Dey, Tianqi Li, and Yusu Wang. An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 36:1-36:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.36,
  author =	{Dey, Tamal K. and Li, Tianqi and Wang, Yusu},
  title =	{{An Efficient Algorithm for 1-Dimensional (Persistent) Path Homology}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{36:1--36:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.36},
  URN =		{urn:nbn:de:0030-drops-121944},
  doi =		{10.4230/LIPIcs.SoCG.2020.36},
  annote =	{Keywords: computational topology, directed graph, path homology, persistent path homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2020.37
Persistence of the Conley Index in Combinatorial Dynamical Systems

Authors: Tamal K. Dey, Marian Mrozek, and Ryan Slechta

Published in: LIPIcs, Volume 164, 36th International Symposium on Computational Geometry (SoCG 2020)

Abstract
A combinatorial framework for dynamical systems provides an avenue for connecting classical dynamics with data-oriented, algorithmic methods. Combinatorial vector fields introduced by Forman [R. Forman, 1998; R. Forman, 1998] and their recent generalization to multivector fields [Mrozek, 2017] have provided a starting point for building such a connection. In this work, we strengthen this relationship by placing the Conley index in the persistent homology setting. Conley indices are homological features associated with so-called isolated invariant sets, so a change in the Conley index is a response to perturbation in an underlying multivector field. We show how one can use zigzag persistence to summarize changes to the Conley index, and we develop techniques to capture such changes in the presence of noise. We conclude by developing an algorithm to "track" features in a changing multivector field.
Cite as

Tamal K. Dey, Marian Mrozek, and Ryan Slechta. Persistence of the Conley Index in Combinatorial Dynamical Systems. In 36th International Symposium on Computational Geometry (SoCG 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 164, pp. 37:1-37:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2020.37,
  author =	{Dey, Tamal K. and Mrozek, Marian and Slechta, Ryan},
  title =	{{Persistence of the Conley Index in Combinatorial Dynamical Systems}},
  booktitle =	{36th International Symposium on Computational Geometry (SoCG 2020)},
  pages =	{37:1--37:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-143-6},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{164},
  editor =	{Cabello, Sergio and Chen, Danny Z.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2020.37},
  URN =		{urn:nbn:de:0030-drops-121958},
  doi =		{10.4230/LIPIcs.SoCG.2020.37},
  annote =	{Keywords: Dynamical systems, combinatorial vector field, multivector, Conley index, persistence}
}
Document
DOI: 10.4230/LIPIcs.WABI.2018.6
Protein Classification with Improved Topological Data Analysis

Authors: Tamal K. Dey and Sayan Mandal

Published in: LIPIcs, Volume 113, 18th International Workshop on Algorithms in Bioinformatics (WABI 2018)

Abstract
Automated annotation and analysis of protein molecules have long been a topic of interest due to immediate applications in medicine and drug design. In this work, we propose a topology based, fast, scalable, and parameter-free technique to generate protein signatures. We build an initial simplicial complex using information about the protein's constituent atoms, including its radius and existing chemical bonds, to model the hierarchical structure of the molecule. Simplicial collapse is used to construct a filtration which we use to compute persistent homology. This information constitutes our signature for the protein. In addition, we demonstrate that this technique scales well to large proteins. Our method shows sizable time and memory improvements compared to other topology based approaches. We use the signature to train a protein domain classifier. Finally, we compare this classifier against models built from state-of-the-art structure-based protein signatures on standard datasets to achieve a substantial improvement in accuracy.
Cite as

Tamal K. Dey and Sayan Mandal. Protein Classification with Improved Topological Data Analysis. In 18th International Workshop on Algorithms in Bioinformatics (WABI 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 113, pp. 6:1-6:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.WABI.2018.6,
  author =	{Dey, Tamal K. and Mandal, Sayan},
  title =	{{Protein Classification with Improved Topological Data Analysis}},
  booktitle =	{18th International Workshop on Algorithms in Bioinformatics (WABI 2018)},
  pages =	{6:1--6:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-082-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{113},
  editor =	{Parida, Laxmi and Ukkonen, Esko},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WABI.2018.6},
  URN =		{urn:nbn:de:0030-drops-93082},
  doi =		{10.4230/LIPIcs.WABI.2018.6},
  annote =	{Keywords: topological data analysis, persistent homology, simplicial collapse, supervised learning, topology based protein feature vector, protein classification}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.31
Graph Reconstruction by Discrete Morse Theory

Authors: Tamal K. Dey, Jiayuan Wang, and Yusu Wang

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Recovering hidden graph-like structures from potentially noisy data is a fundamental task in modern data analysis. Recently, a persistence-guided discrete Morse-based framework to extract a geometric graph from low-dimensional data has become popular. However, to date, there is very limited theoretical understanding of this framework in terms of graph reconstruction. This paper makes a first step towards closing this gap. Specifically, first, leveraging existing theoretical understanding of persistence-guided discrete Morse cancellation, we provide a simplified version of the existing discrete Morse-based graph reconstruction algorithm. We then introduce a simple and natural noise model and show that the aforementioned framework can correctly reconstruct a graph under this noise model, in the sense that it has the same loop structure as the hidden ground-truth graph, and is also geometrically close. We also provide some experimental results for our simplified graph-reconstruction algorithm.
Cite as

Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Graph Reconstruction by Discrete Morse Theory. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 31:1-31:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2018.31,
  author =	{Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Graph Reconstruction by Discrete Morse Theory}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{31:1--31:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.31},
  URN =		{urn:nbn:de:0030-drops-87443},
  doi =		{10.4230/LIPIcs.SoCG.2018.31},
  annote =	{Keywords: graph reconstruction, discrete Morse theory, persistence}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2018.32
Computing Bottleneck Distance for 2-D Interval Decomposable Modules

Authors: Tamal K. Dey and Cheng Xin

Published in: LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018)

Abstract
Computation of the interleaving distance between persistence modules is a central task in topological data analysis. For 1-D persistence modules, thanks to the isometry theorem, this can be done by computing the bottleneck distance with known efficient algorithms. The question is open for most n-D persistence modules, n>1, because of the well recognized complications of the indecomposables. Here, we consider a reasonably complicated class called 2-D interval decomposable modules whose indecomposables may have a description of non-constant complexity. We present a polynomial time algorithm to compute the bottleneck distance for these modules from indecomposables, which bounds the interleaving distance from above, and give another algorithm to compute a new distance called dimension distance that bounds it from below.
Cite as

Tamal K. Dey and Cheng Xin. Computing Bottleneck Distance for 2-D Interval Decomposable Modules. In 34th International Symposium on Computational Geometry (SoCG 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 99, pp. 32:1-32:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2018.32,
  author =	{Dey, Tamal K. and Xin, Cheng},
  title =	{{Computing Bottleneck Distance for 2-D Interval Decomposable Modules}},
  booktitle =	{34th International Symposium on Computational Geometry (SoCG 2018)},
  pages =	{32:1--32:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-066-8},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{99},
  editor =	{Speckmann, Bettina and T\'{o}th, Csaba D.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.32},
  URN =		{urn:nbn:de:0030-drops-87453},
  doi =		{10.4230/LIPIcs.SoCG.2018.32},
  annote =	{Keywords: Persistence modules, bottleneck distance, interleaving distance}
}
Document
DOI: 10.4230/LIPIcs.ISAAC.2017.28
Temporal Hierarchical Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 92, 28th International Symposium on Algorithms and Computation (ISAAC 2017)

Abstract
We study hierarchical clusterings of metric spaces that change over time. This is a natural geo- metric primitive for the analysis of dynamic data sets. Specifically, we introduce and study the problem of finding a temporally coherent sequence of hierarchical clusterings from a sequence of unlabeled point sets. We encode the clustering objective by embedding each point set into an ultrametric space, which naturally induces a hierarchical clustering of the set of points. We enforce temporal coherence among the embeddings by finding correspondences between successive pairs of ultrametric spaces which exhibit small distortion in the Gromov-Hausdorff sense. We present both upper and lower bounds on the approximability of the resulting optimization problems.
Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Hierarchical Clustering. In 28th International Symposium on Algorithms and Computation (ISAAC 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 92, pp. 28:1-28:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ISAAC.2017.28,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Hierarchical Clustering}},
  booktitle =	{28th International Symposium on Algorithms and Computation (ISAAC 2017)},
  pages =	{28:1--28:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-054-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{92},
  editor =	{Okamoto, Yoshio and Tokuyama, Takeshi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ISAAC.2017.28},
  URN =		{urn:nbn:de:0030-drops-82519},
  doi =		{10.4230/LIPIcs.ISAAC.2017.28},
  annote =	{Keywords: clustering, hierarchical clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms}
}
Document
DOI: 10.4230/LIPIcs.ESA.2017.34
Temporal Clustering

Authors: Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos

Published in: LIPIcs, Volume 87, 25th Annual European Symposium on Algorithms (ESA 2017)

Abstract
We study the problem of clustering sequences of unlabeled point sets taken from a common metric space. Such scenarios arise naturally in applications where a system or process is observed in distinct time intervals, such as biological surveys and contagious disease surveillance. In this more general setting existing algorithms for classical (i.e. static) clustering problems are not applicable anymore. We propose a set of optimization problems which we collectively refer to as temporal clustering. The quality of a solution to a temporal clustering instance can be quantified using three parameters: the number of clusters k, the spatial clustering cost r, and the maximum cluster displacement delta between consecutive time steps. We consider spatial clustering costs which generalize the well-studied k-center, discrete k-median, and discrete k-means objectives of classical clustering problems. We develop new algorithms that achieve trade-offs between the three objectives k, r, and delta. Our upper bounds are complemented by inapproximability results.
Cite as

Tamal K. Dey, Alfred Rossi, and Anastasios Sidiropoulos. Temporal Clustering. In 25th Annual European Symposium on Algorithms (ESA 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 87, pp. 34:1-34:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2017.34,
  author =	{Dey, Tamal K. and Rossi, Alfred and Sidiropoulos, Anastasios},
  title =	{{Temporal Clustering}},
  booktitle =	{25th Annual European Symposium on Algorithms (ESA 2017)},
  pages =	{34:1--34:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-049-1},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{87},
  editor =	{Pruhs, Kirk and Sohler, Christian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2017.34},
  URN =		{urn:nbn:de:0030-drops-78567},
  doi =		{10.4230/LIPIcs.ESA.2017.34},
  annote =	{Keywords: clustering, multi-objective optimization, dynamic metric spaces, moving point sets, approximation algorithms, hardness of approximation}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.23
Declutter and Resample: Towards Parameter Free Denoising

Authors: Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
In many data analysis applications the following scenario is commonplace: we are given a point set that is supposed to sample a hidden ground truth K in a metric space, but it got corrupted with noise so that some of the data points lie far away from K creating outliers also termed as ambient noise. One of the main goals of denoising algorithms is to eliminate such noise so that the curated data lie within a bounded Hausdorff distance of K. Popular denoising approaches such as deconvolution and thresholding often require the user to set several parameters and/or to choose an appropriate noise model while guaranteeing only asymptotic convergence. Our goal is to lighten this burden as much as possible while ensuring theoretical guarantees in all cases. Specifically, first, we propose a simple denoising algorithm that requires only a single parameter but provides a theoretical guarantee on the quality of the output on general input points. We argue that this single parameter cannot be avoided. We next present a simple algorithm that avoids even this parameter by paying for it with a slight strengthening of the sampling condition on the input points which is not unrealistic. We also provide some preliminary empirical evidence that our algorithms are effective in practice.
Cite as

Mickael Buchet, Tamal K. Dey, Jiayuan Wang, and Yusu Wang. Declutter and Resample: Towards Parameter Free Denoising. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 23:1-23:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SoCG.2017.23,
  author =	{Buchet, Mickael and Dey, Tamal K. and Wang, Jiayuan and Wang, Yusu},
  title =	{{Declutter and Resample: Towards Parameter Free Denoising}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{23:1--23:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.23},
  URN =		{urn:nbn:de:0030-drops-72133},
  doi =		{10.4230/LIPIcs.SoCG.2017.23},
  annote =	{Keywords: denoising, parameter free, k-distance,compact sets}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.36
Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers

Authors: Tamal K. Dey, Facundo Mémoli, and Yusu Wang

Published in: LIPIcs, Volume 77, 33rd International Symposium on Computational Geometry (SoCG 2017)

Abstract
Data analysis often concerns not only the space where data come from, but also various types of maps attached to data. In recent years, several related structures have been used to study maps on data, including Reeb spaces, mappers and multiscale mappers. The construction of these structures also relies on the so-called nerve of a cover of the domain. In this paper, we aim to analyze the topological information encoded in these structures in order to provide better understanding of these structures and facilitate their practical usage. More specifically, we show that the one-dimensional homology of the nerve complex N(U) of a path-connected cover U of a domain X cannot be richer than that of the domain X itself. Intuitively, this result means that no new H_1-homology class can be "created" under a natural map from X to the nerve complex N(U). Equipping X with a pseudometric d, we further refine this result and characterize the classes of H_1(X) that may survive in the nerve complex using the notion of size of the covering elements in U. These fundamental results about nerve complexes then lead to an analysis of the H_1-homology of Reeb spaces, mappers and multiscale mappers. The analysis of H_1-homology groups unfortunately does not extend to higher dimensions. Nevertheless, by using a map-induced metric, establishing a Gromov-Hausdorff convergence result between mappers and the domain, and interleaving relevant modules, we can still analyze the persistent homology groups of (multiscale) mappers to establish a connection to Reeb spaces.
Cite as

Tamal K. Dey, Facundo Mémoli, and Yusu Wang. Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 36:1-36:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SoCG.2017.36,
  author =	{Dey, Tamal K. and M\'{e}moli, Facundo and Wang, Yusu},
  title =	{{Topological Analysis of Nerves, Reeb Spaces, Mappers, and Multiscale Mappers}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{36:1--36:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-038-5},
  ISSN =	{1868-8969},
  year =	{2017},
  volume =	{77},
  editor =	{Aronov, Boris and Katz, Matthew J.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2017.36},
  URN =		{urn:nbn:de:0030-drops-72220},
  doi =		{10.4230/LIPIcs.SoCG.2017.36},
  annote =	{Keywords: Topology, Nerves, Mapper, Multiscale Mapper, Reeb Spaces}
}
Document
DOI: 10.4230/LIPIcs.ESA.2016.35
SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse

Authors: Tamal K. Dey, Dayu Shi, and Yusu Wang

Published in: LIPIcs, Volume 57, 24th Annual European Symposium on Algorithms (ESA 2016)

Abstract
In topological data analysis, a point cloud data P extracted from a metric space is often analyzed by computing the persistence diagram or barcodes of a sequence of Rips complexes built on P indexed by a scale parameter. Unfortunately, even for input of moderate size, the size of the Rips complex may become prohibitively large as the scale parameter increases. Starting with the Sparse Rips filtration introduced by Sheehy, some existing methods aim to reduce the size of the complex so as to improve the time efficiency as well. However, as we demonstrate, existing approaches still fall short of scaling well, especially for high dimensional data. In this paper, we investigate the advantages and limitations of existing approaches. Based on insights gained from the experiments, we propose an efficient new algorithm, called SimBa, for approximating the persistent homology of Rips filtrations with quality guarantees. Our new algorithm leverages a batch collapse strategy as well as a new sparse Rips-like filtration. We experiment on a variety of low and high dimensional data sets. We show that our strategy presents a significant size reduction, and our algorithm for approximating Rips filtration persistence is order of magnitude faster than existing methods in practice.
Cite as

Tamal K. Dey, Dayu Shi, and Yusu Wang. SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse. In 24th Annual European Symposium on Algorithms (ESA 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 57, pp. 35:1-35:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.ESA.2016.35,
  author =	{Dey, Tamal K. and Shi, Dayu and Wang, Yusu},
  title =	{{SimBa: An Efficient Tool for Approximating  Rips-Filtration Persistence via Simplicial Batch-Collapse}},
  booktitle =	{24th Annual European Symposium on Algorithms (ESA 2016)},
  pages =	{35:1--35:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-015-6},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{57},
  editor =	{Sankowski, Piotr and Zaroliagis, Christos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2016.35},
  URN =		{urn:nbn:de:0030-drops-63869},
  doi =		{10.4230/LIPIcs.ESA.2016.35},
  annote =	{Keywords: Rips filtration, Homology groups, Persistence, Topological data analysis}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.491
Comparing Graphs via Persistence Distortion

Authors: Tamal K. Dey, Dayu Shi, and Yusu Wang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster.
Cite as

Tamal K. Dey, Dayu Shi, and Yusu Wang. Comparing Graphs via Persistence Distortion. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 491-506, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{dey_et_al:LIPIcs.SOCG.2015.491,
  author =	{Dey, Tamal K. and Shi, Dayu and Wang, Yusu},
  title =	{{Comparing Graphs via Persistence Distortion}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{491--506},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.491},
  URN =		{urn:nbn:de:0030-drops-51285},
  doi =		{10.4230/LIPIcs.SOCG.2015.491},
  annote =	{Keywords: Graph matching, metric graphs, persistence distortion, topological method}
}
Document
DOI: 10.4230/LIPIcs.SOCG.2015.827
Topological Analysis of Scalar Fields with Outliers

Authors: Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang

Published in: LIPIcs, Volume 34, 31st International Symposium on Computational Geometry (SoCG 2015)

Abstract
Given a real-valued function f defined over a manifold M embedded in R^d, we are interested in recovering structural information about f from the sole information of its values on a finite sample P. Existing methods provide approximation to the persistence diagram of f when geometric noise and functional noise are bounded. However, they fail in the presence of aberrant values, also called outliers, both in theory and practice. We propose a new algorithm that deals with outliers. We handle aberrant functional values with a method inspired from the k-nearest neighbors regression and the local median filtering, while the geometric outliers are handled using the distance to a measure. Combined with topological results on nested filtrations, our algorithm performs robust topological analysis of scalar fields in a wider range of noise models than handled by current methods. We provide theoretical guarantees and experimental results on the quality of our approximation of the sampled scalar field.
Cite as

Mickaël Buchet, Frédéric Chazal, Tamal K. Dey, Fengtao Fan, Steve Y. Oudot, and Yusu Wang. Topological Analysis of Scalar Fields with Outliers. In 31st International Symposium on Computational Geometry (SoCG 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 34, pp. 827-841, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@InProceedings{buchet_et_al:LIPIcs.SOCG.2015.827,
  author =	{Buchet, Micka\"{e}l and Chazal, Fr\'{e}d\'{e}ric and Dey, Tamal K. and Fan, Fengtao and Oudot, Steve Y. and Wang, Yusu},
  title =	{{Topological Analysis of Scalar Fields with Outliers}},
  booktitle =	{31st International Symposium on Computational Geometry (SoCG 2015)},
  pages =	{827--841},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-83-5},
  ISSN =	{1868-8969},
  year =	{2015},
  volume =	{34},
  editor =	{Arge, Lars and Pach, J\'{a}nos},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SOCG.2015.827},
  URN =		{urn:nbn:de:0030-drops-51052},
  doi =		{10.4230/LIPIcs.SOCG.2015.827},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Scalar Field Analysis, Nested Rips Filtration, Distance to a Measure}
}
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