The Reeb graph edit distance is universal
For a Morse function $f: X\to \mathbb R$ on a compact smooth manifold, the Reeb graph of $f$ is the quotient space $X/\sim_f$, with $x\sim_f$ $y$ iff $x$ and $y$ belong to the same connected component of some level set $f^{-1}(t)$ for some real number $t$. It is proved in Proposition 2 that any Reeb graph of a PL (piece-wise linear) function is a finite topological graph. In Section 3, the authors define some pseudo-metrics on the collection of the Reeb graphs for all the Morse functions (or PL functions) on a fixed space $X$. The authors define the universal properties of a pseudo-metric. They construct a distance $d_U$ and prove that it is universal in Proposition 5. They prove that $d_U$ is intrinsic in Proposition 6 and state that whether $d_U$ is a geodesic metric is unknown. They also review and re-introduce the functional distortion distance and the interleaving distance and claim that these two distances are stable but not universal. Finally, they give some lower bounds. In Section 4, the authors introduce a new distance, the edit distance $d_e$. They prove that $d_e$ is stable and universal. In Section 5, the authors further explore the edit distance of Reeb graphs $d_{eGraph}$ as well as its stability and universality. In Section 6, the authors discuss the motivation of the study of $d_U$, $d_e$, and $d_{eGraph}$ in topological data analysis, the relations between these distances and graph zigzagging, and some further questions which are of interest and could motivate further research.
- Categorified Reeb graphs
- Distances between datasets
- FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
- scientific article; zbMATH DE number 475456 (Why is no real title available?)
- scientific article; zbMATH DE number 3106699 (Why is no real title available?)
- Measuring distance between Reeb graphs (extended abstract)
- Natural pseudo-distance and optimal matching between reduced size functions
- Natural pseudodistances between closed manifolds
- Nilpotent types and fracture squares in homotopy type theory
- On intrinsic geometry of surfaces in normed spaces
- Parametrized complexity theory.
- Reeb graphs of curves are stable under function perturbations
- Stability of persistence diagrams
- Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
- The edit distance for Reeb graphs of surfaces
- The natural pseudo-distance as a quotient pseudo-metric, and applications
- The theory of the interleaving distance on multidimensional persistence modules
- Generalized persistence diagrams for persistence modules over posets
- Universality of persistence diagrams and the bottleneck and Wasserstein distances
- The edit distance for Reeb graphs of surfaces
- Reeb graphs of curves are stable under function perturbations
- Stable shape comparison of surfaces via Reeb graphs
- Local equivalence and intrinsic metrics between Reeb graphs
- Measuring distance between Reeb graphs (extended abstract)
- Edit Distance and Persistence Diagrams over Lattices
- FPT-algorithms for computing Gromov-Hausdorff and interleaving distances between trees
- Strong equivalence of the interleaving and functional distortion metrics for Reeb graphs
- Distances and isomorphism between networks: stability and convergence of network invariants
- Realizable piecewise linear paths of persistence diagrams with Reeb graphs
- Universal distances for extended persistence
- Classical multidimensional scaling on metric measure spaces
- Labeled interleaving distance for Reeb graphs
- Measure-theoretic Reeb graphs and Reeb spaces
- Tight quasi-universality of Reeb graph distances
- Intrinsic interleaving distance for merge trees
- Measure-theoretic Reeb graphs and Reeb spaces
- Geometry and stability of supervised learning problems
- Gromov-Wasserstein bound between Reeb and Mapper graphs
This page was built for publication: The Reeb graph edit distance is universal
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2052722)
