Abstract
Much recent work in bilingual lexicon induction (BLI) views word embeddings as vectors in Euclidean space. As such, BLI is typically solved by finding a linear transformation that maps embeddings to a common space. Alternatively, word embeddings may be understood as nodes in a weighted graph. This framing allows us to examine a node's graph neighborhood without assuming a linear transform, and exploits new techniques from the graph matching optimization literature. These contrasting approaches have not been compared in BLI so far. In this work, we study the behavior of Euclidean versus graph-based approaches to BLI under differing data conditions and show that they complement each other when combined.
Introduction
Bilingual Lexicon Induction (BLI) aims to automatically generate translation dictionaries between languages using monolingual word embeddings. Traditionally, this is framed as a mapping problem: finding a linear transformation (rotation and scaling) to align two vector spaces. This Euclidean approach, typically solved via the Procrustes problem, assumes that semantic spaces across languages are "isomorphic." However, this assumption often fails for linguistically distant languages or noisy data. This paper explores an alternative graph-based framing that matches local neighborhood structures, treating embeddings as nodes in a weighted graph rather than points in a global Euclidean space.
Methodology
The study compares two distinct paradigms for BLI:
- Orthogonal Procrustes (Euclidean): This approach finds an orthogonal matrix $W$ to map source embeddings to a target space based on a set of seed translation pairs. It often employs Cross-Domain Similarity Local Scaling (CSLS) to mitigate the "hubness" problem, where certain words appear as neighbors to many others.
- Seeded Graph Matching (SGM): This graph-based approach represents each language as a similarity graph where edges denote cosine similarity. It solves the Quadratic Assignment Problem, matching nodes such that edge weights between matched pairs are maximally similar.
The authors also evaluate iterative versions of these algorithms, where induced dictionaries serve as seeds for subsequent rounds. Furthermore, a Combined Cyclic System is proposed, where SGM and Procrustes iteratively refine each other's outputs.
Experimental Setup
Experiments were conducted on English-German (En-De) and Russian-English (Ru-En) pairs using 300-dimensional fastText embeddings. Evaluation utilized MUSE dictionaries, filtered for one-to-one mappings. Performance was measured across varying seed sizes (100 to 4,000 words).
Results and Discussion
The results highlight significant differences in how these methods handle data scarcity and noise:
- Low-Data Performance: SGM significantly outperforms Procrustes when seed data is extremely limited. For Ru-En with 100 seeds, SGM achieved 50.1% P@1, while Procrustes managed only 4.1%. SGM's reliance on local topology makes it more robust to the lack of a stable global rotation.
- Iterative Improvement: While SGM starts stronger in low-data regimes, Iterative Procrustes (IterProc) demonstrates superior self-correction. Procrustes can drift away from noisy seeds toward a better global alignment, whereas SGM is more sensitive to initial seed quality.
- Hubness Mitigation: SGM's combinatorial nature inherently enforces one-to-one mappings, effectively solving the hubness problem without post-processing.
The Combined Cyclic System yielded the best overall results, reaching 62.2% P@1 for En-De with 100 seeds, surpassing standalone iterative versions.
Conclusion
This work demonstrates that Euclidean and graph-based approaches to BLI offer complementary strengths. SGM is a powerful "low-data champion" that excels in initial alignment, while Procrustes is better suited for iterative refinement. Combining these paradigms leads to more robust and accurate lexicon induction. Future work will explore the scalability of graph-based methods and their performance in domain-misaligned scenarios.
Summary updated