メタデータとか

Aditya Grover & Jure Leskovecの論文.KDD2016に採択されている.

第2著者の Jure Leskovec 氏は SNAP というプロジェクトでグラフのデータやライブラリを公開している.その SNAP にも node2vec の専用のページがある.

図はすべて原論文から転載です.

本題

展開

おおまかな展開はこんな感じ:

  • リンク予測やノードのマルチラベリングでつかえるような特徴量としてノードの分散表現を獲得したい
  • 自然言語処理で成功してる word2vec のアルゴリズム Skip-Gram with Negative-Sampling のグラフへの適用を考えると,ノードの系列を生成するようなサンプリングの方法を工夫する必要がある
  • そこでランダムウォークを元にしたノードのサンプリングを行う(ここまでは deepwalk と一緒)
    • 幅優先探索のように周囲のノードだけをサンプルするのは不十分
      • 同じようなノードを何回も見てしまう
      • ノードの次数分布を考えると良くない
    • 構造的な特徴も考慮したい
      • これには深さ優先探索がよいが,分散が大きくなるため不十分
  • リンク予測とノードのラベリングの実験

なぜ node2vec が必要か

グラフのリンク予測やノードラベリングにつかえる汎用性のある特徴量を獲得したいとき,隣接行列に対して PCA のような次元削減は,大規模グラフに向かず,特徴量としても振るわない.そこで,word2vec のようなニューラルネットワークを用いた特徴量獲得を考える. 特にこの論文では

  1. 同じコミュニティに属しているようなノード
  2. ハブや橋のような構造的な役割をもったノード

を考慮してノードを特徴量に変換する.分散表現の獲得には Skip-Gram with Negative-Sampling (SGNS) の学習アルゴリズムを使うため,SGNS について簡単に説明する.

SG は文中に出現した1単語からその周囲で共起する単語を予測するように学習するアルゴリズム. SG のモデルは3層のニューラルネットワークである.このとき,出力層は語彙数次元だけあるため,SoftMaxの定義式:

の分母の計算に時間がかかる.このため,word2vec では Negative-Sampling という方法を使う.どうするかというと,入力の単語ベクトルと文脈の単語ベクトルの2つを用意する(両方最適化の対象).実際に共起する単語を正例,共起しない単語を負例とした2値で学習を行う.

SGNS のグラフへの適用を考える.ストレートな方法としては,幅優先探索か深さ優先探索の一方を使った SGNS の正例サンプリングが考えられる.

上で述べたノードを探索法と対応付けると

  1. 同じコミュニティに属しているようなノード:深さ優先探索
  2. ハブや橋のような構造的な役割をもったノード:幅優先探索

となる.しかし,それぞれ以下のような欠点がある.

  • 幅優先探索:隣接ノードしか考慮しないので,大域的な情報が学習に使えない
  • 深さ優先探索:
    • サンプルの分散が大きい
    • 深すぎると正例として不適切

なのでこれらの両方を満たすようなノードのサンプリングが必要となる.

提案手法

長さ のランダムウォークを行う.ノード から に遷移する確率を で定義する.このとき, は正規化項で, へはリンクが存在するものとする.

は, で定義される.このとき, はエッジの重みで, は,最短パスに依存する重み付けである.

次に の定義について説明する.

node2vec-fig2

この図では,ノード から に遷移した際に,次の遷移先の の値を求めている.

の定義式は

  • if
  • if
  • if

である.ただし, はノード から までの最短距離で, は,指定する必要のあるパラメータ. は,すでに訪れたノードへの戻りやすさを制御するパラメータで, の値が大きいと,すでに訪れたノード (図の ) には戻りにくくなり, の値が小さいと, に戻りやすくなる. の値が小さいときは,幅優先探索的になり, の値が大きいときは,深さ優先探索的になる.