Two-Sided Wasserstein Procrustes Analysis

Kun Jin, Chaoyue Liu, Cathy XiaIJCAI 2021 · DOI

Introduction

In modern machine learning, the ability to find correspondences between disparate datasets is a fundamental challenge. Whether aligning protein structures in biology or translating word embeddings in natural language processing, we often encounter the "unsupervised alignment" problem: finding a mapping between two sets of points without pre-existing labels or a shared coordinate system.

While Optimal Transport (OT) has emerged as a powerful tool for finding point-to-point correspondences by minimizing the "cost" of moving one distribution to another, it possesses a significant limitation. Standard OT assumes that both datasets already reside in the same metric space with identical dimensions. When datasets are rotated, scaled, or exist in different dimensionalities, standard OT often fails to find a meaningful alignment.

The TWP Framework

To address these limitations, we introduce Two-Sided Wasserstein Procrustes Analysis (TWP). This framework jointly learns global transformations to map datasets into a shared latent space while simultaneously solving for the optimal local correspondences.

TWP integrates two classical mathematical concepts:

  1. Two-sided Procrustes Analysis: This provides the global geometric alignment, including rotation, projection, and scaling.
  2. Wasserstein Distance: This provides the local matching precision through an optimal transport plan.
Figure 3: Comparison of alignment results. (a) Standard Optimal Transport (OT) fails to maintain class separation when datasets are misaligned. (b) TWP successfully aligns the datasets while preserving the underlying class structure.

Joint Optimization and Geometry Preservation

Unlike previous approaches that attempt to solve for transformation and matching sequentially—a process prone to local optima—TWP optimizes the transformation matrices ($P_x, P_y$), the scaling factor ($k$), and the transport plan ($\Gamma$) simultaneously.

To ensure the transformations do not collapse the data into a single point, the authors incorporate a Laplacian-based regularizer. This term acts as a "geometric anchor," ensuring that points that are neighbors in their original high-dimensional space remain neighbors in the aligned latent space. The resulting non-convex problem is solved using a three-block Gauss-Seidel method, which iteratively updates the matching, transformation, and scaling components to ensure convergence.

Experimental Evaluation

The versatility of TWP was tested across several domains, demonstrating its robustness to noise and its ability to handle cross-dimensional alignment.

Protein Structure Alignment

In structural biology, aligning the 3D coordinates of proteins is essential for understanding functional similarities. TWP was applied to align different models of the Glutaredoxin protein. By learning the optimal rotation and translation without prior knowledge of residue correspondences, TWP achieved high-fidelity structural overlays.

Figure 6: The final alignment of two protein structures (Protein 1 and Protein 2) in a shared 3D space, demonstrating TWP's ability to find geometric correspondences in biological data.

Domain Adaptation and Language Translation

TWP's performance on synthetic "Moons" datasets showed remarkable robustness, maintaining 100% accuracy across rotation angles up to 130 degrees—a scenario where competing methods like OTDA and JDOT failed. In real-world benchmarks like the Office-Caltech image dataset, TWP outperformed established domain adaptation methods in the majority of cross-domain tasks. Furthermore, in unsupervised word translation, TWP proved competitive with state-of-the-art adversarial methods, particularly in English-Spanish and English-French pairs.

Conclusion

Two-Sided Wasserstein Procrustes Analysis offers a robust, dimension-agnostic solution for unsupervised dataset alignment. By combining global geometric transformations with local transport plans, it overcomes the rigid requirements of standard Optimal Transport. While the computational cost of solving the underlying optimization problems remains a consideration for very large-scale data, TWP represents a significant step forward in aligning complex, high-dimensional distributions.

Summary updated

BibTeX
@inproceedings{jin2021two,
  author = {Kun Jin and Chaoyue Liu and Cathy Xia},
  title = {{Two-Sided Wasserstein Procrustes Analysis}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2021},
  doi = {10.24963/ijcai.2021/484},
}
Figure