Efficient Graph-based Word Sense Induction by Distributional Inclusion Vector Embeddings

Haw-Shiuan Chang, Amol Agrawal, Ananya Ganesh, Anirudha Desai, Vinayak Mathur, Alfred Hough, Andrew McCallumTextGraphs @ NAACL 2018 · OpenReview

Abstract

Word sense induction (WSI), which addresses polysemy by unsupervised discovery of multiple word senses, resolves ambiguities for downstream NLP tasks and also makes word representations more interpretable. This paper proposes an accurate and efficient graph-based method for WSI that builds a global non-negative vector embedding basis (which are interpretable like topics) and clusters the basis indexes in the ego network of each polysemous word. By adopting distributional inclusion vector embeddings as our basis formation model, we avoid the expensive step of nearest neighbor search that plagues other graph-based methods without sacrificing the quality of sense clusters. Experiments on three datasets show that our proposed method produces similar or better sense clusters and embeddings compared with previous state-of-the-art methods while being significantly more efficient.

Introduction

Word Sense Induction (WSI) is the unsupervised discovery of the multiple meanings (senses) a word might have based on raw text—for example, distinguishing "bank" as a financial institution versus a river edge. Graph-based clustering is a popular approach for WSI because it naturally handles hierarchical clustering, allowing researchers to capture different granularities of senses.

However, traditional graph-based WSI methods are computationally expensive. They typically require building ego-networks by finding the nearest neighbors for every target word in the vocabulary (an $O(|V|^2)$ operation) or clustering tens of thousands of individual word mentions. This makes scaling them up to large corpora or fine-grained sense discovery highly impractical without relying on expensive external dependency parsers.

Methodology

The proposed method flips the standard script: instead of clustering words or mentions, it clusters topics (basis indexes). The overall pipeline is divided into three main sections: basis formation, similarity measurement, and sense embedding refinement.

System architecture for the proposed graph-based WSI method.

1. Global Topic Modeling with DIVE

The process begins with Distributional Inclusion Vector Embeddings (DIVE), a non-negative variation of the skip-gram model. DIVE compresses the sparse bag-of-words vocabulary into a set of interpretable "basis indexes" (essentially topics, like "food" or "technology").

2. Topic-Level Ego Networks

For a given target word (e.g., "core"), the model identifies the DIVE basis indexes where the word has a high value. These topics become the nodes in a compact ego network.

Visualization of the WSI process for the word 'core'.

By using DIVE's 100-300 dimensions as nodes, the graph size drops from thousands of words to approximately 6 to 19 nodes per target word. This entirely eliminates the nearest-neighbor bottleneck.

3. Target-Dependent Similarity

To connect these nodes, the model measures similarity. Instead of comparing topics globally, it only looks at the features (words) relevant to the target word. For instance, for "apple", the "technology" topic and "food" topic are kept distinct, but for "bank", the "money" and "country" topics might be merged to form the financial sense.

4. Clustering & Refinement

Because the resulting network is so small, global optimization (spectral clustering) can be run almost instantly. Finally, these topic clusters are converted into actual sense embeddings using a weighted average of skip-gram embeddings, followed by an Expectation-Maximization (EM) step to refine them against the corpus.

Evaluation and Results

The model was evaluated on several benchmarks, including WaCkypedia for training, Word Context Relevance (WCR) R1 for context matching, and the Turk bootstrap Word Sense Inventory (TWSI) and SemEval-2013 Task 13 for sense identification.

Efficiency

The ego networks constructed by DIVE contained only 6.4 nodes (for 100 dimensions) or 19 nodes (for 300 dimensions) on average. This makes the clustering step computationally trivial compared to traditional methods that cluster thousands of neighboring words.

Performance

  • Context Matching (WCR R1): The DIVE (100 dimensions) approach achieved 63.2% Precision@1, significantly outperforming the state-of-the-art Word Graph (WG) baseline (42.1%).
  • Sense Identification (TWSI): On the balanced TWSI dataset—which removes bias toward the most frequent sense—DIVE outperformed WG (39.6% vs 38.6% F1), demonstrating its ability to capture the "long tail" of less common senses.
  • SemEval-2013: DIVE achieved comparable performance to existing baselines (e.g., 29.3% WNDCG vs WG's 29.0%), proving it maintains quality while drastically improving speed.

Discussion

A key insight of this work is that clustering topics is vastly cheaper than clustering words. By using a global basis with local, target-dependent context, the method preserves the nuance of traditional graph methods without the overhead. This approach proves particularly adept at isolating less common senses, such as discovering the educational sense of "core" alongside its physical meaning.

However, some limitations remain. Simply averaging embeddings within a cluster doesn't always yield a perfect representation of a sense, necessitating the EM refinement step. Additionally, while graph-based methods allow for dynamic cluster sizing, this study primarily used fixed cluster counts for experimental simplicity. Future work may explore increasing the DIVE dimensions to further improve sense resolution.

Summary updated

BibTeX
@inproceedings{chang2018efficient,
  author = {Haw-Shiuan Chang and Amol Agrawal and Ananya Ganesh and Anirudha Desai and Vinayak Mathur and Alfred Hough and Andrew McCallum},
  title = {{Efficient Graph-based Word Sense Induction by Distributional Inclusion Vector Embeddings}},
  booktitle = {TextGraphs @ NAACL},
  year = {2018},
  url = {https://openreview.net/forum?id=HAeZ34gYLWc},
}
Figure