Open Shumpei-Kikuta opened 5 years ago
William L. Hamilton, Rex Ying, and Jure Leskovec
2017, IEEE
伝統的なembeddingの手法は,ヒューリスティックに特徴を作成し,それを保存するような手法をとっていたが,特徴の作成は難しく,グラフに大きく依存してしまう. 近年は,自動的にグラフの特徴を学び,ベクトル空間にマッピングする手法が盛んである. ほとんどの手法は教師なし学習を用いており,学習にはグラフ全体もしくは隣接行列を用いる.教師あり学習においては,ノードのラベル情報などを用いてマッピングする. このマッピングのプロセスは,embeddingと呼ばれ,ノードを分散表現encodeするプロセスと,分散表現から元のグラフの特徴を再現するdecodeのプロセスに分けられる. nodeのembeddigは多数あるが,以下の違いによって説明できる.
(例えばDeep walkでは隣接しているノードを近いと定義する(how many hops) . あるノードが存在する元で他のノードがcontextに存在する事後確率を最大化することで,encodeする. decodeにおいては,cosine類似度などを取ることでembedding空間上での距離を計算する.損失関数はskipgramにおける交差エントロピー誤差である.)
直接的にembedding Matrix Zを作成するアプローチ.以下の式で表される. viはノードiのone-hot-vector. つまり,one-hot-vectorにemebedding Matrixをかけることでencodingする手法.
Laplacian eigenmaps and inner-product method and Hope are the remarkable methods. 異なるのは,エンベッティング後の内積を元のグラフにおけるどの指標に近づけるかである.
Deep Walk, node2vec, Line and HARP. HARPはmeta-strategyという概念を提示し,meta-strategyに従ってグラフを変換した後にランダムウォークをすれば,全ての手法の精度が高まることを示した.
二つの手法は以下の問題点がある. ・パラメータがシェアされていないため,過学習,過小学習に陥りやすい.計算コストも大きい. ・label, attribute 情報などを無視している. ・まだ存在しないノードに対応できない.
これらの問題のどこかにアプローチした手法を紹介する.
手法は以下の通り.
ポイントは,以前の手法はone-hot-encodingを直接encodeしていたため,パラメータがシェアされていなかった.この手法は特徴量をencodeするため,パラメータがシェアされる. また,ENC,DECが非線形関数なため,より良い特徴量を生成しやすい.
ノードに貼られた属性や,次元情報を用いる.使用する情報は,ある関数に従って埋め込まれるためconvolutionと言われる. GraphSAGEなどがある.(別のISSUE)でまとめる.
現状の課題として,以下が挙げられる.
encoder-decoder frameworkは非常に有用.
Author
William L. Hamilton, Rex Ying, and Jure Leskovec
Published
2017, IEEE
Introduction
伝統的なembeddingの手法は,ヒューリスティックに特徴を作成し,それを保存するような手法をとっていたが,特徴の作成は難しく,グラフに大きく依存してしまう. 近年は,自動的にグラフの特徴を学び,ベクトル空間にマッピングする手法が盛んである. ほとんどの手法は教師なし学習を用いており,学習にはグラフ全体もしくは隣接行列を用いる.教師あり学習においては,ノードのラベル情報などを用いてマッピングする. このマッピングのプロセスは,embeddingと呼ばれ,ノードを分散表現encodeするプロセスと,分散表現から元のグラフの特徴を再現するdecodeのプロセスに分けられる. nodeのembeddigは多数あるが,以下の違いによって説明できる.
(例えばDeep walkでは隣接しているノードを近いと定義する(how many hops) . あるノードが存在する元で他のノードがcontextに存在する事後確率を最大化することで,encodeする. decodeにおいては,cosine類似度などを取ることでembedding空間上での距離を計算する.損失関数はskipgramにおける交差エントロピー誤差である.)
Direct encoding approaches
直接的にembedding Matrix Zを作成するアプローチ.以下の式で表される.
viはノードiのone-hot-vector.
つまり,one-hot-vectorにemebedding Matrixをかけることでencodingする手法.
Matrix Factorization
Laplacian eigenmaps and inner-product method and Hope are the remarkable methods. 異なるのは,エンベッティング後の内積を元のグラフにおけるどの指標に近づけるかである.![2018-10-26 11 17 30](https://user-images.githubusercontent.com/38586033/47557350-bee23500-d910-11e8-95f7-8197bc6305d4.png)
Random walk
Deep Walk, node2vec, Line and HARP. HARPはmeta-strategyという概念を提示し,meta-strategyに従ってグラフを変換した後にランダムウォークをすれば,全ての手法の精度が高まることを示した.
Generalized encoder-decoder architecture
二つの手法は以下の問題点がある. ・パラメータがシェアされていないため,過学習,過小学習に陥りやすい.計算コストも大きい. ・label, attribute 情報などを無視している. ・まだ存在しないノードに対応できない.
これらの問題のどこかにアプローチした手法を紹介する.
Autoencoder method
手法は以下の通り.![2018-10-26 12 07 38](https://user-images.githubusercontent.com/38586033/47560152-c0fbc200-d917-11e8-8ded-89abafa64902.png)
Convolutional encoders
ノードに貼られた属性や,次元情報を用いる.使用する情報は,ある関数に従って埋め込まれるためconvolutionと言われる. GraphSAGEなどがある.(別のISSUE)でまとめる.
Future work
現状の課題として,以下が挙げられる.