# Graph Reconstruction by Discrete Morse Theory

arXiv: https://arxiv.org/abs/1803.05093 · HTML: https://mlsanity.com/paper/1803.05093/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 14 Mar 2018.

## Built on by (most cited first, 5 of 5)

- [Topology-Aware Segmentation Using Discrete Morse Theory](https://mlsanity.com/paper/2103.09992/) (2021)
- [Topology-Aware Uncertainty for Image Segmentation](https://mlsanity.com/paper/2306.05671/) (2023)
- [Learning Probabilistic Topological Representations Using Discrete Morse Theory](https://mlsanity.com/paper/2206.01742/) (2022)
- [Equivariant geometric learning for digital rock physics: estimating formation factor and effective permeability tensors from Morse graph](https://mlsanity.com/paper/2104.05608/) (2021)
- [Graph Representation via Elements of Discrete Morse and Cobordism Theories](https://mlsanity.com/paper/2610.01937/) (2026)

## Abstract (arXiv)

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.