【論文要約】node2vec: Scalable Feature Learning for Networks

元論文：node2vec: Scalable Feature Learning for Networks

Grover, A. and Leskovec, J., 2016, August. node2vec: Scalable feature learning for networks. In Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining (pp. 855-864).

どんな論文？

グラフにおける頂点の埋め込み表現の学習方法としてnode2vecを提案した論文。
既存研究を上回る埋め込み表現が得られることを示した。

学習方法としては、「長さ l のrandom walk をサンプリング→Skip-gram→word2vecと同様の学習」 という流れになっており、頂点(node)がword2vecの 単語(word)のように扱われる。

先行研究と比べてどこがすごい？

頂点の埋め込み表現を学習する方法について、先行研究はコストが高かったり性能が十分でなかったりした。
この研究で提案された node2vecは、頂点数に対して線形にスケールしながらも、既存研究を上回る埋め込み表現を、下流タスクに依存しない形で学習する方法を提示した。

技術・手法・モデルのキモはどこ？

DFS・BFSから着想を得たサンプリング手法により、すべての頂点に対して長さ l の r 個のrandom walks を計算
→ Skip-gram を適用しword2vecと同様に学習

DFS・BFSのイメージ

実際のrandom walksで用いる遷移確率

アルゴリズムの詳細

どうやって有効だと検証した？

マルチラベル分類においてnode2vecが既存の最先端技術よりも有効であることを実験により示した

頂点分類

リンク予測

パラメータ変更時の性能変化 、辺の欠損, 辺の追加の際の頑強性チェックも行った

スケーラビリティについても頂点数に対して線形であることを実験により示した

議論はある？

• 2016年とこの分野では比較的古い論文なので最新研究でさらに良いものが出ているか？ちょうどGCNが出始めたあたりなので、タスクの性能自体はこれより良いものがたくさんありそう。埋め込み表現の獲得という観点ではこれを上回るものがあるのか？
• 汎用的であるが故に、辺の重みや元々ある頂点の特徴量などを考慮できていない？

次に読むべき論文は？

• connected papers
• (知らなければ）word2vec