DeepWalk: Online Learning of Social Representations (KDD2014) 読んだ

[1403.6652] DeepWalk: Online Learning of Social Representations
実装もある．
DeepWalk - Online Learning of Social Representations - Bryan Perozzi's old website

概要

グラフ構造のデータから latent representation を学習する．skip-gramなどでは入力が文章集合になっているが，提案手法では random walk でそれを実現する．
contributionは3つ．

• グラフデータを分析する手法として deep learning を適用した．
• マルチラベル分類タスクに提案手法を適用し精度を上げた．
• 並列実行可能なのでスケーラビリティもすごい．

タスク

グラフについて次元の特徴ベクトル集合とラベル集合が与えられた上でとの関係を学習したい．
既存研究ではグラフ構造が与えられた上でのラベルの事後分布を計算するが，提案手法ではラベルに依存しないグラフ構造を学習した上でそれをラベル予測に使う(unsupervised learningをすると言っている)．

手法

アイデアとしては

• ランダムウォークでグラフから取り出した部分系列の集合中のノードの出現数は power law に従う
  • グラフデータに対するランダムウォークの有効性はこれまで示されている
• 自然言語における単語の出現数は power law に従う
• 自然言語処理における skip-gram をグラフデータに適用できるのではないか

という流れで，グラフからランダムウォークで取り出した部分系列を「文章」としてskip-gramに入力する．シンプル．
アルゴリズムはランダムウォークと更新の二つに大きく分かれる．

ランダムウォーク

グラフの中からランダムに選んだ頂点からスタートして，長さtになるまでランダムに隣接した頂点にジャンプすることを繰り返す．
実際には，グラフ中の全頂点から行うランダムウォークを回繰り返す．

更新

ランダムウォークで得られた系列を使ってskip-gramを学習する．
skip-gramの学習を愚直にやると全頂点で内積計算してsoftmax取る必要があるので Hierarchical Softmaxで効率化する．
それに加えて，skip-gramの更新そのものも，データがスパース(すなわち1度に更新されるパラメータもスパース)なのでSGDを並列化(asynchronous version of stochastic gradient descent, ASGD)しても問題ない．
実験したところ，並列化によってスケーラブルになり，パフォーマンスにも影響が無かった．

実験

BlogCatalog，Flickr，YouTubeのデータでマルチラベル分類．
いい感じに精度が出ている．
BlogCatalogではSpectralClusteringに負けたりしていたけど，YouTubeデータは巨大すぎてSpectralClusteringが実行できなかった．提案手法では余裕で計算できているので良し．

低次元表現の例が論文冒頭の空手ネットワークのみなのが少し寂しい，youtubeデータの2次元表現とか見たかった．