---
title: "Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms — Mihalcea 2005"
description: "Mihalcea proposes a sequence labeling method that builds a graph whose vertices are all candidate… 53.0% precision. 16 references, cited by 42 papers here."
authors: ["Rada Mihalcea"]
year: 2005
venue: "Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/H05-1052/"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/mihalcea-2005-unsupervised-large-vocabulary-word-sense/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mihalcea-2005-unsupervised-large-vocabulary-word-sense/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2005](https://md.research.elamur.ai/free/en/papers/2005/) / Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling

# Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling

**Authors:** [Rada Mihalcea](https://md.research.elamur.ai/free/en/authors/rada-mihalcea/) · **Year:** 2005 · **Venue:** Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing · **Licence:** [CC BY-NC-SA 3.0 (ACL Anthology, before 2016)](https://creativecommons.org/licenses/by-nc-sa/3.0/)

**Links:** [Publisher's page](https://aclanthology.org/H05-1052/) · [PDF](https://aclanthology.org/H05-1052.pdf) · [OpenAlex](https://openalex.org/W1991862576)

**Citations:** 540 citations (OpenAlex, 2026-10-14) · [42](https://md.research.elamur.ai/free/en/papers/mihalcea-2005-unsupervised-large-vocabulary-word-sense/cited-by/) in our library, of the 140,884 papers whose bibliographies we read

## Summary
Most NLP labeling methods assign a tag to each word in isolation and ignore how the labels of neighbouring words constrain one another. Mihalcea proposes a sequence labeling method that builds a graph whose vertices are all candidate labels for the words in a sequence. Weighted edges encode dependencies between labels of words that lie within a set distance (MaxDist). A weighted PageRank random walk is run over this graph until scores converge, and each word then receives its highest-scoring label. All words are therefore annotated jointly, using global evidence from the whole graph.

The method is tested on unsupervised all-words word sense disambiguation, where edge weights come only from overlaps between dictionary sense definitions. On standard sense-annotated data (SENSEVAL-2, SemCor), joint labeling reduces errors by a statistically significant 10.7% compared with labeling each word separately. It also outperforms earlier unsupervised WSD systems. This shows that modelling label dependencies pays off even when the only resource is a plain dictionary, with no structured semantic network and no annotated corpus.

## Key points
- **Algorithm:** label graph plus weighted PageRank with damping factor d = 0.85. Because every candidate sense receives a score, the method yields a ranking over senses and can return more than one sense per word.
- **Main results:**
  - Overall accuracy is 54.2%.
  - This beats Mihalcea et al. (2004) at 50.9%, McCarthy et al. (2004) at 53.0% precision, and Litkowski (2001) at 45.1%, all measured on SENSEVAL-2.
  - The individual-labeling Lesk variant used as a comparison reaches 48.7% precision on SENSEVAL-2.
- **SemCor (10 random documents):** sequence labeling scores 56.5%, individual labeling 47.4%, and a random baseline 35.3%.
- **SemCor nouns:** the method reaches 64.2%, versus 62.09% for the lexical-chain approach of Galley and McKeown (2003). The author notes the comparison is not exact because tie-breaking differs: random choice here, WordNet sense order in their work.
- **Robustness:** results hold across fine- and coarse-grained sense distinctions and across different context window sizes.

*Our summary of the paper, in our own words — not its text. The work belongs to its authors; read it at the links above.*

Fields: [AI & machine learning](https://md.research.elamur.ai/free/en/shelves/ai/)

Topics: [🔀 Word sense disambiguation](https://md.research.elamur.ai/free/en/topics/word-sense-disambiguation/)

## Institutions

- [University of North Texas](https://md.research.elamur.ai/free/en/universities/university-of-north-texas/) — University, Denton, United States · 13 works · 3,921 citations

## Cite

Cite as: Rada Mihalcea. 2005. Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling. Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this page. BibTeX from the library's record of the work.

```bibtex
@inproceedings{mihalcea2005unsupervised,
  title = {{Unsupervised Large-Vocabulary Word Sense Disambiguation with Graph-based Algorithms for Sequence Data Labeling}},
  author = {Rada Mihalcea},
  booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  doi = {10.3115/1220575.1220627},
  url = {https://doi.org/10.3115/1220575.1220627}
}
```

- [← previous Arabic Tokenization, Part-of-Speech Tagging and Morphological Disambiguation in One Fell Swoop](https://md.research.elamur.ai/free/en/papers/habash-2005-arabic-tokenization-part-speech-tagging/)
- [next → Improving Machine Translation Performance by Exploiting Non-Parallel Corpora](https://md.research.elamur.ai/free/en/papers/munteanu-2005-improving-machine-translation-performance-exploiting/)
- [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/)

## References

16 references, 4 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. S. Brin and L. Page. 1998. The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30(1–7). [our card](https://md.research.elamur.ai/free/en/papers/brin-1998-anatomy-large-scale-hypertextual-web/)
2. A. Budanitsky and G. Hirst. 2001. Semantic distance in wordnet: An experimental, application-oriented evaluation of five measures. In Proceedings of the NAACL Workshop on WordNet and Other Lexical Resources, Pittsburgh. [find](https://scholar.google.com/scholar?q=A%2E+Budanitsky+and+G%2E+Hirst%2E+2001%2E+Semantic+distance+in+wordnet%3A+An+experimental%2C+application%2Doriented+evaluation+of+five+measures%2E+In+Proceedings+of+the+NAACL+Workshop+on+WordNet+and+Other+Lexical+Res)
3. J. Cowie, L. Guthrie, and J. Guthrie. 1992. Lexical disambiguation using simulated annealing. In Proceedings of the 5th International Conference on Computational Linguistics (COLING 1992). [find](https://scholar.google.com/scholar?q=J%2E+Cowie%2C+L%2E+Guthrie%2C+and+J%2E+Guthrie%2E+1992%2E+Lexical+disambiguation+using+simulated+annealing%2E+In+Proceedings+of+the+5th+International+Conference+on+Computational+Linguistics+%28COLING+1992%29%2E)
4. D. Cutting, J. Kupiec, J. Pedersen, and P. Sibun. 1992. A practical part-of-speech tagger. In Proceedings of the Third Conference on Applied Natural Language Processing ANLP-92. [our card](https://md.research.elamur.ai/free/en/papers/cutting-1992-practical-part-speech-tagger/)
5. M. Galley and K. McKeown. 2003. Improving word sense disambiguation in lexical chaining. In Proceedings of the 18th International Joint Conference on Artificial Intelligence (IJCAI 2003), Acapulco, Mexico, August. [find](https://scholar.google.com/scholar?q=M%2E+Galley+and+K%2E+McKeown%2E+2003%2E+Improving+word+sense+disambiguation+in+lexical+chaining%2E+In+Proceedings+of+the+18th+International+Joint+Conference+on+Artificial+Intelligence+%28IJCAI+2003%29%2C+Acapulco%2C+Me)
6. G. Grimmett and D. Stirzaker. 1989. Probability and Random Processes. Oxford University Press. [find](https://scholar.google.com/scholar?q=G%2E+Grimmett+and+D%2E+Stirzaker%2E+1989%2E+Probability+and+Random+Processes%2E+Oxford+University+Press%2E)
7. M.E. Lesk. 1986. Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone. In Proceedings of the SIGDOC Conference 1986, Toronto. [find](https://scholar.google.com/scholar?q=M%2EE%2E+Lesk%2E+1986%2E+Automatic+sense+disambiguation+using+machine+readable+dictionaries%3A+How+to+tell+a+pine+cone+from+an+ice+cream+cone%2E+In+Proceedings+of+the+SIGDOC+Conference+1986%2C+Toronto%2E)
8. K. Litkowski. 2001. Use of machine readable dictionaries in word sense disambiguation for Senseval-2. In Proceedings of ACL/SIGLEX Senseval-2, Toulouse, France. [find](https://scholar.google.com/scholar?q=K%2E+Litkowski%2E+2001%2E+Use+of+machine+readable+dictionaries+in+word+sense+disambiguation+for+Senseval%2D2%2E+In+Proceedings+of+ACL%2FSIGLEX+Senseval%2D2%2C+Toulouse%2C+France%2E)
9. D. McCarthy, R. Koeling, J. Weeds, and J. Carroll. 2004. Using automatically acquired predominant senses for word sense disambiguation. In Proceedings of ACL/SIGLEX Senseval-3, Barcelona, Spain. [find](https://scholar.google.com/scholar?q=D%2E+McCarthy%2C+R%2E+Koeling%2C+J%2E+Weeds%2C+and+J%2E+Carroll%2E+2004%2E+Using+automatically+acquired+predominant+senses+for+word+sense+disambiguation%2E+In+Proceedings+of+ACL%2FSIGLEX+Senseval%2D3%2C+Barcelona%2C+Spain%2E)
10. R. Mihalcea, P. Tarau, and E. Figa. 2004. PageRank on semantic networks, with application to word sense disambiguation. In Proceedings of the 20st International Conference on Computational Linguistics (COLING 2004). [our card](https://md.research.elamur.ai/free/en/papers/mihalcea-2004-pagerank-semantic-networks-application-word/)
11. G. Miller, C. Leacock, T. Randee, and R. Bunker. 1993. A semantic concordance. In Proceedings of the 3rd DARPA Workshop on Human Language Technology, Plainsboro, New Jersey. [our card](https://md.research.elamur.ai/free/en/papers/miller-1993-semantic-concordance/)
12. G. Miller. 1995. Wordnet: A lexical database. Communication of the ACM, 38(11):39–41. [find](https://scholar.google.com/scholar?q=G%2E+Miller%2E+1995%2E+Wordnet%3A+A+lexical+database%2E+Communication+of+the+ACM%2C+38%2811%29%3A39%E2%80%9341%2E)
13. J. Morris and G. Hirst. 1991. Lexical cohesion, the thesaurus, and the structure of text. Computational Linguistics, 17(1):21–48. [find](https://scholar.google.com/scholar?q=J%2E+Morris+and+G%2E+Hirst%2E+1991%2E+Lexical+cohesion%2C+the+thesaurus%2C+and+the+structure+of+text%2E+Computational+Linguistics%2C+17%281%29%3A21%E2%80%9348%2E)
14. M. Palmer, C. Fellbaum, S. Cotton, L. Delfs, and H.T. Dang. 2001. English tasks: all-words and verb lexical sample. In Proceedings of ACL/SIGLEX Senseval-2, Toulouse, France. [find](https://scholar.google.com/scholar?q=M%2E+Palmer%2C+C%2E+Fellbaum%2C+S%2E+Cotton%2C+L%2E+Delfs%2C+and+H%2ET%2E+Dang%2E+2001%2E+English+tasks%3A+all%2Dwords+and+verb+lexical+sample%2E+In+Proceedings+of+ACL%2FSIGLEX+Senseval%2D2%2C+Toulouse%2C+France%2E)
15. B. Snyder and M. Palmer. 2004. The English all-words task. In Proceedings of ACL/SIGLEX Senseval-3, Barcelona, Spain. [find](https://scholar.google.com/scholar?q=B%2E+Snyder+and+M%2E+Palmer%2E+2004%2E+The+English+all%2Dwords+task%2E+In+Proceedings+of+ACL%2FSIGLEX+Senseval%2D3%2C+Barcelona%2C+Spain%2E)
16. F. Vasilescu, P. Langlais, and G. Lapalme. 2004. Evaluating variants of the Lesk approach for disambiguating words. In Proceedings of the Conference of Language Resources and Evaluations (LREC 2004). [find](https://scholar.google.com/scholar?q=F%2E+Vasilescu%2C+P%2E+Langlais%2C+and+G%2E+Lapalme%2E+2004%2E+Evaluating+variants+of+the+Lesk+approach+for+disambiguating+words%2E+In+Proceedings+of+the+Conference+of+Language+Resources+and+Evaluations+%28LREC+2004%29%2E)