PaperlayerView exact revision on arXiv

Source-linked AI summary

Measuring Distance between Reeb Graphs

Ulrich Bauer, Xiaoyin Ge, Yusu Wang

arXiv:1307.2839v2cs.CGmath.ATmath.MG

TL;DR

Reeb graphs summarize scalar functions, but comparing them requires a distance that captures graph structure while remaining stable under changes in the input function. The paper defines the functional distortion distance using continuous maps between Reeb graphs. It is stable, more discriminative than the relevant persistence-diagram bottleneck distances, and supports persistence preservation under a natural simplification.

  • Problem

    Comparing Reeb graphs requires a meaningful distance that accounts for their structure and remains stable as the input function changes.

    Source: §1 · p. 2, §2 · p. 5

  • Method

    The functional distortion distance compares Reeb graphs through continuous maps, accounting for both function-value differences and distortion of the induced distances.

    Source: §3 · p. 6

  • Results

    The distance is L∞-stable and lower-bounds bottleneck distances for both 0th ordinary and 1st extended persistence diagrams.

    Source: §8 · p. 21

  • Takeaways & Limitations

    Under the studied simplification, persistent features remain persistent, so collapsing small branches and loops does not destroy larger features.

    Source: §1 · p. 2

    Developing more efficient algorithms to approximate the functional distortion distance remains an open problem.

    Source: §8 · p. 21

Abstract

from arXiv · show

One of the prevailing ideas in geometric and topological data analysis is to provide descriptors that encode useful information about hidden objects from observed data. The Reeb graph is one such descriptor for a given scalar function. The Reeb graph provides a simple yet meaningful abstraction of the input domain, and can also be computed efficiently. Given the popularity of the Reeb graph in applications, it is important to understand its stability and robustness with respect to changes in the input function, as well as to be able to compare the Reeb graphs resulting from different functions. In this paper, we propose a metric for Reeb graphs, called the functional distortion distance. Under this distance measure, the Reeb graph is stable against small changes of input functions. At the same time, it remains discriminative at differentiating input functions. In particular, the main result is that the functional distortion distance between two Reeb graphs is bounded from below by (and thus more discriminative than) the bottleneck distance between both the ordinary and extended persistence diagrams for appropriate dimensions. As an application of our results, we analyze a natural simplification scheme for Reeb graphs, and show that persistent features in Reeb graph remains persistent under simplification. Understanding the stability of important features of the Reeb graph under simplification is an interesting problem on its own right, and critical to the practical usage of Reeb graphs.

1 Introduction

Reeb graphs summarize scalar functions, but comparing them requires a distance that is stable under function changes and sensitive to graph structure. The paper introduces the functional distortion distance and relates it to persistence, Gromov–Hausdorff distance, and simplification.

1 Introduction

  • Reeb graphs provide a useful abstraction of scalar functions and have been used in graphics and visualization applications.The paper also notes their efficient computation and relevance to high-dimensional data analysis.Source: §1 · p. 1
  • Earlier approaches for curves and merge trees do not establish the same result for loop-bearing Reeb graphs, while a branch-decomposition distance is neither stable nor general beyond trees.Source: §1 · p. 2
  • For Reeb graphs, functional distortion distance is stable under input-function perturbations, has the same type of sup norm stability as persistence diagrams, and is bounded below by persistence-diagram bottleneck distance, hence more discriminative.Source: §1 · p. 2
  • The functional distortion distance is related to a functional version of Gromov–Hausdorff distance and is equivalent to the interleaving distance on merge trees.Source: §1 · p. 2
  • Under a natural Reeb graph simplification, persistent features remain persistent, avoiding cascading destruction of larger features when small branches and loops are collapsed.The authors present this as an application of their distance results.Source: §1 · p. 2

2 Preliminaries and Problem Definition

A Reeb graph represents how connected components of level sets change as a scalar value varies. Persistence diagrams encode branching and cycle features, but not how those features are connected in the graph.

2 Preliminaries and Problem Definition

  • A Reeb graph is a quotient representation of level-set connectivity, with the scalar function inducing a function on the graph.The paper assumes regularity conditions under which the quotient has the structure of a finite 1-dimensional regular CW complex.Source: §2 · p. 3
  • The persistence setup assumes tame functions, with finitely many homologically critical levels and finite homology groups at those levels.Under the stated conditions, the Reeb graph is finite.Source: §2 · p. 3
  • Finite ordinary persistence pairs of a Reeb graph correspond to branching features, while its 1st extended persistence pairs correspond to cycle features.The paper treats these correspondences under generic assumptions on node values and types.Source: §2 · p. 5
  • Persistence diagrams record feature lifetimes but omit how features are connected, motivating a distance that also accounts for Reeb graph structure.Figure 1 illustrates two trees with identical persistence diagrams but different structures.Source: Figure 1 · p. 4, §2 · p. 5

3 A Metric on Reeb Graphs

The functional distortion distance compares both graph structure and the scalar functions carried by Reeb graphs. It uses continuous maps between the graphs and combines function-value differences with distortion of a function-induced metric.

3 A Metric on Reeb Graphs

  • Graph isomorphism alone is unsuitable because small function perturbations can create arbitrarily many new branches and loops.Source: §3 · p. 5
  • The function-induced distance between two points is the minimum height of a path joining them, equivalently the shortest interval range containing both points in one connected component.Path height is the maximum function value minus the minimum along that path.Source: §3 · p. 6
  • Continuous maps in both directions between Reeb graphs induce correspondences used to compare their points.Source: §3 · p. 6
  • The functional distortion distance combines distortion of the induced point distances with differences in function values at corresponding points.Its definition is a continuous, function-aware variant of Gromov–Hausdorff distance.Source: §3 · p. 6
  • The distance is a pseudometric, and becomes a metric on equivalence classes of Reeb graphs under function-preserving homeomorphisms.The definition also applies to graphs whose function is strictly monotonic on each edge.Source: §3 · p. 6

4 Properties of the Functional Distortion Distance

This section establishes stability and discriminative properties of the functional distortion distance, including an upper bound in terms of input-function change and lower bounds on persistence-diagram bottleneck distances. It also proves control of the first extended persistence-diagram distance via a 3δ-matching of stable cycles.

4.1 Stability

  • For tame functions on a common domain whose Reeb quotient maps have continuous sections, dFD is at most the sup-norm difference between the functions.Source: §4.1 · p. 7

4.2 Relation to Ordinary Persistence Diagram

  • For both f and -f, the 0th ordinary persistence-diagram bottleneck distance is at most dFD, covering minima/down-forks and maxima/up-forks.Source: §4.2 · p. 8

4.3 Relation to Extended Persistence Diagram

  • The 1st extended persistence-diagram bottleneck distance is at most 3dFD, relating the Reeb graphs’ cycle features to their functional distortion distance.The proof constructs a 3δ-matching between thin bases, pairing each 3δ-stable cycle exactly once with a 3δ-close cycle.Source: §4.3 · pp. 8, 9, 11
  • The comparison maps are nearly inverse on cycles, up to cycles that are not 2δ-stable, and map thin-cycle ranges into intervals expanded by δ at each endpoint.Source: §4.3 · pp. 10–11
  • The cycles specified in Proposition 4.8 form a basis for Z1(R f ).Their distinct dominating cycles imply linear independence, yielding a basis that need not be thin.Source: §4.3 · p. 12
  • The submatrix eΦ has linearly independent columns, so Hall’s theorem gives a matching covering every 3δ-stable cycle in Gf with a 3δ-close cycle in Gg.Each nonzero entry represents a pair of 3δ-close cycles; independence follows from stability of the image of any sum of selected basis cycles.Source: §4.3 · pp. 12–13
  • dB(ExDg1(R f ), ExDg1(Rg)) ≤ 3δ = 3dFD(R f , Rg), established by a 3δ-matching between the extended persistence diagrams.The proof constructs an injective map matching 3δ-stable cycles in each Reeb graph to 3δ-close cycles in the other.Source: §4.3 · pp. 13–14
  • Alternating-path augmentations modify the injective map while preserving 3δ-closeness and increase its coverage until every 3δ-stable cycle in Gg is included.Each augmentation adds one stable cycle of Gg to the image; the process terminates with a 3δ-matching.Source: §4.3 · pp. 13–14

5 Relation to Gromov–Hausdorff Distance

The functional distortion distance is related to a functional Gromov–Hausdorff distance that accounts for both metric distortion and function-value differences. The paper bounds the two distances within a factor of three and explains how continuous maps can be built from near-optimal correspondences.

