DROPS

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}
}

Search Results

Documents authored by Shi, Dayu

SimBa: An Efficient Tool for Approximating Rips-Filtration Persistence via Simplicial Batch-Collapse

Abstract

Cite as

Comparing Graphs via Persistence Distortion

Abstract

Cite as

Thanks for your feedback!

Could not send message