Language Model-Based Document Clustering Using Random Walks

Güneş ErkanNAACL 2006

TL;DR

This paper introduces a novel document representation for clustering that leverages language models and random walks on a document graph. By representing documents as vectors of generation probabilities from other documents' language models, and then reinforcing these probabilities with random walks, the authors achieve significant improvements over traditional TF-IDF representations in document clustering tasks.

What Problem Does This Paper Address?

Traditional document clustering methods often rely on the "bag-of-words" model, where documents are represented as vectors of term frequencies (like TF-IDF). While effective, this approach can miss nuanced semantic relationships between documents. The authors propose that documents generated from similar language models are likely to belong to the same cluster. They aim to capture these deeper semantic connections by moving beyond simple term co-occurrence and instead modeling how likely one document is to generate another, and then using graph-based techniques to refine these relationships.

Methods

The core of the paper lies in a new document representation and a method to enhance it:

  • Language Model Generation Probabilities: Instead of term-based vectors, each document is represented as an n-dimensional vector, where 'n' is the total number of documents in the corpus. The j-th dimension of document d_i's vector represents the probability that d_i is generated by the language model of document d_j. To handle varying document lengths, these probabilities are "flattened" (normalized) to ensure comparability.
  • Generation Graph: These generation probabilities form the basis of a directed graph where documents are nodes and link weights are proportional to the generation probabilities. This graph can be thought of as documents "citing" each other based on their language model similarities.
  • Reinforcement with Random Walks: To discover "hidden" semantic relationships not immediately apparent from direct generation links, the authors employ random walks on this generation graph. By simulating random walks of a fixed length (t-steps), they compute "t-step generation probabilities." These probabilities, aggregated into gent vectors, capture indirect relationships and reinforce existing ones, providing a richer representation.
  • Top Generators and Sparsity: To address computational efficiency and focus on strong relationships, they introduce the concept of "top generators," considering only the 'c' documents that yield the highest generation probabilities for each document. This results in sparse vectors, making computations like cosine similarity more efficient.

Datasets

The authors evaluated their method using several standard corpora:

  • classic3: A collection of technical paper abstracts from three different areas.
  • bbc and bbcsport: Corpora of BBC news articles, with 5 news classes each.
  • 20news: A large corpus of newsgroup articles, divided into 20 classes.
  • Reuters-21578 and TDT2: Corpora used for hierarchical clustering experiments, containing news articles with single labels.

Key Insights and Ideas

  • Language Model Similarity is a Stronger Signal: The fundamental idea that documents generated by similar language models are semantically related is a powerful insight that drives the entire approach.
  • Random Walks Uncover Hidden Connections: Direct generation probabilities are a good start, but random walks are crucial for revealing deeper, indirect semantic links between documents that might otherwise be missed.
  • Sparsity for Efficiency: The "top generators" approach effectively creates sparse vectors, which is vital for scaling graph-based methods to larger datasets without prohibitive computational costs.
  • Graph Structure Matters: Viewing document relationships as a directed graph and applying graph traversal techniques like random walks offers a novel perspective on document similarity.

Key Results

The paper demonstrates significant improvements over the traditional TF-IDF representation across various clustering algorithms (k-means, single-link, average-link, complete-link) and datasets.

  • K-means: The proposed gent vectors (especially gen² and gen³ representing 2-step and 3-step random walks) consistently outperformed TF-IDF, with accuracy improvements often in the range of 10-20 percentage points. The confidence intervals for gent vectors were also narrower, indicating more stable results.
  • Hierarchical Clustering: Average-link clustering with gent vectors achieved the highest results, outperforming TF-IDF. While TF-IDF occasionally performed comparably to gen¹ and gen², gen³ generally showed the best performance.
  • Parameter Sensitivity: The authors found that the number of outgoing links per document (c) needed to be sufficiently large (around 80) for good performance, and the random walk parameter t=3 yielded the best results, suggesting that longer walks can make vectors too dense.

Limitations and Future Work

  • Parameter Tuning: While the authors aimed for minimal parameter tuning, they acknowledge that performance can be sensitive to parameters like c (number of top generators) and t (random walk length). They found c=80 and t=3 to be good general choices.
  • Scalability: Although sparsity helps, the initial computation of all-pairs generation probabilities can still be computationally intensive for very large corpora.
  • Future Work: The authors suggest investigating various graph-based relationships for explaining semantic structure in text collections. Potential applications include information retrieval, text classification, and summarization. They also plan to explore other graph-based clustering approaches and further analyze the "small world" effect observed in their generation graphs.

Summary updated

BibTeX
@inproceedings{erkan2006language,
  author = {Güneş Erkan},
  title = {{Language Model-Based Document Clustering Using Random Walks}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2006},
}
Figure