5 Relation to Gromov–Hausdorff Distance

  • The functional Gromov–Hausdorff distance accounts for differences in function values as well as metric distortion between corresponding points.The functional distortion distance is described as a variant of Gromov–Hausdorff distance restricted to continuous correspondences.Source: §5 · p. 14
  • d_fGH(Rf, Rg) ≤ dFD(Rf, Rg) ≤ 3d_fGH(Rf, Rg).The functional Gromov–Hausdorff distance roughly measures distortion in both function values and induced metrics.Source: §5 · p. 14
  • Without terms controlling function values, standard Gromov–Hausdorff distance is not generally equivalent to its continuous-map variant up to a constant factor.The paper states that this relation does not hold in general.Source: §5 · p. 14
  • Starting from an ε-optimal pair of maps, the proof ε-subdivides arcs of Rf and extends the node map continuously along embedded paths in Rg; it constructs the symmetric map similarly.For every x ∈ Rf, the constructed map φε satisfies |f(x) − g ◦ φε(x)| ≤ 3β + 5ε; symmetrically, ψε satisfies the corresponding bound for every ỹ ∈ Rg.Source: §5 · p. 15

6 Relation to Interleaving Distance for Merge Trees

For merge trees, the interleaving distance and functional distortion distance are isometric. The section defines interleaving through compatible maps and proves the equality by establishing bounds in both directions.

6 Relation to Interleaving Distance for Merge Trees

  • The interleaving distance is the infimum ε for which maps in both directions are ε-compatible, with function values shifted by ε and compositions equal to 2ε-shift maps.The section assumes merge trees extended by an extra arc from the root whose function value extends to +∞.Source: §6 · p. 16
  • For two merge trees, the interleaving distance equals the functional distortion distance.The paper states that the distances are isometric for merge trees.Source: §6 · p. 16
  • The proof establishes the equality by bounding functional Gromov–Hausdorff distance by interleaving distance and interleaving distance by functional distortion distance.These inequalities are given in Lemmas 6.3 and 6.4.Source: §6 · pp. 16–17

7 Simplification of Reeb Graphs

The section defines a persistence-pair-based simplification of Reeb graphs and bounds how much it changes the graph’s functional distortion and persistence diagrams. Features with persistence at most δ can be removed while larger-persistence features are preserved with bounded change.

7.1 A Natural Simplification Scheme for Reeb Graphs

  • The scheme removes ordinary pairs by merging branches and extended pairs by merging the two sub-curves of a cycle, eliminating each corresponding diagram point.For ordinary pairs, points with equal function values on the selected paths are identified; for extended pairs, the cycle paths are merged into a monotonic arc.Source: §7.1 · pp. 18–19
  • The simplified graph is a quotient that collapses merging paths for selected persistence pairs, with the induced function preserving original function values.Each merging path has height at most the persistence of its pair.Source: §7.1 · p. 19
  • For points identified by the quotient, their functional distance is at most 2δ; for suitable monotonic paths, arbitrary preimages have distance at most 2δ plus the simplified path’s height.These bounds control the distortion introduced by the simplification.Source: §7.1 · p. 19

7.2 Distance between R and eR

  • The quotient map bounds the functional Gromov–Hausdorff distance between the original and simplified graphs by δ.The argument uses the quotient map as a correspondence and bounds the change in distances between paired points.Source: §7.2 · pp. 20–21
  • The stated diagram bound is 9δ when features of persistence at most δ are removed by the described strategy.The authors then give a direct argument improving the bound to 6δ.Source: §7.2 · p. 21
  • 6δ: removing features of persistence at most δ yields ordinary and extended persistence diagrams at bottleneck distance at most 6δ, using the improved functional-distortion bound.The stated theorem gives a 9δ bound; the authors note that a direct argument improves it to 6δ.Source: §7.2 · p. 21

8 Concluding Remarks

The paper presents functional distortion distance as a stable, discriminative way to compare Reeb graphs, and uses distance bounds to show that persistent features survive simplification. It leaves efficient computation open and identifies a factor-3 bound as a possible target for improvement.

8 Concluding Remarks

  • Functional distortion distance is stable under changes in the input function and is bounded below by bottleneck distances for the 0th ordinary and 1st extended persistence diagrams.The authors state that this makes it more discriminative than those persistence-diagram distances.Source: §8 · p. 21
  • Bounding the distance between a Reeb graph and its simplification establishes that important persistent features are preserved under simplification.The paper presents this as addressing a practical issue in using Reeb graphs.Source: §8 · p. 21
  • Theorem 4.3’s factor-3 bound remains a possible improvement target, with factor 1 proposed for comparison.The authors leave open whether that improvement is possible for functional distortion distance or another distance.Source: §8 · p. 21
  • More efficient algorithms for computing functional distortion distance remain an open problem; the authors believe an approximation algorithm may take exponential time.The paper relates this expectation to what is known for the ε-interleaving distance for merge trees.Source: §8 · p. 21
Loading 1307.2839v2…