📄 A Graph Model for Unsupervised Lexical Acquisition

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

• I1. 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.
• I2. 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.
• I3. 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.
• I4. 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.
• I5. 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.