Breaking isometric ties and introducing priors in Gromov-Wasserstein distances

Pinar Demetci, Quang Huy Tran, Ievgen Redko, Ritambhara SinghAISTATS 2024 · OpenReview

Abstract

Gromov-Wasserstein distance has many applications in machine learning due to its ability to compare measures across metric spaces and its invariance to isometric transformations. However, in certain applications, this invariant property can be too flexible, thus undesirable. Moreover, the Gromov-Wasserstein distance solely considers pairwise sample similarities in input datasets, disregarding the raw feature representations. We propose a new optimal transport formulation, called Augmented Gromov-Wasserstein (AGW), that allows for some control over the level of rigidity to transformations. It also incorporates feature alignments, enabling us to better leverage prior knowledge on the input data for improved performance. We first present theoretical insights into the proposed method. We then demonstrate its usefulness for single-cell multi-omic alignment tasks and heterogeneous domain adaptation in machine learning.

Introduction

In machine learning and computational biology, aligning datasets from disparate feature spaces—such as comparing gene expression in mice to protein levels in humans—is a fundamental challenge. The Gromov-Wasserstein (GW) distance is frequently employed for this task because it is isometry-invariant, focusing on internal relational structures rather than absolute coordinates.

However, this invariance can be a double-edged sword. GW cannot distinguish between a shape and its reflection or rotation if the internal distances remain the same. For instance, in digit recognition, GW might incorrectly align a '6' with a '9'. Furthermore, GW ignores raw feature values, making it difficult to incorporate expert knowledge (priors) about which features should correspond.

Methodology: Augmented Gromov-Wasserstein (AGW)

To address these limitations, we introduce Augmented Gromov-Wasserstein (AGW). AGW acts as a bridge between two existing optimal transport techniques:

  1. Gromov-Wasserstein (GW): Preserves relational structure between samples.
  2. CO-Optimal Transport (COOT): Focuses on raw feature representations and jointly learns alignments for both samples and features.

The AGW formulation uses a convex combination of GW and COOT losses, controlled by a hyperparameter $\alpha$. By optimizing this joint loss via a Block Coordinate Descent (BCD) algorithm, AGW learns two coupling matrices: one for samples and one for features. This dual-alignment approach allows feature-level similarities to guide the geometric alignment, effectively "breaking ties" between mathematically identical but semantically distinct isometries.

Experimental Results

We evaluated AGW across several domains, including digit alignment, single-cell multi-omics, and heterogeneous domain adaptation.

Digit Alignment and Breaking Isometric Ties

In the task of matching MNIST (28x28) and USPS (16x16) digits, AGW significantly outperformed baseline methods. While GW and COOT struggled with certain digit pairs due to geometric symmetries, AGW's ability to leverage feature-level information allowed for more accurate alignments.

Figure 2: Alignment of MNIST and USPS digits showing AGW's superior accuracy and ability to resolve isometric ambiguities.

As shown in Figure 2, AGW achieved an accuracy of 68.20%, compared to 48.13% for GW and 58.41% for COOT. The feature coupling learned by AGW helps distinguish between digits that are often misaligned by methods relying solely on geometry or raw features alone.

Biological Precision in Multi-omics

On the CITE-seq dataset, which involves aligning antibody levels with gene expression, AGW demonstrated superior precision. It correctly assigned 19 out of 25 antibodies to their encoding genes in an unsupervised setting, outperforming UCOOT and COOT.

Figure 6: Alignment probability and correlation matrices for CITE-seq data comparing AGW, COOT, UCOOT, and bindSC.

Key Insights

  • Guidance via Priors: AGW allows for the inclusion of prior knowledge, such as orthologous genes, by penalizing the feature coupling matrix. This "feature-level supervision" leads to substantial improvements in sample-level alignment quality.
  • Efficiency: AGW often converges in approximately 1/5th the iterations required by standard GW, as the COOT term provides a refining effect that stabilizes the optimization process.
  • Theoretical Robustness: AGW satisfies a relaxed triangle inequality and is more restrictive than GW in a semantically helpful way, while remaining more flexible than COOT.

Conclusion

AGW provides a powerful framework for cross-domain alignment by balancing geometric structure with feature-level information. While highly effective, future work will address the "balanced mass" constraint to handle datasets with varying sample sizes or significant outliers. Additionally, exploring AGW in continuous spaces remains an open area of research.

Summary updated

Abstract

Gromov-Wasserstein distance has many applications in machine learning due to its ability to compare measures across metric spaces and its invariance to isometric transformations. However, in certain applications, this invariant property can be too flexible, thus undesirable. Moreover, the Gromov-Wasserstein distance solely considers pairwise sample similarities in input datasets, disregarding the raw feature representations. We propose a new optimal transport formulation, called Augmented Gromov-Wasserstein (AGW), that allows for some control over the level of rigidity to transformations. It also incorporates feature alignments, enabling us to better leverage prior knowledge on the input data for improved performance. We first present theoretical insights into the proposed method. We then demonstrate its usefulness for single-cell multi-omic alignment tasks and heterogeneous domain adaptation in machine learning.
BibTeX
@inproceedings{demetci2024breaking,
  author = {Pinar Demetci and Quang Huy Tran and Ievgen Redko and Ritambhara Singh},
  title = {{Breaking isometric ties and introducing priors in Gromov-Wasserstein distances}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2024},
  url = {https://openreview.net/forum?id=I4dMvOIjGo},
}
Figure