Elamur Research⌕
☰
home / papers / 2004 / LexRank: Graph-based Lexical Centrality as Salience in Text Summarization

LexRank: Graph-based Lexical Centrality as Salience in Text Summarization

Paper · 2004 · Gunes Erkan and Dragomir R. Radev

Summary

The paper addresses multi-document extractive summarization, in which the most important sentences must be selected from a group of texts on a single topic. Previously, sentence importance was mostly assessed by the presence of keywords or by proximity to the cluster centroid. The authors propose a different approach. Sentences become vertices of a graph, and edges are weighted by the cosine similarity of their tf×idf vectors. A sentence's weight is determined by its centrality in this graph, by analogy with "prestige" in social networks and with PageRank. Three measures are compared: Degree, LexRank with a threshold, and continuous LexRank. All three are integrated as features into the MEAD system and evaluated on the DUC 2003 and DUC 2004 data. In most cases, the degree-based methods outperform the Centroid approach and the other systems participating in DUC. LexRank with a threshold performs best. Another finding is that the method is largely robust to the noise that arises when documents are poorly clustered by topic. A similarity graph can be built for many NLP tasks, so the approach has broader applicability than summarization alone.

Key points

  • LexRank computes a sentence's weight via the eigenvector (eigenvector centrality) of the stochastic similarity matrix, i.e., via a random walk on the sentence graph. Similarity between sentences is computed as the cosine between tf×idf vectors.
  • The authors compare three centrality measures: Degree, LexRank with a threshold (unweighted graph), and continuous LexRank (weighted graph). The choice of cosine threshold, e.g., 0.1, 0.2, or 0.3, strongly affects which sentences turn out to be central.
  • The LexRank-based system ranked first in several DUC 2004 tasks. DUC 2003 data were added for a broader evaluation.
  • Even the simplest measure, Degree, produces better summaries than the lead-based baselines and Centroid. To handle repetition across documents, the authors use the MEAD reranker.
  • As future work, the authors describe random walks on bipartite "feature–object" graphs for semi-supervised classification, e.g., for spam detection.

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, topics and concepts

📚 Shelves 4The field of science this work belongs to (OpenAlex fields).Computer Science · 16,667 worksArtificial Intelligence · 16,194 worksArts and Humanities · 16,039 worksLanguage and Linguistics · 15,891 works

🧭 Topics 1Research subjects and languages the work is about.Summarization · 232 works

💡 Concepts 1Key ideas and methods explained on our concept pages.Text summarization · 49 works

Cite

Cite as Gunes Erkan and Dragomir R. Radev. 2004. LexRank: Graph-based Lexical Centrality as Salience in Text Summarization. arXiv:1109.2128 · Journal Of Artificial Intelligence Research, Volume 22, pages 457-479, 2004.

The paper itself, not this page. BibTeX from the library's record of the work. DOI 10.1613/jair.1523 · arXiv 1109.2128

@misc{erkan2004lexrank,
  title = {{LexRank: Graph-based Lexical Centrality as Salience in Text Summarization}},
  author = {Gunes Erkan and Dragomir R. Radev},
  year = {2004},
  doi = {10.1613/jair.1523},
  eprint = {1109.2128},
  archivePrefix = {arXiv},
  url = {https://doi.org/10.1613/jair.1523}
}

References

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

  1. Barzilay, R., & Elhadad, M. (1999). Using Lexical Chains for Text Summarization. In Mani, I., & Maybury, M. T. (Eds.), Advances in Automatic Text Summarization, pp. 111–121. The MIT Press.
  2. Barzilay, R., & Lee, L. (2003). Learning to paraphrase: An unsupervised approach using multiple-sequence alignment. In Proceedings of HLT-NAACL.
  3. Baxendale, P. (1958). Man-made index for technical litterature - an experiment. IBM J. Res. Dev., 2 (4), 354–361. find
  4. Brandow, R., Mitze, K., & Rau, L. F. (1995). Automatic condensation of electronic publications by sentence selection. Information Processing and Management, 31 (5), 675–685. find
  5. Brew, C., & im Walde, S. S. (2002). Spectral clustering for german verbs. In Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics. find
  6. Brin, S., & Page, L. (1998). The anatomy of a large-scale hypertextual Web search engine. Computer Networks and ISDN Systems, 30 (1–7), 107–117.
  7. Carbonell, J. G., & Goldstein, J. (1998). The use of MMR, diversity-based reranking for reordering documents and producing summaries. In Research and Development in Information Retrieval, pp. 335–336. find
  8. Collins, M. (1997). Three generative, lexicalised models for statistical parsing. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics.
  9. Daumé III, H., & Marcu, D. (2004). A phrase-based hmm approach to document/abstract alignment. In Lin, D., & Wu, D. (Eds.), Proceedings of EMNLP 2004, pp. 119–126 Barcelona, Spain. Association for Computational Linguistics. find
  10. Edmundson, H. (1969). New Methods in Automatic Extracting. Journal of the Association for Computing Machinery, 16 (2), 264–285. find
  11. Erkan, G., & Radev, D. R. (2004a). Lexpagerank: Prestige in multi-document text summarization. In Lin, D., & Wu, D. (Eds.), Proceedings of EMNLP 2004, pp. 365–371 Barcelona, Spain. Association for Computational Linguistics. find
  12. Erkan, G., & Radev, D. R. (2004b). The University of Michigan at DUC 2004. In Proceedings of the Document Understanding Conferences Boston, MA. find
  13. Hatzivassiloglou, V., Klavans, J., Holcombe, M., Barzilay, R., Kan, M., & McKeown, K. (2001). Simfinder: A flexible clustering tool for summarization.. find
  14. Jing, H. (2002). Using hidden markov modeling to decompose Human-Written summaries. CL, 28 (4), 527–543.
  15. Knight, K., & Marcu, D. (2000). Statistics-based summarization — step one: Sentence compression. In Proceeding of The 17th National Conference of the American Association for Artificial Intelligence (AAAI-2000), pp. 703–710. find
  16. Kupiec, J., Pedersen, J. O., & Chen, F. (1995). A trainable document summarizer. In Research and Development in Information Retrieval, pp. 68–73. find
  17. Lin, C.-Y. (1999). Training a Selection Function for Extraction. In Proceedings of the Eighteenth Annual International ACM Conference on Information and Knowledge Management (CIKM), pp. 55–62 Kansas City. ACM. find
  18. Lin, C.-Y., & Hovy, E. (2003). Automatic evaluation of summaries using n-gram co-occurrence. In Proceedings of 2003 Language Technology Conference (HLT-NAACL 2003), Edmonton, Canada, May 27 - June 1. find
  19. Luhn, H. (1958). The Automatic Creation of Literature Abstracts. IBM Journal of Research Development, 2 (2), 159–165. find
  20. Mani, I., & Bloedorn, E. (1997). Multi-document summarization by graph search and matching. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), pp. 622–628 Providence, Rhode Island. American Association for Artificial Intelligence. find
  21. McKeown, K. R., Barzilay, R., Evans, D., Hatzivassiloglou, V., Teufel, S., Kan, Y. M., & Schiffman, B. (2001). Columbia Multi-Document Summarization: Approach and Evaluation. In Proceedings of the 24th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval New… find
  22. Mihalcea, R., & Tarau, P. (2004). Textrank: Bringing order into texts. In Lin, D., & Wu, D. (Eds.), Proceedings of EMNLP 2004, pp. 404–411 Barcelona, Spain. Association for Computational Linguistics. find
  23. Mihalcea, R., Tarau, P., & Figa, E. (2004). Pagerank on semantic networks, with application to word sense disambiguation. In Proceedings of The 20st International Conference on Computational Linguistics (COLING 2004) Geneva, Switzerland.
  24. Moens, M.-F., Uyttendaele, C., & Dumortier, J. (1999). Abstracting of legal cases: the potential of clustering based on the selection of representative objects. J. Am. Soc. Inf. Sci., 50 (2), 151–161. find
  25. Osborne, M. (2002). Using Maximum Entropy for Sentence Extraction. In ACL Workshop on Text Summarization. find
  26. Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The pagerank citation ranking: Bringing order to the web. Technical report, Stanford University, Stanford, CA.
  27. Radev, D. (2000). A common theory of information fusion from multiple text sources, step one: Cross-document structure. In Proceedings, 1st ACL SIGDIAL Workshop on Discourse and Dialogue Hong Kong. find
  28. Radev, D., Blair-Goldensohn, S., & Zhang, Z. (2001). Experiments in single and multi-document summarization using MEAD. In First Document Understanding Conference New Orleans, LA. find
  29. Radev, D. R., Jing, H., & Budzikowska, M. (2000). Centroid-based summarization of multiple documents: sentence extraction, utility-based evaluation, and user studies. In ANLP/NAACL Workshop on Summarization Seattle, WA.
  30. Radev, D. R., & McKeown, K. R. (1998). Generating natural language summaries from multiple on-line sources. Computational Linguistics, 24 (3), 469–500.
  31. Salton, G., Singhal, A., Mitra, M., & Buckley, C. (1997). Automatic Text Structuring and Summarization. Information Processing & Management, 33 (2), 193–207. find
  32. Seneta, E. (1981). Non-negative matrices and markov chains. Springer-Verlag, New York. find
  33. Sparck-Jones, K. (1972). A statistical interpretation of term specificity and its application in retrieval. Journal of Documentation, 28 (1), 11–20. find
  34. Toutanova, K., Manning, C., & Ng, A. (2004). Learning random walk models for inducing word dependency distributions. In Proceedings of ICML. find
  35. Witbrock, M., & Mittal, V. O. (1999). Ultra-Summarization: A Statistical Approach to Generating Highly Condensed Non-Extractive Summaries. In SIGIR99, pp. 315–316 Berkeley, CA. find
  36. Yarowsky, D. (1995). Unsupervised word sense disambiguation rivaling supervised methods. In Proceedings of the 33rd Annual Meeting of the Association for Computational Linguistics.
  37. Zha, H. (2002). Generic Summarization and Key Phrase Extraction Using Mutual Reinforcement Principle and Sentence Clustering. In Proceedings of the 25th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval Tampere, Finland. find

Updated

↑ back to top

This page in Markdown → https://md.research.elamur.ai/free/en/papers/erkan-2011-lexrank-graph-based-lexical-centrality/