読んだ：Learning Social Network Embeddings for Predicting Information Diffusion（WSDM2014）

情報拡散の分析・モデル化は既知のグラフや近接的な構造の上で扱われる。
しかし、複数のアクターとメディアの相互関係による潜在的な現象は複雑であり、
既存のモデルや限られた仮説だけでは説明できない。
我々は、この問題に対する新たなアプローチとして、連続的な空間上に
観測された時間的なダイナミクスをマッピングする。
拡散カスケードに関係するノードは潜在的に表現された空間に投影される。
これは、投影空間内ノードの近接性をカスケード内の感染時間の近接性に
反映した拡散カーネルを学習することになる。
提案手法はいくつかのこれまでにない特徴を持っていて、
・パラメータはカスケードサンプルから直接学習し、それまでの拡散構造には従わない
・等式が投影空間内に閉じた形で表されることから、離散的なモデルに比べて予測に対する推定が早い
本手法の拡散予測の精度並びに推定スピードが既存のものより優れていることを示す。

カスケードからユーザ間の情報拡散における距離感を潜在空間に写像してあげるイメージ。

●定義とモデリング

N人のユーザ集合U
Cカスケード集合
$C_l \subseteq C$ ...学習用のカスケード集合
$C_t \subseteq C$ ...テスト用のカスケード集合
$s^c$ ...カスケード $c \subseteq C$ の情報源
$S^c \subset U$ ...カスケードcに含まれるユーザ集合
$t^c(u_i)$ ...カスケード内でユーザがアクションを行った時刻
$q_c \in \mathbb{R}^Q$ ...カスケードcの特徴ベクトル
Qは特徴空間の大きさ

「アプローチ」
観測された拡散過程を連続(ユークリッド)空間に配置すること。
そのために、カスケード集合からダイナミクスをとらえることが出来る拡散カーネルを学習する。
$Z=\mathbb{R}^n$ ...n次元ユークリッド空間で定義される潜在空間
カーネルの学習は、今回で言えば空間Zの特定位置にノードを配置することであり、
潜在空間は学習用のカスケードから得られた感染時刻を表す。
f:id:A_Koide0519:20140314155552p:plain

「この手法の利点」

連続空間への配置問題は従来からある最適化法で容易に解ける
グラフ構造や拡散傾向の仮説を作らなくてよい
シミュレーションの必要がない
他の情報との統合が容易

「拡散カーネル」"CDK"
幾何学的多様体 $\chi$ を定義する。
その際、拡散カーネルを $K(t,y,x):\mathbb{R}^+*\chi*\chi \rightarrow \mathbb{R}$ と表現する。
カスケードの情報源yと時刻tと位置x
ただし、 $t=0$ のとき $K(0,y,x)=\delta(y-x)$
$\delta$ はディラックのデルタ関数
n次元のユークリッド空間に対して、拡散カーネルは以下のように書く
$K(t,y,x)=(4 \pi t)^{\frac{-n}{2}}e^{\frac{||y-x||^2}{4t}}}$

「潜在空間内の拡散カーネルの学習」
ベストな拡散カーネルを学習する問題。
拡散カーネル関数を以下のように置き換える。
$K(t,s^c,u_i)$
情報源 $s^c$ が与えられた時の時刻tでの $u_i$ の感染スコアを返す。
$Z=(z_{u_i}...z_{u_N}),z_{u_i} \in \mathbb{R}$
潜在空間 $\mathbb{R}$ ないのユーザ $u_i$ の位置。
最終的にこんな感じ
$K_Z(t,s^c,u_i)=(4\pi t)^{\frac{n}{2}}e^{\frac{-||z_{s^c}-z{u_i}||^2}{4t}}$
この問題は、どのように情報が拡散したかをモデル化すること、すなわち
各カスケードcに対して最適なZを見つける問題となる。
このときの経験誤差（標本誤差）を以下のように定義する。
$L(Z)=\sum_{c \in C_l}\Delta(K_Z(.,s^c,.),c)$
$\Delta(K_Z(.,s^c,.),c)$ は、情報源 $s^c$ が与えられた時の、拡散カーネル $K_Z$ と
観測されたcとの差異。最終的には、経験誤差を最小にするようなZを推定
する問題となる。
また、２つの制約条件を与える。
1.任意のユーザ $u_i$ と $u_j$ があるカスケードcに存在し、 $u_i$ の方が早くアクションをとった、すなわち $t^c(u_i)\ < t^c(u_j)$ の時、 $K_Z$ は以下のように定義される。
$\forall t, K_Z(t,s^c,u_i) > K_Z(t,s^c,u_j)$
2.任意のユーザ $u_i$ と $u_j$ が、 $u_i$ はカスケードcに存在し $u_j$ は存在しないとき、
$K_Z$ は以下のように定義される
$\forall t, K_Z(t,s^c,u_i) > K_Z(t,s^c,u_j)$

[Zの学習]
学習には確率的勾配降下法を使う。潜在空間上のユーザ間の位置関係を学習率 $\alpha$ を使って修正して行く。
[感染過程の算出]
情報源から各ノードの距離を計算するだけ

これらの操作から、既存の手法よりの高速に処理が可能になる。
※実験部分では速度の向上には全く触れられていない．．．

「属性を使った拡散カーネル」"CSDK"
情報の内容によって拡散の仕方を変える。contentsを表す特徴ベクトル $q^c$ を拡散カーネルに導入して、ユーザ間の位置関係がcontentsにも引っ張られるようにする。

●実験
データは３つのWebデータ。
ブログの投稿関係グラフ、Memetracker、Digg(Facebookのシェアみたいな感じ？)
ベースラインではユーザ間の関係を表したグラフを使うが、提案手法では当然
使わない。

評価手法はMean Average PrecisionとPrecision-Recall Curve
情報源を与えたときに、早く伝わるユーザから順番に並べていく。
そのランキングが実際のカスケードで伝わった順番とどれだけ合っているか。

ベースラインとして５つ用意
1学習データで影響を受けた回数をそのままスコアにしたもの
2学習データで早く感染しやすいユーザ程感染スコアを高くする
3ICモデル...グラフ構造と拡散確率
4Netrate...グラフ構造を必要としない
5GraphDiffusion...グラフ構造を利用したカーネル法

提案手法がほとんどの場合で良いスコアが出る。
contentsを導入した手法CSDKが最も性能が良かった。

●所感
内容としては普通に面白いけど、自分が期待していた期待影響度最大化とかそういう話ではなかった。実際のソーシャルネットワークでの、グラフ構造上でのユーザ間の関係と、情報拡散上でのユーザ間の関係は実はこんなに違うんですよ的な話のほうがしっくりくる感じがした。
読んでる途中で"これ最終的に伝わった人数とかどういう風に推定するんだ？"と思ったけど、評価の部分でようやくそういう問題設定じゃないんだなと納得できた感じだった。問題設定の部分とかちゃんと読めてなかったのかな。