Introduction
Update summarization is a specialized task in multi-document summarization where the goal is to provide a concise summary of new developments in a news story for a reader who is already familiar with earlier reports. This requires the system to identify novel information while maintaining relevance to the core topic. Researchers from the Harbin Institute of Technology (HITIR) addressed this challenge at the Text Analysis Conference (TAC) 2008 by proposing a language-independent, graph-based extractive approach. Their system, which combines Spectral Clustering with a novel Evolutionary Manifold-Ranking algorithm, achieved top-tier performance in semantic-based evaluations.
Methodology
The HITIR approach is designed to be language-independent by avoiding deep linguistic rules and instead relying on the structural properties of document collections.
Sub-topic Partitioning via Spectral Clustering
To ensure broad coverage of the news story's facets, the system first partitions sentences into sub-topics. By treating sentences as nodes in a graph, the system employs Spectral Clustering to group similar sentences. A significant advantage of this method is its ability to automatically determine the optimal number of sub-topics based on the mathematical properties (eigenvalues) of the sentence-similarity matrix, eliminating the need for manual parameter tuning.
Evolutionary Manifold-Ranking
The core of the content selection process is the Evolutionary Manifold-Ranking algorithm. Traditional manifold-ranking determines sentence importance based on its relationship to a query and its neighbors. HITIR "evolved" this by introducing an iterative feedback mechanism—a "relay propagation" effect. The query is expanded to include not only the topic title but also summaries of previous time slices and lead sentences of new documents. This allows the system to track the progression of a story over time, effectively filtering out redundant information from previous document sets.
Sentence Selection
Final sentence selection is performed using a greedy algorithm. It selects the highest-ranking sentences from various sub-topics while applying a redundancy penalty to ensure the final 100-word summary captures diverse new information.
Experimental Setup
The system was evaluated on the TAC 2008 Update Summary track dataset, which consists of 48 topics from the AQUAINT-2 collection. Each topic includes 20 documents divided into two sets: Set A (initial 10 documents) and Set B (subsequent 10 documents). The task was to generate a summary of Set B under the assumption that the reader had already processed Set A.
Results and Analysis
HITIR submitted three system variations (11, 41, and 62). System 11, which utilized the full suite of Spectral Clustering and Evolutionary Manifold-Ranking, emerged as the most effective configuration.
As shown in the table above, System 11 achieved the 1st rank in the Pyramid evaluation (average modified score and average number of SCUs). This indicates that the system was highly effective at identifying the most important semantic content units. However, there was a notable discrepancy between semantic performance and linguistic quality. While System 11 ranked 5th in overall responsiveness, it fell to 27th in linguistic quality. This suggests that while the extractive method identifies the correct facts, the lack of post-processing for coherence results in less fluid summaries.
Conclusion
The HITIR system demonstrates that graph-based methods like Spectral Clustering and Evolutionary Manifold-Ranking are powerful tools for language-independent update summarization. The "relay" concept successfully tracks information evolution across document sets. Future work will focus on improving the linguistic fluency of the generated summaries to bridge the gap between content selection and readability.
Summary updated