Blog summarization: CIKM 2007

Citation

Meishan Hu, Aixin Sun and Ee-Peng Lim, "Comments-oriented blog summarization by sentence extraction ", Proceedings of the sixteenth ACM conference on Conference on information and knowledge management, 2007

Online version

Download from NTU website

Summary

This paper aims at blog summarization by identifying important sentences of a blog by analyzing the comments made to it, and then extracting these sentences to present a summary of the blog. Authors use a Reader-Quotation-Topic model to give representativeness score to different words in user comments. Then, “significant” sentences from the blog are selected based on two methods: Density-based Selection and Summation-based selection. Authors employed humans to create summaries of the blogs to evaluate their method against. Please see the Blog Summarization CIKM 2007 dataset page for information about dataset. Below, is presented a closer look at Reader-Quotation-Topic model and the two sentence-selection methodologies along with the results of the experiments.

Reader-Quotation-Topic (ReQuT) model

Each word is given a Reader, a Quotation and a Topic measure. The motivation is that words written by “authoritative” readers, or the ones found in comments which are quoted in other comments, or those that relate to mostly discussed topics, are important than others. So ReQuT scores are given to each word, and the overall importance of that word is judged by a weighted sum of the ReQuT scores.

The Math behind this

Reader Measure

Given the full set of comments to a blog, the authors construct a directed reader graph $G_{R}:=(V_{R},E_{R})$. Each node $r_{a}\epsilon V_{R}$ is a reader, and an edge $e_{R}(r_{b},r_{a})\epsilon E_{R}$ exists if $r_{b}$ mentions $r_{a}$ in one of $r_{b}$’s comments. The weight on an edge, $W_{R}(r_{b},r_{a})$, is the ratio between the number of times $r_{b}$ mentions $r_{a}$ against all times $r_{b}$ mentions other readers (including $r_{a}$). The authors compute reader authority using a ranking algorithm, shown in Equation 1, where $|R|$ denotes the total number of readers of the blog, and d is the damping factor.

$A(r_{a})=d*1/|R|+(1-d)\Sigma W_{R}(r_{b},r_{a})*A(r_{b})............(1)$
$RM(w_{k})=\Sigma tf(w_{k},c_{i})*A(r_{a})...............................(2)$
The reader measure of a word $w_{k}$, denoted by $RM(w_{k})$, is given in Equation 2, where $tf(w_{k},c_{i})$ is the term frequency of word $w_{k}$ in comment $c_{i}$.

Quotation Measure

For the set of comments associated with each blog post, the authors construct a directed acyclic quotation graph $G_{Q}:=(V_{Q},E_{Q})$. Each node $c_{i}\epsilon V_{Q}$ is a comment, and an edge $(c_{j},c_{i})\epsilon E_{Q}$ indicates $c_{j}$ quoted sentences from $c_{i}$. The weight on an edge, $W_{Q}(c_{j},c_{i})$, is 1 over the number of comments that c_j ever quoted. The authors derive the quotation degree $D(c_{i})$ of a comment $c_{i}$ using Equation 3. A comment that is not quoted by any other comment receives a quotation degree of $1/|C|$ where $|C|$ is the number of comments associated with the given post. $D(c_{i})=1/|C|+\Sigma W_{Q}(c_{j},c_{i})*D(c_{j})...........(3)$
$Q_{M}(w_{k})=\Sigma tf(w_{k},c_{i})*D(c_{i})..................(4)$
The quotation measure of a word $w_{k}$, denoted by $QM(w_{k})$, is given in Equation 4. Word $w_{k}$ appears in comment $c_{i}$.

Topic Measure

Given the set of comments associated with each blog post, the authors group these comments into topic clusters using a Single-Pass Incremental Clustering algorithm presented in [1]. The authors conjecture that a hotly discussed topic has a large number of comments all close to the topic cluster centroid. Thus they propose Equation 5 to compute the importance of a topic cluster, where $|c_{i}|$ is the length of comment $c_{i}$ in number of words, $C$ is the set of comments, and $sim(c_{i},t_{u})$ is the cosine similarity between comment $c_{i}$ and the centroid of topic cluster $t_{u}$.

$T(t_{u})=1/\Sigma |c_{j}|*\Sigma |c_{i}|*sim(c_{i},t_{u})......................(5)$
$TM(w_{k})=\Sigma tf(w_{k},c_{i})*T(t_{u})......................................(6)$

Equation 6 defines the topic measure of a word $w_{k}$, denoted by $TM(w_{k})$. Comment $c_{i}$ is clustered into topic cluster $t_{u}$.

Overall Word Representativeness or Importance Score

The representativeness score of a word $Rep(w_{k})$ is the combination of reader-, quotation- and topic- measures in ReQuT model. The three measures are first normalized independently based on their corresponding maximum values and then combined linearly to derive $Rep(w_{k})$ using Equation 7. In this equation $\alpha$, $\beta$ and $\gamma$ are the coefficients (0 ≤ $\alpha$, $\beta$, $\gamma$ ≤ 1.0 and $\alpha$ + $\beta$ + $\gamma$ = 1.0).

$Rep(w_{k})=\alpha *RM(w_{k})+\beta *QM(w_{k})+\gamma *TM(w_{k}).......................(7)$

Sentence Selection Criteria

Density Based Selection: Based on representativeness score of keywords and the distance between two keywords in a sentence. In equation 8, K is the total number of keywords contained in i^th sentence $s_{i}$, $Score(w_{j})$ is the representativeness score of keyword $w_{j}$, and $distance(w_{j},w_{j}+1)$ is the number of non-keywords (including stopwords) between the two adjacent keywords $w_{j}$ and $w_{j}+1$ in $s_{i}$.

$Score(s_{i})=1/K*(K+1)*\Sigma Score(w_{j})*Score(w_{j+1})/distance(w_{j},w_{j+1})^{2}............................(8)$

Summation Based Selection: Based on the number of keywords contained in a sentence. In equation 9, $|s_{i}|$ is the length of sentence $s_{i}$ in number of words (including stopwords), and $tau$ ($tau$ > 0) is a parameter to flexibly control the contribution of a word’s representativeness score.

$Rep(s_{i})=1/|s_{i}|*(\Sigma Rep(w_{k})^{\tau })^{1/\tau }................................(9)$

Results

Two metrics were used: R-Precision and NDCG. NDCG is described in [2].

References

[1] D. Shen, Q. Yang, J.-T. Sun, and Z. Chen. Thread detection in dynamic text message streams. In Proc. of SIGIR ’06, pages 35–42, Seattle, Washington, 2006.
[2] K. Jrvelin and J. Keklinen. IR evaluation methods for retrieving highly relevant documents. In Proc. of SIGIR ’00, pages 41–48, Athens, Greece, 2000.