Network Embeddingの主要な手法について2
Network Embeddingの主要な手法についてのメモ．
今回はGraRep, struc2vec, SiNE.
1はこちら．
netres-bigdata.hatenablog.com
GraRep
LINEではfirst-orderとsecond-orderに関して最適化を行なうが，k-orderに関しても最適化を使用という論文*1.
最適化に際して，skip-gramを行列式変形と解釈しなおし，それに関して最適化を行なう．
(GraRepについてはあまり理解できていないので，指摘・意見などがあればコメントなどいただけると幸いです．)
struc2vec
各ノードがネットワーク内で果たす役割に対応したベクトル表現を得る手法[1704.03165] struc2vec: Learning Node Representations from Structural Identity．
ネットワークからコンテキストを作り，階層的ソフトマックスで最適化を行なう．
実験では飛行機の運行ネットワーク内で活発な飛行場とそうでない飛行場を4段階に分け，それらを分類することができるかで行っているが，ソーシャルネットワークとかで考えるとインフルエンサーを見つけると言ったタスクに近くなるのだろうか．
SiNE
正負重み付きグラフ(signed network)のエンベッディング手法*2.
通常の重み付きグラフではエッジの重みは正の値であるが，正負重み付きグラフではエッジの重みに負の値を許す．このようにすることで，友好関係と敵対関係，賛成と反対と言った正負の関係をモデル化することができる．
SiNEでは正の重みのエッジを持つノード対は負の重みのエッジを持つノード対より近くにあるという知見に基づき，ニューラルネットワークの出力に対してマージン最大化をlossとして学習を行なう．
実験ではエッジの正負の予測を行い，当時のSOTAを達成(現在は更新されているようだ．)
*1:Cao, Shaosheng, Wei Lu, and Qiongkai Xu. "Grarep: Learning graph representations with global structural information." Proceedings of the 24th ACM international on conference on information and knowledge management. ACM, 2015.
*2:Wang, Suhang, et al. "Signed network embedding in social media." Proceedings of the 2017 SIAM international conference on data mining. Society for Industrial and Applied Mathematics, 2017.
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とか)
Graph Convolutionを実装してみる
Graph Convolutional Networkを実装してみました。
続きを読む