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:
- 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.
- 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.
- Topic Level: Groups of similar stories are aggregated into broader topics.
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.
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