Source-linked AI summary
Categorified Reeb Graphs
Vin de Silva, Elizabeth Munch, Amit Patel
TL;DR
The paper addresses the need to reason about a space of Reeb graphs in data applications. It uses the correspondence between constructible cosheaves and Reeb graphs to develop interleaving-based distances with stability results.
Problem
Data applications motivate considering not only individual Reeb graphs but the whole space of Reeb graphs.
Method
The paper uses the correspondence between constructible cosheaves and Reeb graphs to transfer ideas between the two settings.
Results
The resulting framework supports an interleaving strategy for defining distances and includes a stability theorem; deciding ε-interleavability is in NP.
Takeaways & Limitations
Reeb graphs emerge as persistent invariants alongside persistence diagrams and dendrograms, with an accessible stability theorem.
Takeaways & Limitations
The cosheaf correspondence and natural isomorphism are restricted: cited results fail or do not extend to arbitrary R-spaces.
Abstract
from arXiv · showhide
The Reeb graph is a construction which originated in Morse theory to study a real valued function defined on a topological space. More recently, it has been used in various applications to study noisy data which creates a desire to define a measure of similarity between these structures. Here, we exploit the fact that the category of Reeb graphs is equivalent to the category of a particular class of cosheaf. Using this equivalency, we can define an `interleaving' distance between Reeb graphs which is stable under the perturbation of a function. Along the way, we obtain a natural construction for smoothing a Reeb graph to reduce its topological complexity. The smoothed Reeb graph can be constructed in polynomial time.
1 Introduction
The paper develops a categorical framework for Reeb graphs, representing them as constructible cosheaves to define stable comparisons and smoothing operations. This framework preserves the graph's information while supporting metrics, complexity reduction, and computational treatment.
- 1.1 Purpose: The paper defines a distance between Reeb graphs, proves stability under input perturbations, and introduces smoothing operations that reduce topological complexity.These are the paper’s stated objectives and contributions.
- 1.2 Reeb graphs and Reeb cosheaves: Category theory identifies Reeb graphs with a particular class of cosheaves, allowing an interleaving distance on cosheaves to induce a distance on Reeb graphs.The approach transfers persistence-style comparison methods into the geometric setting.
- 1.1 Purpose: The authors distinguish their global smoothing operation from local loop collapses: it makes small modifications everywhere while removing small loops.The paper presents this smoothing construction as a novel operation arising naturally on cosheaves.
- 1.1 Purpose: The geometric Reeb graph is formed by identifying points lying in the same connected component of a levelset, thereby tracking levelset components across function values.For Morse functions on compact manifolds and piecewise linear functions on compact polyhedra, the result is a finite graph.
- 1.2 Reeb graphs and Reeb cosheaves: For each open interval, the Reeb cosheaf records path-components of its preimage and maps induced by inclusions of intervals.In the constructible case, this functorial data is sufficient to recover the geometric Reeb graph.
- 1.3 Category theory: The paper establishes natural isomorphisms and an equivalence between Reeb graphs and constructible cosheaves, making the categorical representation mathematically interchangeable with the geometric one.The stated relations include RI ≅ identity, C′′R ≅ C′, and an equivalence between Reeb and Cshc.
2 The geometric categories
The paper develops geometric categories of real-valued spaces, restricts to constructible spaces with finite critical structure, and represents their Reeb graphs through finite vertex-edge data. The Reeb functor carries constructible R-spaces to R-graphs, and each R-graph is naturally isomorphic to its Reeb graph.
- 2.2 The category of constructible R-spaces: Constructible R-spaces are built from finitely many critical fibers and cylindrical regions between critical values, covering Morse, piecewise-linear, semialgebraic, and o-minimal examples.Each region is attached through maps between the spaces over adjacent critical values.
- 2.3 The category of Reeb graphs: An R-graph is a constructible R-space whose critical fibers and interval fibers are finite discrete sets, equivalently a compact 1-dimensional polyhedron with embedded edge restrictions.Its morphisms are inherited from the category of R-spaces.
- 2.3 The category of Reeb graphs: For an R-graph, a finite critical set specifies vertex sets over critical values, edge sets over intervening intervals, and attaching maps at both endpoints.The resulting space is the quotient of vertices and edge cylinders under the endpoint identifications, with the function given by projection.
- 2.3 The category of Reeb graphs: The restriction over each open interval is a covering map, so morphisms between R-graphs are determined combinatorially by consistent maps on vertices and edges.The covering structure ensures each source edge maps to exactly one target edge once selected.
- 2.4 The Reeb functor R: The geometric Reeb graph is obtained by identifying points in the same connected component of each levelset, producing a quotient R-space with a continuous inherited function.The quotient map defines a morphism from the original R-space to its Reeb graph.
- 2.4 The Reeb functor R: The Reeb functor sends constructible R-spaces to R-graphs and makes every R-graph naturally isomorphic to its Reeb graph.Thus, on constructible spaces, the functor acts as a projection onto the category of Reeb graphs.
3 The cosheaf categories
The paper organizes Reeb-graph information into pre-cosheaves, cosheaves, and constructible cosheaves, then proves that constructible Reeb graphs and constructible cosheaves are equivalent descriptions.
- 3.1–3.3 The cosheaf categories: The three categories progress from all interval-valued set functors, to cosheaves satisfying gluing, to finite constructible cosheaves with finitely many critical values.Pre is the largest category; Csh is its full cosheaf subcategory; Cshc is the full constructible subcategory.
- 3.1 Pre-cosheaves: An R-space induces a pre-cosheaf by assigning each interval I the space f^-1(I), with inclusions for interval inclusions; post-composition yields homology and component-valued examples.The path-component functor produces a set-valued pre-cosheaf, while homology produces an abelian-group-valued one.
- 3.2 Cosheaves: A cosheaf requires F(U) to be the colimit of the values on every interval cover, equivalently encoding compatible gluing across overlaps.The paper gives disjoint-union, connected-component, and universal-property interpretations of this condition.
- 3.3 The category of constructible cosheaves: Constructible cosheaves are determined by finite interval and overlap data, and isomorphisms on short intervals suffice to establish a natural isomorphism globally.The combinatorial data consist of finite sets and maps between adjacent critical intervals; any two realizations are canonically isomorphic.
- 3.4 The Reeb cosheaf functor C: The path-component construction C(f) is a cosheaf, whereas homology and connected components need not satisfy the cosheaf condition in general.Mayer–Vietoris explains the homology failure, and a connected but not path-connected example separates connected from path components.
- 3.5 Equivalence of categories: The functor from Reeb graphs to constructible cosheaves is an equivalence, and the Reeb graph of a constructible R-space agrees with the display locale of its Reeb cosheaf.The geometric and cosheaf constructions are naturally isomorphic in the constructible setting.
4 The interleaving distance
The paper defines Reeb-graph distance by transporting interleaving distance from constructible cosheaves, then gives geometric smoothing and thickening constructions that preserve this framework. The resulting distance is stable under function perturbations, while smoothing is contractive and has explicit topological effects.
- 4.1 Interleaving of pre-cosheaves: Reeb distance is defined by converting Reeb graphs to cosheaves and setting dR(f, g) = di(C(f), C(g)).The construction uses the equivalence between Reeb graphs and constructible cosheaves to compare graphs through interleavings.
- 4.1 Interleaving of pre-cosheaves: The distance is stable under perturbations: for constructible R-spaces, perturbing the function by at most ε yields an ε-interleaving of their Reeb cosheaves and graphs.The proof uses inclusions induced by the supremum bound and the natural isomorphism between geometric and cosheaf constructions.
- 4.1 Interleaving of pre-cosheaves: dR is an extended metric on isomorphism classes, but it is finite only when the compared graphs have the same number of path components.It is an extended pseudometric on graphs, becomes an extended metric on isomorphism classes, and may take the value infinity.
- 4.2 Smoothing functors: Smoothing forms a semigroup of endofunctors, is contractive for interleaving distance, and preserves cosheaves and constructible cosheaves.For pre-cosheaves, di(Sε(F), Sε(G)) ≤ di(F, G); the restriction results retain the relevant categorical subcategories.
- 4.3 Thickening functors: Thickening and smoothing commute up to natural isomorphism, with CTε ≃ SεC, and thickening preserves constructible R-spaces.This correspondence transfers smoothing between cosheaves and the geometric side of the construction.
- 4.4 Topological smoothing of R-graphs: Topological smoothing is defined by Uε = RTε; its fibers over t are connected components of f^-1[t−ε, t+ε], and its vertices shift to Sε = (S +ε)∪(S −ε).The resulting functors form a contraction semigroup, satisfying dR(Uε(f), Uε(g)) ≤ dR(f, g).
5 Algorithms
The paper develops polynomial-time construction and recognition procedures for smoothed Reeb graphs and ε-interleavings, while showing that computing the exact interleaving distance is graph-isomorphism-hard.
- 5.2 Computing the Smoothed Reeb Graph: O(m log(m + n)) is achieved by exploiting the smoothing structure rather than applying a generic Reeb-graph algorithm to the thickened complex.
- 5.1 Maintenance of Level Set Representation: The smoothing algorithm represents level-set windows with a derived graph Ht and maintains its connected components using a rooted spanning forest H.
- 5.1.2 Updating H: As the window moves across critical values, UpdateH adds or removes vertices and their incident edges to keep H consistent with the changing level-set representation.
- 5.1.1 Maintenance of Level Set Representation: The algorithm assigns each edge a deletion-time weight so the maintained spanning tree favors updates requiring deletions rather than repeated additions and removals.
- 5.4 Complexity: O(m log(n + m)) is the overall running time for computing the smoothed Reeb graph of a graph with n vertices and m edges.
- 5.5 Complexity of the Reeb interleaving distance: “Can (X, f) and (Y, g) be ε-interleaved?” is in NP, but deciding whether the interleaving distance is zero is graph-isomorphism hard.
6 Discussion
The discussion connects Reeb graphs to persistence and broader cosheaf methods, while identifying limitations in constructibility, smoothing interpretation, and efficient interleaving-distance computation.
- Persistence: The correspondence between constructible cosheaves and R-graphs transfers persistence ideas to geometric Reeb graphs, including interleaving distances and stability results.
- Non-Constructibility: The cosheaf framework is broader than Reeb graphs because it can accommodate non-constructible cosheaves, although no immediate applications of that extra generality are claimed.
- Higher dimensions: Reeb spaces extend the construction to maps into higher-dimensional manifolds, with constructible Reeb spaces corresponding to finite-set-valued constructible cosheaves.
- Non-Constructibility: The theory emphasizes constructible objects because non-constructible cosheaves lack a clean geometric interpretation in the paper’s equivalence theorem.
- Simplification versus smoothing: Smoothing can remove small noisy loops but also globally changes the function, including steady divergence of its maximum and minimum values.
- Computational complexity: Efficient computation or estimation of the interleaving distance remains unresolved, and the obvious fixed-ε algorithm has worst-case exponential running time.