TL;DR
This paper introduces a novel unsupervised framework to align and embed heterogeneous datasets into a shared, arbitrary metric space (Euclidean or non-Euclidean). By combining unbalanced optimal transport (OT) with Gromov-Wasserstein (GW) marginal penalization, the method successfully maps data without known correspondences while preserving their intrinsic geometries.
What Problem Does This Paper Address?
In machine learning and data science, we often need to compare or integrate datasets from completely different domains—such as matching 3D shapes in different poses or aligning single-cell multi-omics data (e.g., genomic vs. transcriptomic profiles). When these datasets live in different spaces, there is no straightforward "ground cost" or distance metric to compare them directly.
While methods like the Gromov-Wasserstein (GW) distance can compare datasets by looking at their internal geometries, they don't actually embed the data into a shared space for joint visualization or downstream analysis. Existing joint embedding methods, like Joint Multidimensional Scaling (JMDS), solve this but are strictly limited to Euclidean spaces. This paper tackles the challenge of embedding heterogeneous datasets into arbitrary target metric spaces, including non-Euclidean geometries like spheres or tori.
Methods
The authors propose a framework called Embedded Wasserstein with GW Penalization ($EW_\lambda$).
At its core, the method sets up an unbalanced optimal transport problem to find a transport plan between the two datasets. To ensure that the embedding doesn't distort the original datasets' structures, the objective function penalizes the marginals using GW distances back to the original spaces.
Mathematically, the problem is reformulated as a quadratic, multi-marginal, unbalanced OT problem over "4-plans" (linking the two source spaces and two copies of the target space). To solve this computationally heavy problem, the authors introduce a bi-convex relaxation. This allows them to alternate between fixing different parts of the transport plan and solving the subproblems efficiently using an entropic regularization scheme (a multi-marginal Sinkhorn algorithm).
A key conceptual contribution is how this method relates to JMDS:
- JMDS fixes the data weights and optimizes the coordinates (supports) of the embedding in a Euclidean space.
- This paper's method fixes the coordinates (supports) as a predefined grid on any arbitrary metric space and optimizes the weights of the atomic measures. This shift is what unlocks the ability to use non-Euclidean target spaces.
Datasets
The method was evaluated on a mix of synthetic and real-world datasets:
- Synthetic 3D Shapes: S-bended rectangles, Swiss rolls (with and without holes), spheres, and tori.
- FAUST Dataset: A standard benchmark containing 3D mesh scans of human shapes in various poses.
- Real-World Single-Cell Multi-Omics:
- SNAREseq: 1,047 single cells with 19 features in one modality and 10 in another.
- scGEM: 177 specimens with 34 and 27 features across two modalities.
- FashionMNIST: Used for 2D shape matching and comparing latent spaces of Autoencoders (AE) vs. Variational Autoencoders (VAE).
Key Insights and Ideas
- Non-Euclidean Flexibility: By fixing the target space's support grid rather than optimizing coordinates, the framework can seamlessly embed data into complex geometries like the 2-sphere or a torus.
- The Role of $\lambda$: The penalization parameter $\lambda$ acts as a geometric dial. As $\lambda \to \infty$, the objective converges to the exact "embedded Wasserstein distance," strictly enforcing isometry. As $\lambda \to 0$, the Wasserstein term dominates, forcing the embeddings to perfectly overlap into a fixed-support GW barycenter.
- Avoiding Artifacts: Unlike JMDS, which can introduce tearing or unexpected holes when unrolling complex geometries due to its free-support nature, this fixed-support approach preserves topological properties much better during alignment.
Key Results
- 3D Shape Alignment: When embedding human shapes from the FAUST dataset into $\mathbb{R}^2$, the proposed method achieved lower distortion errors ($GW^2 = 0.0048$) and better alignment ($W^2 = 0.027$) than JMDS ($GW^2 = 0.0057, W^2 = 0.046$) at $\lambda = 10$.
- Single-Cell Alignment: On the SNAREseq dataset, the method achieved a FOSCTTM score of 0.165 (lower is better, indicating a higher fraction of samples correctly matched) and a KNN classification accuracy of 0.943, outperforming JMDS (0.219 / 0.872), SCOT (0.402 / 0.447), and UnionCom (0.436 / 0.380).
Limitations and Future Work
The primary limitation of this method is the curse of dimensionality. Because it relies on a fixed, predefined grid in the target space, the computational complexity scales exponentially with the dimension of the target space. Consequently, the target space is practically restricted to low dimensions (e.g., 2D or 3D manifolds).
As a future direction, the authors aim to develop a non-Euclidean free-support solver. This would combine the geometric flexibility of this method with the coordinate-optimizing nature of GW barycenter algorithms, potentially bypassing the need for a rigid grid.
Summary updated