圖嵌入方法之Node2vec

（Ⅰ）主要思想

node2vec的思想同DeepWalk一樣：生成隨機游走，對隨機游走采樣得到（節點，上下文）的組合，然后用處理詞向量的方法對這樣的組合建模得到網絡節點的表示。不過在生成隨機游走過程中做了一些創新。

DeepWalk介紹見我另一篇博客

（Ⅱ）核心介紹

Node2vec是DeepWalk的一個改進，只是隨機游走的差異很小。它有參數P和Q。參數Q定義了random walk發現圖中未發現部分的概率，而參數P定義了random walk返回到前一個節點的概率。參數P控制節點周圍微觀視圖的發現。參數Q控制較大鄰域的發現。它可以推斷出社區和復雜的依賴關系。

下圖中顯示了Node2vec中一個隨機行走步長的概率。我們只是從紅結點走了一步到綠結點。返回到紅色節點的概率是1/P，而返回到與前一個(紅色)節點沒有連接的節點的概率是1/Q。到紅結點相鄰結點的概率是1。

所以node2vec節點采樣的概率如上所示。
參數p、q的意義分別如下：

返回概率p：

• 如果 p > max(q,1) ，那么采樣會盡量不往回走，對應上圖的情況，就是下一個節點不太可能是上一個訪問的節點t。
• 如果 p < max(q,1) ，那么采樣會更傾向于返回上一個節點，這樣就會一直在起始點周圍某些節點來回轉來轉去。

出入參數q：

• 如果 q > 1 ，那么游走會傾向于在起始點周圍的節點之間跑，可以反映出一個節點的BFS特性。
• 如果 q < 1 ，那么游走會傾向于往遠處跑，反映出DFS特性。

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

（Ⅲ）偽代碼賞析

首先看一下算法的參數，圖G、表示向量維度d、每個節點生成的游走個數r，游走長度l，上下文的窗口長度k，以及之前提到的p、q參數。

根據p、q和之前的公式計算一個節點到它的鄰居的轉移概率。

將這個轉移概率加到圖G中形成G’。

walks用來存儲隨機游走，先初始化為空。

外循環r次表示每個節點作為初始節點要生成r個隨機游走。

然后對圖中每個節點。

生成一條隨機游走walk。

將walk添加到walks中保存。

然后用SGD的方法對walks進行訓練。

第6步中一條walk的生成方式如下：

將初始節點u添加進去。

walk的長度為l，因此還要再循環添加l-1個節點。

當前節點設為walk最后添加的節點。

找出當前節點的所有鄰居節點。

根據轉移概率采樣選擇某個鄰居s。

將該鄰居添加到walk中。

https://zhuanlan.zhihu.com/p/100586855
https://zhuanlan.zhihu.com/p/46344860

總結

以上是生活随笔為你收集整理的图嵌入方法基础学习之Node2vec的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。