論文メモ

node2vec: Scalable Feature Learning for Networks

概要

  • node2vec
  • deepwalkと同様、無向グラフの潜在ベクトルを取得する
  • DeepWalkとの対比
    • DeepWalk [24]。このアプローチは，一様なランダムウォークをシミュレートすることで，d次元の特徴表現を学習する．DeepWalkのサンプリング戦略は、p=1、q=1のnode2vecの特殊なケースと見ることができる。
  • LINE [28]。このアプローチは，2つの別々のフェーズでd次元の特徴表現を学習する．最初のフェーズでは、ノードの直近の隣人に対するBFSスタイルのシミュレーションによってd/2次元を学習する。第2段階では，ソースノードから2ホップの距離にあるノードを厳密にサンプリングすることで，次のd/2次元を学習
  • 現在の特徴量学習アプローチは、ネットワークで観察される接続パターンの多様性を捉えるには十分な表現力を持っていない
  • DeepWalkはp=1, q=1の特殊な場合
  • ノードのネットワーク近傍を（サンプルとして）生成するために、2次ランダムウォークの手法
  • dtxは{0, 1, 2}のいずれか
  • πvx = αpq(t, x) · wvx
  • q < 1の場合、歩行はノードtからより遠くのノードを訪問する傾向
  • q＞1の場合，ランダムウォークはノードtに近いノードに偏っている
  • パラメータqは、探索が「内向き」と「外向き」のノードを区別
  • グラフ内のすべてのノードの直近の隣人を保存するための空間計算量はO(|E|)
  • アイディアだけをあとから聞けば、理解できるが、最初に考えつくのが難しいのだろう。。。
  • Line, Node2vec, DeepWalk