Gromov-Wasserstein Alignment of Word Embedding Spaces

David Alvarez-Melis, Tommi S. Jaakkola

Abstract

Cross-lingual or cross-domain correspondences play key roles in tasks ranging from machine translation to transfer learning. Recently, purely unsupervised methods operating on monolingual embeddings have become effective alignment tools. Current state-of-the-art methods, however, involve multiple steps, including heuristic post-hoc refinement strategies. In this paper, we cast the correspondence problem directly as an optimal transport (OT) problem, building on the idea that word embeddings arise from metric recovery algorithms. Indeed, we exploit the Gromov-Wasserstein distance that measures how similarities between pairs of words relate across languages. We show that our OT objective can be estimated efficiently, requires little or no tuning, and results in performance comparable with the state-of-the-art in various unsupervised word translation tasks.

Introduction

To translate words between languages without a dictionary, researchers often attempt to "align" word embedding spaces. If you have a vector space for English and one for French, the goal is to find a transformation that maps "cat" to "chat." The challenge is that these spaces are "unregistered"—they are learned independently and might be rotated or scaled differently. Previous unsupervised methods relied on adversarial training, which is notoriously unstable, hard to tune, and computationally expensive. This paper proposes aligning these spaces directly by comparing their internal geometric structures using Optimal Transport.

Methods: Relational Alignment via Gromov-Wasserstein

The authors frame the alignment as a Gromov-Wasserstein (GW) distance problem. Unlike standard Optimal Transport, which requires a pre-defined cost to move a point from space A to space B, GW matches points based on how their distances to other points compare. For example, if "dog" and "cat" are close in English, GW looks for two words in French that are similarly close to each other.

Visualization of intra-language similarity matrices and the resulting optimal Gromov-Wasserstein coupling.

The approach involves computing intra-language similarity matrices (using cosine similarity) for both languages. They use an iterative algorithm involving Sinkhorn iterations to make the quadratic optimization problem computationally feasible. To handle large vocabularies, they align a subset of the most frequent words (e.g., 20,000) using GW, then use the resulting "pseudo-matches" to solve a classic Procrustes problem for the rest of the vocabulary.

Key Results and Insights

The method was evaluated on major benchmarks like MUSE and the Dinu dataset. On MUSE, GW performed on par with state-of-the-art adversarial methods, achieving ~81-82% Precision@1 for EN-ES and EN-FR. On harder datasets like Dinu, GW (with normalization) outperformed previous methods, particularly on difficult pairs like English to Finnish.

Accuracy and optimization objective progress over iterations for different language pairs.

A significant advantage of this approach is its stability. Unlike adversarial methods, which can fluctuate wildly, the GW objective function decreases monotonically. This makes it much easier to monitor convergence. Furthermore, the method is remarkably efficient, running in minutes on a standard CPU, and requires almost no hyperparameter tuning.

Conclusion

Gromov-Wasserstein alignment offers a robust and efficient alternative to adversarial methods for unsupervised word translation. By exploiting the relational nature of word embeddings, it avoids the instability of GAN-based approaches while achieving comparable or superior accuracy. Future work may focus on scaling the method to even larger semantic units or different types of relational data through stochastic optimization.

Summary updated

Abstract

Cross-lingual or cross-domain correspondences play key roles in tasks ranging from machine translation to transfer learning. Recently, purely unsupervised methods operating on monolingual embeddings have become effective alignment tools. Current state-of-the-art methods, however, involve multiple steps, including heuristic post-hoc refinement strategies. In this paper, we cast the correspondence problem directly as an optimal transport (OT) problem, building on the idea that word embeddings arise from metric recovery algorithms. Indeed, we exploit the Gromov-Wasserstein distance that measures how similarities between pairs of words relate across languages. We show that our OT objective can be estimated efficiently, requires little or no tuning, and results in performance comparable with the state-of-the-art in various unsupervised word translation tasks.
BibTeX
@inproceedings{alvarezmelis2018gromov,
  author = {David Alvarez-Melis and Tommi S. Jaakkola},
  title = {{Gromov-Wasserstein Alignment of Word Embedding Spaces}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2018},
  url = {https://openreview.net/forum?id=Sk46xfzObH},
}
Figure