READING:

from EDBT/ICDT 2014

SPEAKER: KAZUHIRO INABA

WHAT THE PAPER IS ABOUT?
• Influence Maximization• ソーシャルグラフ上を口コミで情報が伝搬していく。できるだけ大勢に情報を広める発信源 “seed set” を求めたい• Topic-aware• 情報の伝わる確率が話題ごとに異なる• Online• 次々と違う話題の情報が飛んでくるので、その都度、よい seed set を、あらかじめ用意しておいた前計算を使って一瞬で求める

INDEPENDENTCASCADE (IC) MODEL[Kempe, Kleinberg, and Tardos; KDD 2003]

有向辺 u  v それぞれに確率 pu,v が割り当てられている
0.8

0.9

0.8

0.5
0.1

0.9

0.8
0.5

0.5
0.1

0.9

0.1

u が情報を最初に知った直後のターン（１回だけ）に隣接する v に確率 pu,v で情報が伝わる

TOPIC-AWARE IC (TIC) MODEL• Z 個の Topic がある。
• 伝わる情報 (論文中では Item) はZ次元ベクトル
γ = (γ1, γ2, ..., γZ)
where 0≦γk ≦1, Σγk = 1• 各辺にZ個の確率 (p1u,v , ..., pZu,v) を割当て確率

Σ γk pku,v で情報が伝わる

SOME NOTES ON

TOPIC-AWARE IC (TIC) MODEL• Item を1つに固定すると IC-model に一致• 実験では Z = 10. 映画レビューSNSで実験• 例: Topic = {1:ホラー, 2:恋愛, 3:SF}• γ = (0.0, 0.8, 0.2) (少しSF色のあるロマンス)• pu,v = (0.9, 0.0, 0.4)
(vさんはuさんの恋愛映画を見る目を全く信用していない)確率Σ γk pku,v で情報が伝わる

PROBLEM
前もって１つ与えられる入力: グラフ (V, E, p)
Graph

あらかじめindex を構築しておくことで実験では |V|～30k, |E|～400k

seed set for γ1

γ1γ2

index

γ3
リアルタイムに与えられる Item γ に対し影響力の大きい seed set を即座に返したい

seed set for γ2
seed set for γ3
実験では |seed|≦50

PROBLEM?
• 「Item を1つに固定すると IC-model に一致」
 Topic のことを忘れて、毎回 IC-model での影響最大化の既存アルゴリズムを実行すれば良いのでは？
 遅い。論文での比較対象は CELF++[Goyal et al. WWW’11] で、数日かかる
 [Ohsaka et al. AAAI’14][Tang et al. SIGMOD’14] などと比べるとどうでしょうかOVERVIEW OF THE APPROACH
確率のついたグラフ (V, E, p) が与えられる
1. h 個の Item を代表点として選ぶ(実験では h = 1000)

2. 各代表点について、あらかじめ seed list を既存の IC-model 用オフラインアルゴリズムで計算しておく (実験では CELF++)
クエリ γ が与えられる
3. γ に近い代表点をいくつか (10個) 取り出す
4. それぞれの代表点でのSeed Listを巧く混ぜる1. INDEX POINTS

元のデータセットに含まれている Item
(レビューされた映画)から学習した
Dirichlet分布でItemを大量にランダム生成したものを
KL-divergence で
K-means++ で
h 個にクラスタリング

2. PRECOMPUTE
Index Point H = {γ1, ..., γh} のそれぞれについて、
IC model での既存手法で L (= 50) ノードの seedlist を計算
τ1=[v1,1, v1,2, ..., v1,L]・・・

Σ γ1kpk(p1, ..., pZ)(CELF++ を使用。
実験に使った述べ時間: 平均60時間 × h)

τ2=[vh,1, vh,2, ..., vh,L]
Σ γhkpkOVERVIEW OF THE APPROACH
確率のついたグラフ (V, E, p) が与えられる
1. h 個の Item を代表点として選ぶ(実験では h = 1000)

2. 各代表点について、あらかじめ seed list を既存の IC-model 用オフラインアルゴリズムで計算しておく (実験では CELF++)
クエリ γ が与えられる
3. γ に近い代表点をいくつか (10個) 取り出す
4. それぞれの代表点でのSeed Listを巧く混ぜる3. SEARCH IN INDEX• 新しくアイテム γ が与えられたときに、Index Point 集合 H から γ に近い点をいくつか取り出すγγ

3. SEARCH IN INDEX: HOW
Index集合を、KL-divergenceで定義されたballで繰り返し分割して、tree状に保持(“Bregman ball tree”)

3. SEARCH IN INDEX: HEURISTICS(How to search 10 neighbors from the tree index?)• Approximate K-NN:• leafを5個訪れたら探索打ち切り• Anderson-Darling test:• 含まれているIndex Pointに対しクエリ γ を統計的に検定し、妥当ならそこで探索打ち切り• Selection:• Rankを混ぜるときにKL-divergenceを正規化した重み付きで混ぜるので、重み0.5%• INFLEX (提案手法): 3つすべて

3. SEARCH IN INDEX: HEURISTICS(How to search 10 neighbors from the tree index?)
Seed list の質 (0 = CELF++と一致)

計算時間

4. RANK AGGREGATION• h個の Index point から得られたノードのランキング (0≦w≦1 の重み付き) を混ぜる
• (w1, [v1,1, v1,2, ..., v1,L ])• ...
• (wh, [vh,1, vh,2, ..., vh,L ])4. RANK AGGREGATION
Weighted Copeland score

Copelandw(v) = Σv’ Σj {wj | τj (v) < τj (v’)}
where τj(v) := Index Point j の seed list での v の順位の高い順に並べる

EXPERIMENTAL SETTINGS• Flixster (映画レビューSNS) dataset• 30k users, 425k social links, 12k movies• “User u rated Item m on Time t” 形式のログ• 著者らが ICDM’12 で提案した手法で、Topic数 Z (= 10) を決め打って 各link の p と各movieの γ を推測したデータを用いる。

FINALRESULT