鴨川η

node2vec: Scalable Feature Learning for Networks

メタデータとか

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

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

脱線すると,node2vecの名前が付いているものは

  • この論文
  • gloveをグラフデータに使ったコード
  • Neo4jの関連

があるので注意されたい.

図はすべて原論文から転載しています.

本題

展開

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

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

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

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

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

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

の分母の計算に時間がかかる. このため,word2vecではNegative-Samplingという方法でSoftMaxの近似計算を行う. どうするかというと,入力の単語ベクトルと文脈の単語ベクトルの2つを用意する(両方最適化の対象). 実際に共起する単語を正例,共起しない単語を負例とした2値で学習を行う. このとき,負例は膨大にあるので頻度に係数かけたような確率でサンプリングする(ゆえにNegative-Sampling).

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

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

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

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

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

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

提案手法

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

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

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

node2vec-fig2

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

の定義式は

  • if
  • if
  • if

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