Human language is inherently ambiguous. A single word like bank can mean a financial institution, the side of a river, or a banking shot in billiards. Traditional Natural Language Processing (NLP) often relies on static, pre-defined dictionaries to enumerate these meanings. However, language is fluid, and rigid definitions fail to capture domain-specific jargon or semantic evolution over time.
Graph-based Word Sense Induction (WSI) offers an elegant, unsupervised alternative by treating the lexicon as a geometric space governed by network topology. The core intuition relies on the small-world property of language networks: while words are broadly interconnected, the specific contexts in which a word is used tend to form tightly knit, dense subgraphs (or communities). As Andrey Kutuzov demonstrates, these structural clusters map directly to distinct semantic meanings. By analyzing the local connectivity around an ambiguous word, we can let its individual senses emerge naturally from the graph's topology without any human-labeled data.
Constructing the Semantic Landscape
To induce senses topologically, we must first transform raw text or lexical relationships into a graph. Researchers have proposed several distinct ways to construct these networks, depending on the available data:
- Co-occurrence and Thesaurus Networks: In these graphs, nodes represent words, and edges represent statistical co-occurrence or distributional similarity within a corpus. For example, Zornitsa Kozareva et al. utilize large-scale word co-occurrence networks to capture broad linguistic connections, while Binny Mathew et al. leverage distributional thesaurus networks to isolate domain-specific sense variations.
- Ego-Graphs from Vector Spaces: Instead of building a massive global network, one can construct a localized "ego-graph" centered on a target word. Varvara Logacheva introduces this via the egvi (Ego-Graph Vector Induction) framework, which extracts the nearest neighbors of a target word from pre-trained embeddings and connects them based on their mutual cosine similarity.
- Word Usage Graphs (WUGs): Rather than connecting different words, WUGs connect individual instances or occurrences of the same word. In DWUG: A large Resource of Diachronic Word Usage Graphs in Four Languages, Dominik Schlechtweg et al. construct graphs where nodes are specific sentences containing the target word, and edges represent human-judged semantic proximity between those usages.
Partitioning the Graph to Uncover Meanings
Once the graph is built, the problem of finding word senses reduces to finding structural boundaries within the network. If a word is polysemous, its neighbors will split into distinct components that are internally dense but weakly connected to each other.
Several algorithmic strategies are used to isolate these semantic components:
- Ego-Network Partitioning and Bridge Removal: Sunny Mitra et al. isolate a target word's local neighborhood (its ego-network) and apply non-parametric graph clustering to discover an arbitrary number of senses. To clean up the boundaries, Andrey Kutuzov shows that identifying and removing "bridge nodes"—nodes with low clustering coefficients that act as weak links between dense subgraphs—effectively isolates distinct semantic senses.
- Minimum Spanning Trees and Edge Betweenness: In the system described by Hans-Péter Zorn et al. for UKP-WSI: UKP Lab Semeval-2013 Task 11 System Description, the authors build a Minimum Spanning Tree of related terms and iteratively remove edges with high edge betweenness. This cuts the structural "bridges" between different meanings, leaving isolated subgraphs that represent distinct senses.
- Clique Detection: A more rigid topological definition of a sense is a clique—a fully connected subgraph where every node is adjacent to every other node. Fabienne Venant defines precise word meanings by identifying maximal cliques within a synonymy graph. Similarly, Rui Wang et al. use cliques within bilingual co-occurrence graphs to model cross-lingual word senses for machine translation.
- Statistical Block Modeling: Moving beyond heuristic clustering, Dominik Schlechtweg et al. apply a Bayesian formulation of the Weighted Stochastic Block Model (WSBM) to Word Usage Graphs in Modeling Sense Structure in Word Usage Graphs with the Weighted Stochastic Block Model. The model infers latent "blocks" (senses) by evaluating both the presence and the weights of edges between usages, capturing fluid and graded semantic structures.
Downstream Applications and Modern Extensions
Inducing word senses from graph topology provides a powerful foundation for several core NLP tasks:
- Word Sense Disambiguation (WSD): Once a graph of potential meanings is established, determining the correct sense of a word in a specific sentence can be framed as a structural centrality problem. As Rada Mihalcea et al. and Roberto Navigli et al. demonstrate, running random walk algorithms like PageRank over these semantic networks allows the structural importance of nodes to dictate the most contextually appropriate meaning without requiring manually labeled training data.
- Lexical Semantic Change (LSC) Detection: Because graph-based induction does not rely on static lexicons, it is uniquely suited for tracking how language evolves over time. In SemEval-2020 Task 1: Unsupervised Lexical Semantic Change Detection, Haim Dubossarsky et al. establish benchmarks for tracking semantic shifts by partitioning time-varying usage graphs. By comparing how these clusters split, merge, or disappear across different eras, frameworks like the one proposed by Sunny Mitra et al. can automatically detect the "birth" or "death" of specific word meanings.
- Graph Neural Networks (GNNs) on Lexical Resources: Modern approaches combine traditional graph topology with deep learning. For instance, Alfonso Ardoiz et al. construct lexical graphs linking words that appear within dictionary definitions, using a Graph Neural Network (specifically a SAGE variant) to capture deep semantic relationships for reverse dictionaries. Similarly, Lu Zhang et al. use GNNs over keyword co-occurrence graphs to disambiguate polysemous terms for weakly-supervised text classification.
By shifting the representation of meaning from discrete text strings to topological structures, graph-based word sense induction captures the fluid, associative, and emergent nature of human language.