Strcu2vec 的簡讀

參考資料

1. http://www.land.ufrj.br/~leo/struc2vec.html
2. pdf — http://www.land.ufrj.br/~leo/struc2vec-slides.pdf
3. github — https://github.com/leoribeiro/struc2vec
4. paper — https://arxiv.org/pdf/1704.03165.pdf

目標

Map network nodes into Euclidean space(struc2vec) 將一個 Network 映射到歐式空間，可以用來解決以下問題:

1. 保住每個節點的距離關係
2. 找出每個節點的小圈圈(快速分類)
3. 保住每個節點的相鄰關係

很多方法都可以做到這件事情，因此這是一個透過針對應用來決定最佳對應(Map function)函數的問題。並沒有所謂的最佳解。只有最適合解。

這類問題都有結構獨特性的問題，透過Automorphism(自同構)的映射函數，很容易找出會有相似結構的節點。

有很多先前的相似工作: word2vec, deepwalk, node2vec, rolx

Struc2Vec的獨特之處

1. 結構相似性不依賴於結點之間間隔距離(hop distance)
2. 鄰居節點的向量會不同，但遠處的節點卻可以因為結構性質而有相似的向量
3. 用節點的結構性質作為分類概念，就算是相似的深度節點，向量也會不
4. 靈活的四步程序

計算Struc2Vec

1. R_k(u): 距離節點u，k個距離的節點集 S
2. s(S): 這個節點集裡的每個節點n，n周遭的節點數量有序集
3. 有序數列的距離函數: g(s(R_k(u)) , s(R_k(v) ) = \frac { \max ( R_k(u) , R_k(v) ) } { \min ( R_k(u) , R_k(v) ) } -1, 採用DTW計算
4. 結構距離函數: f_k(u,v) = f_{k-1}(u,v) + g(s(R_k(u)) , s(R_k(v) ) 其中f_{-1} = 0 與如果 u 與 v 在 k個相鄰節點結構同構的話, 那麼 f_k(u,v) = f_{k-1}(u,v) 也就是說 g(s(R_k(u)) , s(R_k(v) ) = 0

5. 任兩個節點的在第k個層weight 應該是 w_k(u,v) = exp{-f_k(u,v)}

6. 採用Random walk 走在多層的layer, 其喜歡的機率為p, 換層的機率為 1-p