鴨川η

LINE: Large-scale Information Network Embedding

メタデータとか

Jian Tang et al.の論文でWWW2015に通っている.

関連研究のdeepwalkの後,node2vecの前に出たものになる.

本題

word2vec(skip-gram)で単語の分散表現を学習したようにノードについても分散表現を求めたい.

ノードが似ているというのは,以下の2つが考えられる:

  1. 隣接ノード対
  2. 直接隣接していないが隣接ノードが共通しているノード対

直接つながっているノード同士というのは例えると,仲のいい友だち(頻繁にreplyを送り合ってるユーザとか)で,後者は,直接面識はないが共通の知り合いがたくさんいる人同士となる.

類似研究であるdeepwalkではrandom walkを行っているため,深さ優先探索的であるが,提案手法(LINE)は幅優先探索的といえる.(node2vecではこれらのいいとこどりをしている)

隣接ノード同士

ノード のエッジ の同時確率を

とする. はノードの分散表現とする. この確率分布 ( は確率分布にはならないような気がするのだが) とempericalな確率分布

とのKLダイバージェンスを最小化するようにノードのベクトルを学習する. ただし 間の重み(非負)で はエッジの集合.

1hop先

今度は条件付き確率で表現する. こっちに文脈としてのノードが出てくる.

最小化するのはさきほどと同様にKLダイバージェンスになる.

このとき の出リンクと接続したノードの集合. KLダイバージェンスにノード の次数をかける. PageRankでもよいらしい. ここでKLダイバージェンスを求める際に,条件付き確率を計算するのはしんどいので,negative-samplingを使う.

2つの目的関数があるのだが,これらを同時に最適化するのはfuture workとなっており,論文では別々に学習したものを別々に使っている. supervisedなケースだとconcatして重みを少し修正して使っている.

実験

言語,SNSなどのグラフを使って分類性能とword analogyで評価をしている. word analogyでは,1hop先をみるLINEがskip-gramよりも性能が良かった.

パラメータの感度分析もあるので使う際に参考になるかもしれない.

その他

  • 著者実装
  • 個人的にはdeepwalkのほうがいい気がしているのだが,node2vecの実験結果をみるとどっちもどっちなので,パラメータやデータ次第かなという印象