Abstract
Word sense disambiguation (WSD) has been a long-standing research objective for natural language processing. In this paper we are concerned with developing graph-based unsupervised algorithms for alleviating the data requirements for large scale WSD. Under this framework, finding the right sense for a given word amounts to identifying the most "important" node among the set of graph nodes representing its senses. We propose a variety of measures that analyze the connectivity of graph structures, thereby identifying the most relevant word senses. We assess their performance on standard datasets, and show that the best measures perform comparably to state-of-the-art.
Introduction
Word Sense Disambiguation (WSD) is the critical task of determining which specific meaning of a word is intended in a given context. While supervised learning models trained on large, hand-labeled datasets currently represent the gold standard, they suffer from a significant "data bottleneck." Creating these labeled resources is expensive and difficult to scale across languages and specialized domains. This research explores an unsupervised alternative: leveraging the mathematical structure of semantic networks like WordNet to identify the correct word sense without the need for labeled training data.
Methodology
The proposed framework operates by transforming a sentence into a graph structure where nodes represent possible word senses and edges represent semantic relationships (e.g., synonyms, hypernyms) derived from a lexicon. The task then becomes identifying the most "important" node for each word using connectivity measures.
Two main categories of measures were evaluated:
- Local Measures: These focus on the immediate structural influence of individual nodes. Examples include In-degree Centrality, PageRank, and the Key Player Problem (KPP), which identifies nodes that are maximally cohesive within the network.
- Global Measures: These assess the overall density or "health" of the entire graph. Measures such as Compactness, Graph Entropy, and Edge Density were tested to determine if selecting a specific combination of senses results in a more cohesive global structure.
Experimental Setup
The algorithms were evaluated using the SemCor corpus and the Senseval-3 English all-words task. To address the inherent sparsity of standard dictionaries, the researchers tested their methods on both the standard WordNet 2.0 and an Enriched WordNet (EnWordNet), which includes 60,000 additional semantic edges extracted from collocation resources.
Results and Discussion
The experimental results revealed that local measures consistently outperform global measures. Global measures often require complex heuristic searches, such as simulated annealing, which are computationally expensive and can introduce noise into the disambiguation process.
As shown in the table above, the Key Player Problem (KPP) emerged as the most effective metric. KPP achieved an F1-score of 31.8% on standard WordNet, which rose to 40.5% when using the enriched version. This performance is comparable to leading similarity-based unsupervised systems of the time, particularly for nouns and adjectives.
The Impact of Graph Density
A critical insight from the study is that the performance of graph-based WSD is directly correlated with the density of the underlying semantic network. The limitation of unsupervised WSD appears to be less about the algorithms themselves and more about the sparsity of current digital dictionaries.
When the graph density increases, the accuracy of the connectivity measures improves dramatically. For senses with more than 200 edges in the enriched graph, the KPP measure achieved an F1-score of 85%. This suggests that as semantic resources become more comprehensive, graph-based structural analysis becomes an increasingly powerful proxy for human linguistic understanding.
Conclusion
This research demonstrates that unsupervised graph connectivity measures, particularly the Key Player Problem, offer a viable path forward for large-scale WSD. While performance on verbs remains a challenge due to persistent data sparsity in lexicons, the success of these measures on enriched networks suggests that future improvements in semantic resource construction will directly translate to higher WSD accuracy. Future work will focus on more efficient global measures and hybrid frameworks that combine multiple connectivity metrics.
Summary updated