🐈

【論文要約】struc2vec Learning Node Representations from Structural Identity

2023/04/23に公開

元論文：struc2vec Learning Node Representations from Structural Identity

Ribeiro, L.F., Saverese, P.H. and Figueiredo, D.R., 2017, August. struc2vec: Learning node representations from structural identity. In Proceedings of the 23rd ACM SIGKDD international conference on knowledge discovery and data mining (pp. 385-394).

どんな論文？

グラフ上のノードの構造的同一性を表す埋め込み表現を学習するための手法としてstruc2vecを提案した論文。

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

node2vecなどの先行研究では、近くにある頂点が似た埋め込み表現になるように学習するようになっていた。しかし、これは遠くにあるが構造的に似ている頂点同士が似た表現にならないという課題がある。

この研究で提案した struc2vec は構造的同一性を踏まえた埋め込み表現を学習することができるため、グラフ構造上の頂点の役割に依存したタスクの性能を向上させることができる。

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

頂点間の構造的距離(structural distance)を定式化
頂点u,v間の構造的距離を定義するために

頂点 u から k 離れた頂点の次数の数列
頂点 v から k 離れた頂点の次数の数列

をそれぞれ考え、数列同士の距離を Dynamic Time Warping (DTW) (以下の式で $g$ )　で計算する
kは0から元のグラフの直径 $k^*$ 程度までの値を取りうる

structural distanceが近い頂点への遷移確率が高くなるようなグラフを新しく定義
まず、構造的距離が近い頂点への遷移確率が高くなるように完全グラフを定義する。
上記のグラフを一つのレイヤーとして、kを0から $k^*$ まで変えた $k^* +1$ 個のレイヤーを重ねて新しいグラフを構築する。

レイヤー同士の接続は同じ頂点同士で行い、以下のように定義される（ $\bar{w_k}$ はレイヤー k での辺の重みの平均値）。