Shumpei-Kikuta
commented
6 years ago Why and What
近年，様々なNetwork embeddingの手法が開発されているが，多くはstructural equivalence(homophilyに基づく) に基づくembeddingである．しかし現実のタスクはregular equivalence(similar role or node name)でラベルが貼られることも多い．本研究では,LSTMを用いて再帰的にembeddingを生成する． regular equivalenceを保存する手法として，1つは全てのノードのペアを比較することが考えられるが，Large-scale networkでは不可能．他には中心性によってembeddingすることが考えられるが，中心性は多様な概念があり，一つの中心性では偏ってしまい，一般性を失う． またstruc2vecが類似研究としてあるが，struc2vecは中心性をヒューリスティックな方法で定義し，それを基にembeddingしている．(解釈: struc2vecは次数中心性に近いものを定義して，次数中心性が近いノードをwalkしやすいようにしている, 計算コストが非常に高く，また次数しか考慮していないため，役割ベースというには一般性を欠く)
How
以下のフレームワークに基づく．
(a)ノード(0)について，隣接ノードを考えると4つある．aggregateするノードの上限が決められており，ここでは3.
(b)3つのノードについて，次数の小さい順にソートし，LSTMのinputとする．
(c)LSTMによって最終アウトプットを計算する．損失関数は以下の通り．
直感的には，目的ノードを隣接ノードをaggregationしたものに近づけていく．
なお，LNはlayer normalizationであり，勾配消失，勾配爆発を防ぐために利用される．
(d) 正則化のための計算．以下の式に従う．
Information
Author
Ke Tu, Peng Cui, Xiao Wang, Philip S. Yu and Wenwu Zhu
Published
KDD 2018