内輪の輪行でリンク予測の話をしたのでスライドをアップする．
Supervised random walks: predicting and recommending links in social networks(WSDM 2011)
ついでにSupervised random walks: predicting and recommending links in social networksも読んだのでそれも貼る．著者はfacebookの人．
Supervised random walks: predicting and recommending links in social networks
概要
先のスライドでも書いたようにこれまでのリンク予測はグラフ構造のみを用いていた．しかしノードやエッジにはリッチな特徴量が付与されているのでこれを利用し，random walkの形で解く．
何故Random walkか?
特徴量ベースで判別器に投げる方法は
- グラフがimbalanceなのでそもそも難しい
- 100万ユーザがいるSNSでユーザ一人あたり10000人も友達がいるか？
- 特徴量を考えたり試したりするのが面倒
Random walkベースの方法は
- 楽
- グラフ構造を利用できるので良い
けど
- どうやって特徴量を埋め込むか？
- random walkは基本的にはリンクがあるかないか(その重み)
定式化
端的に言えば，random walkで用いる遷移確率を最小化問題として解く．
まず，問題設定としてグラフと開始ノード
が与えられる．
これに加え，sが将来リンクを貼るであろうノード集合とリンクを貼らないであろうノード集合
が与えられる．これが正例と負例に当たる．読んでいる感じDをsの隣接ノードとして与えているっぽい(sec4のfacebookのデータ説明の部分，Dはsが2009年11月1日から2011年1月13日までにfriendになったノードとした，としている)．
ノード間にある特徴量ベクトルを
で書く．その後，
とした上で，遷移行列
とする．
じゃあこのはどう求めるのかというと，random walkの定常確率について
なる制約を置いた状態で
を求める．この制約は「DはLより繋がりやすい」というのを式にしたもの．
しかしこれでは制約が強すぎるので，損失関数を考えて
にしてやる．
あとはpersonalized pagerankの式がとなり，定常確率は
になるので準ニュートン法でガリガリ解いていく．制約式の中にpagerankの定常確率が入ってるのでそこが少し面倒．
つまり何が新しいか？
PageRank などの random walk ベースの手法を使う時，通常はエッジの重みのみで遷移確率を計算する．提案手法である supervised random walk ではその遷移確率そのものにfeatureを埋め込み，その後，最小化問題で遷移確率(というよりそのまま定常確率)を計算している．計算の際にノード集合D，Lを使うので supervised になっている．
最小化のあたり数式が並んでて敬遠してたが読んだら思ったより抵抗なく読めた．
