5 Search Results for "Schreiber, Hannah"

Document
DOI: 10.4230/LIPIcs.SoCG.2025.29
Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent

Authors: Mathieu Carrière, Seunghyun Kim, and Woojin Kim

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The generalized persistence diagram (GPD) is a natural extension of the classical persistence barcode to the setting of multi-parameter persistence and beyond. The GPD is defined as an integer-valued function whose domain is the set of intervals in the indexing poset of a persistence module, and is known to be able to capture richer topological information than its single-parameter counterpart. However, computing the GPD is computationally prohibitive due to the sheer size of the interval set. Restricting the GPD to a subset of intervals provides a way to manage this complexity, compromising discriminating power to some extent. However, identifying and computing an effective restriction of the domain that minimizes the loss of discriminating power remains an open challenge. In this work, we introduce a novel method for optimizing the domain of the GPD through gradient descent optimization. To achieve this, we introduce a loss function tailored to optimize the selection of intervals, balancing computational efficiency and discriminative accuracy. The design of the loss function is based on the known erosion stability property of the GPD. We showcase the efficiency of our sparsification method for dataset classification in supervised machine learning. Experimental results demonstrate that our sparsification method significantly reduces the time required for computing the GPDs associated to several datasets, while maintaining classification accuracies comparable to those achieved using full GPDs. Our method thus opens the way for the use of GPD-based methods to applications at an unprecedented scale.
Cite as

