Applications in data science, shape analysis, and object classification frequently require comparison of probability distributions defined on different ambient spaces. To accomplish this, one requires a notion of distance on a given class of metric measure spaces—that is, compact metric spaces endowed with probability measures. Such distances are typically defined as comparisons between metric measure space invariants, such as distance distributions (also referred to as shape distributions, distance histograms, or shape contexts in the literature). Generally, distances defined in terms of distance distributions are actually pseudometrics, in that they may vanish when comparing nonisomorphic spaces. The goal of this paper is to set up a formal framework for assessing the discrimininative power of distance distributions, that is, the extent to which these pseudometrics fail to define proper metrics. We formulate several precise inverse problems in terms of these invariants and answer them in several categories of metric measure spaces, including the category of plane curves, where we give a counterexample to the curve histogram conjecture of Brinkman and Olver, the categories of embedded and Riemannian manifolds, where we obtain sphere rigidity results, and the category of metric graphs, where we obtain a local injectivity result along the lines of classical work of Boutin and Kemper on point cloud configurations. The inverse problems are further contextualized by the introduction of a variant of the Gromov–Wasserstein distance on the space of metric measure spaces, which is inspired by the original Monge formulation of optimal transport.
Graphs in metric spaces appear in a wide range of data sets, and there is a large body of work focused on comparing, matching, or analyzing collections of graphs in different ambient spaces. In this survey, we provide an overview of a diverse collection of distance measures that can be defined on the set of finite graphs immersed (and in some cases, embedded) in a metric space. For each of the distance measures, we recall their definitions and investigate which of the properties of a metric they satisfy. Furthermore we compare the distance measures based on these properties and discuss their computational complexity.
more » « less- NSF-PAR ID:
- 10389784
- Publisher / Repository:
- Springer Science + Business Media
- Date Published:
- Journal Name:
- La Matematica
- Volume:
- 2
- Issue:
- 1
- ISSN:
- 2730-9657
- Format(s):
- Medium: X Size: p. 197-222
- Size(s):
- p. 197-222
- Sponsoring Org:
- National Science Foundation
More Like this
-
more » « less
Abstract -
more » « less
Abstract The Gromov–Wasserstein distance—a generalization of the usual Wasserstein distance—permits comparing probability measures defined on possibly different metric spaces. Recently, this notion of distance has found several applications in Data Science and in Machine Learning. With the goal of aiding both the interpretability of dissimilarity measures computed through the Gromov–Wasserstein distance and the assessment of the approximation quality of computational techniques designed to estimate the Gromov–Wasserstein distance, we determine the precise value of a certain variant of the Gromov–Wasserstein distance between unit spheres of different dimensions. Indeed, we consider a two-parameter family
$$\{d_{{{\text {GW}}}p,q}\}_{p,q=1}^{\infty }$$ p andq and the metric of the underlying spaces, we are able to determine the exact value of the distance$$d_{{{\text {GW}}}4,2}$$ -
more » « less
Abstract To characterize the location (mean, median) of a set of graphs, one needs a notion of centrality that has been adapted to metric spaces. A standard approach is to consider the Fréchet mean. In practice, computing the Fréchet mean for sets of large graphs presents many computational issues. In this work, we suggest a method that may be used to compute the Fréchet mean for sets of graphs which is metric independent. We show that the technique proposed can be used to determine the Fréchet mean when considering the Hamming distance or a distance defined by the difference between the spectra of the adjacency matrices of the graphs.
-
Abstract. We develop persistent homology in the setting of filtrations of (Cˇech) closure spaces. Examples of filtrations of closure spaces include metric spaces, weighted graphs, weighted directed graphs, and filtrations of topological spaces. We use various products and intervals for closure spaces to obtain six homotopy theories, six cubical singular homology theories, and three simplicial singular homology theories. Applied to filtrations of closure spaces, these homology theories produce persistence modules. We extend the definition of Gromov-Hausdorff distance from metric spaces to filtrations of closure spaces and use it to prove that any persistence module obtained from a homotopy-invariant functor on closure spaces is stable.more » « less
-
The Frechet distance is often used to measure distances between paths, with applications in areas ranging from map matching to GPS trajectory analysis to hand- writing recognition. More recently, the Frechet distance has been generalized to a distance between two copies of the same graph embedded or immersed in a metric space; this more general setting opens up a wide range of more complex applications in graph analysis. In this paper, we initiate a study of some of the fundamental topological properties of spaces of paths and of graphs mapped to R^n under the Frechet distance, in an effort to lay the theoretical groundwork for understanding how these distances can be used in practice. In particular, we prove whether or not these spaces, and the metric balls therein, are path-connected.more » « less
