面白いデータを探して

適当に書く。間違えていたら教えてください。

Network Embeddingの主要な手法について1

研究のためにNetwork Embeddingでよく扱われる手法についてまとめていきます.
例によって備忘録的な感じなので,主に何がしたい論文なのかに焦点を当てたいと思います.詳細に関しては論文などを見てください.
今回はDeepWalk, Node2Vec, LINE, SDNEの4つについて.

DeepWalk

論文は[1403.6652] DeepWalk: Online Learning of Social Representationsです.
前に記事を書いています.
netres-bigdata.hatenablog.com

Node2Vec

DeepWalkの改良的な論文[1607.00653] node2vec: Scalable Feature Learning for Networks
DeepWalkでは学習データのサンプリングの際にランダムウォークを用いています.そのランダムウォークにいい感じにバイアスをかけてやることによっていい感じのサンプルを取ってこようという主題.
「いい感じ」とは幅優先探索深さ優先探索のバランスを考慮してサンプリングがしたいということです.幅優先探索を行なうとネットワーク上でハブになっているノードのようなネットワーク上でのそのノードの役割をよく考えることができますが,ネットワーク上で近いノードの情報しか獲得できません.一方で,深さ優先探索ではネットワークのより広い範囲のノードの情報を得ることができますが,サンプリングされるノードの分散が大きく,探索範囲が深すぎると問題になる.そこでこれらを調整するためにランダムウォークの次のノードの選び方にバイアスをかける.

LINE

DeepWalkやNode2Vecとはまた少し考え方が違う手法
[1503.03578] LINE: Large-scale Information Network Embedding
.時系列的にはDeepWalkの次でNode2Vecより前に発表された論文.
LINEでは次の2つの学習を行なう.

  • first-order proximity : エッジでつながっているノードは近くに
  • second-order proximity : 隣接ノードの組が近いノードは近くに

second-order proximityは隣接ノードの組が近いノードは近いベクトル表現を得るように学習させるが,これは直接エッジで繋がれてはいないが,隣接ノードが近いノード対は近い役割を持っているはずであるという考え方による.
同時に最適化するのは今後の課題として,これらを独立に学習させてconcatすると精度がいいらしい.

SDNE

考え方としてはLINEに近いが,学習器にautoencoderを用いている*1
LINEと同じくfirst-order proximityとsecond-order proximityを考えるが,ネットワークの構造は high non-linearityを持つ.したがって,これらを保持するためには表現力が高いモデルを用いた方がいいはずである.そのために,DNN(今回はautoencoder)を使おうという論文.
自分が試してみたところ,精度は割と出る(Node2Vecと同じか少しいいくらい)だが,大きいネットワークに使おうとすると計算時間が非常にかかる.DNNを使うため,最適化にかかるコストが大きいことがネックかなあという感じ.

最後に

次はGCN関係をまとめたい.(GCN, graphSAGEとか)

*1:Wang, Daixin, Peng Cui, and Wenwu Zhu. "Structural deep network embedding." Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016.