Elamur Research⌕
☰
home / papers / 2013 / TopicRank: Graph-Based Topic Ranking for Keyphrase Extraction

TopicRank: Graph-Based Topic Ranking for Keyphrase Extraction

Summary

The paper addresses unsupervised keyphrase extraction, where graph-based methods such as TextRank and SingleRank rank individual words and then assemble or score phrases. This approach scatters a topic's evidence across many vertices and tends to favour long but unimportant phrases. TopicRank moves ranking up one level.

  • Candidates: noun-phrase candidates (maximal runs of nouns and adjectives) are stemmed.
  • Topics: candidates are grouped into topics with hierarchical agglomerative clustering.
  • Graph: topics become vertices of a complete graph. Edge weights come from how close the topics' candidates appear in the text.
  • Ranking and selection: TextRank's ranking scores the topics, and one representative phrase is chosen from each top-ranked topic.

The method was compared with TF-IDF and two graph-based baselines on four datasets that differ in language, domain and document length: Inspec, SemEval, WikiNews and DEFT. TopicRank beats the baselines on three of them. On Inspec, which has short abstracts, it falls behind, but an oracle analysis suggests a better phrase-selection step could close that gap. The work shows that a topic-level, parameter-light graph can reduce redundancy and improve topical coverage without training data.

Key points

  • Candidate clustering: two candidates count as similar when at least 25% of their stemmed words overlap, a threshold set empirically. Clustering uses HAC with average linkage, chosen as a middle ground between complete and single linkage.
  • Edge weights: each weight sums the reciprocal distances between all pairs of offset positions of the two topics' candidates. This removes the hand-tuned co-occurrence window used by TextRank and SingleRank.
  • Ablation: treating topics as vertices yields significantly better results than SingleRank on three datasets: SemEval, WikiNews and DEFT. Using raw phrases as vertices hurts on Inspec, because the short abstracts produce disconnected graph components.
  • Selection strategy: three ways of picking a topic's representative were compared, namely first occurrence, most frequent and centroid. First occurrence wins clearly. On the scientific-article sets, SemEval and DEFT, the other two strategies collapse to an f-score of only a few percent.
  • Upper bound: an oracle counts any top-ranked cluster that contains a reference keyphrase as a correct match. Under this measure, TopicRank could beat all baselines on all four datasets.

Interesting ideas

  • I1. Cluster before ranking: merging near-duplicate candidates into one vertex removes redundancy and concentrates their evidence. This could carry over to summarization, entity ranking or tag suggestion.
  • I2. Distance-based weights on a complete graph: weighting a fully connected graph by reciprocal positional distance replaces a window-size hyperparameter. That is handy when applying a method to new languages or genres without tuning.
  • I3. One output per top cluster: picking a single item from each of the top k clusters guarantees that k results cover k distinct topics. This is a simple diversity mechanism for any top-k extraction task.
  • I4. First mention as representative: the first occurrence of a concept often gives its full form, while later mentions are abbreviations or partial references. This positional heuristic suits scientific and technical text.
  • I5. Oracle upper bound for a pipeline stage: scoring how good the output would be under a perfect selector separates ranking quality from selection quality. It shows which pipeline stage deserves further 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: Natural language processing

Cited by

76 papers of our library cite it (of the 140884 whose bibliographies we read); 1 of them have a page here, 75 not yet.

Cite

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

