Multi-Document Summarization via the Minimum Dominating Set

Proceedings of the 23rd International Conference on Computational Linguistics (Coling 2010), pages 984–992, Beijing, August 2010 Multi-Document Summarization via the Minimum Dominating Set Chao Shen and Tao Li School of Computing and Information Sciences Florida Internation University {cshen001|taoli}@cs.fiu.edu Abstract Multi-document summarization has been an important problem in infor- mation retrieval. It aims to dis- till the most important information from a set of documents to gener- ate a compressed summary. Given a sentence graph generated from a set of documents where vertices repre- sent sentences and edges indicate that the corresponding vertices are simi- lar, the extracted summary can be de- scribed using the idea of graph dom- ination. In this paper, we propose a new principled and versatile frame- work for multi-document summariza- tion using the minimum dominating set. We show that four well-known summarization tasks including generic, query-focused, update, and compara- tive summarization can be modeled as different variations derived from the proposed framework. Approximation algorithms for performing summariza- tion are also proposed and empirical experiments are conducted to demon- strate the effectiveness of our proposed framework. 1 Introduction As a fundamental and effective tool for docu- ment understanding and organization, multi- document summarization enables better infor- mation services by creating concise and infor- mative reports for a large collection of doc- uments. Specifically, in multi-document sum- marization, given a set of documents as input, the goal is to produce a condensation (i.e., a generated summary) of the content of the entire input set (Jurafsky and Martin, 2008). The generated summary can be generic where it simply gives the important information con- tained in the input documents without any particular information needs or query/topic- focused where it is produced in response to a user query or related to a topic or concern the development of an event (Jurafsky and Mar- tin, 2008; Mani, 2001). Recently, new summarization tasks such as update summarization (Dang and Owczarzak, 2008) and comparative summarization (Wang et al., 2009a) have also been proposed. Up- date summarization aims to generate short summaries of recent documents to capture new information different from earlier docu- ments and comparative summarization aims to summarize the differences between compa- rable document groups. In this paper, we propose a new principled and versatile framework for multi-document summarization using the minimum dominat- ing set. Many known summarization tasks in- cluding generic, query-focused, update, and comparative summarization can be modeled as different variations derived from the pro- posed framework. The framework provides an elegant basis to establish the connections be- tween various summarization tasks while high- lighting their differences. In our framework, a sentence graph is first generated from the input documents where vertices represent sentences and edges indicate that the corresponding vertices are similar. A natural method for describing the extracted summary is based on the idea of graph dom- ination (Wu and Li, 2001). A dominating set of a graph is a subset of vertices such that every vertex in the graph is either in the sub- set or adjacent to …

Content truncated to 500 words