search

Shumpei-Kikuta / Papers

Summarizing papers I've already read
0 stars 0 forks source link

struc2vec #4

Open Shumpei-Kikuta opened 6 years ago

Shumpei-Kikuta commented 6 years ago

paper

Author: Leonardo F. R. Ribeiro, Pedro H. P. Saverese and Daniel R. Figueiredo Published: KDD2017

Why

これまでエンベッティングの手法は様々開発されているが，役割ベースでエンベッティングする手法はない．これまでのエンベッティングはhomophily(似ているノードは繋がりやすい,繋がっているノードは似ている) タンパク質の役割ネットワーク，航空網のネットワークなどではネットワーク上で役割が重要な役割を果たすため，役割を保存するエンベッティングが必要．

Contribution

What

考え方は以下の通り

  1. ノードu, v の構造的類似性を計算する
  2. 多層ネットワークMを作る
  3. Biased random walkでノードの列を生成
  4. Skip-gramへ

How

  1. ノードu, vの構造的類似性を計算する． この式に基づいて計算． "image" k: ノードからのhop数, R: ノードからkホップの位置にあるノードの配列 s: Rの次数の配列を降順にソートした配列 g: 配列同士の近さを求める関数

イメージは，ノードu, vの周りにあるノードの次数が近ければfは大きくなる →f は構造的類似性を表す．

  1. 多層ネットワークMを作る kの値によって多層のネットワークを作る． 全ての層において，全てのノードが存在する． ノードu,v の近さがfkで求められるので，全ての組み合わせに対してfkを求める． fkに大きさによってエッジに重みをつける(Biased random walk用).

  2. Biased random walkでノードの列を生成 まず，層を移動するか決める． 層を移動する基準は，似ているノードの量，似ているノードが多い(エッジの重みが大きいものが多い)時は，上の層へ，似ているノードが少ない時は下の層へ移動する． 層が決まったら，エッジの重みに従って遷移する． これを繰り返す．

  3. skip-gramへ おきまりのやり方．