Personalized PageRankとLabel Propagationが等価という話 - でかいチーズをベーグルする

無向グラフの時のPersonalized PageRank*1とLabel Propagation*2（LGCとも呼ばれる）が本質的に等価というお話。つまりLabel Propagationを計算したいときはPersonalized PageRankを計算すれば等価な結果が得られる。Personalized PageRankとLabel Propagationを知ってる人向けに書くのでわからない人はブラウザの戻るボタンを押してね。 まず、Label Propagationは以下のように書ける。 ただし、で、Wはデータ間の類似度行列、Dは次数の対角行列を示す。また、yはlabeled exampleのラベルを格納するベクトルで、positiveなら1、そうでなければ0を格納する（unlabeledも0）。αは0から1のパラメータ。この等式を満たすfが求められればLabel Propagati