Research map / Point clouds / Point cloud classification
Generalized Dimension Reduction Using Semi-Relaxed Gromov-Wasserstein Distance
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Proposes manifold-valued multidimensional scaling via semi-relaxed Gromov-Wasserstein distance, proving Monge-map existence, connections to Gromov-Hausdorff distance, and an SRGW+GD algorithm applied to MNIST, rotated MNIST, world cities, and redistricting ensembles.
Problem
Dimension reduction usually embeds data into Euclidean space, but practitioners often want embeddings into other manifolds or metric spaces that reflect known geometry or topology; the classical MDS objective does not directly handle such targets.
Approach
Generalizes semi-relaxed Gromov-Wasserstein distance to L^p-type distortions on general metric measure spaces, shows it is realized by a Monge map under cocompact isometric group actions, links the p=infinity symmetrized version to modified Gromov-Hausdorff distance, and uses srGW solutions to initialize gradient descent on the MDS functional.
Key results
- On MNIST into R^2, SRGW+GD achieves slightly lower distortion than SMACOF MDS on all ten digit datasets and runs 3 to 14 times faster.
- On rotated MNIST embedded into S^1, SRGW+GD achieves lower distortion than circular coordinates (CC) and lower than naive GD in nearly all cases.
- On 20 world cities embedded into a sphere of radius 6371 km, SRGW+GD keeps pairwise distance errors within 14 km, versus distortion 264.724 for MDS into R^3.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use SRGW+GD instead of SMACOF MDS for Euclidean embeddings | MNIST digit datasets · MNIST0–MNIST9 | distortion (dis_2): 1.556 -> 1.554; 0.794 -> 0.777; 1.761 -> 1.751; 1.594 -> 1.586; 1.523 -> 1.518; 1.602 -> 1.594; 1.495 -> 1.477; 1.350 -> | Helped |
| Use SRGW+GD instead of SMACOF MDS for planar embeddings | Rotated MNIST datasets · R-MNIST0–R-MNIST9 (R²) | distortion (dis_2): 1.989 -> 1.987; 1.200 -> 1.202; 2.020 -> 2.019; 1.873 -> 1.873; 1.880 -> 1.828; 1.812 -> 1.812; 1.942 -> 1.900; 1.828 -> | Mixed |
| Initialize gradient descent with the srGW embedding instead of random initialization | SRGW+GD · Rotated MNIST on S¹ | distortion (dis_2) | Helped |
| Use SRGW+GD instead of circular coordinates (CC) | Rotated MNIST circular embeddings · R-MNIST datasets on S¹ | distortion (dis_2): 5.467 -> 2.534; 1.818 -> 1.702; 5.586 -> 2.591; 5.459 -> 2.439; 4.846 -> 2.329; 5.325 -> 2.401; 2.758 -> 2.437; 2.594 -> | Helped |
| Embed the 20 city locations on a geodesic sphere instead of using an MDS embedding in R³ | SRGW+GD · 20 largest world cities | pairwise distance error: 14 kilometers; 264.724 | Helped |
| Use a circle as the target space for redistricting ensembles | SRGW+GD visualizations · Two-district redistricting ensembles | qualitative geometry preservation | Helped |
Surprising findings
- The srGW p-distance does not satisfy the triangle inequality for p < infinity, so it is not a pseudometric in that regime.
Limitations
- The Monge map guarantee relies on the source space being finite and the target being proper with a cocompact isometry group action.
- The srGW approximation via POT is not guaranteed to produce a Monge map, though it did in practice.
- Choosing the target manifold scale or the initial discretized grid requires hyperparameters such as grid size and scale factors.
Experimental setup
Datasets: MNIST rotated MNIST (self-generated) 20 largest world cities (WGS-84 geodesic distances) redistricting ensembles of 1,000 ReCom plans for six two-district states using Census blockgroups
Benchmarks: MNIST rotated MNIST world cities geodesic distances redistricting ensembles
Metrics: distortion (dis_2) compute time maximum pairwise distance error (km)
Baselines: PCA SMACOF MDS t-SNE circular coordinates naive gradient descent (GD)
Builds on: Gromov-Wasserstein distance semi-relaxed Gromov-Wasserstein distance SMACOF MDS Gromov-Hausdorff distance ReCom algorithm
Closest papers by meaning
- Neuc-MDS: Non-Euclidean Multidimensional Scaling Through Bilinear Forms (NeurIPS 2024 · similarity 0.86)
- Randomized Dimensionality Reduction for Euclidean Maximization and Diversity Measures (ICML 2025 · similarity 0.86)
- Finsler Multi-Dimensional Scaling: Manifold Learning for Asymmetric Dimensionality Reduction and Embedding (CVPR 2025 · similarity 0.85)
- Bridging Arbitrary and Tree Metrics via Differentiable Gromov Hyperbolicity (NeurIPS 2025 · similarity 0.85)
- Semidefinite Relaxations of the Gromov-Wasserstein Distance (NeurIPS 2024 · similarity 0.85)
- Implications of Distance over Redistricting Maps: Central and Outlier Maps (AAAI 2024 · similarity 0.85)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.