NODE2VEC理論到複現

參考知乎： node2vec 原文連結： node2vec: Scalable Feature Learning for Networks 複現代碼見： Colab

Introduction

複雜網絡主要有兩種任務，一網絡節點的分類，通俗點說就是将網絡中的節點進行聚類，我們關心的是哪些節點具有類似的屬性，就将其分到同一個類别中。二是連結預測，就是預測網絡中哪些頂點有潛在的關聯。

前面的DeepWalk借鑒了詞嵌入模型skip-gram的思想，node2vec也是如此，最重要的不同就是在遊走的方式上有了改進，在得到序列後的處理方式和DeepWalk是一緻的。下面主要探讨的就是這樣的序列是怎樣得到的，又是怎麼有利于網絡嵌入的。

模型

目标函數

原文中介紹了對于優化目标函數的推導，和skipgram中的思想是類似的，首先要盡可能使得節點與周圍鄰居節點同時出現的機率盡可能大，也就是最大化下函數（其中

表示從節點

映射到嵌入向量，

表示

的鄰居節點）：

同時假設觀察一個鄰居節點的機率獨立于觀察其他鄰居節點的機率，這樣就有：

綜合起來所有節點後，優化的目标函數就為：

這和skipgram中介紹的有很大的相似性，且

的計算量太大，故也是采用負采樣的方法，這也是為什麼說這篇論文也借鑒了skipgram的思想。其創新點主要在下面要講的遊走方式上。這樣創新的遊走方式能夠捕捉到網絡連接配接的多樣性。

遊走方式

在學習了前面的LINE模型後，會有這樣一種感覺，圖中的節點資訊主要蘊含兩種，一種是同質性資訊，一種是結構相似性的資訊。第一種很好了解，就是聚集在一個社群之中的節點之間有着相似的特征，是以在向量表示中也就更加貼近，而第二種就好像下圖中的u節點和s6節點，都是各自社群的中心，理應具有某種程度上的相似的向量表示資訊。

圖的遊走方式有兩種，深度優先DFS和廣度優先BFS，學習得到的向量表示也就更能蘊含節點的同質性和結構相似性特征，這其實也和LINE中的一階二階相似性有異曲同工的感覺。BFS傾向于在初始節點的周圍遊走，可以反映出一個節點的鄰居的微觀特性；而DFS一般會跑的離初始節點越來越遠，可以反映出一個節點鄰居的宏觀特性。具體為什麼這樣兩種遊走方式可以得到這樣的效果可以參考

node2vec添加了p和q兩個參數，來控制遊走的方式。

具體來說，如圖所示，目前節點是v，是由t節點走來，并在每條與v直接相連的邊上定義了往四個方向的跳轉機率（也即右邊的公式）。

對于參數p

• 如果

  

  也即

  

  ，那麼采樣會盡量不往回走，對應上圖的情況，就是下一個節點不太可能是上一個通路的節點t，而應當是其他的x123節點。

• 

  

  ，那麼采樣會更傾向于傳回上一個節點，這樣就會一直在起始點周圍某些節點來回轉來轉去。

對于參數q

• 

  

  ，也就是說在x1和x23之間選擇更傾向于選擇x1，x1所代表的時節點t周圍的節點，也就是說遊走會傾向于在起始點周圍的節點之間跑，可以反映出一個節點的BFS特性。

• 

  

  ，也就是說在x1和x23之間選擇更傾向于選擇x23，那麼遊走會傾向于往遠處跑，反映出DFS特性

當p=1，q=1時，遊走方式就等同于DeepWalk中的随機遊走。

代碼複現

node2vec論文源碼中主要包含了main.py和node2vec.py，下圖是對整個架構的概括：

僞代碼：

LearnFeatures需要傳入圖G，每個節點向量表示的次元d，每個節點要生成r條walk，每條walk長度為l，視窗大小k（類似于word2vec中的上下文視窗大小），參數p和q。

根據圖G（節點，邊，權重）和參數p，q生成一個Π，Π中存的是圖中每個節點以及對應的下一節點機率，将該資訊加在原圖G上，形成一個新圖G'。

接下來，疊代r此，并調用node2vecWalk對每個節點生成一個長度為l的walk（形成walk時要借助G'來決定怎麼找到下一個節點），形成的r×|V|個walk整合成一個walks序列，将其輸入到類似于w2v中，輸出一個矩陣，即我們需要的矩陣。

node2vecWalk，需要輸入帶有G'資訊的圖，需要生成walk的節點u，需要生成的walk的長度l。

walk的list第一個是u，接下來疊代l詞，每次疊代都先将walk的最後一個元素作為目前節點curr，再得到目前節點curr的周圍節點以及對應的機率資訊，得到最大的一個機率對應的下一個節點，将節點添加到walk并進行下一次疊代。

具體的複現：

（參考

Github

）

複現效果

micro-F1

（文中圖，最上面的是node2vec）

使用0.9的資料集BlogCatalog得到的Micro-F1=0.4009

可視化

使用資料量較小的wiki資料集可視化效果：（代碼見：

已經可以看到部分顔色的點有明顯的聚集現象。（可視化以及micro-F1的方法在deepwalk中已經介紹）

其他問題

如果是帶權圖：

需要采用alias_table的方法，在采樣節點的時候，需要采用此方法來既考慮到邊權的影響，又不至于耗費太大記憶體，這部分在前面學習LINE的時候已經有所說明。

别名采樣

。應用到這裡的時候，則需要先對所有的邊進行一輪别名采樣，将采樣完成後的圖再輸入到模型中，此時輸入的圖應當視為無權無向圖。