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

--

--

aha 專長於組裝各式語言與各大平台服務,打造最小可行產品原型.曾獲得2011 政府開放資料平台App社會組首獎.2015 PIXNET Mobile Service社會組首獎.2014 DSC R 課程講師.2017pycon與2017 DSC講者,2022 法律x法遵黑客松第三名。

Love podcasts or audiobooks? Learn on the go with our new app.

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Cheng-Yu Lin

Cheng-Yu Lin

aha 專長於組裝各式語言與各大平台服務,打造最小可行產品原型.曾獲得2011 政府開放資料平台App社會組首獎.2015 PIXNET Mobile Service社會組首獎.2014 DSC R 課程講師.2017pycon與2017 DSC講者,2022 法律x法遵黑客松第三名。