Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms

This paper introduces and analyzes the Gromov–Wasserstein (GW) quantization problem, which extends classical Wasserstein quantization (and thus k-means clustering) to the setting of gauged measure spaces, where the goal is to approximate a probability measure by a discrete one while directly preserving the intrinsic relational structure (gauge) between points, rather than only the ambient metric.

The main contributions are:

• Problem formulation and existence: The GW quantization problem is defined for general gauged measure spaces, and it is shown to admit a solution (Theorem 3.4). The solution is characterized: the optimal gauge matrix is given by block means of the original gauge (Theorem 3.2), and optimal couplings concentrate on Voronoi cells defined by certain cost functions (Theorem 3.3).

• Quantization rates: For Euclidean spaces with gauges given by the Euclidean distance, its square, or the scalar product, two-sided bounds relating the GW quantization value to constant multiples of the Wasserstein quantization value are established (Proposition 4.1, Theorems 4.3 and 4.5). These yield the sharp rate q GW n(X) n-1/d (Corollaries 4.4 and 4.6). The lower-bound constants are shown to be necessarily measure-dependent (Appendix E).

• Monge maps: For the scalar-product gauge, existence of Monge maps (optimal couplings induced by a measurable map) from the input space to an optimal quantizer is proven (Theorem 4.7). In one dimension, the GW quantization problem reduces exactly to the Wasserstein one (Theorem 4.8).

• Algorithm: A conditional gradient method (Algorithm 1) is proposed as a Lloyd-type algorithm for GW quantization. It is shown to monotonically decrease the objective when a line search is used, and its cluster points are stationary (Theorem 5.3). For the scalar-product gauge, the unit step size is monotone and, on finite spaces, the iteration terminates in finitely many steps (Corollary 5.4).

• Numerical experiments: Proof-of-concept experiments demonstrate the practical utility: quantizing 3D shapes (Subsection 6.1), accelerating pairwise GW distance computations (Subsection 6.2), empirically confirming the theoretical quantization rates (Subsection 6.3), and pruning neural networks (Subsection 6.4).

Key technical details from the paper:

• The GW quantization problem is defined as q GW n(X) = Y in GM n GW 2(X, Y), where GM n is the set of gm-spaces supported on at most n points.

• Existence is proven via a minimizing sequence argument, using weak compactness and the pointwise bound from Theorem 3.2.

• The characterization in Theorem 3.4 states that for an optimal quantizer = ([n],,) with optimal coupling, the gauge satisfies i,i' = 1 over i i' integral integral g(x,x') d i(x) d i'(x'), and each i is concentrated on the set where the cost i(x) = sum i' integral (g(x,x') - i,i') squared d i'(x') is minimal.

• For the Euclidean distance gauge, the upper bound is q GW n(X) at most 2L q W n(xi) with L the Lipschitz constant of the gauge as a function of the metric (Proposition 4.1). The lower bound is q GW n(X) at least sqrt lambda(xi) q W n(xi) for the squared distance, and q GW n(X) at least sqrt lambda(xi) over diam(X) q W n(xi) for the distance (Theorem 4.3).

• For the scalar product gauge, the bounds are sqrt lambda(M xi) q W n(xi) at most q GW n(X) at most sqrt 2 lambda(M xi) q W n(xi) (Theorem 4.5).

• The algorithm is derived as a conditional gradient method on the reduced objective R(pi) = G Q GW(G, pi). The directional derivative is given by 2 sum i integral i(pi) d(eta i - pi i) (Proposition 5.1).

• The numerical experiments show that GW quantization produces structurally different clusters than Wasserstein k-means (e.g., preserving geodesic structure in 3D shapes), achieves approximation errors consistent with the theoretical rates, and can be used to prune neural networks more effectively than baseline methods.

Improvements to AI Systems:

1. Structure-Aware Data Compression and Clustering

• Replace standard k-means/Wasserstein clustering with GW quantization in unsupervised learning pipelines to preserve intrinsic relational structures (e.g., geodesic distances, graph adjacency, or similarity matrices) rather than only Euclidean distances.

• Capability: AI systems can cluster non-Euclidean data (e.g., social networks, molecular structures, 3D meshes) with clusters that maintain topological and geometric coherence, improving downstream tasks like anomaly detection or community detection.

2. Efficient Pairwise Distance Acceleration for Graph/Shape Matching

• Use GW quantization to create a small set of representative prototype structures (e.g., subgraphs or shape templates) and compute pairwise GW distances only between these prototypes, then approximate full pairwise distances via a Nyström-like extension.

• Capability: AI systems can scale graph matching, shape retrieval, or domain adaptation to large datasets (millions of nodes/shapes) with near-linear complexity, enabling real-time retrieval in databases of 3D objects or knowledge graphs.

3. Theoretically-Grounded Quantization for Generative Models

• Integrate the sharp rate q GW n n-1/d into autoencoder or VAE training as a regularizer, replacing standard reconstruction loss with a GW quantization loss on latent codes.

• Capability: Generative models learn latent spaces that preserve relational structure between data points (e.g., preserving pairwise similarity in latent space), leading to more meaningful interpolations and better out-of-distribution detection.

4. Monge-Map-Based Optimal Transport for Domain Adaptation

• Leverage the proven existence of Monge maps (Theorem 4.7) for scalar-product gauges to design deterministic, invertible transformations between source and target domains in transfer learning.

• Capability: AI systems can perform exact, structure-preserving domain alignment (e.g., aligning sensor data from different devices) without stochastic sampling, improving robustness in cross-domain classification or regression.

5. Neural Network Pruning with Structural Preservation

• Apply the GW quantization algorithm (Algorithm 1) to prune neurons/weights by clustering them based on their activation patterns or weight correlations (as gauges), rather than magnitude or Hessian-based methods.

• Capability: Pruned networks retain functional redundancy and relational structure between neurons, leading to higher accuracy retention and better generalization after pruning, especially for graph neural networks or transformers.

6. Monotone, Convergent Lloyd-Type Algorithms for Non-Euclidean Data

• Replace heuristic clustering updates in self-organizing maps or neural gas with the conditional gradient method (Theorem 5.3), which guarantees monotone decrease and stationarity.

• Capability: AI systems can train structure-preserving quantizers on manifolds or graphs with provable convergence, eliminating the need for manual tuning of learning rates or step sizes.

7. Finite-Time Termination for Discrete-State Systems

• For discrete gauges (e.g., categorical data or finite graphs), use the finite-step termination property (Corollary 5.4) to design exact clustering algorithms that stop in a bounded number of iterations.

• Capability: AI systems can perform exact, reproducible clustering on discrete data (e.g., categorical features in tabular data) without stochastic approximations, improving interpretability and auditability in high-stakes applications like healthcare or finance.

8. Sharp Rate-Based Sample Complexity Bounds

• Use the two-sided bounds (Theorems 4.3 and 4.5) to derive minimum required quantizer size n for a given approximation error in structure-preserving compression tasks.

• Capability: AI systems can automatically determine optimal memory/accuracy trade-offs in compressing large-scale relational data (e.g., knowledge graphs or point clouds), reducing storage costs while guaranteeing error bounds.