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

• URL: http://arxiv.org/abs/2608.11016v1
• Date: Tue, 11 Aug 2026 14:58:31 GMT
• Title: Gromov-Wasserstein Quantization and Clustering: Structure, Rates, and Algorithms
• Abstract summary: This paper studies the Gromov-Wasserstein (GW) quantization, which additionally aims at clustering the ambient geometry of the space.<n>We show existence of solutions to the GW quantization problem and give a characterization that justifies an analogue to the $k$-means algorithm.<n> numerical experiments show that GW quantization opens up many modeling possibilities beyond normal clustering methods.
• Score: 2.7787719874237986
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• 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.

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)
• Approximation Theory, Computing, and Deep Learning on the Wasserstein Space [0.5735035463793009]
  We address the challenge of approximating functions in infinite-dimensional spaces from finite samples. Our focus is on the Wasserstein distance function, which serves as a relevant example. We adopt three machine learning-based approaches to define functional approximants.
  arXiv  Detail & Related papers  (2023-10-30T13:59:47Z)
• Automated regime detection in multidimensional time series data using sliced Wasserstein k-means clustering [0.0]
  We study the behaviour of the Wasserstein k-means clustering algorithm applied to time series data. We extend the technique to multidimensional time series data by approximating the multidimensional Wasserstein distance as a sliced Wasserstein distance. We show that the sWk-means method is effective in identifying distinct market regimes in real multidimensional financial time series.
  arXiv  Detail & Related papers  (2023-10-02T15:37:56Z)
• Variational Quantum Approximated Spectral Clustering [0.6718184400443239]
  We propose Variational Quantum Approximated Spectral Clustering (VQASC), which extends quantum distance-based classifier models to the clustering framework.<n>Our approach uses efficient quantum circuit designs whose depth scales sub-quadratically with dataset size, enabling the computation of weighted sums over various matrix representations of an undirected graph.
  arXiv  Detail & Related papers  (2023-09-08T17:54:42Z)
• GRAPE optimization for open quantum systems with time-dependent decoherence rates driven by coherent and incoherent controls [77.34726150561087]
  The GRadient Ascent Pulse Engineering (GRAPE) method is widely used for optimization in quantum control. We adopt GRAPE method for optimizing objective functionals for open quantum systems driven by both coherent and incoherent controls. The efficiency of the algorithm is demonstrated through numerical simulations for the state-to-state transition problem.
  arXiv  Detail & Related papers  (2023-07-17T13:37:18Z)
• Higher-order topological kernels via quantum computation [68.8204255655161]
  Topological data analysis (TDA) has emerged as a powerful tool for extracting meaningful insights from complex data. We propose a quantum approach to defining Betti kernels, which is based on constructing Betti curves with increasing order.
  arXiv  Detail & Related papers  (2023-07-14T14:48:52Z)
• End-to-end resource analysis for quantum interior point methods and portfolio optimization [63.4863637315163]
  We provide a complete quantum circuit-level description of the algorithm from problem input to problem output. We report the number of logical qubits and the quantity/depth of non-Clifford T-gates needed to run the algorithm.
  arXiv  Detail & Related papers  (2022-11-22T18:54:48Z)
• Wasserstein Iterative Networks for Barycenter Estimation [80.23810439485078]
  We present an algorithm to approximate the Wasserstein-2 barycenters of continuous measures via a generative model. Based on the celebrity faces dataset, we construct Ave, celeba! dataset which can be used for quantitative evaluation of barycenter algorithms.
  arXiv  Detail & Related papers  (2022-01-28T16:59:47Z)
• 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)
• Determinantal consensus clustering [77.34726150561087]
  We propose the use of determinantal point processes or DPP for the random restart of clustering algorithms. DPPs favor diversity of the center points within subsets. We show through simulations that, contrary to DPP, this technique fails both to ensure diversity, and to obtain a good coverage of all data facets.
  arXiv  Detail & Related papers  (2021-02-07T23:48:24Z)
• Projection Robust Wasserstein Barycenter [36.97843660480747]
  approximating the Wasserstein barycenter is numerically challenging because of the curse of dimensionality. This paper proposes the projection robust Wasserstein barycenter (PRWB) that mitigates the curse of dimensionality.
  arXiv  Detail & Related papers  (2021-02-05T19:23:35Z)

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.