The Z-Gromov-Wasserstein Distance

• URL: http://arxiv.org/abs/2408.08233v3
• Date: Mon, 06 Jan 2025 16:39:40 GMT
• Title: The Z-Gromov-Wasserstein Distance
• Abstract summary: The Gromov-Wasserstein (GW) distance is a powerful tool for comparing metric measure spaces.<n>We introduce a method for comparing $Z$-networks by defining a generalization of GW distance.<n>This construction subsumes many previously known metrics and offers a unified approach to understanding their shared properties.
• Score: 7.05973856505985
• License: http://creativecommons.org/publicdomain/zero/1.0/
• Abstract: The Gromov-Wasserstein (GW) distance is a powerful tool for comparing metric measure spaces which has found broad applications in data science and machine learning. Driven by the need to analyze datasets whose objects have increasingly complex structure (such as node and edge-attributed graphs), several variants of GW distance have been introduced in the recent literature. With a view toward establishing a general framework for the theory of GW-like distances, this paper considers a vast generalization of the notion of a metric measure space: for an arbitrary metric space $Z$, we define a $Z$-network to be a measure space endowed with a kernel valued in $Z$. We introduce a method for comparing $Z$-networks by defining a generalization of GW distance, which we refer to as $Z$-Gromov-Wasserstein ($Z$-GW) distance. This construction subsumes many previously known metrics and offers a unified approach to understanding their shared properties. This paper demonstrates that the $Z$-GW distance defines a metric on the space of $Z$-networks which retains desirable properties of $Z$, such as separability, completeness, and geodesicity. Many of these properties were unknown for existing variants of GW distance that fall under our framework. Our focus is on foundational theory, but our results also include computable lower bounds and approximations of the distance which will be useful for practical applications.

Related papers

• Beyond Procrustes distances: a multilinear Gromov-Wasserstein distance capturing chirality [1.053849862914584]
  Existing shape analysis metrics fail to distinguish between a shape and its mirror image.<n>We introduce a multilinear generalization of the Gromov-Wasserstein objective.<n>We develop efficient algorithms to compute the Chiral Gromov-Wasserstein distances.
  arXiv  Detail & Related papers  (2026-08-27T23:14:38Z)
• Terminal Dimension Reduction for Time Series with Applications [53.49083917849734]
  Terminal embeddings have emerged as a powerful tool for dimension reduction.<n>We develop a generalization of terminal embeddings to affine line-segments that overcomes this issue.<n>We obtain the first dimension-free coresets for clustering time-series under the Fréchet distance.
  arXiv  Detail & Related papers  (2026-07-10T15:05:30Z)
• $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)
• Magnitude Distance: A Geometric Measure of Dataset Similarity [9.19444526847653]
  We propose textitmagnitude distance, a novel distance metric on finite datasets.<n>We prove several theoretical properties of magnitude distance, including its limiting behavior across scales.<n>We show that magnitude distance remains discriminative in high-dimensional settings when the scale is appropriately tuned.
  arXiv  Detail & Related papers  (2026-02-09T16:23:43Z)
• $\mathbb{R}^{2k}$ is Theoretically Large Enough for Embedding-based Top-$k$ Retrieval [99.8640829555514]
  This paper studies the minimal dimension required to embed subset memberships ($m$ elements and $mchoose k$ subsets of at most $k$ elements) into vector spaces, denoted as Minimal Embeddable Dimension (MED)<n>The tight bounds of MED are derived theoretically and supported empirically for various notions of "distances" or "similarities," including the $ell$ metric, inner product and cosine similarity.
  arXiv  Detail & Related papers  (2026-01-28T18:45:43Z)
• DP-CSGP: Differentially Private Stochastic Gradient Push with Compressed Communication [71.60998478544028]
  We propose Differentially Private Gradient Push with Compressed communication (termedfrac-CSGP) for decentralized learning graphs.<n>For general non-math and smooth objective functions, we show that our algorithm is designed to maintain high accuracy and efficient communication.
  arXiv  Detail & Related papers  (2025-12-15T17:37:02Z)
• Infinity Search: Approximate Vector Search with Projections on q-Metric Spaces [94.12116458306916]
  We show that in $q$-metric spaces, metric trees can leverage a stronger version of the triangle inequality to reduce comparisons for exact search.<n>We propose a novel projection method that embeds datasets with arbitrary dissimilarity measures into $q$-metric spaces.
  arXiv  Detail & Related papers  (2025-06-06T22:09:44Z)
• 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. GW distances are inherently sensitive to outlier noise and cannot accommodate partial matching. 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)
• 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)
• Parameterized Approximation Schemes for Clustering with General Norm Objectives [0.6956677722498498]
  This paper considers the well-studied regime of designing a $(k,epsilon)$-approximation algorithm for a $k$-clustering problem. Our main contribution is a clean and simple EPAS that settles more than ten clustering problems.
  arXiv  Detail & Related papers  (2023-04-06T15:31:37Z)
• 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)
• Supervised Training of Conditional Monge Maps [107.78770597815242]
  Optimal transport (OT) theory describes general principles to define and select, among many possible choices, the most efficient way to map a probability measure onto another. We introduce CondOT, a multi-task approach to estimate a family of OT maps conditioned on a context variable. We demonstrate the ability of CondOT to infer the effect of an arbitrary combination of genetic or therapeutic perturbations on single cells.
  arXiv  Detail & Related papers  (2022-06-28T19:34:44Z)
• 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)
• FriendlyCore: Practical Differentially Private Aggregation [67.04951703461657]
  We propose a simple and practical tool $mathsfFriendlyCore$ that takes a set of points $cal D$ from an unrestricted (pseudo) metric space as input. When $cal D$ has effective diameter $r$, $mathsfFriendlyCore$ returns a "stable" subset $cal D_Gsubseteq cal D$ that includes all points. $mathsfFriendlyCore$ can be used to preprocess the input before privately aggregating it, potentially simplifying the aggregation or boosting its accuracy
  arXiv  Detail & Related papers  (2021-10-19T17:43:50Z)
• 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)
• A deep network construction that adapts to intrinsic dimensionality beyond the domain [79.23797234241471]
  We study the approximation of two-layer compositions $f(x) = g(phi(x))$ via deep networks with ReLU activation. We focus on two intuitive and practically relevant choices for $phi$: the projection onto a low-dimensional embedded submanifold and a distance to a collection of low-dimensional sets.
  arXiv  Detail & Related papers  (2020-08-06T09:50:29Z)
• 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.