A Novel Sliced Fused Gromov-Wasserstein Distance

• URL: http://arxiv.org/abs/2508.02364v1
• Date: Mon, 04 Aug 2025 12:51:10 GMT
• Title: A Novel Sliced Fused Gromov-Wasserstein Distance
• Authors: Moritz Piening, Robert Beinert,
• Abstract summary: We show that our novel sliced FGW significantly reduces the numerical effort while remaining in to the distance and allowing the distance.<n>We also show that our new pseudo-metric for spaces that bounds FGW from and its geometries GW is more robust than the original GW and FGW programs.
• Score: 1.534667887016089
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The Gromov--Wasserstein (GW) distance and its fused extension (FGW) are powerful tools for comparing heterogeneous data. Their computation is, however, challenging since both distances are based on non-convex, quadratic optimal transport (OT) problems. Leveraging 1D OT, a sliced version of GW has been proposed to lower the computational burden. Unfortunately, this sliced version is restricted to Euclidean geometry and loses invariance to isometries, strongly limiting its application in practice. To overcome these issues, we propose a novel slicing technique for GW as well as for FGW that is based on an appropriate lower bound, hierarchical OT, and suitable quadrature rules for the underlying 1D OT problems. Our novel sliced FGW significantly reduces the numerical effort while remaining invariant to isometric transformations and allowing the comparison of arbitrary geometries. We show that our new distance actually defines a pseudo-metric for structured spaces that bounds FGW from below and study its interpolation properties between sliced Wasserstein and GW. Since we avoid the underlying quadratic program, our sliced distance is numerically more robust and reliable than the original GW and FGW distance; especially in the context of shape retrieval and graph isomorphism testing.

Related papers

• Pave Your Own Path: Graph Gradual Domain Adaptation on Fused Gromov-Wasserstein Geodesics [59.07903030446756]
  Graph neural networks are highly vulnerable to distribution shifts on graphs.<n>We present Gadget, the first framework for non-IID graph data.<n> Gadget can be seamlessly integrated with existing graph DA methods to handle large shifts on graphs.
  arXiv  Detail & Related papers  (2025-05-19T05:03:58Z)
• Metric properties of partial and robust Gromov-Wasserstein distances [3.9485589956945204]
  The Gromov-Wasserstein (GW) distances define a family of metrics, based on ideas from optimal transport.<n>GW distances are inherently sensitive to outlier noise and cannot accommodate partial matching.<n>We show that our new distances define true metrics, that they induce the same topology as the GW distances, and that they enjoy additional robustness to perturbations.
  arXiv  Detail & Related papers  (2024-11-04T15:53:45Z)
• Linear Partial Gromov-Wasserstein Embedding [8.23887869467319]
  The Gromov-Wasserstein (GW) problem has attracted growing interest in the machine learning and data science communities.<n>We propose the linear partial Gromov-Wasserstein embedding, a linearized embedding technique for the PGW problem.<n>Similar to the linearization technique for the classical OT problem, we prove that LPGW defines a valid metric for metric measure spaces.
  arXiv  Detail & Related papers  (2024-10-22T03:54:52Z)
• Vanishing Point Estimation in Uncalibrated Images with Prior Gravity Direction [82.72686460985297]
  We tackle the problem of estimating a Manhattan frame. We derive two new 2-line solvers, one of which does not suffer from singularities affecting existing solvers. We also design a new non-minimal method, running on an arbitrary number of lines, to boost the performance in local optimization.
  arXiv  Detail & Related papers  (2023-08-21T13:03:25Z)
• Bridging Discrete and Backpropagation: Straight-Through and Beyond [62.46558842476455]
  We propose a novel approach to approximate the gradient of parameters involved in generating discrete latent variables. We propose ReinMax, which achieves second-order accuracy by integrating Heun's method, a second-order numerical method for solving ODEs.
  arXiv  Detail & Related papers  (2023-04-17T20:59:49Z)
• 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)
• Pseudonorm Approachability and Applications to Regret Minimization [73.54127663296906]
  We convert high-dimensional $ell_infty$-approachability problems to low-dimensional pseudonorm approachability problems. We develop an algorithmic theory of pseudonorm approachability, analogous to previous work on approachability for $ell$ and other norms.
  arXiv  Detail & Related papers  (2023-02-03T03:19:14Z)
• 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)
• 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)
• On Projection Robust Optimal Transport: Sample Complexity and Model Misspecification [101.0377583883137]
  Projection robust (PR) OT seeks to maximize the OT cost between two measures by choosing a $k$-dimensional subspace onto which they can be projected. Our first contribution is to establish several fundamental statistical properties of PR Wasserstein distances. Next, we propose the integral PR Wasserstein (IPRW) distance as an alternative to the PRW distance, by averaging rather than optimizing on subspaces.
  arXiv  Detail & Related papers  (2020-06-22T14:35:33Z)
• Preventing Posterior Collapse with Levenshtein Variational Autoencoder [61.30283661804425]
  We propose to replace the evidence lower bound (ELBO) with a new objective which is simple to optimize and prevents posterior collapse. We show that Levenstein VAE produces more informative latent representations than alternative approaches to preventing posterior collapse.
  arXiv  Detail & Related papers  (2020-04-30T13:27:26Z)
• 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.