Real-Time Top-R Topic Detection on
Twitter with Topic Hijack Filtering
Kohei Hayashi (NII & ERATO)
August 3, 2015
Joint work with• Takanori Maehara (Shizuoka Univ)• Masashi Toyoda (Univ Tokyo)• Ken-ichi Kawarabayashi (NII & ERATO)
1 / 25

Twitter

SNS with short messages (tweets)
Big data 41M users, 1.4B interactions
Diversity Covering any topics: news, politics, TV, ...
Rapid 1 tweet ≤ 140 chars⇒ Low latency
2 / 25

Automatic Trend Detection on Twitter3 / 25

Automatic Trend Detection on Twitter

A promising data resource for topic detection• Find word clusters by word co-occurrence• May discover breaking news and events even fasterthan news media
3 / 25

Two Challenges• Topic Detection in Real-time• Noise Filtering

4 / 25

Topic Detection in Real-time

An ultimate goal of topic detection on Twitter• Have to deal with 0.27M tweets/min• Words rarely co-occur⇒ Severely degrade the quality of topics
5 / 25

Noise Filtering
Many spam tweets generated by not human• e.g. “tweet buttons”

Exaggerate co-occurrence and “hijack” important topics
6 / 25

Contributions
A streaming topic detection algorithm based on
non-negative matrix factorization (NMF)
1. Highly scalable:
Able to deal with a 20M×1M sparse matrix/sec
2. Automatic topic hijacking detection & elimination

7 / 25

Contributions
A streaming topic detection algorithm based on
non-negative matrix factorization (NMF)
1. Highly scalable:
Able to deal with a 20M×1M sparse matrix/sec
2. Automatic topic hijacking detection & elimination.
TechnicalPoints.
1. Reformulate NMF in a stochastic manner• Stochastic gradient descent (SGD) updates withO(NNZ) time2.

.

Use of statistical testing• Assume normal topics follow power law
7 / 25

Streaming NMF

8 / 25

Topic Detection by NMF
Consider to obtain R topics from all past tweets
TweetsUser-word
co-occurrence
userword

9 / 25

Topic Detection by NMF
Consider to obtain R topics from all past tweets
TweetsUser-word
co-occurrence
userword

9 / 25

Topic Detection by NMF
Consider to obtain R topics from all past tweets
Frequency
table

User-word
co-occurrence
userTopics

word

word

0userTweets

09 / 25

.
Problem.
min
I×RU∈R+,V∈RJ×R+fλ (X; U, V),1λfλ (X; U, V) = kX − UV> k2F + (kUk2F + kVk2F )22.
.
BatchAlgorithm.
Repeat until convergence:
1. U ← [U − η∇U fλ (X; U, V)]+. 2. V ← [V − η∇V fλ (X; U, V)]+
Guaranteed converging to stationary points
10 / 25

Stochastic Formulation• Now we observe X(t) for each time t(t)• Keep track to X̄

= 1t

∑t(s)
s=1 X(t)• Eﬃcient updates from X̄

(t+1)

to X̄

?

11 / 25Stochastic Formulation• Now we observe X(t) for each time t(t)• Keep track to X̄

= 1t

∑t(s)
s=1 X(t)• Eﬃcient updates from X̄

(t+1)

to X̄

?

Key idea: decompose fλ for each t.
1∑(t)kX̄ − UV> k2F =kX(s) − UV> k2F + const.
t s.
11 / 25

Stochastic Formulation• Now we observe X(t) for each time t(t)• Keep track to X̄

= 1t

∑t(s)
s=1 X(t)• Eﬃcient updates from X̄

(t+1)

to X̄

?

