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

Abstract

Clustering is a fundamental class of data analysis techniques with the most important representatives being centroid-based methods like $k$-means. Such methods are strongly connected to quantization problems, which aim to approximate general probability measures with discrete ones. For example, $k$-means corresponds to quantization with respect to the Wasserstein distance. While Wasserstein quantization clusters points within a fixed space, this paper studies Gromov-Wasserstein (GW) quantization, which additionally aims at clustering the ambient geometry of the space. We show existence of solutions to the GW quantization problem and give a characterization that justifies an analogue to the $k$-means algorithm (Lloyd's algorithm) to approximate them numerically. We further calculate the quantization rate for usual Euclidean geometries that are used in the GW context, and relate it to standard Wasserstein quantization rates. Finally, numerical experiments show that GW quantization opens up many modeling possibilities beyond normal clustering methods (e.g., for geodesic distances of 3D shapes or structured pruning of neural networks) and that the introduced algorithm leads to useful numerical solutions with approximation quality often in line with theoretically optimal rates.

Disclosure

“1/(4(n + 1)) n+1 Hence no constant c > 0 with qGW n ≥ c qW n can hold uniformly over GM, for any of the three gauges. AI Tool Disclosure. We used AI, primarily Claude Opus 5 and Fable 5, as follows: First, to identify many inaccuracies in earlier versions of this paper. Second, to generate most of the code for the experiments; we only reviewed the correctness via structural tests and by spot-checking parts o”

PDF page 46

Classification

Code generation, completion, or debugging

Multiplier

2

Verified

2026-08-23T05:09:53.212084Z

Structural counts