Correlating summarization of multi-source news with k-way graph bi-clustering

ABSTRACT

With the emergence of enormous amount of online news, it is desirable to construct text mining methods that can extract, compare and highlight similarities of them. In this paper, we explore the research issue and methodology of correlated summarization for a pair of news articles. The algorithm aligns the (sub)topics of the two news articles and summarizes their correlation by sentence extraction. A pair of news articles are modelled with a weighted bipartite graph. A mutual reinforcement principle is applied to identify a dense subgraph of the weighted bipartite graph. Sentences corresponding to the subgraph are correlated well in textual content and convey the dominant shared topic of the pair of news articles. As a further enhancement for lengthy articles, a k-way bi-clustering algorithm can first be used to partition the bipartite graph into several clusters, each containing sentences from the two news reports. These clusters correspond to shared subtopics, and the above mutual reinforcement principle can then be applied to extract topic sentences within each subtopic group.

REFERENCES

• 1: Jaime Carbonell , Jade Goldstein, The use of MMR, diversity-based reranking for reordering documents and producing summaries, Proceedings of the 21st annual international ACM SIGIR conference on Research and development in information retrieval, p.335-336, August 24-28, 1998, Melbourne, Australia [doi>10.1145/290941.291025]
• 2: R. Cooley, J. Srivastava, and B. Mobasher. Web mining: Information and pattern discovery on the world wide web. pages 558--567, 1997.
• 3: Jim Cowie , Wendy Lehnert, Information extraction, Communications of the ACM, v.39 n.1, p.80-91, Jan. 1996 [doi>10.1145/234173.234209]
• 4: Dragomir R. Radev , Sasha Blair-Goldensohn , Zhu Zhang , Revathi Sundara Raghavan, Interactive, Domain-Independent Identification and Summarization of Topically Related News Articles, Proceedings of the 5th European Conference on Research and Advanced Technology for Digital Libraries, p.225-238, September 04-09, 2001
• 5: Jeffrey Dean , Monika R. Henzinger, Finding related pages in the World Wide Web, Proceeding of the eighth international conference on World Wide Web, p.1467-1479, May 1999, Toronto, Canada
• 6: M. Dixon. An overview of document mining technology. http://citeseer.ist.psu.edu/dixon97overview.html, 1997.
• 7: L. Ertoz, M. Steinbach, and V. Kumar. Finding topics in collections of documents: A shared nearest neighbor approach. In Text Mine '01, Workshop on Text Mining, First SIAM International Conference on Data Mining, Chicago, IL, 2001.
• 8: P. Gawrysiak. Using data mining methodology for text retrieval. In Proceedings of International Information Science and Education Conference, Gdansk, Poland, 1999.
• 9: Jade Goldstein , Vibhu Mittal , Jaime Carbonell , Mark Kantrowitz, Multi-document summarization by sentence extraction, NAACL-ANLP 2000 Workshop on Automatic summarization, p.40-48, April 30-30, 2000, Seattle, Washington [doi>10.3115/1117575.1117580]
• 10: M. Gu, H. Zha, C. Ding, X. He, and H. Simon. Spectral relaxation models and structure analysis for k-way graph clustering and bi-clustering. Technical Report CSE-01-007, Department of Computer Science and Engineering, the Pennsylvania State University, 2001.
• 11: Taher H. Haveliwala , Aristides Gionis , Dan Klein , Piotr Indyk, Evaluating strategies for similarity search on the web, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511502]
• 12: Minqing Hu , Bing Liu, Mining and summarizing customer reviews, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014073]
• 13: Raymond Kosala , Hendrik Blockeel, Web mining research: a survey, ACM SIGKDD Explorations Newsletter, v.2 n.1, p.1-15, June, 2000 [doi>10.1145/360402.360406]
• 14: S. Lawrence and C. Giles. Accessibility of information on the web. Nature, 400:107--109, 1999.
• 15: I. Mani and E. Bloedorn. Multi-document summarization by graph search and matching. In Proceedings of the Fourteenth National Conference on Artificial Intelligence (AAAI-97), pages 622--628, Providence, RI, 1997.
• 16: 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]
• 17: Mark T. Maybury , Inderjeet Mani, Advances in Automatic Text Summarization, MIT Press, Cambridge, MA, 1999
• 18: D. Marcu. Automatic abstracting. Encyclopedia of Library and Information Science, pages 245--256, 2003.
• 19: J. L. Neto, A. D. Santos, C. A. A. Kaestner, and A. A. Freitas. Document clustering and text summarization. In 4th International Conference on Practical Applications of Knowledge Discovery and Data Ming, London, 2000.
• 20: C. D. Paice, Constructing literature abstracts by computer: techniques and prospects, Information Processing and Management: an International Journal, v.26 n.1, p.171-186, 1990 [doi>10.1016/0306-4573(90)90014-S]
• 21: M. Porter. An algorithm for suffix stripping. Program, 14(3):130--137, 1980.
• 22: Dragomir R. Radev, A common theory of information fusion from multiple text sources step one: cross-document structure, Proceedings of the 1st SIGdial workshop on Discourse and dialogue, p.74-83, October 07-08, 2000, Hong Kong [doi>10.3115/1117736.1117745]
• 23: Dragomir R. Radev , Weiguo Fan, Automatic summarization of search engine hit lists, Proceedings of the ACL-2000 workshop on Recent advances in natural language processing and information retrieval: held in conjunction with the 38th Annual Meeting of the Association for Computational Linguistics, October 08-08, 2000, Hong Kong [doi>10.3115/1117755.1117768]
• 24: Dragomir R. Radev , Kathleen R. McKeown, Generating natural language summaries from multiple on-line sources, Computational Linguistics, v.24 n.3, September 1998
• 25: Horst D. Simon , Hongyuan Zha, Low-Rank Matrix Approximation Using the Lanczos Bidiagonalization Process with Applications, SIAM Journal on Scientific Computing, v.21 n.6, p.2257-2274, Dec 1999 [doi>10.1137/S1064827597327309]
• 26: C. Wayne. Multilingual topic detection and tracking: Successful research enabled by corpora and evaluation. In Proceedings of Language Resources and Evaluation Conference (LREC), pages 1487--1494, 2000.

INDEX TERMS

Keywords:
biclustering, bipartite graph, correlated summarization, news summarization