An official website of the United States government
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 }$$ of Gromov–Wasserstein distances between metric measure spaces. By exploiting a suitable interaction between specific values of the parameterspandqand the metric of the underlying spaces, we are able to determine the exact value of the distance$$d_{{{\text {GW}}}4,2}$$ between all pairs of unit spheres of different dimensions endowed with their Euclidean distance and their uniform measure.
more »
« less
Computing the Gromov-Wasserstein Distance between Two Surface Meshes Using Optimal Transport
The Gromov-Wasserstein (GW) formalism can be seen as a generalization of the optimal transport (OT) formalism for comparing two distributions associated with different metric spaces. It is a quadratic optimization problem and solving it usually has computational costs that can rise sharply if the problem size exceeds a few hundred points. Recently fast techniques based on entropy regularization have being developed to solve an approximation of the GW problem quickly. There are issues, however, with the numerical convergence of those regularized approximations to the true GW solution. To circumvent those issues, we introduce a novel strategy to solve the discrete GW problem using methods taken from statistical physics. We build a temperature-dependent free energy function that reflects the GW problem’s constraints. To account for possible differences of scales between the two metric spaces, we introduce a scaling factor s in the definition of the energy. From the extremum of the free energy, we derive a mapping between the two probability measures that are being compared, as well as a distance between those measures. This distance is equal to the GW distance when the temperature goes to zero. The optimal scaling factor itself is obtained by minimizing the free energy with respect to s. We illustrate our approach on the problem of comparing shapes defined by unstructured triangulations of their surfaces. We use several synthetic and “real life” datasets. We demonstrate the accuracy and automaticity of our approach in non-rigid registration of shapes. We provide numerical evidence that there is a strong correlation between the GW distances computed from low-resolution, surface-based representations of proteins and the analogous distances computed from atomistic models of the same proteins.
more »
« less
- Award ID(s):
- 1760485
- PAR ID:
- 10465354
- Date Published:
- Journal Name:
- Algorithms
- Volume:
- 16
- Issue:
- 3
- ISSN:
- 1999-4893
- Page Range / eLocation ID:
- 131
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
Elastic metrics can provide a powerful tool to study the heterogeneity arising from cellular morphology. To assess their potential application (e.g. classifying cancer treated cells), we consider a specific instance of the elastic metric, the Square Root Velocity (SRV) metric and evaluate its performance against the linear metric for two datasets of osteosarcoma (bone cancer) cells including pharmacological treatments, and normal and cancerous breast cells. Our comparative statistical analysis shows superior performance of the SRV at capturing cell shape heterogeneity when comparing distance to the mean shapes, with better separation and interpretation between different cell groups. Secondly, when using multidimensional scaling (MDS) to find a low-dimensional embedding for unrescaled contours, we observe that while the linear metric better preserves original pairwise distances, the SRV yields better classification.more » « less
-
Abstract 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
-
Oliva, Gabriele (Ed.)We define a new family of similarity and distance measures on graphs, and explore their theoretical properties in comparison to conventional distance metrics. These measures are defined by the solution(s) to an optimization problem which attempts find a map minimizing the discrepancy between two graph Laplacian exponential matrices, under norm-preserving and sparsity constraints. Variants of the distance metric are introduced to consider such optimized maps under sparsity constraints as well as fixed time-scaling between the two Laplacians. The objective function of this optimization is multimodal and has discontinuous slope, and is hence difficult for univariate optimizers to solve. We demonstrate a novel procedure for efficiently calculating these optima for two of our distance measure variants. We present numerical experiments demonstrating that (a) upper bounds of our distance metrics can be used to distinguish between lineages of related graphs; (b) our procedure is faster at finding the required optima, by as much as a factor of 10 3 ; and (c) the upper bounds satisfy the triangle inequality exactly under some assumptions and approximately under others. We also derive an upper bound for the distance between two graph products, in terms of the distance between the two pairs of factors. Additionally, we present several possible applications, including the construction of infinite “graph limits” by means of Cauchy sequences of graphs related to one another by our distance measure.more » « less
-
Comparing spherical probability distributions is of great interest in various fields, including geology, medical domains, computer vision, and deep representation learning. The utility of optimal transport-based distances, such as the Wasserstein distance, for comparing probability measures has spurred active research in developing computationally efficient variations of these distances for spherical probability measures. This paper introduces a high-speed and highly parallelizable distance for comparing spherical measures using the stereographic projection and the generalized Radon transform, which we refer to as the Stereographic Spherical Sliced Wasserstein (S3W) distance. We carefully address the distance distortion caused by the stereographic projection and provide an extensive theoretical analysis of our proposed metric and its rotationally invariant variation. Finally, we evaluate the performance of the proposed metrics and compare them with recent baselines in terms of both speed and accuracy through a wide range of numerical studies, including gradient flows and self-supervised learning. Our code is available at https://github.com/mint-vu/s3wd.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.3390/a16030131
