2026-07-22T07:05:31Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8744 2024-03-06T10:42:33Z ddc:004 open_access

Graph Reconstruction by Discrete Morse Theory Dey, Tamal K. Wang, Jiayuan Wang, Yusu graph reconstruction discrete Morse theory persistence 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Tamal K. Dey and Jiayuan Wang and Yusu Wang 2018 Is Part Of LIPIcs, Volume 99, 34th International Symposium on Computational Geometry (SoCG 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2018.31 urn:nbn:de:0030-drops-87443 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2018.31 eng https://creativecommons.org/licenses/by/3.0/legalcode