An Analysis of Euclidean vs. Graph-Based Framing for Bilingual Lexicon Induction from Word Embedding Spaces

Kelly Marchisio, Youngser Park, Ali Saad-Eldin, Anton Alyakin, Kevin Duh, Carey E. Priebe, Philipp Koehn

Abstract

This research presents the first head-to-head comparison between two fundamentally different paradigms for inducing bilingual dictionaries from word embeddings: treating them as vectors in a Euclidean space versus nodes in a weighted graph. We demonstrate that while Euclidean methods excel at global alignment with sufficient supervision, graph-based methods are significantly more robust in low-resource scenarios. By integrating both approaches into a combined cyclic system, we achieve performance that surpasses either method in isolation, effectively addressing the "cold start" problem in bilingual lexicon induction.

Introduction

Bilingual Lexicon Induction (BLI) is the task of automatically finding word translations using only monolingual word embeddings. Traditionally, this has been framed as a Euclidean geometry problem: if English and German word vectors are structurally similar (isomorphic), one can find a linear transformation to align the two clouds. However, linguistic differences and training noise often cause these embedding spaces to diverge, leading to alignment failure.

An alternative is the graph-based view, which treats words as nodes in a graph where edges represent semantic similarity. Instead of rotating a global cloud, this approach attempts to match graphs by finding nodes with similar local neighborhood structures. Until now, these two perspectives had not been rigorously compared or integrated.

Methodological Paradigms

The study evaluates two representative algorithms:

  1. Procrustes (Euclidean): A standard approach that solves for an orthogonal mapping matrix to align seed words, using nearest-neighbor search to identify new translations.
  2. Seeded Graph Matching (SGM): A combinatorial optimization approach that aligns the adjacency matrices of the two language graphs, focusing on connectivity patterns rather than linear relationships.
Comparison of Euclidean (a) and Graph-based (b) alignment paradigms.

Key Insights and Results

Experiments using fastText embeddings for English, German, and Russian revealed distinct operational strengths for each method:

  • SGM as the "Low-Seed Hero": With only 100 known translation pairs, Procrustes manages only ~4% precision. In contrast, SGM leverages local graph structure to achieve over 45-50% precision, making it far superior when supervision is scarce.
  • Procrustes as the "Bootstrapping Beast": While SGM starts strong, its improvement slows as more seeds are added. Procrustes, once provided enough data to perceive the global alignment, improves much faster during iterative bootstrapping rounds.
  • The Combined Cyclic System: Because the methods fail in different ways—Euclidean methods struggle with non-isometry, while graph methods struggle with scaling—they are highly complementary. In a combined system, SGM can provide high-confidence initial seeds that Procrustes then uses for rapid global refinement.
The combined cyclic system and the preference for SGM vs. Iterative Procrustes based on seed count.

Conclusion

The findings suggest that the choice between Euclidean and graph-based methods should be dictated by the available data. Graph-based methods are essential for low-resource "cold starts," while Euclidean methods are better suited for large-scale iterative refinement. Future work will focus on reducing the computational complexity of graph matching to scale these hybrid systems to larger vocabularies and many-to-many translation mappings.

Summary updated

BibTeX
@inproceedings{marchisio2021analysis,
  author = {Kelly Marchisio and Youngser Park and Ali Saad-Eldin and Anton Alyakin and Kevin Duh and Carey E. Priebe and Philipp Koehn},
  title = {{An Analysis of Euclidean vs. Graph-Based Framing for Bilingual Lexicon Induction from Word Embedding Spaces}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2021},
  url = {https://openreview.net/forum?id=_CmfGIJSBdj},
}
Figure