  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.