Key idea: decompose fλ for each t.
1∑(t)kX̄ − UV> k2F =kX(s) − UV> k2F + const.
t s
If X(t) is i.i.d. random variable,(t)> 2(t)> 2(t). kE[X ] − UV kF = EkX − UV kF + var[X ]Now we can use stochastic optimization
11 / 25.
Streaming
Algorithm.
For t = 1, . . . , T :1. AU ← ∇U ∇U fλ ,AV ← ∇V ∇V fλ (metrics)
(t)
(t−1)
2. U
← [U− ηt ∇U fλ (X(t) ; U, V(t−1) )A−1
U ]+(t)(t−1)− ηt ∇V fλ (X(t) ; U(t) , V)A−1
V ]+. 3. V ← [VGuaranteed converging to the stationary points of(t)fλ (X̄ ; U, V) for some ηn and i.i.d. {X(t) }12 / 25

Comparing with the Batch NMF ...
Much faster(t)• Update cost: depends on NNZ(X(t) )  NNZ(X̄ )Memory eﬃcient• Able to discard X(1) , . . . , X(t−1)

13 / 25

Comparing with the Batch NMF ...
Much faster(t)• Update cost: depends on NNZ(X(t) )  NNZ(X̄ )Memory eﬃcient• Able to discard X(1) , . . . , X(t−1)
Smoothing eﬀect
U(t) = [(1 − ηt )U(t−1) + ηt X(t) V(t−1) A−1U ]+= [(1 − ηt )U(t−1) + ηt argmin fλ (X(t) ; U, V(t−1) )]+U• A weighted average ofthe prev solution and the NMF solution of X(t)• Mitigates the sparsity of X(t)13 / 25

Topic Hijacking Detection

14 / 25

Problem Setting
Goal: Find hijacked topics
Idea: Check word distributions• The word dist of a hijacked topic should be diﬀerent
from the word dist of a normal topic

15 / 25

Problem Setting
Goal: Find hijacked topics
Idea: Check word distributions• The word dist of a hijacked topic should be diﬀerent
from the word dist of a normal topic• NMF estimates topic-speciﬁc word dists as V
Xij ∝ p(useri , wordj )∑∝p(topicr )p(useri |topicr )p(wordj |topicr )∝r∑

uir vjrr
15 / 25

Deﬁning Normal/Hijacked Topics
Normal topics:• Many users involve⇒ Mixing many diﬀerent vocabularies⇒ Heavy-tailed (Zipf’s law)

16 / 25

Deﬁning Normal/Hijacked Topics
Normal topics:• Many users involve⇒ Mixing many diﬀerent vocabularies⇒ Heavy-tailed (Zipf’s law).
Deﬁnition:
A Normal Topic.
Topic r is normal ifp(rank(word) | topicr )= power(α).
16 / 25

Deﬁning Normal/Hijacked Topics (Cont’d)Hijacked topics:• Few users involve⇒ The same vocabulary is repeatedly used
⇒ Uniform probs & (almost) no tail17 / 25

Deﬁning Normal/Hijacked Topics (Cont’d)Hijacked topics:• Few users involve⇒ The same vocabulary is repeatedly used⇒ Uniform probs & (almost) no tail.
Deﬁnition:A Hijacked Topic.
Topic r is hijacked ifp(rank(word) | topicr )= step(rankmin ).
17 / 25

Log-likelihood Ratio Test
L(rankmin ) =∑jlog

step(rankj | rankmin )power(rankj | α̂).

Theorem (Asymptotic normality [Vuong’89]).
√Let N be # of observed words. Then, L(rankmin )/ N converges in
distribution to N (0, σ 2 ) where)2 ()2N (1 ∑step(rankj | rankmin )12σ =log−L(rankmin ) .
N j=1power(rankj | α̂)N.

18 / 25

Log-likelihood Ratio Test
L(rankmin ) =∑jlogstep(rankj | rankmin )power(rankj | α̂).

Theorem (Asymptotic normality [Vuong’89]).
√Let N be # of observed words. Then, L(rankmin )/ N converges indistribution to N (0, σ 2 ) where)2 ()2N (1 ∑step(rankj | rankmin )
12
σ =
log
−L(rankmin ) .
N j=1power(rankj | α̂)N.
For r = 1, . . . , R:
• Estimate α̂ = argmaxα log power(rank(uk ) | α)
• For rankmin = 1, . . . , 140:
• Compute L(rankmin )• Topic r is hijacked if p-val < 0.05

18 / 25

Experiments

19 / 25

DataJapanese Twitter stream• April 15–16, 2013••••

417K users
1.98M words
15.3M tweets
69.4M co-occurrences• Generated X(t) for each 10K co-occurrences

20 / 25

Runtime
NMF
Batch
OnlineDynamicStreaming
w/ Filter[Cao+ 07]
[Saha+ 12][proposed][proposed]

1%
10%
27.0m
1.9h
5.6h
9.2h
16.7h >24h
4.0m 21.7m
5.3m 24.1m

100%
16.4h
17.8h
>24h
3.6h
3.8h

21 / 25

RuntimeNMF
Batch
OnlineDynamicStreaming
w/ Filter.

[Cao+ 07]
[Saha+ 12][proposed][proposed]

1%
10%
27.0m
1.9h
5.6h
9.2h
16.7h >24h
4.0m 21.7m
5.3m 24.1m

100%
16.4h
17.8h
>24h
3.6h
3.8h

4 Streaming NMF: ×5–250 faster!
• 67K tweets/m⇒ The real-time speed of all jp tweets!

. 4 Filtering cost is ignorable
21 / 25

Perplexity• Similarity between a topic dist and a target dist
• Used Y! headlines1 for the target term dist
• Lower is better
NMFBatch
OnlineDynamicStreaming
w/ Filter

1[Cao+ 07]
[Saha+ 12][proposed][proposed]

1%
9.01E+09
1.06E+04
6.53E+04
5.65E+07
5.25E+09

10%
6.32E+06
3.25E+04
N/A
3.25E+04
2.40E+04

100%
4.51E+04
1.83E+04
N/A
8.71E+03
7.90E+03

http://news.yahoo.co.jp/list
22 / 25

Perplexity• Similarity between a topic dist and a target dist
• Used Y! headlines1 for the target term dist
• Lower is better
NMFBatch
OnlineDynamicStreaming
w/ Filter[Cao+ 07]
[Saha+ 12][proposed][proposed]

1%
9.01E+09
1.06E+04
6.53E+04
5.65E+07
5.25E+09

10%100%
6.32E+06 4.51E+04
3.25E+04 1.83E+04
N/A
N/A
3.25E+04 8.71E+03
2.40E+04 7.90E+03.

4 Streaming NMF: best at 100% data
. 4 Topic hijacking ﬁlter improves perplexity
1

http://news.yahoo.co.jp/list
22 / 25ᐇ㝿䛻ྲྀ䜜䛯䝖䝢䝑䜽䠄2013/4/15䠅
ObtainedTopics䝪䝇䝖䞁䝬䝷䝋䞁⇿◚஦௳䛾䝖䝢䝑䜽䜢☜ㄆ23 / 25

DetectedHijacking Phrasesྲྀ䜚㝖䛛䜜䛯୙ṇ䝖䝢䝑䜽䛾౛••••ᗈ࿌⣔䝅䝛䝬䝖䜳䝕䜲 ዿ⢭ 䝖䝮 ᫎ⏬ 䝝䝸䜴䝑䝗 ᡓ㜚 䜽䝹䞊䝈 ୺₇Ⓨ኎ 2013 ᝟ሗ 㛤ദ ཧຍ ၟရ ධⲴ㝈ᐃ ᝟ሗ 㛤ദ 䜲䝧䞁䝖 ዲホ ၟရ @******䝸䝥䝷䜲 ᐩኈᒣ ᵽཱྀ 䝣䜵䝇䝔䜱䝞䝹 ⯆࿡ ᪩✄⏣ 㛤ദ ⌧ᅾ ୙ၥ ເ㞟 䝇䝍䝑䝣 ኱• 䝸䝣䜷䝻䞊 䜰䜹䜴䞁䝖 19836 䝣䜷䝻䝽䞊 Only ᕼᮃ ᨭ᥼ 696382 ஺ὶ ┦┦஫ᣑᩓ⣔• ↓ᩱ ᪥ᮏ ᣑᩓ ᕼᮃ 2013/04 䝸䝥• 䈡⽜ 䅫㕁 㟤斀 㑵䷎ ⮬㐫 塭䓚 㔜⁁ 姽Ὁ 㨇≽• ᡤ᭷ City 䝫䜲䞁䝖 ๓ᅇ Tweet 䜰䜽䝉䝇 ⋓ᚓ Intel• ⮬ື 䛰䜜 ᐉఏ AutoTweet 䜸䞊䝖䝒䜲䞊䝖 Twitter ᐃᮇ タᐃ 䝃䜲䝖䝪䝑䝖⣔• 䛸䝜 ʘ䞉 ‫ ؓث ث؟ اؓ أا ثا ؓأ ؟ؓ أ؟‬൞ൣ• ‫ؓ ثؑا‬䛕 ؑ‫ أؑ ػ‬Å䞉 ؓ䛙 䖃൘‫ك‬Ө ؓ䜗 䚹) ‫ ؑ؟‬䚹䞉• *䞉 䜨
䞉* :.䚹..䚹.: *䞉' *䜨'䞉 :.䚹. .䚹.:㢦ᩥᏐ⣔24 / 25

Summary
Proposed the streaming algorithm for Twitter topic
detection• Works in real time(would handle all jp tweets in theory)• Automatically ﬁlters spam topics

25 / 25

Summary
Proposed the streaming algorithm for Twitter topic
detection• Works in real time(would handle all jp tweets in theory)• Automatically ﬁlters spam topics

Thank you!
25 / 25

Integrated Twitter Topic Detection System

For t = 1, . . . , T :(t)1. Generate X
from tweets ∈/ BlacklistO(Nt )2. Update U, V by SGD
O(Nt R2 + R3 )3. With some intervals,
Detect Topic Hijacking and update Blacklist O(J)26 / 25