Mathieu Carrière, Seunghyun Kim, and Woojin Kim. Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 29:1-29:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{carriere_et_al:LIPIcs.SoCG.2025.29,
  author =	{Carri\`{e}re, Mathieu and Kim, Seunghyun and Kim, Woojin},
  title =	{{Sparsification of the Generalized Persistence Diagrams for Scalability Through Gradient Descent}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{29:1--29:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.29},
  URN =		{urn:nbn:de:0030-drops-231810},
  doi =		{10.4230/LIPIcs.SoCG.2025.29},
  annote =	{Keywords: Multi-parameter persistent homology, Generalized persistence diagram, Generalized rank invariant, Non-convex optimization, Gradient descent}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2025.58
Tracking the Persistence of Harmonic Chains: Barcode and Stability

Authors: Tao Hou, Salman Parsa, and Bei Wang

Published in: LIPIcs, Volume 332, 41st International Symposium on Computational Geometry (SoCG 2025)

Abstract
The persistence barcode is a topological descriptor of data that plays a fundamental role in topological data analysis. Given a filtration of data, the persistence barcode tracks the evolution of its homology groups. In this paper, we introduce a new type of barcode, called the harmonic chain barcode, which tracks the evolution of harmonic chains. In addition, we show that the harmonic chain barcode is stable. Given a filtration of a simplicial complex of size m, we present an algorithm to compute its harmonic chain barcode in O(m³) time. Consequently, the harmonic chain barcode can enrich the family of topological descriptors in applications where a persistence barcode is applicable, such as feature vectorization and machine learning.
Cite as

Tao Hou, Salman Parsa, and Bei Wang. Tracking the Persistence of Harmonic Chains: Barcode and Stability. In 41st International Symposium on Computational Geometry (SoCG 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 332, pp. 58:1-58:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hou_et_al:LIPIcs.SoCG.2025.58,
  author =	{Hou, Tao and Parsa, Salman and Wang, Bei},
  title =	{{Tracking the Persistence of Harmonic Chains: Barcode and Stability}},
  booktitle =	{41st International Symposium on Computational Geometry (SoCG 2025)},
  pages =	{58:1--58:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-370-6},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{332},
  editor =	{Aichholzer, Oswin and Wang, Haitao},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2025.58},
  URN =		{urn:nbn:de:0030-drops-232100},
  doi =		{10.4230/LIPIcs.SoCG.2025.58},
  annote =	{Keywords: Persistent homology, harmonic chains, topological data analysis}
}
Document
Vision
DOI: 10.4230/TGDK.1.1.3
Knowledge Engineering Using Large Language Models

Authors: Bradley P. Allen, Lise Stork, and Paul Groth

Published in: TGDK, Volume 1, Issue 1 (2023): Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge, Volume 1, Issue 1

Abstract
Knowledge engineering is a discipline that focuses on the creation and maintenance of processes that generate and apply knowledge. Traditionally, knowledge engineering approaches have focused on knowledge expressed in formal languages. The emergence of large language models and their capabilities to effectively work with natural language, in its broadest sense, raises questions about the foundations and practice of knowledge engineering. Here, we outline the potential role of LLMs in knowledge engineering, identifying two central directions: 1) creating hybrid neuro-symbolic knowledge systems; and 2) enabling knowledge engineering in natural language. Additionally, we formulate key open research questions to tackle these directions.
Cite as

Bradley P. Allen, Lise Stork, and Paul Groth. Knowledge Engineering Using Large Language Models. In Special Issue on Trends in Graph Data and Knowledge. Transactions on Graph Data and Knowledge (TGDK), Volume 1, Issue 1, pp. 3:1-3:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@Article{allen_et_al:TGDK.1.1.3,
  author =	{Allen, Bradley P. and Stork, Lise and Groth, Paul},
  title =	{{Knowledge Engineering Using Large Language Models}},
  journal =	{Transactions on Graph Data and Knowledge},
  pages =	{3:1--3:19},
  ISSN =	{2942-7517},
  year =	{2023},
  volume =	{1},
  number =	{1},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/TGDK.1.1.3},
  URN =		{urn:nbn:de:0030-drops-194777},
  doi =		{10.4230/TGDK.1.1.3},
  annote =	{Keywords: knowledge engineering, large language models}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2022.25
On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class

Authors: Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber

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

Abstract
Homology features of spaces which appear in applications, for instance 3D meshes, are among the most important topological properties of these objects. Given a non-trivial cycle in a homology class, we consider the problem of computing a representative in that homology class which is optimal. We study two measures of optimality, namely, the lexicographic order of cycles (the lex-optimal cycle) and the bottleneck norm (a bottleneck-optimal cycle). We give a simple algorithm for computing the lex-optimal cycle for a 1-homology class in a closed orientable surface. In contrast to this, our main result is that, in the case of 3-manifolds of size n² in the Euclidean 3-space, the problem of finding a bottleneck optimal cycle cannot be solved more efficiently than solving a system of linear equations with an n × n sparse matrix. From this reduction, we deduce several hardness results. Most notably, we show that for 3-manifolds given as a subset of the 3-space of size n², persistent homology computations are at least as hard as rank computation (for sparse matrices) while ordinary homology computations can be done in O(n² log n) time. This is the first such distinction between these two computations. Moreover, it follows that the same disparity exists between the height persistent homology computation and general sub-level set persistent homology computation for simplicial complexes in the 3-space.
Cite as

Erin Wolf Chambers, Salman Parsa, and Hannah Schreiber. On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class. In 38th International Symposium on Computational Geometry (SoCG 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 224, pp. 25:1-25:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{chambers_et_al:LIPIcs.SoCG.2022.25,
  author =	{Chambers, Erin Wolf and Parsa, Salman and Schreiber, Hannah},
  title =	{{On Complexity of Computing Bottleneck and Lexicographic Optimal Cycles in a Homology Class}},
  booktitle =	{38th International Symposium on Computational Geometry (SoCG 2022)},
  pages =	{25:1--25:15},
  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.25},
  URN =		{urn:nbn:de:0030-drops-160338},
  doi =		{10.4230/LIPIcs.SoCG.2022.25},
  annote =	{Keywords: computational topology, bottleneck optimal cycles, homology}
}
Document
DOI: 10.4230/LIPIcs.SoCG.2017.57
Barcodes of Towers and a Streaming Algorithm for Persistent Homology

Authors: Michael Kerber and Hannah Schreiber

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

Abstract
A tower is a sequence of simplicial complexes connected by simplicial maps. We show how to compute a filtration, a sequence of nested simplicial complexes, with the same persistent barcode as the tower. Our approach is based on the coning strategy by Dey et al. (SoCG 2014). We show that a variant of this approach yields a filtration that is asymptotically only marginally larger than the tower and can be efficiently computed by a streaming algorithm, both in theory and in practice. Furthermore, we show that our approach can be combined with a streaming algorithm to compute the barcode of the tower via matrix reduction. The space complexity of the algorithm does not depend on the length of the tower, but the maximal size of any subcomplex within the tower. Experimental evaluations show that our approach can efficiently handle towers with billions of complexes.
Cite as

Michael Kerber and Hannah Schreiber. Barcodes of Towers and a Streaming Algorithm for Persistent Homology. In 33rd International Symposium on Computational Geometry (SoCG 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 77, pp. 57:1-57:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)

Copy BibTex To Clipboard

@InProceedings{kerber_et_al:LIPIcs.SoCG.2017.57,
  author =	{Kerber, Michael and Schreiber, Hannah},
  title =	{{Barcodes of Towers and a Streaming Algorithm for Persistent Homology}},
  booktitle =	{33rd International Symposium on Computational Geometry (SoCG 2017)},
  pages =	{57:1--57: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.57},
  URN =		{urn:nbn:de:0030-drops-71936},
  doi =		{10.4230/LIPIcs.SoCG.2017.57},
  annote =	{Keywords: Persistent Homology, Topological Data Analysis, Matrix reduction, Streaming algorithms, Simplicial Approximation}
}
  • Refine by Type
  • 5 Document/PDF
  • 3 Document/HTML

  • Refine by Publication Year
  • 2 2025
  • 1 2023
  • 1 2022
  • 1 2017

  • Refine by Author
  • 2 Parsa, Salman
  • 2 Schreiber, Hannah
  • 1 Allen, Bradley P.
  • 1 Carrière, Mathieu
  • 1 Chambers, Erin Wolf
  • Show More...

  • Refine by Series/Journal
  • 4 LIPIcs
  • 1 TGDK

  • Refine by Classification
  • 2 Mathematics of computing → Algebraic topology
  • 1 Computing methodologies → Machine learning
  • 1 Computing methodologies → Natural language processing
  • 1 Computing methodologies → Philosophical/theoretical foundations of artificial intelligence
  • 1 Mathematics of computing → Geometric topology
  • Show More...

  • Refine by Keyword
  • 1 Generalized persistence diagram
  • 1 Generalized rank invariant
  • 1 Gradient descent
  • 1 Matrix reduction
  • 1 Multi-parameter persistent homology
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

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