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

元論文：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 での辺の重みの平均値）。

その後、新しく定義したグラフ上での random walk を考え、 word2vec, node2vec のように、random walk をSkip-Gram で学習する。

どうやって有効だと検証した？

まず、対称的なグラフで学習し、その頂点の埋め込み表現を可視化した。

一つはBarbell graphで、もう一つは Mirrored Karate network。

Barbell graph

Mirrored Karate network

また、 air-trafic networks のデータセットを用いて、構造的同一性が大きく影響する頂点分類のタスクに関して既存手法を上回る性能を示した。

ランダムグラフの頂点数を変化させて計算を行い、実行時間について測定する実験も行った。線形ではないが、実用的な時間で実行可能なことを示した。

議論はある？

• あくまで構造的同一性に特化した話なのでタスクによって使い分けは必要。node2vecのほうが良いケースも多そう。

次に読むべき論文は？

• struc2vec_ Learning Node Representations from Structural Identity _ Connected Papers