Abstract: We propose a novel probabilistic technique for modeling and extracting salient structure from large document collections. As in clustering and topic modeling, our goal is to provide an organizing perspective into otherwise overwhelming amounts of information. We are particularly interested in revealing and exploiting relationships between documents. To this end, we focus on extracting diverse sets of threads—singly-linked, coherent chains of important documents. To illustrate, we extract research threads from citation graphs and construct timelines from news articles. Our method is highly scalable, running on a corpus of over 30 million words in about four minutes, more than 75 times faster than a dynamic topic model. Finally, the results from our model more closely resemble human news summaries according to several metrics and are also preferred by human judges.
The Challenge of Document Threading
As digital document collections scale to millions of items, traditional organization methods like clustering or topic modeling often reach their limits. While clustering groups similar items, it frequently ignores the "narrative arc" or chronological progression between them. Similarly, topic models like Latent Dirichlet Allocation (LDA) identify broad themes but struggle to help a user follow a specific story or a specific line of research through time.
This research introduces a scalable probabilistic framework for document threading: the process of finding a small set of paths through a graph of documents where edges represent citations or chronological similarity. The objective is to extract threads that satisfy three primary criteria:
- Salience: They must contain the most important or representative documents.
- Coherence: Each thread must follow a logical, smooth progression of ideas.
- Diversity: The final set of threads should cover different aspects of the collection without redundant overlap.
Methodology: Structured Determinantal Point Processes
The core of this approach is the Structured Determinantal Point Process (SDPP). Determinantal Point Processes (DPPs) are elegant probabilistic models that naturally favor diversity. In a standard DPP, the probability of selecting a subset of items is proportional to the geometric volume spanned by their feature vectors. If two items are highly similar, their vectors are nearly parallel, the volume they span is small, and the model is statistically less likely to select both.
While standard DPPs select individual items, SDPPs allow for the selection of complex structures—in this case, paths (threads) through a graph. The model defines the "quality" of a thread based on the importance of its constituent documents and the strength of the links between them. By treating the diversity of a set of stories as a geometric volume, the model performs global optimization, choosing the best set of threads simultaneously rather than picking them one by one in a greedy fashion.
Scalability via Random Projections
SDPP inference is typically computationally expensive when feature dimensions ($D$) are high, such as in text processing where the vocabulary can reach tens of thousands of words. To overcome this, the authors utilize random projections (based on the Johnson-Lindenstrauss lemma) to compress high-dimensional vectors into a much smaller space (e.g., $d \approx 50$). This compression preserves the "volume" relationships essential for the DPP, making the model practical for massive datasets without sacrificing theoretical guarantees.
Experimental Evaluation
The model was evaluated on two distinct types of structured data: the Cora Citation Graph (~28,000 computer science papers) and the New York Times English Gigaword corpus (over 200,000 news articles). In the news domain, the model's output was compared against human-curated summaries from Agence France-Presse.
Key Results
- Efficiency: The $k$-SDPP model processed a corpus of 30 million words in approximately four minutes. This represents a 75x speedup over traditional Dynamic Topic Models (DTMs).
- Human Preference: In Mechanical Turk evaluations, human judges rated the $k$-SDPP threads as significantly more coherent than those produced by $k$-means or DTMs.
- The "Interloper" Test: When random "distractor" articles were inserted into timelines, participants were much more successful at identifying the fakes in $k$-SDPP threads, suggesting a superior natural "flow."
- Summarization Quality: The model outperformed baselines on ROUGE scores, indicating that the automated threads closely mirrored the content and structure of human-written news summaries.
Discussion and Future Work
The authors distinguish between "topic-oriented" and "story-oriented" modeling. While DTMs are effective for observing how a broad topic (like "politics") evolves, they often fail to capture a specific story (like "the 2005 Papal transition"). The threading approach is explicitly designed for the latter.
Despite its success, the current model is limited to extracting linear chains. Real-world information often follows more complex structures, such as branching trees or intersecting "metro maps." Future work may involve extending the SDPP framework to handle these non-linear structures and exploring methods to handle variable thread lengths more dynamically.
Summary updated