でかいチーズをベーグルする

でかいチーズはベーグルすべきです。

Personalized PageRankとLabel Propagationが等価という話

無向グラフの時のPersonalized PageRank*1とLabel Propagation*2(LGCとも呼ばれる)が本質的に等価というお話。つまりLabel Propagationを計算したいときはPersonalized PageRankを計算すれば等価な結果が得られる。Personalized PageRankとLabel Propagationを知ってる人向けに書くのでわからない人はブラウザの戻るボタンを押してね。

まず、Label Propagationは以下のように書ける。

{ \displaystyle
f = \alpha Sf + (1-\alpha ) y
}

ただし、 S = D^{-1/2} W D^{-1/2}で、Wはデータ間の類似度行列、Dは次数の対角行列を示す。また、yはlabeled exampleのラベルを格納するベクトルで、positiveなら1、そうでなければ0を格納する(unlabeledも0)。αは0から1のパラメータ。この等式を満たすfが求められればLabel Propagationが計算できたことになる。

次にPersonalized PageRank

{ \displaystyle
x = \alpha Px + (1-\alpha ) b
}

ただし、 P = W D^{-1}。またbはpreference vectorを表す。

ここで、SはPを用いて以下のように書ける。

{ \displaystyle
S = D^{-1/2} P D^{1/2}
}

これを使うと、Label Propagationの式は以下のように書き換えられる。

{ \displaystyle
f = \alpha D^{-1/2} P D^{1/2}f + (1-\alpha ) y
}

両辺に D^{1/2}をかけて

{ \displaystyle
D^{1/2}f = \alpha  P D^{1/2}f + (1-\alpha ) D^{1/2}y
}

ここで x' = D^{1/2}f, b'=D^{1/2}yと置くと、

{ \displaystyle
x' = \alpha Px' + (1-\alpha ) b'
}

Personalized PageRankを同じ式になった! b'は要素の合計が1になるように正規化されてないけどPersonalized PageRankの計算の収束性には影響ない。これでPageRankを計算するプログラムを使ってLabel Propagationを計算できるようになった。まとめると、

手順

  1.  P = WD^{-1}
  2.  b = D^{1/2}y
  3.  x = PPR(P,b) # PPR(P,b)はPersonalized PageRank vector xを計算する
  4.  f = D^{-1/2}x

まとめ

ランダムウォーク系のアルゴリズムってそれぞれかなり密につながってるからこれも結構自明な結果だったりする*3。これが分かることによって何が嬉しいかというとPersonalized PageRankを高速に計算するアルゴリズムが出てきたらそれを使ってLabel Propagationも高速に計算できるようになることかな。

*1:Scaling personalized web search, WWW2003

*2:Learning with Local and Global Consistency, NIPS2003

*3:ソースは"Ranking on Data Manifolds", NIPS03