Sketch the Storyline with CHARCOAL: A Non-Parametric Approach

Siliang Tang, Fei Wu, Si Li, Weiming Lu, Zhongfei Zhang, Yueting Zhuang

Abstract

CHARCOAL is a novel hierarchical non-parametric Bayesian model designed to address the challenges of clustering news articles into coherent stories and broader topics while simultaneously extracting temporal storylines. Traditional models often require pre-specified cluster counts and struggle to capture narrative flow. CHARCOAL introduces the hybrid distance-dependent Chinese Restaurant Process (hddCRP), which adaptively learns the number of stories and topics from data. By leveraging named entities as narrative anchors and joint modeling of stories and topics, CHARCOAL achieves significant improvements in clustering accuracy and qualitative interpretability over state-of-the-art baselines.

Introduction

In the modern news landscape, a single event can trigger a cascade of articles that evolve over time. While traditional topic models excel at grouping related content, they often fail to capture the underlying narrative—the "storyline"—that connects these events. Furthermore, most existing approaches treat article clustering and storyline extraction as disjoint tasks and require manual tuning of the number of topics, which is impractical for dynamic news streams.

This paper introduces CHARCOAL (HierARChical tOpic model for news Article cLustering), a unified framework that reveals the hidden "skeleton" of news evolution. By organizing articles into stories and stories into topics within a single probabilistic model, CHARCOAL provides a more logical and automated way to navigate complex news archives.

Methods

The core of CHARCOAL is the hybrid distance-dependent Chinese Restaurant Process (hddCRP). This prior extends the standard distance-dependent CRP (ddCRP) to a hierarchical setting. In a ddCRP, data points (customers) are linked to other points based on similarity and temporal proximity. CHARCOAL "stacks" these processes across three levels:

  1. Article Level: Individual articles are linked to previous related articles to form a storyline. The distance measure incorporates shared entities (people, locations) and a temporal decay function, reflecting the reality that news articles typically reference recent, specific events.
  2. Story Level: Articles that do not link to a predecessor (self-links) initiate new stories. These stories are then clustered based on content similarity using Jensen-Shannon Divergence.
  3. Topic Level: Groups of similar stories are aggregated into broader topics.
Graphical representation of the CHARCOAL model architecture.

The model employs Collapsed Gibbs Sampling for inference, allowing it to iteratively refine links and cluster assignments. This non-parametric approach allows the model to discover the appropriate number of stories and topics automatically, providing flexibility across different dataset scales.

Key Insights

A critical innovation in CHARCOAL is the use of Named Entity Recognition (NER). While bag-of-words representations can be volatile as a story evolves, entities like specific individuals or locations act as "narrative glue," providing stable links across time. Additionally, the paper demonstrates that joint modeling—clustering stories and topics simultaneously—yields superior results compared to two-stage pipelines. This synergy allows the topic-level structure to inform story-level clustering and vice versa.

Results

The authors evaluated CHARCOAL on several large-scale datasets from the New York Times, including categories like International News, Sports, and Business. Quantitative evaluation focused on three primary metrics: Purity, Normalized Mutual Information (NMI), and Rand Index.

Comparison of CHARCOAL against baseline methods across NMI, Purity, and R-Index metrics.

As shown in the performance analysis, CHARCOAL consistently outperforms baseline methods such as Hierarchical Dirichlet Process (HDP) and hierarchical Latent Dirichlet Allocation (hLDA). For instance, on the SPORTS dataset, CHARCOAL achieved a Purity of 0.8934, significantly higher than HDP (0.7256). Qualitatively, the model successfully disentangled parallel narrative threads within complex events, such as separating the "search" and "investigation" phases of the MH370 disappearance, while correctly grouping them under a single topic.

Conclusion

CHARCOAL offers a robust, non-parametric solution for organizing news archives into meaningful hierarchies and storylines. While the model's complexity is mitigated by temporal decay, future work could focus on further scaling the approach for multi-year archives. Additionally, the heavy reliance on NER suggests that improvements in entity disambiguation could further enhance storyline coherence. Despite these challenges, CHARCOAL represents a significant step toward automated, narrative-aware news analysis.

Summary updated

Abstract

Generating a coherent synopsis and revealing the development threads for news stories from the increasing amounts of news content remains a formidable challenge. In this paper, we proposed a hddCRP (hybird distant-dependent Chinese Restaurant Process) based HierARChical tOpic model for news Article cLustering, abbreviated as CHARCOAL. Given a bunch of news articles, the outcome of CHARCOAL is threefold: 1) it aggregates relevant new articles into clusters (i.e., stories); 2) it disentangles the chain links (i.e., storyline) between articles in their describing story; 3) it discerns the topics that each story is assigned (e.g., Malaysia Airlines Flight 370 story belongs to the aircraft accident topic and U.S presidential election stories belong to the politics topic). CHARCOAL completes this task by utilizing a hddCRP as prior, and the entities (e.g., names of persons, organizations, or locations) that appear in news articles as clues. Moveover, the adaptation of non-parametric nature in CHARCOAL makes our model can adaptively learn the appropriate number of stories and topics from news corpus. The experimental analysis and results demonstrate both interpretability and superiority of the proposed approach.
BibTeX
@inproceedings{tang2015sketch,
  author = {Siliang Tang and Fei Wu and Si Li and Weiming Lu and Zhongfei Zhang and Yueting Zhuang},
  title = {{Sketch the Storyline with CHARCOAL: A Non-Parametric Approach}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure