Leveraging the Wikipedia Graph for Evaluating Word Embeddings

Joachim Giesen, Paul Kahlmeyer, Frank Nussbaum, Sina Zarrieß

Introduction

Word embeddings are fundamental to modern Natural Language Processing (NLP), representing words as vectors in a high-dimensional space where semantic similarity is captured by geometric proximity. Traditionally, these embeddings are evaluated against human-curated datasets where participants rate the similarity of word pairs. However, such datasets are expensive to produce, difficult to scale, and often unavailable for low-resource languages.

To address these challenges, researchers have introduced WALES (Wikipedia Agent using Local Embedding Similarities). This novel metric leverages the inherent semantic structure of the Wikipedia hyperlink graph to evaluate embeddings automatically and at scale. By tasking an AI agent to navigate between articles using only local embedding similarities, WALES provides a robust proxy for semantic understanding that correlates strongly with human judgment.

The WALES Framework

The core of the WALES approach is the Information Foraging framework applied to the Wikipedia graph, where articles serve as nodes and hyperlinks as edges.

The evaluation involves a "greedy" agent starting at a source article (e.g., Baseball) with the goal of reaching a target article (e.g., Earth). At each step, the agent examines the titles of all articles linked from its current location. It then selects the next node based on the highest cosine similarity between the candidate article's title and the target article's title, as determined by the word embedding under evaluation.

Figure 3: Example navigation paths from 'baseball' to 'earth' using different word embedding models.

The Metric

The performance of an embedding is quantified by the WALES score:

$$WALES = \frac{L_{shortest}}{L_{actual}}$$

where $L_{shortest}$ is the theoretical shortest path in the graph and $L_{actual}$ is the length of the path taken by the agent. A score of 1.0 indicates perfect navigation efficiency. To prevent aimless wandering, a penalty parameter ($\gamma$) is often applied to longer paths.

Experimental Results and Validation

The researchers tested WALES using a subgraph of English Wikipedia (approx. 38,609 nodes) across several standard embeddings: Word2Vec, GloVe, fasttext, and ELMo.

Correlation with Human Benchmarks

A critical finding is that WALES correlates strongly with traditional human-labeled datasets. As shown in the correlation heatmap below, WALES exhibits particularly high Spearman rank correlation with datasets focused on semantic relatedness (e.g., WordSim-353-rel) rather than just strict similarity.

Figure 1: Correlation matrix between the WALES metric and various traditional human-labeled semantic evaluation datasets.

Key Findings

  • Performance Rankings: In navigation tasks, fasttext and GloVe consistently outperformed Word2Vec and the context-dependent ELMo in efficiency.
  • Human vs. Agent: Agents utilizing high-quality embeddings like fasttext frequently discovered shorter paths than the average human player in "The Wiki Game," suggesting that embedding geometry effectively captures latent semantic connections.
  • Efficiency: The metric is computationally inexpensive; evaluating 1,000 tasks takes less than three seconds on modern hardware, making it an ideal "sanity check" during the model development cycle.

Discussion and Limitations

While WALES offers a scalable alternative to human benchmarks, it has limitations. Wikipedia titles are predominantly nouns, which may bias the evaluation against verbs or adjectives compared to specialized datasets like SimVerb-3500. Furthermore, the metric's reliability depends on the density and quality of the underlying Wikipedia graph, which can vary significantly across different languages.

Despite these constraints, the portability of Wikipedia—available in over 300 languages—makes WALES a powerful tool for evaluating embeddings in low-resource settings. Future work may involve extending this framework to other structured knowledge bases like Wikidata or using navigation efficiency as a training objective to further refine word representations.

Summary updated

Abstract

Deep learning models for different NLP tasks often rely on pre-trained word embeddings, that is, vector representations of words. Therefore, it is crucial to evaluate pre-trained word embeddings independently of downstream tasks. Such evaluations try to assess whether the geometry induced by a word embedding captures connections made in natural language, such as, analogies, clustering of words, or word similarities. Here, traditionally, similarity is measured by comparison to human judgment. However, explicitly annotating word pairs with similarity scores by surveying humans is expensive. We tackle this problem by formulating a similarity measure that is based on an agent for routing the Wikipedia hyperlink graph. In this graph, word similarities are implicitly encoded by edges between articles. We show on the English Wikipedia that our measure correlates well with a large group of traditional similarity measures, while covering a much larger proportion of words and avoiding explicit human labeling. Moreover, since Wikipedia is available in more than 300 languages, our measure can easily be adapted to other languages, in contrast to traditional similarity measures.
BibTeX
@inproceedings{giesen2022leveraging,
  author = {Joachim Giesen and Paul Kahlmeyer and Frank Nussbaum and Sina Zarrieß},
  title = {{Leveraging the Wikipedia Graph for Evaluating Word Embeddings}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2022},
  doi = {10.24963/ijcai.2022/574},
}
Figure