Centrality Meets Centroid: A Graph-based Approach for Unsupervised Document Summarization

Haopeng Zhang, Jiawei ZhangarXiv 2021 · OpenReview

TL;DR

This paper introduces CCSUM, a novel unsupervised document summarization method that treats summarization as a subgraph selection problem. By combining graph centrality and centroid-based approaches, CCSUM effectively leverages both sentence relationships and semantic content to generate more coherent and informative summaries than previous sentence-by-sentence methods.

What Problem Does This Paper Address?

Creating high-quality document summaries often requires large datasets of human-annotated document-summary pairs. This annotation process is time-consuming and expensive, making it difficult to scale. Consequently, there's a growing interest in unsupervised summarization methods that don't rely on such labeled data. Existing unsupervised methods often fall into two camps: centrality-based (focusing on sentence connectivity) or centroid-based (focusing on sentence similarity to the document's overall meaning). However, these approaches tend to operate at the sentence level, selecting sentences one by one, which can lead to redundancy and a lack of overall summary coherence. This paper aims to bridge this gap by proposing a summary-level approach that effectively combines both graph connectivity and semantic content.

Methods

The proposed method, Centrality Centroid Summarization (CCSUM), operates in two main stages:

  1. Candidate Summary Generation (Centrality-based Subgraph Extraction):
    • Sentence Relation Graph Construction: A document is first represented as a graph where sentences are nodes and edge weights represent semantic similarity. Sentence embeddings are generated using a fine-tuned BERT model, and positional encodings are added. Edge weights are calculated using cosine similarity between sentence embeddings, with a threshold applied to filter out weak connections.
  2. Subgraph Centrality: Instead of ranking individual sentences, CCSUM identifies candidate summaries by extracting subgraphs of a fixed size (e.g., 3 sentences). A "subgraph centrality" metric is defined, which essentially measures the external influence of a subgraph within the larger document graph. Subgraphs with higher centrality are considered more promising candidate summaries.
  3. Summary Selection (Centroid-based Subgraph Matching):
    • Document Centroid: The overall document is represented by a centroid vector, which is the mean of all sentence embeddings.
  4. Subgraph Matching: The candidate subgraphs (potential summaries) are then compared to the document centroid. The method uses a message-passing architecture to update node representations within the graph, creating a more refined representation for both the document and the candidate summaries. The semantic similarity between the document centroid and each candidate summary's representation is calculated.
  5. Final Summary Selection: The candidate summary that is semantically closest to the document centroid is selected as the final summary.

This approach moves beyond sentence-level selection by treating the entire summary as a subgraph and selecting the best subgraph based on its centrality and its semantic alignment with the document.

Datasets

The paper evaluates CCSUM on two widely used single-document summarization datasets:

  • CNN/Daily Mail: This dataset consists of news articles from CNN and Daily Mail, with associated highlights used as summaries.
  • NYT: This dataset is derived from the New York Times Annotated Corpus, containing news articles and abstractive summaries written by professional editors.

The paper notes that the CNN/Daily Mail dataset exhibits a strong positional bias, where salient information is often concentrated at the beginning of documents.

Key Insights and Ideas

  • Summary-Level Extraction: Treating summarization as a subgraph selection problem, rather than a sentence-by-sentence ranking, allows for a more holistic approach that can capture better summary coherence and reduce redundancy.
  • Synergistic Use of Centrality and Centroid: The paper effectively combines graph connectivity (centrality) with semantic content (centroid) to improve summarization quality. Centrality helps identify potentially important groups of sentences, while the centroid helps select the group that best represents the overall document meaning.
  • Addressing Positional Bias: By incorporating positional encodings and using a summary-level approach, CCSUM is shown to be less susceptible to positional bias, which is a common issue in datasets like CNN/Daily Mail.
  • Graph Construction Matters: The paper highlights the importance of carefully constructing the sentence relation graph, particularly through the use of a similarity threshold to filter out noisy connections, which significantly impacts performance.

Key Results

  • CCSUM achieves state-of-the-art performance among unsupervised extractive summarization methods on both the CNN/Daily Mail and NYT datasets, as measured by ROUGE F1 scores.
  • The method's performance is comparable to some supervised methods trained on much larger datasets, demonstrating its effectiveness in capturing salient information.
  • Human evaluation using a question-answering paradigm shows that CCSUM summaries retain key information effectively, outperforming baselines like LEAD-3 and achieving scores close to the Oracle system.
  • Analysis of hyperparameter sensitivity reveals that the similarity threshold (θ) for graph construction has a significant impact on performance, indicating the importance of filtering noisy sentence relationships.

Limitations and Future Work

  • Positional Bias in Datasets: While CCSUM is less affected by positional bias than some baselines, the paper acknowledges that datasets like CNN/Daily Mail are inherently biased, which can still influence results.
  • Hyperparameter Tuning: The performance is sensitive to hyperparameters like the similarity threshold (θ) and the subgraph centrality weighting factor (β), requiring careful tuning.
  • Future Work: The authors suggest extending CCSUM to multi-document summarization and supervised settings using graph neural networks. They also plan to explore further improvements in graph construction and representation learning.

Summary updated

Abstract

Unsupervised document summarization has re-acquired lots of attention in recent years thanks to its simplicity and data independence. In this paper, we propose a graph-based unsupervised approach for extractive document summarization. Instead of ranking sentences by salience and extracting sentences one by one, our approach works at a summary-level by utilizing graph centrality and centroid. We first extract summary candidates as subgraphs based on centrality from the sentence graph and then select from the summary candidates by matching to the centroid. We perform extensive experiments on two bench-marked summarization datasets, and the results demonstrate the effectiveness of our model compared to state-of-the-art baselines.
BibTeX
@misc{zhang2021centrality,
  author = {Haopeng Zhang and Jiawei Zhang},
  title = {{Centrality Meets Centroid: A Graph-based Approach for Unsupervised Document Summarization}},
  year = {2021},
  eprint = {2103.15327},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2103.15327},
}
Figure