---
title: "A Graph Model for Unsupervised Lexical Acquisition (2002)"
description: "Widdows and Dorow propose an unsupervised way to gather semantic categories… 82% accuracy. 14 references, cited by 74 papers here."
authors: ["Dominic Widdows", "Beate Dorow"]
year: 2002
venue: "COLING 2002: The 19th International Conference on Computational Linguistics"
source: "https://aclanthology.org/C02-1114/"
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/widdows-2002-graph-model-unsupervised-lexical-acquisition/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/widdows-2002-graph-model-unsupervised-lexical-acquisition/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2002](https://md.research.elamur.ai/free/en/papers/2002/) / A Graph Model for Unsupervised Lexical Acquisition

# A Graph Model for Unsupervised Lexical Acquisition

**Authors:** [Dominic Widdows](https://md.research.elamur.ai/free/en/authors/dominic-widdows/) and Beate Dorow · **Year:** 2002 · **Venue:** [COLING 2002: The 19th International Conference on Computational Linguistics](https://md.research.elamur.ai/free/en/venues/coling/) ([COLING 2002](https://md.research.elamur.ai/free/en/venues/coling/2002/)) · **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/C02-1114/) · [PDF](https://aclanthology.org/C02-1114.pdf) · [OpenAlex](https://openalex.org/W2079641356)

**Citations:** 244 citations (OpenAlex, 2026-10-14) · [74](https://md.research.elamur.ai/free/en/papers/widdows-2002-graph-model-unsupervised-lexical-acquisition/cited-by/) in our library, of the 141,840 papers whose bibliographies we read

## Summary
Hand-built lexicons such as WordNet have gaps in fast-moving domains, cover few languages besides English, and miss senses that matter in a given corpus. For example, WordNet has no "computer company" sense for *apple*. Widdows and Dorow propose an unsupervised way to gather semantic categories from the PoS-tagged British National Corpus. They build a graph whose nodes are nouns. Two nouns are linked when they appear joined by "and" or "or", which usually means they sit together in a list.

On this graph they run an incremental clustering procedure. Starting from a seed word, it repeatedly adds the neighbouring node most tightly connected to the cluster's existing neighbourhood. This limits the "infection" problem of earlier bootstrapping methods.

They tested ten categories, retrieving 20 words from a single seed per category and checking each word strictly against WordNet classes. Overall accuracy was 82%, well above earlier list-based approaches. The same graph also exposes ambiguity: removing a word's node splits its local neighbourhood into separate components, one per sense. This yields an annotation-free route to sense discovery.

## Key points
- **Data:** the graph comes from the PoS-tagged BNC, using only the symmetric noun–conjunction–noun relation.
- **Graph size:** 99,454 noun nodes and 587,475 links, about a quarter of the roughly 400,000 noun types in the corpus.
- **Link cutoff:** each word keeps only its top-n neighbours, which turns weights into a ranking and favours more frequent words.
- **Scoring rule:** a candidate u is scored by |N(u) ∩ N(A)| / |N(u)|, the share of u's links that land in the cluster's neighbourhood.
- **Evaluation:** ten classes were fixed beforehand (places, crimes, vehicles, tools, clothes, musical instruments, body parts, diseases, foodstuffs and academic subjects).
- **Comparison with earlier work:** the method reached 82% accuracy, against 17% (Riloff and Shepherd, 1997), 35% (Roark and Charniak, 1998) and up to 78% (Riloff and Jones, 1999).
- **Failure case:** the tools class was contaminated through the word *hand*.
- **Polysemy example:** the local graph of *apple* splits into fruit, tree and computer components.
- **Demo:** an online demonstration was released at infomap.stanford.edu/graphs.

## Interesting ideas
- **Neighbourhood-proportion scoring instead of raw co-occurrence.** A word joins a cluster only if many of its links fall inside the cluster's neighbourhood. One very frequent pairing, such as "Apple and Novell", therefore cannot pull in unrelated terms. The same rule could protect any bootstrapping or label-propagation pipeline against drift caused by idioms or noisy pairs.
- **Senses as components after deleting the hub.** If you remove the target word from its local graph, the pieces left over are its corpus-specific senses. The number of senses falls out naturally, so you never pick a cluster count. This could work cheaply for domain sense discovery in languages without a WordNet, such as Ukrainian corpora.
- **Coordination as a cheap similarity signal.** Lists joined by "and"/"or" need only a PoS tagger, not a parser. The relation is symmetric, which keeps the graph algorithms simple, so this makes a practical starting point for low-resource lexicon building.
- **Repeatable evaluation against a lexical resource.** Categories were fixed in advance and each output word was checked strictly against WordNet class membership instead of human judgement. This gives a reproducible, cheap benchmark for comparing acquisition methods.
- **Sense components as WSD features.** Words in each sense component could act as context indicators for disambiguation, replacing hand-labelled training data. The authors propose this but leave its evaluation to future work.

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

## Institutions

- [Stanford University](https://md.research.elamur.ai/free/en/universities/stanford-university/) — University, Stanford, United States · 310 works · 284,480 citations

📚 Shelves (6): [🖥️ Computer Science](https://md.research.elamur.ai/free/en/shelves/computer-science/) · 9,086 works · [🤖 Artificial Intelligence](https://md.research.elamur.ai/free/en/shelves/computer-science/artificial-intelligence/) · 8,889 works · [🎭 Arts and Humanities](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/) · 9,296 works · [🗣️ Language and Linguistics](https://md.research.elamur.ai/free/en/shelves/arts-and-humanities/language-and-linguistics/) · 9,206 works · [💭 Psychology](https://md.research.elamur.ai/free/en/shelves/psychology/) · 798 works · [💭 Developmental and Educational Psychology](https://md.research.elamur.ai/free/en/shelves/psychology/developmental-and-educational-psychology/) · 260 works

## Cite

Cite as: Dominic Widdows and Beate Dorow. 2002. A Graph Model for Unsupervised Lexical Acquisition. COLING 2002: The 19th International Conference on Computational Linguistics.

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

```bibtex
@inproceedings{widdows2002graph,
  title = {{A Graph Model for Unsupervised Lexical Acquisition}},
  author = {Dominic Widdows and Beate Dorow},
  booktitle = {COLING 2002: The 19th International Conference on Computational Linguistics},
  year = {2002},
  doi = {10.3115/1072228.1072342},
  url = {https://doi.org/10.3115/1072228.1072342}
}
```

- [← previous Toward a Broad-coverage Bilingual Corpus for Speech Translation of Travel Conversations in the Real World](https://md.research.elamur.ai/free/en/papers/takezawa-2002-broad-coverage-bilingual-corpus-speech/)
- [next → An Empirical Evaluation of Knowledge Sources and Learning Algorithms for Word Sense Disambiguation](https://md.research.elamur.ai/free/en/papers/lee-2002-empirical-evaluation-knowledge-sources-learning/)
- [↑ back to papers of 2002](https://md.research.elamur.ai/free/en/papers/2002/)

## References

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

1. Béla Bollobás. 1998. Modern Graph Theory. Number 184 in Graduate texts in Mathematics. Springer-Verlag. [find](https://scholar.google.com/scholar?q=Be%CC%81la+Bolloba%CC%81s%2E+1998%2E+Modern+Graph+Theory%2E+Number+184+in+Graduate+texts+in+Mathematics%2E+Springer%2DVerlag%2E)
2. Christiane Fellbaum. 1998. WordNet: An electronic lexical database. MIT press, Cambridge MA. [find](https://scholar.google.com/scholar?q=Christiane+Fellbaum%2E+1998%2E+WordNet%3A+An+electronic+lexical+database%2E+MIT+press%2C+Cambridge+MA%2E)
3. W. Gale, K. Church, and D. Yarowsky. 1992. One sense per discourse. In DARPA speech and Natural Language Workshop, Harriman, NY. [find](https://scholar.google.com/scholar?q=W%2E+Gale%2C+K%2E+Church%2C+and+D%2E+Yarowsky%2E+1992%2E+One+sense+per+discourse%2E+In+DARPA+speech+and+Natural+Language+Workshop%2C+Harriman%2C+NY%2E)
4. Adam Kilgarriff and Joseph Rosenzweig. 2000. English senseval: report and results. In LREC, Athens. [find](https://scholar.google.com/scholar?q=Adam+Kilgarriff+and+Joseph+Rosenzweig%2E+2000%2E+English+senseval%3A+report+and+results%2E+In+LREC%2C+Athens%2E)
5. Dekang Lin. 1998. [Automatic retrieval and clustering of similar words](https://md.research.elamur.ai/free/en/papers/lin-1998-automatic-retrieval-clustering-similar-words/). In COLING-ACL, Montreal, August.
6. Christopher D. Manning and Hinrich Schütze. 1999. Foundations of Statistical Natural Language Processing. The MIT Press, Cambridge, Massachusetts. [find](https://scholar.google.com/scholar?q=Christopher+D%2E+Manning+and+Hinrich+Schu%CC%88tze%2E+1999%2E+Foundations+of+Statistical+Natural+Language+Processing%2E+The+MIT+Press%2C+Cambridge%2C+Massachusetts%2E)
7. C. Mervis and E. Rosch. 1981. Categorization of natural objects. Annual Review of Psychology, 32:89–115. [find](https://scholar.google.com/scholar?q=C%2E+Mervis+and+E%2E+Rosch%2E+1981%2E+Categorization+of+natural+objects%2E+Annual+Review+of+Psychology%2C+32%3A89%E2%80%93115%2E)
8. George A. Miller and William G. Charles. 1991. [find](https://scholar.google.com/scholar?q=George+A%2E+Miller+and+William+G%2E+Charles%2E+1991%2E)
9. Contextual correlates of semantic similarity. Language and Cognitive Processes, 6(1):1–28. [find](https://scholar.google.com/scholar?q=Contextual+correlates+of+semantic+similarity%2E+Language+and+Cognitive+Processes%2C+6%281%29%3A1%E2%80%9328%2E)
10. Ellen Riloff and Rosie Jones. 1999. Learning dictionaries for infomation extraction by multi-level bootstrapping. In Proceedings of the Sixteenth National Conference on Artificial Intelligence, pages 472–479. AAAI. [find](https://scholar.google.com/scholar?q=Ellen+Riloff+and+Rosie+Jones%2E+1999%2E+Learning+dictionaries+for+infomation+extraction+by+multi%2Dlevel+bootstrapping%2E+In+Proceedings+of+the+Sixteenth+National+Conference+on+Artificial+Intelligence%2C+pages+)
11. Ellen Riloff and Jessica Shepherd. 1997. [A corpus-based approach for building semantic lexicons](https://md.research.elamur.ai/free/en/papers/riloff-1997-corpus-based-approach-building-semantic/). In Claire Cardie and Ralph Weischedel, editors, Proceedings of the Second Conference on Empirical Methods in Natural Language Processing, pages 117–124. Association for Computational Linguistics, Somerse…
12. Brian Roark and Eugene Charniak. 1998. Noun-phrase co-occurence statistics for semi-automatic semantic lexicon construction. In COLING-ACL, pages 1110–1116. [find](https://scholar.google.com/scholar?q=Brian+Roark+and+Eugene+Charniak%2E+1998%2E+Noun%2Dphrase+co%2Doccurence+statistics+for+semi%2Dautomatic+semantic+lexicon+construction%2E+In+COLING%2DACL%2C+pages+1110%E2%80%931116%2E)
13. E. Rosch. 1988. Principles of categorization. In A. Collins and E. E. Smith, editors, Readings in Cognitive Science: A Perspective from Psychology and Artificial Intelligence, pages 312–322. Kaufmann, San Mateo, CA. [find](https://scholar.google.com/scholar?q=E%2E+Rosch%2E+1988%2E+Principles+of+categorization%2E+In+A%2E+Collins+and+E%2E+E%2E+Smith%2C+editors%2C+Readings+in+Cognitive+Science%3A+A+Perspective+from+Psychology+and+Artificial+Intelligence%2C+pages+312%E2%80%93322%2E+Kaufmann%2C)
14. Hinrich Schütze. 1998. [Automatic word sense discrimination](https://md.research.elamur.ai/free/en/papers/schutze-1998-automatic-word-sense-discrimination/). Computational Linguistics, 24(1):97–124.

*Updated 24 October 2026*