Efficient Approximation of Gromov-Wasserstein Distance using Importance
Sparsification
- URL: http://arxiv.org/abs/2205.13573v1
- Date: Thu, 26 May 2022 18:30:40 GMT
- Title: Efficient Approximation of Gromov-Wasserstein Distance using Importance
Sparsification
- Authors: Mengyu Li, Jun Yu, Hongteng Xu, Cheng Meng
- Abstract summary: We propose a novel importance sparsification method, called Spar-GW, to approximate Gromov-Wasserstein distance efficiently.
We demonstrate that the proposed Spar-GW method is applicable to the GW distance with arbitrary ground cost.
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.
- Score: 34.865115235547286
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: As a valid metric of metric-measure spaces, Gromov-Wasserstein (GW) distance
has shown the potential for the matching problems of structured data like point
clouds and graphs. However, its application in practice is limited due to its
high computational complexity. To overcome this challenge, we propose a novel
importance sparsification method, called 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. We demonstrate that the
proposed Spar-GW method is applicable to the GW distance with arbitrary ground
cost, and it reduces the complexity from $\mathcal{O}(n^4)$ to
$\mathcal{O}(n^{2+\delta})$ for an arbitrary small $\delta>0$. 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 Spar-GW to
state-of-the-art methods in both synthetic and real-world tasks.
Related papers
- Scalable 3D Registration via Truncated Entry-wise Absolute Residuals [65.04922801371363]
A $3$D registration approach can process more than ten million ($107$) point pairs with over $99%$ random outliers.
We call our method TEAR, as it involves minimizing an outlier-robust loss that computes Truncated Entry-wise Absolute Residuals.
arXiv Detail & Related papers (2024-04-01T04:43:39Z) - Partial Gromov-Wasserstein Metric [8.503892585556901]
The Gromov-Wasserstein (GW) distance has gained increasing interest in the machine learning community in recent years.
We propose a particular case of the UGW problem, termed Partial Gromov-Wasserstein (PGW)
arXiv Detail & Related papers (2024-02-06T03:36:05Z) - Semidefinite Relaxations of the Gromov-Wasserstein Distance [11.014678654943234]
The Gromov-Wasser (GW) distance is a variant of the optimal transport problem that allows one to match objects between spaces.
In this work, we propose a semi-definite relaxation of the GW distance.
Our relaxation provides a manner to compute the ratio of any transport to the global optimal solution.
arXiv Detail & Related papers (2023-12-22T10:09:52Z) - Linearized Wasserstein dimensionality reduction with approximation
guarantees [65.16758672591365]
LOT Wassmap is a computationally feasible algorithm to uncover low-dimensional structures in the Wasserstein space.
We show that LOT Wassmap attains correct embeddings and that the quality improves with increased sample size.
We also show how LOT Wassmap significantly reduces the computational cost when compared to algorithms that depend on pairwise distance computations.
arXiv Detail & Related papers (2023-02-14T22:12:16Z) - Outlier-Robust Gromov-Wasserstein for Graph Data [31.895380224961464]
We introduce a new and robust version of the Gromov-Wasserstein (GW) distance called RGW.
RGW features optimistically perturbed marginal constraints within a Kullback-Leibler divergence-based ambiguity set.
We demonstrate the effectiveness of RGW on real-world graph learning tasks, such as subgraph matching and partial shape correspondence.
arXiv Detail & Related papers (2023-02-09T12:57:29Z) - Communication-Efficient Adam-Type Algorithms for Distributed Data Mining [93.50424502011626]
We propose a class of novel distributed Adam-type algorithms (emphi.e., SketchedAMSGrad) utilizing sketching.
Our new algorithm achieves a fast convergence rate of $O(frac1sqrtnT + frac1(k/d)2 T)$ with the communication cost of $O(k log(d))$ at each iteration.
arXiv Detail & Related papers (2022-10-14T01:42:05Z) - Orthogonal Gromov-Wasserstein Discrepancy with Efficient Lower Bound [11.086440815804226]
The Gromov-Wasserstein (GW) formulates a node graph between the structured data based on optimal transportation datasets.
We take inspiration from the connection with the assignment problem, and propose the Gromov-Wasserstein discrepancy as a surrogate of GW.
arXiv Detail & Related papers (2022-05-12T02:10:56Z) - Quantized Gromov-Wasserstein [10.592277756185046]
Quantized Gromov Wasserstein (qGW) is a metric that treats parts as fundamental objects and fits into a hierarchy of theoretical upper bounds for the problem.
We develop an algorithm for approximating optimal GW matchings which yields algorithmic speedups and reductions in memory complexity.
We are able to go beyond outperforming state-of-the-art and apply GW matching at scales that are an order of magnitude larger than in the existing literature.
arXiv Detail & Related papers (2021-04-05T17:03:20Z) - Byzantine-Resilient Non-Convex Stochastic Gradient Descent [61.6382287971982]
adversary-resilient distributed optimization, in which.
machines can independently compute gradients, and cooperate.
Our algorithm is based on a new concentration technique, and its sample complexity.
It is very practical: it improves upon the performance of all prior methods when no.
setting machines are present.
arXiv Detail & Related papers (2020-12-28T17:19:32Z) - Fast and Robust Comparison of Probability Measures in Heterogeneous
Spaces [62.35667646858558]
We introduce the Anchor Energy (AE) and Anchor Wasserstein (AW) distances, which are respectively the energy and Wasserstein distances instantiated on such representations.
Our main contribution is to propose a sweep line algorithm to compute AE emphexactly in log-quadratic time, where a naive implementation would be cubic.
We show that AE and AW perform well in various experimental settings at a fraction of the computational cost of popular GW approximations.
arXiv Detail & Related papers (2020-02-05T03:09:23Z)
This list is automatically generated from the titles and abstracts of the papers in this site.
This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.