Unsupervised Story Discovery from Continuous News Streams via Scalable Thematic Embedding

Susik Yoon, Dongha Lee, Yunyi Zhang, Jiawei Han

Abstract

Massive news streams present a significant challenge for information retrieval: tracking evolving "stories"—sequences of related articles about specific events—without human supervision. While Large Language Models (LLMs) provide powerful text representations, standard embedding techniques often fail to distinguish between distinct but superficially similar events due to the inclusion of non-indicative content. This paper presents USTORY, a scalable framework that introduces "thematic embedding" to discover news stories in real-time. By dynamically weighting sentence embeddings based on temporal themes and utilizing a pane-based clustering approach, USTORY outperforms existing baselines by up to 51.7% while maintaining linear scalability.

Introduction

In the modern digital landscape, news is a firehose of information. For researchers, journalists, and the public, tracking how a single event evolves into a multi-day story is nearly impossible without automated assistance. The core challenge of online story discovery lies in the "text-rich and evolving" nature of news. Traditional keyword-based methods lack semantic depth, while modern LLM-based approaches often suffer from "noisy" embeddings.

Researchers from UIUC and Yonsei University addressed these limitations in their SIGIR '23 paper by introducing USTORY. Unlike previous methods that treat every sentence in an article with equal importance, USTORY identifies and prioritizes the sentences that are most relevant to the current temporal theme of a story.

The Challenge of Noisy News Streams

When news articles are embedded using standard Pretrained Sentence Encoders (PSEs), the resulting vectors are often "indiscriminative." This is because news articles contain a mix of highly specific, story-indicative information and generic, non-indicative filler.

An article about 2023 California Floods illustrating the mix of story-indicative (thematic) and generic (indiscriminative) sentences.

As shown in Figure 1, an article about the 2023 California floods might contain critical sentences about "atmospheric rivers" alongside generic instructions like "Please be out of the area." If a system averages these sentences equally, the specific signal of the flood event is diluted by the noise of the generic sentences. This makes it difficult for clustering algorithms to separate the flood story from other unrelated weather events or general safety reports.

The USTORY Framework

USTORY solves the noise and scalability problems through three primary innovations:

1. Thematic Embedding

Instead of a static representation, USTORY represents articles dynamically. The system first identifies "thematic keywords" using a time-decayed version of TF-IDF. This allows the model to capture what is currently trending and unique to the news cycle. It then uses a PSE to embed sentences but weights them based on their "theme relevance." This ensures that story-indicative sentences contribute significantly more to the final article vector than generic ones.

2. Novelty-Aware Adaptive Clustering

To handle the continuous stream, USTORY employs a confidence-based assignment mechanism. When a new article arrives, the system calculates its fit into existing stories based on two factors: semantic similarity (via embeddings) and symbolic similarity (via keyword distributions). If an article’s similarity to all existing stories falls below a certain threshold, it is identified as a "novel" event and used to seed a new potential story.

3. Pane-based Story Summary (PSS)

To maintain real-time performance, USTORY avoids keeping every historical article in active memory. Instead, it uses "panes"—time-sliced summaries that store aggregate statistics such as term frequencies and the sum of embeddings. This PSS architecture allows the system to update story representations in a single pass, ensuring that the system scales linearly with the volume of the news stream.

Evaluation and Key Insights

The authors evaluated USTORY on four real-world datasets, including Newsfeed and the Wikipedia Current Event Portal (WCEP). The results demonstrated that sentences are the "Goldilocks" unit for news analysis: words lack context, while whole articles often exceed LLM token limits and contain too much noise.

Comparison of thematic vs. indiscriminative embeddings, showing tighter clustering and better separation of distinct stories.

The effectiveness of the thematic approach is visualized in Figure 2. By filtering for story-relevant sentences, the thematic embedding creates much tighter, more distinct clusters in the embedding space. In contrast, the indiscriminative approach (averaging) results in overlapping clusters that lead to errors in story discovery. Quantitatively, USTORY-SenRB (using Sentence-BERT) achieved a $B^3$-F1 score of approximately 0.81 on the WCEP datasets, a significant improvement over the 0.70 achieved by traditional baselines.

Conclusion

USTORY represents a significant step forward in automated news monitoring. By combining deep semantic embeddings with traditional symbolic keyword analysis and a scalable pane-based architecture, it provides a robust solution for tracking complex, evolving stories in real-time. Future work may explore weakly supervised settings, incorporating external knowledge bases to further refine the identification of niche temporal themes.

Summary updated

Abstract

Unsupervised discovery of stories with correlated news articles in real-time helps people digest massive news streams without expensive human annotations. A common approach of the existing studies for unsupervised online story discovery is to represent news articles with symbolic- or graph-based embedding and incrementally cluster them into stories. Recent large language models are expected to improve the embedding further, but a straightforward adoption of the models by indiscriminately encoding all information in articles is ineffective to deal with text-rich and evolving news streams. In this work, we propose a novel thematic embedding with an off-the-shelf pretrained sentence encoder to dynamically represent articles and stories by considering their shared temporal themes. To realize the idea for unsupervised online story discovery, a scalable framework USTORY is introduced with two main techniques, theme- and time-aware dynamic embedding and novelty-aware adaptive clustering, fueled by lightweight story summaries. A thorough evaluation with real news data sets demonstrates that USTORY achieves higher story discovery performances than baselines while being robust and scalable to various streaming settings.
BibTeX
@inproceedings{yoon2023unsupervised,
  author = {Susik Yoon and Dongha Lee and Yunyi Zhang and Jiawei Han},
  title = {{Unsupervised Story Discovery from Continuous News Streams via Scalable Thematic Embedding}},
  booktitle = {International ACM SIGIR Conference on Research and Development in Information Retrieval},
  year = {2023},
}
Figure