Modeling Sense Structure in Word Usage Graphs with the Weighted Stochastic Block Model

Dominik Schlechtweg, Enrique Castaneda, Jonas Kuhn, Sabine Schulte im WaldeACL 2021

TL;DR

This paper introduces a novel Bayesian approach to model the nuanced structure of word meanings using Word Usage Graphs (WUGs). By applying a Weighted Stochastic Block Model (WSBM), the authors provide a principled way to infer word senses and their relationships, offering a more robust alternative to traditional discrete sense inventories.

What Problem Does This Paper Address?

Understanding word meaning is a fundamental challenge in linguistics and NLP. Traditional approaches often rely on discrete word senses (e.g., dictionary entries), but real-world language use is more fluid, with meanings that can be graded, overlapping, and context-dependent. Word Usage Graphs (WUGs) attempt to capture this nuance by representing word uses as nodes in a graph, with edge weights indicating semantic proximity. However, existing methods for analyzing WUGs, such as clustering heuristics, lack a rigorous probabilistic foundation. This paper addresses the need for a principled, probabilistic model to infer and analyze the fine-grained semantic structure within WUGs, moving beyond discrete sense assumptions.

Methods

The core of this work is the application of a Bayesian formulation of the Weighted Stochastic Block Model (WSBM) to WUGs. The WSBM is a generative model for random graphs where nodes (word uses) are assumed to belong to latent "blocks" (analogous to word senses). The model infers these blocks by considering both the existence and the weights of edges between nodes.

Key methodological contributions include:

  • Bayesian WSBM for WUGs: Adapting the WSBM to model human-annotated WUGs, which are often noisy and sparse.
  • Marginalizing over edge probabilities: To address the specific characteristics of WUG data (where edge probabilities might not perfectly reflect stochastic equivalence), the authors marginalize over edge probabilities. This makes the inferred block structure more independent of the observed edge probability distribution and primarily driven by edge weights.
  • Model Selection: Employing the Minimum Description Length (MDL) principle to select the best-fitting model, allowing for rigorous comparison of different model configurations (e.g., number of blocks, edge weight distributions).
  • Edge Weight Distributions: Investigating various distributions (binomial, Poisson, geometric) for modeling edge weights between blocks, aiming to capture the graded nature of semantic similarity.

Datasets

The study utilizes human-annotated Word Usage Graphs (WUGs) from the DWUG DE/EN data sets (Schlechtweg et al., 2021). These datasets consist of WUGs for 88 German and English words, derived from diachronic corpora. Annotators judged the semantic relatedness of word use pairs on a scale, resulting in weighted undirected graphs.

Key Insights and Ideas

  • Graded Meaning is Key: The paper strongly supports the idea that word meanings are not discrete but rather graded and overlapping, which is well-captured by probabilistic models like WSBM.
  • WSBM as a Sense Inference Tool: The WSBM provides a principled way to infer the number of word senses and assign word uses to these senses, offering a data-driven alternative to manual sense inventory creation.
  • Sparsity is a Challenge: The sparsity of human annotations in WUGs significantly influences model fitting. Richer annotations lead to more reliable block assignments, while sparse data can lead to spurious similarities.
  • Edge Weight Distributions Matter: The choice of distribution for modeling edge weights between blocks is crucial. While binomial distributions performed well, the authors highlight the need for more flexible distributions to accurately model the observed weight patterns, especially for between-block relationships.
  • Model-Agnostic Interpretation: The authors emphasize that the WSBM framework is flexible; the inferred blocks can be interpreted as word senses, but the model itself doesn't inherently rely on the "sense" concept, making it applicable to other graph-based semantic structures.

Key Results

  • Model Selection: The study found that for most WUGs, the optimal number of inferred blocks was one or two, suggesting simpler structures are often sufficient. The highest number of blocks found was five.
  • Edge Weight Distribution Performance: The binomial distribution generally provided the best fit for edge weights across the majority of graphs.
  • Correspondence to Existing Clustering: The inferred block structures showed strong correspondence (often > 0.9 accuracy) with results from previous, non-probabilistic clustering methods (Schlechtweg et al., 2021), validating the WSBM's ability to capture meaningful semantic groupings. However, for complex structures, discrepancies were observed.
  • Link Prediction: The model achieved high scores (IME > 0.8) for predicting missing edges in about half of the graphs, indicating good recoverability of graph structure. Predictability was generally higher for simpler block structures.
  • Qualitative Analysis: The paper provides detailed analysis of specific words (Festspiel, Abgesang, zersetzen), illustrating how the WSBM can uncover nuanced semantic distinctions and handle cases with clear or ambiguous sense structures.

Limitations and Future Work

  • Edge Weight Distribution Flexibility: The authors acknowledge that current distributions (binomial, Poisson, geometric) struggle to fully capture the observed weight distributions, particularly for between-block relationships. They suggest exploring more flexible distributions, such as a signed (invertible) geometric distribution, for improved fits.
  • Sparsity of Annotation: Addressing the challenge of sparse annotations is a key future direction. The authors propose developing efficient and iterative sampling techniques for edges to mitigate this.
  • Annotator Variability: The influence of individual annotator interpretation on inferred structures is noted. Future work could involve multi-graph models that represent information from each annotator individually.
  • Comparison with Other Models: The paper suggests future work could involve comparing WSBMs with other probabilistic models like Gaussian Mixture Models and Latent Space models, as well as exploring Mixed Membership SBMs and multi-graph models.

Summary updated

BibTeX
@inproceedings{schlechtweg2021modeling,
  author = {Dominik Schlechtweg and Enrique Castaneda and Jonas Kuhn and Sabine Schulte im Walde},
  title = {{Modeling Sense Structure in Word Usage Graphs with the Weighted Stochastic Block Model}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure