Metric graphs are meaningful objects for modeling complex structures that arise in many real-world applications, such as road networks, river systems, earthquake faults, blood vessels, and filamentary structures in galaxies. To study metric graphs in the context of comparison, we are interested in determining the relative discriminative capabilities of two topology-based distances between a pair of arbitrary finite metric graphs: the persistence distortion distance and the intrinsic Cech distance. We explicitly show how to compute the intrinsic Cech distance between two metric graphs based solely on knowledge of the shortest systems of loops for the graphs. Our main theorem establishes an inequality between the intrinsic Cech and persistence distortion distances in the case when one of the graphs is a bouquet graph and the other is arbitrary. The relationship also holds when both graphs are constructed via wedge sums of cycles and edges.
Recently, several distances for comparing metric graphs have been proposed based on ideas from computational topology. In the case of a special type of metric graph called a Reeb graph, these distances include: the functional distortion distance @cite_5 , the combinatorial edit distance @cite_24 , the interleaving distance @cite_3 , and its variant in the setting of merge trees @cite_26 . In particular, the functional distortion distance can be considered as a variation of the Gromov-Hausdorff distance between two metric spaces @cite_5 . The interleaving distance is defined via algebraic topology and utilizes the equivalence between Reeb graphs and cosheaves @cite_3 . For metric graphs in general, both the persistence distortion distance @cite_6 and the intrinsic distance @cite_18 take into consideration the structure of metric graphs, independent of their geometric embeddings, by treating them as continuous metric spaces. In @cite_10 , Oudot and Solomon point out that since compact geodesic spaces can be approximated by finite metric graphs in the Gromov--Hausdorff sense @cite_13 (see also the recent work of M 'emoli and Okutan @cite_16 ), one can study potentially complicated length spaces by studying the persistence distortion of a sequence of approximating graphs.
@cite_13 @cite_18 @cite_26 @cite_6 @cite_3 @cite_24 @cite_5 @cite_16 @cite_10
1756475526 1511069251 2962902468 2890370060 2570705339 2142420687 2012238497 1968781546 2093171982
The Reeb graph is a construction that studies a topological space through the lens of a real valued function. It has been commonly used in applications, however its use on real data means that it is desirable and increasingly necessary to have methods for comparison of Reeb graphs. Recently, several metrics on the set of Reeb graphs have been proposed. In this paper, we focus on two: the functional distortion distance and the interleaving distance. The former is based on the Gromov-Hausdorff distance, while the latter utilizes the equivalence between Reeb graphs and a particular class of cosheaves. However, both are defined by constructing a near-isomorphism between the two graphs of study. In this paper, we show that the two metrics are strongly equivalent on the space of Reeb graphs. Our result also implies the bottleneck stability for persistence diagrams in terms of the Reeb graph interleaving distance. Metric graphs are ubiquitous in science and engineering. For example, many data are drawn from hidden spaces that are graph-like, such as the cosmic web. A metric graph offers one of the simplest yet still meaningful ways to represent the non-linear structure hidden behind the data. In this paper, we propose a new distance between two finite metric graphs, called the persistence-distortion distance, which draws upon a topological idea. This topological perspective along with the metric space viewpoint provide a new angle to the graph matching problem. Our persistence-distortion distance has two properties not shared by previous methods: First, it is stable against the perturbations of the input graph metrics. Second, it is a continuous distance measure, in the sense that it is defined on an alignment of the underlying spaces of input graphs, instead of merely their nodes. This makes our persistence-distortion distance robust against, for example, different discretizations of the same underlying graph. Despite considering the input graphs as continuous spaces, that is, taking all points into account, we show that we can compute the persistence-distortion distance in polynomial time. The time complexity for the discrete case where only graph nodes are considered is much faster. We propose a metric for Reeb graphs, called the functional distortion distance. Under this distance, 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 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. A standard result in metric geometry is that every compact geodesic metric space can be approximated arbitrarily well by finite metric graphs in the Gromov-Hausdorff sense. It is well known that the first Betti number of the approximating graphs may blow up as the approximation gets finer. In our work, given a compact geodesic metric space @math , we define a sequence @math of non-negative real numbers by @math By construction, and the above result, this is a non-increasing sequence with limit @math . We study this sequence and its rates of decay with @math . We also identify a precise relationship between the sequence and the first Vietoris-Rips persistence barcode of @math . Furthermore, we specifically analyze @math and find upper and lower bounds based on hyperbolicity and other metric invariants. As a consequence of the tools we develop, our work also provides a Gromov-Hausdorff stability result for the Reeb construction on geodesic metric spaces with respect to the function given by distance to a reference point. This paper addresses the basic question of how well a tree can approximate distances of a metric space or a graph. Given a graph, the problem of constructing a spanning tree in a graph which strongly preserves distances in the graph is a fundamental problem in network design. We present scaling distortion embeddings where the distortion scales as a function of @math , with the guarantee that for each @math simultaneously, the distortion of a fraction @math of all pairs is bounded accordingly. Quantitatively, we prove that any finite metric space embeds into an ultrametric with scaling distortion @math . For the graph setting, we prove that any weighted graph contains a spanning tree with scaling distortion @math . These bounds are tight even for embedding into arbitrary trees. These results imply that the average distortion of the embedding is constant and that the @math distortion is @math . For probabilistic embedding into spanning trees we prove a scaling distortion of @math , which implies constant @math -distortion for every fixed @math . We introduce a novel measure called e-four-pointscondition (e-4PC), which assigns a value e ∈ [0,1] to every metric space quantifying how close the metric is to a tree metric. Data-sets taken from real Internet measurements indicate remarkable closeness of Internet latencies to tree metrics based on this condition. We study embeddings of e-4PC metric spaces into trees and prove tight upper and lower bounds. Specifically, we show that there are constants c1 and c2 such that, (1) every metric (X,d) which satisfies the e-4PC can be embedded into a tree with distortion (1+e)c1log|X|, and (2) for every e ∈: [0,1] and any number of nodes, there is a metric space (X,d) satisfying the e-4PC that does not embed into a tree with distortion less than (1+e)c2log|X|. In addition, we prove a lower bound on approximate distance labelings of e-4PC metrics, and give tight bounds for tree embeddings with additive error guarantees. We consider the problem of computing the smallest possible distortion for embedding of a given n-point metric space into ℝ d , where d is fixed (and small). For d = 1, it was known that approximating the minimum distortion with a factor better than roughly n 1 12 is NP-hard. From this result we derive inapproximability with a factor roughly n 1 (22d-10) for every fixed d ≥ 2, by a conceptually very simple reduction. However, the proof of correctness involves a nontrivial result in geometric topology (whose current proof is based on ideas due to Jussi Vaisala), For d > 3, we obtain a stronger inapproximability result by a different reduction: assuming P≠NP, no polynomial-time algorithm can distinguish between spaces embeddable in ℝ d with constant distortion from spaces requiring distortion at least n c d , for a constant c > 0. The exponent c d has the correct order of magnitude, since every n-point metric space can be embedded in ℝ d with distortion O(n 2 d log 3 2 n) and such an embedding can be constructed in polynomial time by random projection. For d = 2, we give an example of a metric space that requires a large distortion for embedding in ℝ 2 , while all not too large subspaces of it embed almost isometrically. We dene a notion of a measured length space X having nonnegative N-Ricci curvature, for N 2 [1;1), or having1-Ricci curvature bounded below byK, forK2 R. The denitions are in terms of the displacement convexity of certain functions on the associated Wasserstein metric space P2(X) of probability measures. We show that these properties are preserved under measured Gromov-Hausdor limits. We give geometric and analytic consequences. This paper has dual goals. One goal is to extend results about optimal transport from the setting of smooth Riemannian manifolds to the setting of length spaces. A second goal is to use optimal transport to give a notion for a measured length space to have Ricci curvature bounded below. We refer to [11] and [44] for background material on length spaces and optimal transport, respectively. Further bibliographic notes on optimal transport are in Appendix F. In the present introduction we motivate the questions that we address and we state the main results. To start on the geometric side, there are various reasons to try to extend notions of curvature from smooth Riemannian manifolds to more general spaces. A fairly general setting is that of length spaces, meaning metric spaces (X;d) in which the distance between two points equals the inmum of the lengths of curves joining the points. In the rest of this introduction we assume that X is a compact length space. Alexandrov gave a good notion of a length space having bounded below by K", with K a real number, in terms of the geodesic triangles in X. In the case of a Riemannian manifold M with the induced length structure, one recovers the Riemannian notion of having sectional curvature bounded below by K. Length spaces with Alexandrov curvature bounded below by K behave nicely with respect to the GromovHausdor topology on compact metric spaces (modulo isometries); they form We introduce and study the notion of the average distortion of a nonexpanding embedding of one metric space into another. Less sensitive than the multiplicative metric distortion, the average distortion captures well the global picture, and, overall, is a quite interesting new measure of metric proximity, related to the concentration of measure phenomenon. We establish close mutual relations between the MinCut- MaxFlow gap in a uniform-demand multicommodity flow, and the average distortion of embedding the suitable (dual) metric into l1. These relations are exploited to show that the shortest-path metrics of special (e.g., planar, bounded treewidth, etc.) graphs embed into l1 with constant average distortion. The main result of the paper claims that this remains true even if l1 is replaced with the line. This result is further sharpened for graphs of a bounded treewidth.