Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification

DOI10.1080/10618600.2023.2165500MaRDI QIDQ6141173zbMATH OpenFDO

Authors

Publication date 22 January 2024

Published in Journal of Computational and Graphical Statistics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2205.13573

zbMATH Keywords

element-wise samplingimportance samplingSinkhorn-scaling algorithmunbalanced Gromov-Wasserstein distance

Mathematics Subject Classification ID

Statistics (62-XX)

Abstract: As a valid metric of metric-measure spaces, Gromov-Wasserstein (GW) distance has shown the potential for matching problems of structured data like point clouds and graphs. However, its application in practice is limited due to the high computational complexity. To overcome this challenge, we propose a novel importance sparsification method, called extsc{Spar-GW}, to approximate GW distance efficiently. In particular, instead of considering a dense coupling matrix, our method leverages a simple but effective sampling strategy to construct a sparse coupling matrix and update it with few computations. The proposed extsc{Spar-GW} method is applicable to the GW distance with arbitrary ground cost, and it reduces the complexity from $O(n^4)$ to $O(n^{2+delta})$ for an arbitrary small $delta>0$. Theoretically, the convergence and consistency of the proposed estimation for GW distance are established under mild regularity conditions. In addition, this method can be extended to approximate the variants of GW distance, including the entropic GW distance, the fused GW distance, and the unbalanced GW distance. Experiments show the superiority of our extsc{Spar-GW} to state-of-the-art methods in both synthetic and real-world tasks.

Cites work

• A homogenized model for vortex sheets
• A statistical perspective on algorithmic leveraging
• An interpolating distance between optimal transport and Fisher-Rao metrics
• Concerning nonnegative matrices and doubly stochastic matrices
• Gromov-Wasserstein distances and the metric approach to object matching
• Monte Carlo strategies in scientific computing.
• On the geometry of metric measure spaces. I
• Optimal Distributed Subsampling for Maximum Quasi-Likelihood Estimators With Massive Data
• Optimal Transport
• Optimal transport in competition with reaction: the Hellinger-Kantorovich distance and geodesic curves
• Sampled Gromov Wasserstein
• Scaling algorithms for unbalanced optimal transport problems
• Scikit-learn: machine learning in Python
• Sliced and Radon Wasserstein barycenters of measures
• The Gromov–Wasserstein distance between networks and stable network invariants
• The Monge–Kantorovitch mass transfer and its computational fluid mechanics formulation
• Unbalanced optimal transport: dynamic and Kantorovich formulations

Cited in

(5)

• Fast gradient computation for Gromov-Wasserstein distance
• Sampling-based methods for multi-block optimization problems over transport polytopes
• Sparsification techniques for large-scale optimal transport problems
• Efficient Approximation of Leverage Scores in Two-Dimensional Autoregressive Models with Application to Image Anomaly Detection
• The Z-Gromov-Wasserstein distance

This page was built for publication: Efficient Approximation of Gromov-Wasserstein Distance Using Importance Sparsification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6141173)