前言

繼DeepWalk后，我們再來看一種基于隨機游走策略的圖嵌入方法——Node2Vec，有點像前者的升級版本，有了前者的基礎，理解起來會快很多。

核心方法

Node2Vec與DeepWalk最大的不同(甚至是唯一的不同)就是在于節點序列的生成機制。DeepWalk在每一步探索下一個節點時，是在其鄰居節點中進行隨機選擇，然后基于深度優先策略生成一個固定長度的節點序列。而Node2Vec在生成節點序列時，引入了更加靈活的機制，通過幾個超參數來控制向不同方向生長的概率。其核心思路用以下三個圖足以充分體現：

在github上可以看其源代碼是這樣的：

def node2vec_walk(self, walk_length, start_node):

'

Simulate a random walk starting from start node.

'

G = self.G

alias_nodes = self.alias_nodes

alias_edges = self.alias_edges

walk = [start_node]

while len(walk) < walk_length:

cur = walk[-1]

cur_nbrs = sorted(G.neighbors(cur))

if len(cur_nbrs) > 0:

if len(walk) == 1:

walk.append(cur_nbrs[alias_draw(alias_nodes[cur][0], alias_nodes[cur][1])])

else:

prev = walk[-2]

next = cur_nbrs[alias_draw(alias_edges[(prev, cur)][0],

alias_edges[(prev, cur)][1])]

walk.append(next)

else:

break

return walk

可見找到當前節點cur的鄰居后，關鍵就是用alias\_draw方法去按某個概率選出來下一個前進的節點。事實上，這個方法并不陌生，在LINE方法的圖嵌入(《LINE: Large-scale Information Network Embedding》)當中也使用了同樣的技巧。這個方法很有趣，所以可以稍微展開一下。

alias抽樣

在討論方法前，可從代碼上感受一下它是干啥的，在Node2vec的源碼中可以看到它的實現邏輯很精煉：

def alias_setup(probs):

K = len(probs)

q = np.zeros(K)

J = np.zeros(K, dtype=np.int)

smaller = []

larger = []

for kk, prob in enumerate(probs):

q[kk] = K*prob

if q[kk] < 1.0:

smaller.append(kk)

else:

larger.append(kk)

while len(smaller) > 0 and len(larger) > 0:

small = smaller.pop()

large = larger.pop()

J[small] = large

q[large] = q[large] + q[small] - 1.0

if q[large] < 1.0:

smaller.append(large)

else:

larger.append(large)

return J, q

def alias_draw(J, q):

'

Draw sample from a non-uniform discrete distribution using alias sampling.

'

K = len(J)

kk = int(np.floor(np.random.rand()*K))

if np.random.rand() < q[kk]:

return kk

else:

return J[kk]

我們手工來一批抽樣，感受一下它的產出是怎樣的：

可見它實現了一個按指定概率抽樣事件的效果，據說這個執行效率是O(1)的，所以應用范圍還是較廣的。下面來快速了解下內在的執行過程，參考資料中3、4可以用來了解原理。假設我們有事件0，1，2，3，我們想分別以概率0.2, 0.2, 0.3, 0.3來抽樣對應的事件，手工示意一下過程中的細節如下圖所示：

如果直接在python中執行上述的alias_setup, 可見輸出的J數組與示意圖中一致，代表了每個位置上被哪個事件來填充過。q數組每個值代表被該位置上數值被其它事件填充前(小于1的時候)分別是多少。

最后在alias_draw中其實生成了兩次隨機數字，kk = int(np.floor(np.random.rand()*K)) 生成了一個隨機索引值，這一個均勻分布的抽樣，抽到每個事件的概率是相等的，都是1/K；然后np.random.rand()又生成了一個(0,1)區間內的隨機數，如果這個值小于q數組中對應索引位置上的原始值，則返回該索引位置對應的事件，否則直接返回那個被拿來填充了該位置的事件，而每個位置上被誰填充過，正是已經保存到J數組中了，所以直接讀J[kk]即可。

向量化表達

插播結束，繼續回來看Node2Vec。根據上述的原則生成了節點序列后，下一步就是進行向量化表達了，這里與DeepWalk就更加統一了，甚至源代碼中就是直接引用了gensim.models中的Word2Vec方法。

這個方法執行的過程中使用的一個優化小技巧值得提一提：負采樣(Negative Sampling)，因為這個方法最近在不同的地方有看到，感覺是個比較有用的思想，所以也可以稍微提一下。

負采樣

要解決的問題：每一個訓練樣本都會去調整SkipGram模型中的每一個參數(這個數量是非常非常多的)，嚴重影響性能。

方法：每一個訓練樣本僅更新一小部分權重，即一個positive word對應的神經元權重 ，外加K個negative word對應的神經元權重。每個negative word補選中的概率正比于其詞頻，一個經驗值公式為：

參考資料

總結

以上是生活随笔為你收集整理的node2vec python_图上的机器学习系列-聊聊Node2vec的全部內容，希望文章能夠幫你解決所遇到的問題。

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