Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing

• URL: http://arxiv.org/abs/2609.03094v1
• Date: Wed, 02 Sep 2026 19:08:50 GMT
• Title: Discrete Gromov-Wasserstein Duality: Algorithms and Isomorphism Testing
• Abstract summary: The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure.<n>Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived.<n>This work furnishes a novel duality result for GW distances with and without entropic regularization.<n>We propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees.
• Score: 15.240268958496172
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The Gromov-Wasserstein (GW) distance provides a principled framework for aligning metric measure (mm) spaces based solely on their intrinsic structure. Its ability to identify isomorphic representations of distributions across spaces renders it valuable for comparing data where equality up to isomorphism occurs naturally such as in graphs or, more generally, distributions on graphs. Recently, a type of dual form for the GW distance between Euclidean distributions with the squared Euclidean or inner product costs was derived, spurring the development of new statistical and algorithmic results for this setting. This work furnishes a novel duality result for GW distances with and without entropic regularization that is applicable to all finitely supported mm spaces. Leveraging this result, we derive the sample complexity of empirical GW distances between finite mm spaces, as well as limit distributions under proper centering and scaling. Furthermore, we propose new algorithms for solving the regularized GW problem which are subject to formal convergence guarantees. These statistical and algorithmic advancements give rise to a principled and efficient framework for testing whether two distributions on the set of graphs with a fixed number of nodes are isomorphic based on samples.

Related papers

• $k$-Nearest Neighbors in Gromov--Wasserstein Space [0.0]
  We implement $k$-nearest neighbors ($k$-NN) classification using the Gromov--Wasserstein (GW) and fGW distances.<n>We show that GW-$k$-NN and fGW-$k$-NN consistently perform well across multiple graph datasets.
  arXiv  Detail & Related papers  (2026-06-09T01:33:01Z)
• Convex Distance Operator Transport: A Convex and Geometry-Preserving Formulation [9.94046521985351]
  We introduce Convex Distance Transport Operator (CDOT), the first convex optimal transport framework that aligns distributions across heterogeneous domains.<n>CDOT employs an operator-based regularization that aligns aggregated distance structures by introducing distance and conditional expectation operators.
  arXiv  Detail & Related papers  (2026-06-01T10:38:09Z)
• GMapLatent: Geometric Mapping in Latent Space [51.317738404571514]
  Cross-domain generative models based on encoder-decoder AI architectures have attracted much attention in generating realistic images.<n>We introduce a canonical latent space representation based on geometric mapping to align the cross-domain latent spaces in a rigorous and precise manner.<n>Experiments on gray-scale and color images validate the efficiency, efficacy and applicability of GMapLatent.
  arXiv  Detail & Related papers  (2025-03-30T12:02:36Z)
• Learning with Norm Constrained, Over-parameterized, Two-layer Neural Networks [54.177130905659155]
  Recent studies show that a reproducing kernel Hilbert space (RKHS) is not a suitable space to model functions by neural networks. In this paper, we study a suitable function space for over- parameterized two-layer neural networks with bounded norms.
  arXiv  Detail & Related papers  (2024-04-29T15:04:07Z)
• 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)
• Spatially relaxed inference on high-dimensional linear models [48.989769153211995]
  We study the properties of ensembled clustered inference algorithms which combine spatially constrained clustering, statistical inference, and ensembling to aggregate several clustered inference solutions. We show that ensembled clustered inference algorithms control the $delta$-FWER under standard assumptions for $delta$ equal to the largest cluster diameter.
  arXiv  Detail & Related papers  (2021-06-04T16:37:19Z)
• Distributional Sliced Embedding Discrepancy for Incomparable Distributions [22.615156512223766]
  Gromov-Wasserstein (GW) distance is a key tool for manifold learning and cross-domain learning. We propose a novel approach for comparing two computation distributions, that hinges on the idea of distributional slicing, embeddings, and on computing the closed-form Wasserstein distance between the sliced distributions.
  arXiv  Detail & Related papers  (2021-06-04T15:11:30Z)
• 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)
• Finding Geometric Models by Clustering in the Consensus Space [61.65661010039768]
  We propose a new algorithm for finding an unknown number of geometric models, e.g., homographies. We present a number of applications where the use of multiple geometric models improves accuracy. These include pose estimation from multiple generalized homographies; trajectory estimation of fast-moving objects.
  arXiv  Detail & Related papers  (2021-03-25T14:35:07Z)
• Block-Approximated Exponential Random Graphs [77.4792558024487]
  An important challenge in the field of exponential random graphs (ERGs) is the fitting of non-trivial ERGs on large graphs. We propose an approximative framework to such non-trivial ERGs that result in dyadic independence (i.e., edge independent) distributions. Our methods are scalable to sparse graphs consisting of millions of nodes.
  arXiv  Detail & Related papers  (2020-02-14T11:42:16Z)
• 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.