Lexical Semantic Relatedness with Random Graph Walks

Thad Hughes, Daniel RamageEMNLP 2007

TL;DR

This paper introduces a novel method for measuring how semantically related two words are by modeling their connections within WordNet as a graph and using random walks to capture all possible paths between them. This approach, which leverages a new divergence measure called Zero-KL (ZKL), achieves state-of-the-art correlation with human judgments of word relatedness.

What Problem Does This Paper Address?

Many Natural Language Processing (NLP) tasks, such as question answering and document summarization, rely on understanding how semantically related words are. Existing methods often struggle with this, especially when words aren't directly linked in resources like WordNet. For instance, "furnace" and "stove" might seem related, but their direct path in WordNet's hypernymy (is-a) hierarchy is long and indirect, leading to low similarity scores. This paper aims to develop a more robust measure of semantic relatedness that accounts for all implicit and explicit paths between words, not just the shortest one, by incorporating various link types within WordNet.

Methods

The core of this work is a random walk model applied to a graph constructed from WordNet. Here's a breakdown:

  • Graph Construction: WordNet's synsets (concepts), tokens (words), and token-part-of-speech combinations are used as nodes. Edges represent various WordNet relationships (hypernymy, meronymy, etc.) and also implicit links derived from gloss definitions and shared word senses. Crucially, these edges are weighted.
  • Random Walk: A particle "walks" through this graph, stochastically following local links. The walk is biased to return to its starting point with a certain probability (β), ensuring a unique stationary distribution. This process models how "connected" a word is to all other nodes in the graph.
  • Stationary Distribution: After many steps, the proportion of time the particle spends at each node converges to a stationary distribution. This distribution is word-specific, reflecting the unique "neighborhood" of each word in the graph.
  • Relatedness Measure: The semantic relatedness between two words is then calculated by measuring the divergence between their respective stationary distributions. The authors propose a new measure called Zero-KL (ZKL) divergence, which is a novel approximation to KL-divergence designed to handle zero probabilities effectively.

The paper also explores three variants of the model based on which edge types are included: MarkovLink (WordNet relations), MarkovGloss (gloss definitions), and MarkovJoined (both).

Datasets

  • WordNet 2.1: Used as the primary lexical resource for constructing the graph.
  • Human Judgments:
    • Miller & Charles (MC) dataset: A subset of 29 noun pairs with human similarity judgments on a scale of 0-4.
  • Rubenstein & Goodenough (RG) dataset: A larger set of 65 common noun pairs with human similarity judgments.
  • WordSimilarity-353 (WS-353) dataset: A collection of 353 word pairs with human judgments on a scale of 0-10, specifically for relatedness (not just similarity).

The paper does not introduce new benchmarks but evaluates against existing human judgment datasets.

Key Insights and Ideas

  • Beyond Shortest Paths: The most significant insight is that considering all paths, not just the shortest, is crucial for robust semantic relatedness. Random walks naturally capture this by exploring the entire graph.
  • WordNet's Richness: WordNet's various link types (beyond just hypernymy) and gloss definitions contain valuable semantic information that can be leveraged by a graph-based approach.
  • Stationary Distributions as Semantic Signatures: Each word's stationary distribution acts as a unique "semantic fingerprint," capturing its connections and context within the entire WordNet graph.
  • ZKL Divergence: The proposed ZKL divergence measure is a novel and effective way to compare these semantic fingerprints, outperforming other standard divergence measures, especially when dealing with sparse distributions.
  • Model Variants Highlight Information Sources: The different model variants (MarkovLink, MarkovGloss) demonstrate the distinct contributions of WordNet's structural relationships versus its definitional text.

Key Results

  • The MarkovLink model combined with ZKL divergence achieved the highest rank correlation with human judgments on the Miller & Charles dataset, reaching an r = .903, which is at the limit of human inter-annotator agreement.
  • This approach also performed strongly on the RG and WS-353 datasets, outperforming several existing WordNet-based measures.
  • The paper shows that ZKL divergence is generally more robust than other measures, particularly for the MarkovLink model.
  • The graph construction resulted in a very sparse graph (fewer than 1 in 10,000 node pairs directly connected), highlighting the challenge of connecting words.

Limitations and Future Work

  • Parameter Sensitivity: While ZKL is shown to be relatively insensitive to the gamma parameter, other measures (like cosine similarity) might be more robust on certain model variants (e.g., MarkovGloss, MarkovJoined).
  • Integration of Other Resources: The authors suggest integrating other lexical resources like Wikipedia into the graph to further enhance the model.
  • Edge Weighting: Determining optimal relative weights for different edge types remains an open challenge, especially when combining multiple resources.
  • Task-Specific Performance: While correlation with human judgments is high, the paper expresses a desire to demonstrate performance gains in real-world NLP tasks.
  • Sense-Tagged Glosses: The MarkovGloss model's reliance on non-sense-tagged glosses introduces noise, suggesting that sense-tagged glosses would improve performance.

Summary updated

BibTeX
@inproceedings{hughes2007lexical,
  author = {Thad Hughes and Daniel Ramage},
  title = {{Lexical Semantic Relatedness with Random Graph Walks}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure