Multi-document summarization using cluster-based link analysis

ABSTRACT

The Markov Random Walk model has been recently exploited for multi-document summarization by making use of the link relationships between sentences in the document set, under the assumption that all the sentences are indistinguishable from each other. However, a given document set usually covers a few topic themes with each theme represented by a cluster of sentences. The topic themes are usually not equally important and the sentences in an important theme cluster are deemed more salient than the sentences in a trivial theme cluster. This paper proposes the Cluster-based Conditional Markov Random Walk Model (ClusterCMRW) and the Cluster-based HITS Model (ClusterHITS) to fully leverage the cluster-level information. Experimental results on the DUC2001 and DUC2002 datasets demonstrate the good effectiveness of our proposed summarization models. The results also demonstrate that the ClusterCMRW model is more robust than the ClusterHITS model, with respect to different cluster numbers.

REFERENCES

• 1: Ricardo A. Baeza-Yates , Berthier Ribeiro-Neto, Modern Information Retrieval, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1999
• 2: Regina Barzilay , Kathleen R. McKeown , Michael Elhadad, Information fusion in the context of multi-document summarization, Proceedings of the 37th annual meeting of the Association for Computational Linguistics on Computational Linguistics, p.550-557, June 20-26, 1999, College Park, Maryland [doi>10.3115/1034678.1034760]
• 3: Hal Daumé, III , Daniel Marcu, Bayesian query-focused summarization, Proceedings of the 21st International Conference on Computational Linguistics and the 44th annual meeting of the Association for Computational Linguistics, p.305-312, July 17-18, 2006, Sydney, Australia [doi>10.3115/1220175.1220214]
• 4: G. Erkan and D. Radev. LexPageRank: prestige in multi-document text summarization. In Proceedings of EMNLP2004.
• 5: Jade Goldstein , Mark Kantrowitz , Vibhu Mittal , Jaime Carbonell, Summarizing text documents: sentence selection and evaluation metrics, Proceedings of the 22nd annual international ACM SIGIR conference on Research and development in information retrieval, p.121-128, August 15-19, 1999, Berkeley, California, United States [doi>10.1145/312624.312665]
• 6: Sanda Harabagiu , Finley Lacatusu, Topic themes for multi-document summarization, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076071]
• 7: Hilda Hardy , Nobuyuki Shimizu , Tomek Strzalkowski , Liu Ting , Xinyang Zhang , G. Bowden Wise, Cross-document summarization by concept classification, Proceedings of the 25th annual international ACM SIGIR conference on Research and development in information retrieval, August 11-15, 2002, Tampere, Finland [doi>10.1145/564376.564399]
• 8: A. K. Jain , M. N. Murty , P. J. Flynn, Data clustering: a review, ACM Computing Surveys (CSUR), v.31 n.3, p.264-323, Sept. 1999 [doi>10.1145/331499.331504]
• 9: Jon M. Kleinberg, Authoritative sources in a hyperlinked environment, Journal of the ACM (JACM), v.46 n.5, p.604-632, Sept. 1999 [doi>10.1145/324133.324140]
• 10: Kevin Knight , Daniel Marcu, Summarization beyond sentence extraction: a probabilistic approach to sentence compression, Artificial Intelligence, v.139 n.1, p.91-107, July 2002 [doi>10.1016/S0004-3702(02)00222-9]
• 11: W. Kraaij, M. Spitters and M. van der Heijden. Combining a mixture language model and Naïve Bayes for multi-document summarization. In SIGIR2001 Workshop on Text Summarization.
• 12: Oren Kurland , Lillian Lee, PageRank without hyperlinks: structural re-ranking using links induced by language models, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076087]
• 13: Oren Kurland , Lillian Lee, Respect my authority!: HITS without hyperlinks, utilizing cluster-based language models, Proceedings of the 29th annual international ACM SIGIR conference on Research and development in information retrieval, August 06-11, 2006, Seattle, Washington, USA [doi>10.1145/1148170.1148188]
• 14: Anton Leuski , Chin-Yew Lin , Eduard Hovy, iNeATS: interactive multi-document summarization, Proceedings of the 41st Annual Meeting on Association for Computational Linguistics, p.125-128, July 07-12, 2003, Sapporo, Japan [doi>10.3115/1075178.1075197]
• 15: Chin-Yew Lin , Eduard Hovy, From single to multi-document summarization: a prototype system and its evaluation, Proceedings of the 40th Annual Meeting on Association for Computational Linguistics, July 07-12, 2002, Philadelphia, Pennsylvania [doi>10.3115/1073083.1073160]
• 16: Chin-Yew Lin , Eduard Hovy, Automatic evaluation of summaries using N-gram co-occurrence statistics, Proceedings of the 2003 Conference of the North American Chapter of the Association for Computational Linguistics on Human Language Technology, p.71-78, May 27-June 01, 2003, Edmonton, Canada [doi>10.3115/1073445.1073465]
• 17: Tie-Yan Liu , Wei-Ying Ma, Webpage Importance Analysis Using Conditional Markov Random Walk, Proceedings of the 2005 IEEE/WIC/ACM International Conference on Web Intelligence, p.515-521, September 19-22, 2005 [doi>10.1109/WI.2005.161]
• 18: Inderjeet Mani , Eric Bloedorn, Summarizing Similarities and Differences Among Related Documents, Information Retrieval, v.1 n.1-2, p.35-67, 1999 [doi>10.1023/A:1009930203452]
• 19: D. Marcu. Discourse-based summarization in DUC-2001. 2001. In SIGIR 2001 Workshop on Text Summarization.
• 20: Kathleen R. McKeown , Judith L. Klavans , Vasileios Hatzivassiloglou , Regina Barzilay , Eleazar Eskin, Towards multidocument summarization by reformulation: progress and prospects, Proceedings of the sixteenth national conference on Artificial intelligence and the eleventh Innovative applications of artificial intelligence conference innovative applications of artificial intelligence, p.453-460, July 18-22, 1999, Orlando, Florida, United States
• 21: R. Mihalcea and P. Tarau. A language independent algorithm for single and multiple document summarization. In Proceedings of IJCNLP2005.
• 22: L. Page, S. Brin, R. Motwani and T. Winograd. The pagerank citation ranking: Bringing order to the web. Technical report, Stanford Digital Libraries, 1998.
• 23: Dragomir R. Radev , Hongyan Jing , Małgorzata Styś , Daniel Tam, Centroid-based summarization of multiple documents, Information Processing and Management: an International Journal, v.40 n.6, p.919-938, November 2004 [doi>10.1016/j.ipm.2003.10.006]
• 24: Horacio Saggion , Kalina Bontcheva , Hamish Cunningham, Robust generic and query-based summarisation, Proceedings of the tenth conference on European chapter of the Association for Computational Linguistics, April 12-17, 2003, Budapest, Hungary [doi>10.3115/1067737.1067793]
• 25: X. Wan and J. Yang. 2006. Improved affinity graph based multi-document summarization. In Proceedings of HLT-NAACL2006.
• 26: Gui-Rong Xue , Qiang Yang , Hua-Jun Zeng , Yong Yu , Zheng Chen, Exploiting the hierarchical structure for link analysis, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076068]
• 27: Benyu Zhang , Hua Li , Yi Liu , Lei Ji , Wensi Xi , Weiguo Fan , Zheng Chen , Wei-Ying Ma, Improving web search results using affinity graph, Proceedings of the 28th annual international ACM SIGIR conference on Research and development in information retrieval, August 15-19, 2005, Salvador, Brazil [doi>10.1145/1076034.1076120]
• 28: D. Zhou, S. A. Orshanskiy, H. Zha and C. L. Giles. Co-ranking authors and documents in a heterogeneous network. In Proceedings of IEEE ICDM2007.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Abstracting methods

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.7 Natural Language Processing
          Subjects: Text analysis

General Terms:
Algorithms, Experimentation, Performance

Keywords:
HITS, cluster-based link analysis, conditional Markov random walk model, multi-document summarization