実験はしてません.

背景

グラフでも分散表現 (Skip-gram with negative sampling) みたいなのが流行りまくっています [1]. 古典的なグラフスペクトラルを行列分解するみたいなやつを除くと

の3つがベースラインでよく使われます. ただし,DeepWalkとnode2vecは,ほぼ一緒なので片方で十分だと思っています. 今回は後者だけを使いたいとします.

node2vecは公式実装が2つあり,python or SparkC++です. 前者と後者でsub-samplingするしないの違いとかいろいろあるんですが,速い後者を考えます.

本記事と似たような議論がnode2vec論文でもあります,ただ読んだ感じ,実装とは違う印象です.


本題

まず,何をフェアにしたいかですが,幸いなことにLINEもnode2vecもSkip-gram with negative samplingとかなり似ています. というわけでskip-gram with negative samplingで更新する単語数をだいたい一緒にしようと考えます.

LINE

LINEではエッジをサンプルし,それを正例とします. いくつエッジをサンプルするかは,グラフの大きさに依存せず,コマンドラインの引数の -samples * Million だけサンプルします. -samplesのデフォルト値は, 1 です. なので,小規模グラフでは1でいいのですが,大規模グラフだとよくありません.

negative samplingの数はコマンドライン引数で変更できます. デフォルトは 5 です.

ちなみに,LINEの問題点として低次数ノードの訓練が上手くいかないというものがあり,擬似的にエッジを生やすコードがあるのですが,試したらひどいことになったので,Issueのように再現するようなら使わないほうがいいと思います.


node2vec

node2vecでは,グラフ上でランダムウォークを行い,それをコーパスとみなしてskip-gram with negative samplingします. ただし,C++実装では,sub-samplingはしません. python実装ではgensimを継承してるのでおそらくsub-samplingします.

今回は,skip-gramを扱うわけなので,ランダムウォークで作ったコーパスに含まれるノード数をLINEの-samplesと一緒にするとLINEが不利になるため,少し計算していきます.

node2vecの正例の数に関係するのは,以下のパラメータです.

  • r: 1ノードを始点としたときのランダムウォークの回数.デフォルト10
  • l: ランダムウォークの長さ.デフォルト80
  • k: 文脈窓幅.デフォルト10
  • e: SGDの反復回数.デフォルト1

素直に考えると扱う正例数は

です. 注意点として k は片側に対する値なので,2倍します. ただ,これだと多めです.

まず窓幅ですが,乱数に依存しており,これはword2vec実装と同様に最大値が k であり,最小値が 1 です [2]. なので期待値を取る必要があります. 例えば,k=10 とするなら

です. よって ではなくて です.

残念ながら,厳密には,これでもまだ多めな見積もりです. 例えば,ランダムウォークの先頭のノードを処理する場合は,さきほど求めた期待値は更に小さくなります.

[0, 1, 2, 3, 4, ..., 79] # l=80

を考えると0を軸として扱う場合は,左側にはノードがないので,期待値も減ります. ここでは話がややこしくなるのを避けて,l>2k, k=10のときで具体例を考えてみます.

  • 0:
  • 1:
  • 9:

というわけで 軸の位置をcとするなら,です. 右側も同様に計算するので,

回のノード対の更新が1ランダムウォークあたりに減ります.

以上より,node2vecでは,

回だけ正例を処理します. この値がLINEの-samplesMと同じくらいだとフェアといえそうです.

negative samplingの個数は固定されており,個数は5です. これは,LINEと同じ値にする必要があるので,LINE側を5とするのが良さそうです.


終わりに

このあたりまで書いて気づいたのですが,node2vec論文では,右側の窓幅しか使っていません. このため,LINEのepoch数をnode2vecの倍してるそうです [3]. C++のコード読んだ感じ両側使ってる気がするのですが,間違っていたら教えてください.


  1. 去年で少なくともサーベイ論文が3つ 

  2. node2vecの該当箇所 

  3. LINEの著者実装にそんなパラメータはないので,-samplesk倍でしょうか