Elamur Research⌕
☰
home / papers / 2007 / Graph Connectivity Measures for Unsupervised Word Sense Disambiguation

Graph Connectivity Measures for Unsupervised Word Sense Disambiguation

Summary

Supervised word sense disambiguation (WSD) depends on costly sense-annotated data, so Navigli and Lapata study unsupervised graph-based WSD. Their main question is which graph connectivity measure best picks the correct sense. For each sentence, they build a subgraph of WordNet by linking the senses of its words through paths of at most 6 edges. They then rank sense nodes using either local measures (in-degree, eigenvector-style PageRank and HITS, KPP, betweenness, and others) or global measures (such as compactness and graph entropy). Global measures are applied to each candidate interpretation of the sentence. The authors evaluate on SemCor and the Senseval-3 English all-words task, using both standard WordNet and an enriched version with many extra relatedness edges (EnWordNet). Local measures consistently beat global ones, and KPP is the most reliable across settings. A denser lexicon raises F1 sharply. With EnWordNet, KPP on Senseval-3 performs about as well as the strongest unsupervised Senseval-3 system for nouns and adjectives. The study matters because these measures do not depend on a particular lexicon or language, so they can be transferred to other sense inventories.

Key points

  • On SemCor with plain WordNet, the best local measure is KPP (F1 31.8%) and the best global measure is graph entropy (F1 29.4%). InDegree and PageRank tie at F1 28.6%, and PageRank beats HITS.
  • Switching to the enriched WordNet improves F1 by 8.7 points for KPP and 11.4 points for InDegree. InDegree, KPP and PageRank all reach roughly 40% F1, while the best global measure, Compactness, reaches 35.9%.
  • For senses with more than 200 edges in the graph, KPP achieves about 85% F1, excluding unambiguous words.
  • On Senseval-3, KPP is statistically on par with IRST-DDD for nouns and adjectives but trails it on verbs. The authors attribute this to EnWordNet having fewer relatedness edges for verbs.
  • Some measures, such as Betweenness and HITS, favour precision, while others, such as KPP, favour recall. The authors propose combining measures as 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.

Fields: AI & machine learning

Topics Word sense disambiguation

Institutions

🎓University of EdinburghEdinburgh · United Kingdom202 works · 55,753 citations🎓Sapienza University of RomeRome · Italy29 works · 6,807 citations

Cite

Cite as Roberto Navigli and Mirella Lapata. 2007. Graph Connectivity Measures for Unsupervised Word Sense Disambiguation. IJCAI-07.

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

