Semidefinite Relaxations of the Gromov-Wasserstein Distance

• URL: http://arxiv.org/abs/2312.14572v3
• Date: Tue, 15 Oct 2024 13:23:42 GMT
• Title: Semidefinite Relaxations of the Gromov-Wasserstein Distance
• Authors: Junyu Chen, Binh T. Nguyen, Shang Hui Koh, Yong Sheng Soh,
• Abstract summary: The Gromov-Wasser (GW) distance is an extension 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 algorithm computes globally optimal transportation plans (in some instances) together with a proof of the global optimality.
• Score: 8.971216891353752
• License:
• Abstract: The Gromov-Wasserstein (GW) distance is an extension of the optimal transport problem that allows one to match objects between incomparable spaces. At its core, the GW distance is specified as the solution of a non-convex quadratic program and is not known to be tractable to solve. In particular, existing solvers for the GW distance are only able to find locally optimal solutions. In this work, we propose a semi-definite programming (SDP) relaxation of the GW distance. The relaxation can be viewed as the Lagrangian dual of the GW distance augmented with constraints that relate to the linear and quadratic terms of transportation plans. In particular, our relaxation provides a tractable (polynomial-time) algorithm to compute globally optimal transportation plans (in some instances) together with an accompanying proof of global optimality. Our numerical experiments suggest that the proposed relaxation is strong in that it frequently computes the globally optimal solution. Our Python implementation is available at https://github.com/tbng/gwsdp.

Related papers

• Relative-Translation Invariant Wasserstein Distance [82.6068808353647]
  We introduce a new family of distances, relative-translation invariant Wasserstein distances ($RW_p$) We show that $RW_p distances are also real distance metrics defined on the quotient set $mathcalP_p(mathbbRn)/sim$ invariant to distribution translations.
  arXiv  Detail & Related papers  (2024-09-04T03:41:44Z)
• Fast Gradient Computation for Gromov-Wasserstein Distance [17.47684854121659]
  The Gromov-Wasserstein distance is a notable extension of optimal transport. The computation of the Gromov-Wasserstein distance and transport plan is expensive. We propose a novel method to accelerate accurate gradient computation by dynamic programming techniques.
  arXiv  Detail & Related papers  (2024-04-13T11:23:34Z)
• An Oblivious Stochastic Composite Optimization Algorithm for Eigenvalue Optimization Problems [76.2042837251496]
  We introduce two oblivious mirror descent algorithms based on a complementary composite setting. Remarkably, both algorithms work without prior knowledge of the Lipschitz constant or smoothness of the objective function. We show how to extend our framework to scale and demonstrate the efficiency and robustness of our methods on large scale semidefinite programs.
  arXiv  Detail & Related papers  (2023-06-30T08:34:29Z)
• MultiZenoTravel: a Tunable Benchmark for Multi-Objective Planning with Known Pareto Front [71.19090689055054]
  Multi-objective AI planning suffers from a lack of benchmarks exhibiting known Pareto Fronts. We propose a tunable benchmark generator, together with a dedicated solver that provably computes the true Pareto front of the resulting instances. We show how to characterize the optimal plans for a constrained version of the problem, and then show how to reduce the general problem to the constrained one.
  arXiv  Detail & Related papers  (2023-04-28T07:09:23Z)
• 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)
• Efficient Approximation of Gromov-Wasserstein Distance using Importance Sparsification [34.865115235547286]
  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.
  arXiv  Detail & Related papers  (2022-05-26T18:30:40Z)
• Near-optimal estimation of smooth transport maps with kernel sums-of-squares [81.02564078640275]
  Under smoothness conditions, the squared Wasserstein distance between two distributions could be efficiently computed with appealing statistical error upper bounds. The object of interest for applications such as generative modeling is the underlying optimal transport map. We propose the first tractable algorithm for which the statistical $L2$ error on the maps nearly matches the existing minimax lower-bounds for smooth map estimation.
  arXiv  Detail & Related papers  (2021-12-03T13:45:36Z)
• Fast and Scalable Optimal Transport for Brain Tractograms [4.610968512889579]
  We present a new multiscale algorithm for solving regularized Optimal Transport problems on a linear memory footprint. We show the effectiveness of this approach on brain tractograms modeled either as bundles of fibers or as track density maps.
  arXiv  Detail & Related papers  (2021-07-05T13:28:41Z)
• Finding Global Minima via Kernel Approximations [90.42048080064849]
  We consider the global minimization of smooth functions based solely on function evaluations. In this paper, we consider an approach that jointly models the function to approximate and finds a global minimum.
  arXiv  Detail & Related papers  (2020-12-22T12:59:30Z)
• The Unbalanced Gromov Wasserstein Distance: Conic Formulation and Relaxation [0.0]
  Comparing metric measure spaces (i.e. a metric space endowed with aprobability distribution) is at the heart of many machine learning problems. The most popular distance between such metric spaces is the metric measureGro-Wasserstein (GW) distance of which is a quadratic. The GW formulation alleviates the comparison of metric spaces equipped with arbitrary positive measures up to isometries.
  arXiv  Detail & Related papers  (2020-09-09T12:38:14Z)
• 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.