Multilingual Spectral Clustering Using Document Similarity Propagation

Dani Yogatama, Kumiko Tanaka-IshiiEMNLP 2009 · OpenReview

Abstract

We present a novel approach for multilingual document clustering using only comparable corpora to achieve cross-lingual semantic interoperability. The method models document collections as a weighted graph, and supervisory information is given as sets of must-linked constraints for documents in different languages. Recursive k-nearest neighbor similarity propagation is used to exploit the prior knowledge and merge two language spaces. Spectral method is applied to find the best cuts of the graph. Experimental results show that using limited supervisory information, our method achieves promising clustering results. Furthermore, since the method does not need any language dependent information in the process, our algorithm can be applied to languages in various alphabetical systems.

Introduction

Multilingual Document Clustering (MLDC) is the task of grouping documents by topic across different languages. The primary obstacle is cross-lingual semantic interoperability: documents in different languages typically reside in disjoint vector spaces because they share few, if any, features (words).

Traditional solutions often rely on Machine Translation (MT) to align these spaces, but MT is computationally expensive and requires extensive bilingual resources. Latent Semantic Analysis (LSA) based methods can bridge languages using cognates, but this fails for languages with different scripts or unrelated vocabularies. This paper proposes a language-independent method that utilizes comparable corpora—collections of documents on similar topics that are not direct translations—to bridge language manifolds through graph-based similarity propagation.

Methodology: Similarity Propagation and Spectral Clustering

The proposed framework consists of two main stages: constructing a unified cross-lingual affinity matrix and performing spectral clustering.

Graph Modeling

A document collection is represented as a weighted graph $G = (V, E, W)$, where $V$ is the set of documents and $W$ is the affinity matrix. Initially, weights are calculated using cosine similarity within each language. Cross-language weights are set to zero, as no direct similarity measure exists between documents of different languages.

Recursive Similarity Propagation

To bridge the language gap, the authors introduce a small number of "must-link" constraints—pairs of documents $(v_i, v_j)$ known to share the same topic in different languages. The core innovation is the Recursive Similarity Propagation algorithm. Instead of merely linking the two documents, the algorithm propagates this similarity to their respective $k$-nearest neighbors.

The similarity propagation process: an initial must-link between $v_i$ and $v_j$ (top) is propagated to their neighbors to align the language manifolds (bottom).

If document $A$ (Language 1) and document $B$ (Language 2) are linked, the algorithm assumes that the neighbors of $A$ should also be similar to $B$, and vice versa. This process is applied recursively with a decay factor $\beta$, effectively "pulling" the two language manifolds together based on their local topological structures. This creates a "broad bridge" between languages that is far more robust than isolated links.

Spectral Clustering

Once the affinity matrix is densified via propagation, spectral clustering is applied. The algorithm computes the top eigenvectors of the normalized Laplacian matrix, projecting the documents into a low-dimensional space where standard K-means clustering can effectively identify topical groups across languages.

Experimental Evaluation

The method was evaluated using the Reuters Corpus Volume 2 (RCV2), focusing on English, French, and Spanish documents across six topics (Science, Sports, Disasters, Religion, Health, and Economy).

Performance Metrics

The researchers measured performance using the Rand Index (RI), Purity, and $F_2$-measure. They specifically looked at how performance scales with the "proportion of supervisory information"—the percentage of the total possible must-link constraints provided to the system.

Clustering performance (Rand Index) for 6 and 4 topics. The "With propagation" method significantly outperforms standard spectral clustering and LSA.

Key Results

As shown in the results, the "With propagation" approach significantly outperforms both standard spectral clustering (without propagation) and LSA-based methods.

  • Efficiency of Supervision: With only 20% supervisory information, the model achieved a Rand Index of approximately 0.91 for the 6-topic task.
  • Ablation Study: The poor performance of the "Without propagation" baseline (RI ~0.69) confirms that the recursive spreading of similarity is the critical factor in aligning disparate language spaces.
  • Scalability: The performance advantage of the propagation method became more pronounced as the number of topics increased, suggesting better handling of complex, multi-topic datasets compared to LSA.

Conclusion

This research demonstrates that multilingual document clustering can be achieved effectively without heavy linguistic resources like translation dictionaries. By leveraging the local neighborhood structure of document manifolds and a small set of cross-lingual links, similarity propagation creates a language-independent bridge. This approach is particularly promising for low-resource languages or language pairs with different writing systems, where traditional alignment methods often fail.

Summary updated

Abstract

We present a novel approach for multilingual document clustering using only comparable corpora to achieve cross-lingual semantic interoperability. The method models document collections as weighted graph, and supervisory information is given as sets of must-linked constraints for documents in different languages. Recursive k-nearest neighbor similarity propagation is used to exploit the prior knowledge and merge two language spaces. Spectral method is applied to find the best cuts of the graph. Experimental results show that using limited supervisory information, our method achieves promising clustering results. Furthermore, since the method does not need any language dependent information in the process, our algorithm can be applied to languages in various alphabetical systems.
BibTeX
@inproceedings{yogatama2009multilingual,
  author = {Dani Yogatama and Kumiko Tanaka-Ishii},
  title = {{Multilingual Spectral Clustering Using Document Similarity Propagation}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2009},
  url = {https://openreview.net/forum?id=S14vFfGdZB},
}
Figure