@inproceedings{bougouin2013topicrank,
  title = {{TopicRank: Graph-Based Topic Ranking for Keyphrase Extraction}},
  author = {Bougouin, Adrien and Boudin, Florian and Daille, Béatrice},
  booktitle = {Proceedings of the Sixth International Joint Conference on Natural Language Processing},
  year = {2013},
  url = {https://aclanthology.org/I13-1062/}
}

References

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

  1. Steven Bird, Ewan Klein, and Edward Loper. 2009. Natural Language Processing with Python. O’Reilly Media. find
  2. David M. Blei, Andrew Y. Ng, and Michael I. Jordan. 2003. Latent Dirichlet Allocation. Journal of Machine Learning Research, 3:993–1022. find our card
  3. Sergey Brin and Lawrence Page. 1998. The Anatomy of a Large-Scale Hypertextual Web Search Engine. Computer Networks and ISDN Systems, 30(1):107– 117. find our card
  4. Pascal Denis and Benoı̂t Sagot. 2009. Coupling an Annotated Corpus and a Morphosyntactic Lexicon for State-of-the-Art POS Tagging with Less Human Effort. In Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation (PACLIC), pages 110–119, Hong Kong, December. City Uni… find
  5. Juhyun Han, Taehwan Kim, and Joongmin Choi. 2007. Web Document Clustering by Using Automatic Keyphrase Extraction. In Proceedings of the 2007 IEEE/WIC/ACM International Conferences on Web Intelligence and Intelligent Agent Technology, pages 56–59, Washington, DC, USA. IEEE Computer Society. find
  6. Kazi Saidul Hasan and Vincent Ng. 2010. Conundrums in Unsupervised Keyphrase Extraction: Making Sense of the State-of-the-Art. In Proceedings of the 23rd International Conference on Computational Linguistics: Posters, pages 365–373, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  7. Taher H. Haveliwala. 2003. Topic-Sensitive PageRank: A Context-Sensitive Ranking Algorithm for Web Search. IEEE Transactions on Knowledge and Data Engineering, 15(4):784–796. find
  8. Anette Hulth. 2003. Improved Automatic Keyword Extraction Given More Linguistic Knowledge. In Proceedings of the 2003 Conference on Empirical Methods in Natural Language Processing, pages 216–223, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  9. Su Nam Kim, Olena Medelyan, Min-Yen Kan, and Timothy Baldwin. 2010. SemEval-2010 task 5: Automatic Keyphrase Extraction from Scientific Articles. In Proceedings of the 5th International Workshop on Semantic Evaluation, pages 21–26, Stroudsburg, PA, USA. Association for Computational Linguistics. find our card
  10. Jon M. Kleinberg. 1999. Authoritative Sources in a Hyperlinked Environment. Journal of the ACM (JACM), 46(5):604–632, sep. find our card
  11. Weiming Liang, Chang-Ning Huang, Mu Li, and Bao-Liang Lu. 2009. Extracting Keyphrases from Chinese News Articles Using TextRank and Query Log Knowledge. In Proceedings of the 23rd Pacific Asia Conference on Language, Information and Computation, pages 733–740, Hong Kong, December. City University of… find
  12. Marina Litvak and Mark Last. 2008. Graph-Based Keyword Extraction for Single-Document Summarization. In Proceedings of the Workshop on Multi-Source Multilingual Information Extraction and Summarization, pages 17–24, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  13. Zhiyuan Liu, Peng Li, Yabin Zheng, and Maosong Sun. 2009. Clustering to Find Exemplar Terms for Keyphrase Extraction. In Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing: Volume 1, pages 257–266, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  14. Zhiyuan Liu, Wenyi Huang, Yabin Zheng, and Maosong Sun. 2010. Automatic Keyphrase Extraction Via Topic Decomposition. In Proceedings of the 2010 Conference on Empirical Methods in Natural Language Processing, pages 366–376, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  15. Olena Medelyan and Ian H. Witten. 2008. Domain-Independent Automatic Keyphrase Indexing with Small Training Sets. Journal of the American Society for Information Science and Technology, 59(7):1026–1040, may. find
  16. Rada Mihalcea and Paul Tarau. 2004. TextRank: Bringing Order Into Texts. In Dekang Lin and Dekai Wu, editors, Proceedings of the 2004 Conference on Empirical Methods in Natural Language Processing, pages 404–411, Barcelona, Spain, July. Association for Computational Linguistics. find
  17. George A. Miller. 1995. WordNet: a Lexical Database for English. Communications of the Association for Computational Linguistics, 38(11):39–41. find our card
  18. Patrick Paroubek, Pierre Zweigenbaum, Dominic Forest, and Cyril Grouin. 2012. Indexation libre et contrôlée d’articles scientifiques. Présentation et résultats du défi fouille de textes DEFT2012 (Controlled and Free Indexing of Scientific Papers. Presentation and Results of the DEFT2012 Text-Mi… find
  19. Karen Spärck Jones. 1972. A Statistical Interpretation of Term Specificity and its Application in Retrieval. Journal of Documentation, 28(1):11–21. find
  20. Takashi Tomokiyo and Matthew Hurst. 2003. A Language Model Approach to Keyphrase Extraction. In Proceedings of the ACL 2003 Workshop on Multiword Expressions: Analysis, Acquisition and Treatment - Volume 18, pages 33–40, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  21. Kristina Toutanova, Dan Klein, Christopher D. Manning, and Yoram Singer. 2003. Feature-Rich Part-of-Speech Tagging with a Cyclic Dependency Network. In Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology - Vol… find our card
  22. George Tsatsaronis, Iraklis Varlamis, and Kjetil Nørvåg. 2010. SemanticRank: Ranking Keywords and Sentences Using Semantic Graphs. In Proceedings of the 23rd International Conference on Computational Linguistics, pages 1074–1082, Stroudsburg, PA, USA. Association for Computational Linguistics. find
  23. Xiaojun Wan and Jianguo Xiao. 2008. Single Document Keyphrase Extraction Using Neighborhood Knowledge. In Proceedings of the 23rd National Conference on Artificial Intelligence - Volume 2, pages 855–860. AAAI Press. find
  24. Ian H. Witten, Gordon W. Paynter, Eibe Frank, Carl Gutwin, and Craig G. Nevill Manning. 1999. KEA: Practical Automatic Keyphrase Extraction. In Proceedings of the 4th ACM Conference on Digital Libraries, pages 254–255, New York, NY, USA. ACM. find

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/bougouin-2013-topicrank-graph-based-topic-ranking/