# Scalable unsupervised alignment of general metric and non-metric structures

arXiv: https://arxiv.org/abs/2406.13507 · HTML: https://mlsanity.com/paper/2406.13507/

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 24 of its 62 references that are in the map.
- First posted on arXiv 19 Jun 2024.

## Builds on (most cited first, 24 of 24)

- [An Image is Worth 16x16 Words: Transformers for Image Recognition at Scale](https://mlsanity.com/paper/2010.11929/) (2020)
- [Sinkhorn Distances: Lightspeed Computation of Optimal Transportation Distances](https://mlsanity.com/paper/1306.0895/) (2013)
- [Improving and generalizing flow-based generative models with minibatch optimal transport](https://mlsanity.com/paper/2302.00482/) (2023)
- [OptNet: Differentiable Optimization as a Layer in Neural Networks](https://mlsanity.com/paper/1703.00443/) (2017)
- [Fast Differentiable Sorting and Ranking](https://mlsanity.com/paper/2002.08871/) (2020)
- [Relative representations enable zero-shot latent space communication](https://mlsanity.com/paper/2209.15430/) (2022)
- [Stochastic Optimization for Large-scale Optimal Transport](https://mlsanity.com/paper/1605.08527/) (2016)
- [Deep Functional Maps: Structured Prediction for Dense Shape Correspondence](https://mlsanity.com/paper/1704.08686/) (2017)
- [Gromov-Wasserstein Alignment of Word Embedding Spaces](https://mlsanity.com/paper/1809.00013/) (2018)
- [Optimal Transport Tools (OTT): A JAX Toolbox for all things Wasserstein](https://mlsanity.com/paper/2201.12324/) (2022)
- [Fused Gromov-Wasserstein distance for structured objects: theoretical foundations and mathematical properties](https://mlsanity.com/paper/1811.02834/) (2018)
- [Tutorial on amortized optimization](https://mlsanity.com/paper/2202.00665/) (2022)
- [Linear-Time Gromov Wasserstein Distances using Low Rank Couplings and Costs](https://mlsanity.com/paper/2106.01128/) (2021)
- [Latent Space Translation via Semantic Alignment](https://mlsanity.com/paper/2311.00664/) (2023)
- [On amortizing convex conjugates for optimal transport](https://mlsanity.com/paper/2210.12153/) (2022)
- [A Unified Framework for Implicit Sinkhorn Differentiation](https://mlsanity.com/paper/2205.06688/) (2022)
- [Matrix Completion on Graphs](https://mlsanity.com/paper/1408.1717/) (2014)
- [Efficient Deformable Shape Correspondence via Kernel Matching](https://mlsanity.com/paper/1707.08991/) (2017)
- [Quantized Gromov-Wasserstein](https://mlsanity.com/paper/2104.02013/) (2021)
- [MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data](https://mlsanity.com/paper/2001.01666/) (2020)
- [Estimating matching affinity matrix under low-rank constraints](https://mlsanity.com/paper/1612.09585/) (2016)
- [Discrete Probabilistic Inverse Optimal Transport](https://mlsanity.com/paper/2112.09754/) (2021)
- [A polynomial-time relaxation of the Gromov-Hausdorff distance](https://mlsanity.com/paper/1610.05214/) (2016)
- [Spectral Geometric Matrix Completion](https://mlsanity.com/paper/1911.07255/) (2019)

## Built on by (most cited first, 2 of 2)

- [The Z-Gromov-Wasserstein Distance](https://mlsanity.com/paper/2408.08233/) (2024)
- [Latent Space Translation via Inverse Relative Projection](https://mlsanity.com/paper/2406.15057/) (2024)

## Abstract (arXiv)

Aligning data from different domains is a fundamental problem in machine learning with broad applications across very different areas, most notably aligning experimental readouts in single-cell multiomics. Mathematically, this problem can be formulated as the minimization of disagreement of pair-wise quantities such as distances and is related to the Gromov-Hausdorff and Gromov-Wasserstein distances. Computationally, it is a quadratic assignment problem (QAP) that is known to be NP-hard. Prior works attempted to solve the QAP directly with entropic or low-rank regularization on the permutation, which is computationally tractable only for modestly-sized inputs, and encode only limited inductive bias related to the domains being aligned. We consider the alignment of metric structures formulated as a discrete Gromov-Wasserstein problem and instead of solving the QAP directly, we propose to learn a related well-scalable linear assignment problem (LAP) whose solution is also a minimizer of the QAP. We also show a flexible extension of the proposed framework to general non-metric dissimilarities through differentiable ranks. We extensively evaluate our approach on synthetic and real datasets from single-cell multiomics and neural latent spaces, achieving state-of-the-art performance while being conceptually and computationally simple.