Jure kdd09

Citation

Jure Leskovec, Lars Backstrom, Jon M. Kleinberg: Meme-tracking and the dynamics of the news cycle. KDD 2009: 497-506.

Online version

[1]

Summary

This is a highly cited KDD paper presenting an unsupervised approach to Temporal information extraction. Specifically it introduces a framework for tracking topic shifts, e.g. news and events, over short time scales.

The key idea is to track news by short, distinctive phrase, which acts as the analogue of "genetic signatures" for different topics. It also produces quantitative analysis of the news cycle on their large-scale and relatively representative news data set.

Method

Some words alternation in a phrase during the quotes called (textual mutation) could inhibit the accurate tracking. To solve this problem, the authors propose a robust method to cluster textual variants of quotes consisting of two stages namely phrase graph construction and clustering.

Pre-processing

First of all, pre-processing is conducted to eliminate the noisy phrases within the data set including:

1. remove the phrases whose word-length is less than 4.

2. remove the phrases whose term-frequency is less than 10.

3. eliminate the phrases whose domain-frequency is at least 25% (avoid spammers).

Graph construction

Each node $p$ in the phrase graph $G$ represents a phrase extracted from the corpus. An edge $(p,q)$ is included for every pair of phrases p and q, which always points from shorter phrases to longer phrases. Two phrases are connected either the edit-distance (treating a word as a token) is smaller than 1 or there is at least a 10-word consecutive overlap between them. In other words, the edge implies the inclusion relation between the phrases and since the direction is strictly pointing to longer phrases the graph becomes a directed acyclic graph (DAG).

The authors fail to elaborate how the weight $w_{pq}$ on each edge is calculated. They only state that the weight is increased as the directed edit distance as well as the frequency of q grows.

Clustering

The goal of clustering is to retrieve all single rooted components so that all phrases in a component are closely related by deleting a set of edges of minimum total weight. The single rooted indicates a directed acyclic sub-graph if it contains exactly one root node (out-degree = 0). As other clustering problem, it proves to be a NP-hard problem. Therefore the authors propose three heuristic towards a feasible clustering solution. And the authors claim using the heuristic (although, in my opinion , the contribution of the heuristic is obscure) they found that keeping an edge to the shortest phrase yields 9% improvement over the baseline, 12% improvement keeping an edge to the most frequent phrases and 13% greedily assigning the node to the cluster with the most edges. The experimental result demonstrates that the volume distribution for both phrase (solid blue) and phrase cluster (dashed green) generated by their cluster method follows power law distribution.

Data set

90 million news and blog articles 390GB collected over the final three months of the 2008 U.S. Presidential Election (from August 1 to October 31 2008).

Experimental Result

Based on the 35,800 non-trivial clusters (at least two phrases), the author extracted 50 largest threads which can be regarded as the cluster of the cluster containing some phrases and the threads are depicted in the following famous figure.

From the above figure we can not only obtain a clue about the news cycle but also get an idea about the popular news in each period. In addition, the authors also conclude their findings by global analysis and local analysis.

Global Analysis

The authors compare the dynamics of news threads to the follicular development within an ecosystem and claims two ingredients affect the dynamics: imitation (different sources imitate one another) and recency (up-to-date news are always favored to old ones). Based on the idea, the author propose a generation model based on the famous preferential attachment model. At each discrete time step $t=1,2,3...$, a source chooses thread j with probability proportional to $f(n_{j})\delta (t-t_{j})$, where $f(\cdot )$ is a monotonically increasing function and $n_{j}$ denotes the #stories about thread j; $\delta (\cdot )$ is a monotonically decreasing function and $t_{j}$ is the first time j was proposed. Intuitively the attachment is governed by two factor preferential to "richer thread" (imitation) and the novelty of the thread (recency).

Related papers

The widely cited Pang et al EMNLP 2002 paper was influenced by this paper - but considers supervised learning techniques. The choice of movie reviews as the domain was suggested by the (relatively) poor performance of Turney's method on movies.

An interesting follow-up paper is Turney and Littman, TOIS 2003 which focuses on evaluation of the technique of using PMI for predicting the semantic orientation of words.