Gradient Flows and Riemannian Structure in the Gromov-Wasserstein Geometry

Zhengxin Zhang, Ziv Goldfeld, Kristjan Greenewald, Youssef Mroueh, Bharath SriperumbudurOpenReview 2024 · DOI · arXiv · OpenReview

TL;DR

This paper introduces the concept of gradient flows and Riemannian geometry within the Gromov-Wasserstein (GW) framework, specifically using the Inner Product GW (IGW) distance. This new approach allows for structure-preserving interpolations and analyses of probability distributions, offering a more global perspective than traditional Wasserstein methods.

What Problem Does This Paper Address?

The standard Wasserstein geometry is powerful for analyzing probability distributions and enabling gradient flow algorithms. However, it can sometimes distort the inherent structure of data, especially when dealing with tasks like shape morphing or aligning heterogeneous datasets. For instance, interpolating between a rotated cat image using Wasserstein geodesics can lead to significant distortions as it prioritizes minimizing transportation cost over preserving the shape's integrity. This paper addresses this limitation by proposing a framework based on the Gromov-Wasserstein (GW) geometry, which is designed to preserve global structure. Specifically, they focus on the Inner Product GW (IGW) distance, a variant that is particularly well-suited for this purpose due to its invariance to orthogonal transformations.

Methods

The authors introduce an implicit minimizing movement scheme for GW gradient flows, inspired by the JKO scheme for Wasserstein gradient flows. This scheme generates a sequence of distributions that are close in IGW distance and aligned in the 2-Wasserstein sense. By taking the time step to zero, they prove that this discrete solution converges to a continuous-time IGW generalized minimizing movement (GMM) that follows the continuity equation. A key innovation is the introduction of a "mobility operator" that transforms the standard Wasserstein gradient to incorporate global structure, essential for GW geometry. This analysis leads to the identification of the Riemannian structure underlying the IGW geometry, enabling a Benamou-Brenier-like formula for IGW and a formal derivation of the IGW gradient.

Datasets

Not discussed in the paper. The experiments use synthetic data, such as point clouds representing shapes like ellipses, squares, and 3D biplanes.

Key Insights and Ideas

  • Structure Preservation: The core idea is that GW geometry, particularly IGW, inherently preserves the global structure of data distributions, unlike Wasserstein geometry which can lead to significant distortions. This is crucial for applications where shape integrity is paramount.
  • Global Mobility Operator: The introduction of a mobility operator that modifies the Wasserstein gradient is a key technical contribution. This operator encodes global information, allowing the gradient flow to respect the overall structure of the distributions.
  • Riemannian Structure for IGW: The paper successfully identifies and defines a Riemannian structure for the IGW geometry, which is a significant step towards understanding its differential properties. This allows for the development of concepts like geodesics and a Benamou-Brenier-like formula.
  • IGW Gradient Flow: The paper establishes the existence and characterization of IGW gradient flows, showing they follow the continuity equation with a velocity field determined by the transformed Wasserstein gradient.

Key Results

  • Convergence of IGW Gradient Flow: The authors prove that their implicit minimizing movement scheme for IGW gradient flows converges to a continuous-time GMM that satisfies the continuity equation.
  • PIDE Characterization: They derive a partial integro-differential equation (PIDE) that characterizes the limiting IGW gradient flow, involving the mobility operator.
  • Benamou-Brenier-like Formula for IGW: A formula analogous to the Benamou-Brenier formula for Wasserstein distance is established for the intrinsic IGW metric.
  • Numerical Validation: Experiments demonstrate that IGW flows preserve shape information during interpolations (e.g., rotations) where Wasserstein flows distort shapes. This is shown for various functionals (potential, interaction, entropy) and for flow matching tasks.

Limitations and Future Work

  • IGW Tangent Space: The exact structure of the IGW tangent space remains an open question.
  • General GW Distance: The current work focuses on the Inner Product GW (IGW) distance. Extending the analysis to the full Gromov-Wasserstein distance (p,q)-GW, which is more general but analytically challenging, is a significant future direction.
  • Convergence Rates: Deriving convergence rates for the functional decay along the IGW gradient flow is suggested as future work.
  • Other Similarity Functions: Exploring GW distances with similarity functions other than the standard inner product is also proposed.
  • Understanding Mobility Operator: A deeper understanding of the properties of the mobility operator, including its fixed points, eigenvalues, and eigenfunctions, is suggested for future research.

Summary updated

Abstract

The Wasserstein space of probability measures is known for its intricate Riemannian structure, which underpins the Wasserstein geometry and enables gradient flow algorithms. However, the Wasserstein geometry may not be suitable for certain tasks or data modalities. Motivated by scenarios where the global structure of the data needs to be preserved, this work initiates the study of gradient flows and Riemannian structure in the Gromov-Wasserstein (GW) geometry, which is particularly suited for such purposes. We focus on the inner product GW (IGW) distance between distributions on Rd. Given a functional F:P2(Rd)→R to optimize, we present an implicit IGW minimizing movement scheme that generates a sequence of distributions {ρi}ni=0, which are close in IGW and aligned in the 2-Wasserstein sense. Taking the time step to zero, we prove that the discrete solution converges to an IGW generalized minimizing movement (GMM) (ρt)t that follows the continuity equation with a velocity field vt∈L2(ρt;Rd), specified by a global transformation of the Wasserstein gradient of F. The transformation is given by a mobility operator that modifies the Wasserstein gradient to encode not only local information, but also global structure. Our gradient flow analysis leads us to identify the Riemannian structure that gives rise to the intrinsic IGW geometry, using which we establish a Benamou-Brenier-like formula for IGW. We conclude with a formal derivation, akin to the Otto calculus, of the IGW gradient as the inverse mobility acting on the Wasserstein gradient. Numerical experiments validating our theory and demonstrating the global nature of IGW interpolations are provided.
BibTeX
@misc{zhang2024gradient,
  author = {Zhengxin Zhang and Ziv Goldfeld and Kristjan Greenewald and Youssef Mroueh and Bharath Sriperumbudur},
  title = {{Gradient Flows and Riemannian Structure in the Gromov-Wasserstein Geometry}},
  year = {2024},
  eprint = {2407.11800},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2407.11800},
  howpublished = {OpenReview},
}
Figure