@inproceedings{navigli2007graph,
  title = {{Graph Connectivity Measures for Unsupervised Word Sense Disambiguation}},
  author = {Roberto Navigli and Mirella Lapata},
  booktitle = {IJCAI-07},
  year = {2007},
  url = {https://www.ijcai.org/Proceedings/07/}
}

References

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

  1. Regina Barzilay and Michael Elhadad. Using lexical chains for text summarization. In Proceedings of the ACL Workshop on Intelligent Scalable Text Summarization, pages 10–17, Madrid, Spain, 1997. our card
  2. B. P. Bonacich. Factoring and weighing approaches to status scores and clique identification. Journal of Mathematical Sociology, 2:113–120, 1972. find
  3. Stephen P. Borgatti. Identifying sets of key players in a network. In Proceedings of the Conference on Integration of Knowledge Intensive Multi-Agent Systems, pages 127–131, Boston, USA, 2003. find
  4. Rodrigo A. Botafogo, Ehud Rivlin, and Ben Shneiderman. Structural analysis of hypertexts: Identifying hierarchies and useful metrics. ACM Transactions on Information Systems, 10(2):142–180, 1992. find
  5. Sergey Brin and Michael Page. Anatomy of a large-scale hypertextual web search engine. In Proceedings of the 7th Conference on World Wide Web, pages 107–117, Brisbane, Australia, 1998. find
  6. Samuel Brody, Roberto Navigli, and Mirella Lapata. Ensemble methods for unsupervised WSD. In Proceedings of the ACL/COLING, Sydney, Australia, 2006. find
  7. Jim Cowie, Joe Guthrie, and Louise Guthrie. Robust textual inference via graph matching. In Proceedings of the 14th COLING, pages 359–365, Nantes, France, 1992. find
  8. J. Edmonds and R. M. Karp. Theoretical improvements in algorithmic efficiency for network flow problems. Journal of the ACM, 19(2):248–264, 1972. find
  9. Christiane Fellbaum, editor. WordNet: an Electronic Lexical Database. MIT Press, 1998. find
  10. Lestor R. Ford and D. R. Fulkerson. Flows in Networks. Princeton University Press, 1962. find
  11. L C. Freeman. Centrality in networks: I. conceptual clarification. Social Networks, 1:215–239, 1979. find
  12. P. Hage and F. Harary. Eccentricity and centrality in networks. Social Networks, 13:57–63, 1995. find
  13. Jon M. Kleinberg. Authoritative sources in a hyperlinked environment. In Proceedings of the 9th ACM-SIAM Symposium on Discrete Algorithms, pages 668–677, San Francisco, California, 1998. our card
  14. Michael Lesk. Automatic sense disambiguation using machine readable dictionaries: How to tell a pine cone from an ice cream cone. In Proceedings of the 5th SIGDOC, pages 24–26, New York, NY, 1986. find
  15. Diana McCarthy, Rob Koeling, Julie Weeds, and John Carroll. Finding predominant senses in untagged text. In Proceedings of the 42nd ACL, pages 280–287, Barcelona, Spain, 2004. our card
  16. Rada Mihalcea. Unsupervised large-vocabulary word sense disambiguation with graph-based algorithms for sequence data labeling. In Proceedings of the HLT/EMNLP, pages 411–418, Vancouver, BC, 2005. our card
  17. George Miller, Claudia Leacock, Tengi Randee, and Ross Bunker. A semantic concordance. In Proceedings of the 3rd DARPA Workshop on HLT, pages 303–308, Plainsboro, New Jersey, 1993. our card
  18. Saif Mohammad and Graeme Hirst. Determining word sense dominance using a thesaurus. In Proceedings of the 11th EACL, pages 121–128, Trento, Italy, 2006. find
  19. Roberto Navigli and Paola Velardi. Structural semantic interconnections: a knowledge-based approach to word sense disambiguation. IEEE Transactions on Pattern Analysis and Machine Intelligence, 27(7):1075–1088, 2005. find
  20. Roberto Navigli. Semi-automatic extension of large-scale linguistic knowledge bases. In Proceedings of the 18th FLAIRS, pages 548–553, Clearwater Beach, Florida, 2005. find
  21. Tou Hwee Ng. Getting serious about word sense disambiguation. In Proceedings of the ACL SIGLEX Workshop on Tagging Text with Lexical Semantics: Why, What, and How?, pages 1–7, Washington, DC, 1997. find
  22. Ganesh Ramakrishnan, Apurva Jadhav, Ashutosh Joshi, Soumen Chakrabarti, and Pushpak Bhattacharyya. Question answering via bayesian inference on lexical relations. In Proceedings of the ACL Workshop on Multilingual Summarization and Question Answering, pages 1–10, Sapporo, Japan, 2003. find
  23. Benjamin Snyder and Martha Palmer. The English all-words task. In Proceedings of the ACL SENSEVAL-3 Workshop, pages 41–43, Barcelona, Spain, 2004. find
  24. Christopher Stokoe. Differentiating homonymy and polysemy in information retrieval. In Proceedings of the HLT/EMNLP, pages 403–410, Vancouver, BC, 2005. find
  25. Carlo Strapparava, Alfio Gliozzo, and Claudio Giuliano. Pattern abstraction and term similarity for word sense disambiguation: Irst at senseval-3. In Proceedings of the ACL SENSEVAL-3 Workshop, pages 229–234, Barcelona, Spain, 2004. find
  26. Trystan Upstill, Nick Craswell, and David Hawking. Predicting fame and fortune: Pagerank or indegree? In Proceedings of the Australasian Document Computing Symposium, Canberra, Australia, 2003. find
  27. David Vickrey, Luke Biewald, Marc Teyssier, and Daphne Koller. Word-sense disambiguation for machine translation. In Proceedings of the HLT/EMNLP, pages 771–778, Vancouver, BC, 2005. our card
  28. Stanley Wasserman and Kathernie Faust. Social Network Analysis: Methods and Applications. Cambridge University Press, Cambridge, UK, 1994. find
  29. David Yarowsky and Radu Florian. Evaluating sense disambiguation across diverse parameter spaces. Natural Language Engineering, 9(4):293–310, 2002. IJCAI-07 1688 find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/navigli-2007-graph-connectivity-measures-unsupervised-word/