目錄

• 前言
• 1.數據導入
• 2.node2vecWalk
• • 2.1 歸一化轉移概率
  • • 2.1.1 原理解析
    • 2.1.2 Alias采樣
    • 2.1.3 代碼實現
  • 2.2 node2vecWalk的實現
• 3.LearnFeatures
• 4.參數選擇
• 5.完整代碼

前言

在KDD 2016 | node2vec：Scalable Feature Learning for Networks
中我們詳細討論了node2vec的機制，但并沒有給出代碼實現。本篇文章將從原文出發，逐步詳細地討論如何一步步實現node2vec。

1.數據導入

數據為《Les Misérables network》，也就是《悲慘世界》中的人物關系網絡：該圖是一個無向圖，圖中共77個節點、254條邊。節點表示《悲慘世界》中的人物，兩個節點之間的邊表示這兩個人物出現在書的同一章，邊的權重表示兩個人物（節點）出現在同一章中的頻率。

import networkx as nx G = nx.les_miserables_graph()

原文中node2vec的算法描述如下：

其中node2vecWalk用于產生一個從節點$u$開始的長為$l$的游走序列，LearningFeatures利用所有節點產生的游走序列來進行word2vec，得到每個節點的向量表示。

下面我將結合原文詳細介紹這兩個算法！！

2.node2vecWalk

2.1 歸一化轉移概率

2.1.1 原理解析

node2vecWalk算法的偽代碼描述如下：

將初始節點$u$加入到walk中

當前節點curr為walk中最后一個節點

根據curr和其對周圍節點的轉移概率選擇下一個節點$s$，并將其加入walk

當walk長度為$l$時采集結束，返回walk

描述比較模糊，我們再看看原文：

當前節點是$v$，下一個要采集的節點是$x$，則我們有如下概率公式：

可以發現，我們只會采樣跟當前節點$v$間有邊存在的節點，對于不與當前節點$v$相連的節點，我們不會去采樣。

采樣概率是一個歸一化的轉移概率：$\frac{{\pi }_{vx}}{Z}$，原文中${\pi }_{vx}$的描述為：


觀察上圖：節點$t$已經被采樣了，緊接著我們采樣了節點$v$，現在需要做的是采樣$v$之后的下一次采樣。根據前文所述，我們只會在節點$v$的鄰接節點中選擇一個進行采樣，也就是在三個$x$中進行采樣。這個時候${\pi }_{vx}={\alpha }_{pq}(t,x)?w_{vx}$，其中$w_{vx}$表示兩個節點間的權重（如果是無權圖，則權重為1）

但是存在一個問題： 如果我們是進行第二次采樣（第一次是初始結點$u$），則有$v=u$，$x$表示與$u$相連的節點。這個時候我們就會發現沒法利用${\pi }_{vx}={\alpha }_{pq}(t,x)?w_{vx}$來計算兩個節點間的轉移概率，因為不存在節點$t$，也就沒法計算${\alpha }_{pq}(t,x)$！！

解決： 此時的${\pi }_{vx}$就是$w_{vx}$。

因此，第一步的思路就很明確了：

如果當前要進行第二次采樣，我們就算出第一個節點$u$到其所有節點的歸一化轉移概率：非歸一化轉移概率${\pi }_{vx}$就是節點$u$與其鄰接節點相連邊的權重（可能不在01間），歸一化就是將所有概率變換到01之間：所有概率除以歸一化常數$Z$，$Z$為這些權重之和。

否則，我們則根據當前節點$v$和上一個被采樣的節點$t$，算出$v$到其所有鄰接節點$x$的非歸一化轉移概率：${\pi }_{vx}={\alpha }_{pq}(t,x)?w_{vx}$，然后同樣除以它們的和來進行歸一化。

2.1.2 Alias采樣

當我們有了當前節點對其所有鄰接節點的轉移概率后，我們應該怎么選擇？是選擇一個轉移概率最大的節點進行采樣嗎？

答案顯而易見，肯定不是！ 原文中算法描述如下：

可以看到作者采用了一種叫做AliasSample的采樣方法，AliasSample，又名“別名采樣”，是一種比較經典的采樣算法。比如：游戲中經常遇到按一定的掉落概率來隨機掉落指定物品的情況，例如掉落銀幣25%，金幣20%, 鉆石10%，裝備5%，飾品40%。現在要求下一個掉落的物品類型，或者說一個掉落的隨機序列，要求符合上述概率。

在本文中可以描述為：我們已經有了待選節點集，也有了選擇它們的概率，現在我們要進行下一次選擇，要求該選擇符合上述概率要求。

在Alias Sample中，我們輸入一個概率列表，最后會得到兩個數組：Prob和Ailas

然后：隨機取某一列$k$(即[1,4]的隨機整數)，再隨機產生一個[0-1]的小數$c$，如果$Prob[k]>c$，那么采樣結果就是$k$，反之則為Alias[k]。

關于Alias Sample的詳細原理可以參考：Alias Sample，這里不再詳細介紹。

2.1.3 代碼實現

有了以上思路后我們就很容易編寫代碼了：

對于第一種情況：我們可以初始化一個字典nodes_info，nodes_info[node]表示與node有關的所有信息，其中nodes_info[node][0]和nodes_info[node][1]分別表示輸入當前node與其鄰接點的轉移概率列表后得到的Alias數組和Prob數組。

對于第二種情況，我們可以初始化一個字典edges_info，其中edges_info[(t, v)][0]和edges_info[(t, v)][1]分別表示輸入$v$到所有$x$的轉移概率列表后得到的Alias數組和Prob數組。

因此，代碼實現如下：

def init_transition_prob(self):""":return:歸一化轉移概率矩陣"""g = self.Gnodes_info, edges_info = {}, {}for node in g.nodes:nbs = sorted(g.neighbors(node)) # 當前節點的鄰居節點probs = [g[node][n]['weight'] for n in nbs] # 概率就是權重# 歸一化norm = sum(probs) # 求和normalized_probs = [float(n) / norm for n in probs] # 歸一化nodes_info[node] = self.alias_setup(normalized_probs) # 利用Alias采樣得到Alias和Probfor edge in g.edges:# 有向圖if g.is_directed():edges_info[edge] = self.get_alias_edge(edge[0], edge[1])# 無向圖else:edges_info[edge] = self.get_alias_edge(edge[0], edge[1])edges_info[(edge[1], edge[0])] = self.get_alias_edge(edge[1], edge[0])self.nodes_info = nodes_infoself.edges_info = edges_info

其中alias_setup函數就是Alias Sample的具體實現，代碼直接參考了網上現成的：

def alias_setup(self, probs):""":probs: v到所有x的概率:return: Alias數組與Prob數組"""K = len(probs)q = np.zeros(K) # 對應Prob數組J = np.zeros(K, dtype=np.int) # 對應Alias數組# Sort the data into the outcomes with probabilities# that are larger and smaller than 1/K.smaller = [] # 存儲比1小的列larger = [] # 存儲比1大的列for kk, prob in enumerate(probs):q[kk] = K * prob # 概率if q[kk] < 1.0:smaller.append(kk)else:larger.append(kk)# Loop though and create little binary mixtures that# appropriately allocate the larger outcomes over the# overall uniform mixture.# 通過拼湊，將各個類別都湊為1while len(smaller) > 0 and len(larger) > 0:small = smaller.pop()large = larger.pop()J[small] = large # 填充Alias數組q[large] = q[large] - (1.0 - q[small]) # 將大的分到小的上if q[large] < 1.0:smaller.append(large)else:larger.append(large)return J, q

對于不是第二次采樣的情況，需要利用get_alias_edge來得到一條邊$(t,v)$中$v$到其鄰居節點轉移概率的Alias數組和Prob數組：

def get_alias_edge(self, t, v):"""Get the alias edge setup lists for a given edge."""g = self.Gp = self.pq = self.qunnormalized_probs = []for v_nbr in sorted(g.neighbors(v)):if v_nbr == t:unnormalized_probs.append(g[v][v_nbr]['weight'] / p)elif g.has_edge(v_nbr, t):unnormalized_probs.append(g[v][v_nbr]['weight'])else:unnormalized_probs.append(g[v][v_nbr]['weight'] / q)norm_const = sum(unnormalized_probs)normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]return self.alias_setup(normalized_probs)

代碼很容易理解：考慮v的鄰居節點v_nbr：如果v_nbr就是t，則非歸一化轉移概率為$\frac{1}{p}\times w$；如果v_nbr與t間有邊，也就是圖中$x_1$，則${\alpha }_{pq}(t,x)=1$，即非歸一化轉移概率為$1\times w$；否則就是圖中$x_2,x_3$這種情況，非歸一化轉移概率為$\frac{1}{q}\times w$。$w$是兩個節點間邊的權重。

有了非歸一化轉移概率后，我們再進行歸一化（除以和），最后再利用alias_setup函數獲得Alias數組和Prob數組。

當我們有了各個節點間的轉移概率時，我們在真正采樣時需要做出決策，在這些相鄰結點中選擇一個作為下一個被采樣的節點：隨機取某一列$k$(即[1,n]的隨機整數，n為鄰居節點的個數)，再隨機產生一個[0-1]的小數$c$，如果$Prob[k]>c$，那么采樣結果就是$k$，反之則為Alias[k]。該采樣函數實現較為簡單：

def alias_draw(self, J, q):"""輸入: Prob數組和Alias數組輸出: 一次采樣結果"""K = len(J)# Draw from the overall uniform mixture.kk = int(np.floor(npr.rand() * K)) # 隨機取一列# Draw from the binary mixture, either keeping the# small one, or choosing the associated larger one.if npr.rand() < q[kk]: # 比較return kkelse:return J[kk]

其中kk或者J[kk]就是我們最終采樣的結果。

2.2 node2vecWalk的實現

有了轉移概率以及采樣策略后，我們就能輕松實現node2vecWalk了：

實現代碼如下：

def node2vecWalk(self, u):walk = [u]g = self.Gl = self.lnodes_info, edges_info = self.nodes_info, self.edges_infowhile len(walk) < l:curr = walk[-1]v_curr = sorted(g.neighbors(curr))if len(v_curr) > 0:if len(walk) == 1:walk.append(v_curr[self.alias_draw(nodes_info[curr][0], nodes_info[curr][1])])else:prev = walk[-2]ne = v_curr[self.alias_draw(edges_info[(prev, curr)][0], edges_info[(prev, curr)][1])]walk.append(ne)else:breakreturn walk

下面對重要代碼進行解析：

curr = walk[-1] v_curr = sorted(g.neighbors(curr))

首先得到當前路徑中的最后一個節點curr，并得到它的所有鄰居節點v_curr。

walk.append(v_curr[self.alias_draw(nodes_info[curr][0], nodes_info[curr][1])])

如果curr的鄰居節點不為空且當前walk的長度為1，即我們前面提到的第一種情況：進行第二次采樣。那么這個時候我們就需要利用Alias Sample從其所有鄰居節點中選擇一個節點：nodes_info[curr][0]和nodes_info[curr][1]分別代表Alias數組和Prob數組。

prev = walk[-2] ne = v_curr[self.alias_draw(edges_info[(prev, curr)][0], edges_info[(prev, curr)][1])]

如果當前不是進行第二次采樣，則分別找到$t$和$v$，也就是prev和curr，然后進行Alias Sample。

最終返回的walk即為從$u$開始的一條長為$l$的隨機游走路徑。

3.LearnFeatures

具體步驟：

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

一共要進行$r$次循環，每一次循環要為圖中每個節點都生成一個長度為$l$的游走序列

第iter次循環中對所有節點都利用node2vec算法生成一個隨機游走序列walk，然后將其加入walks

得到所有節點的$r$個隨機游走序列后，利用SGD方法得到每一個節點的向量表示。

代碼實現：

def learning_features(self):g = self.Gwalks = []nodes = list(g.nodes())for iter in range(self.r):np.random.shuffle(nodes)for node in nodes:walk = self.node2vecWalk(node)walks.append(walk)# embeddingwalks = [list(map(str, walk)) for walk in walks]model = Word2Vec(sentences=walks, vector_size=self.d, window=self.k, min_count=0, sg=1, workers=3)f = model.wvreturn f

walks中存儲中每一個節點的$r$條長為$l$的隨機游走路徑，輸出前兩條：

['MmeBurgon', 'Gavroche', 'Mabeuf', 'Feuilly', 'Gavroche', 'MmeBurgon', 'Gavroche', 'Bossuet', 'Enjolras', 'Feuilly', 'Mabeuf', 'MotherPlutarch', 'Mabeuf', 'Courfeyrac', 'Bossuet', 'Combeferre', 'Courfeyrac', 'Combeferre', 'Bossuet', 'Enjolras', 'Feuilly', 'Enjolras', 'Claquesous', 'Montparnasse', 'Brujon', 'Babet', 'Valjean', 'Toussaint', 'Cosette', 'Valjean', 'Woman1', 'Valjean', 'Cosette', 'Marius', 'Bossuet', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Combeferre', 'Gavroche', 'Bahorel', 'Feuilly', 'Bossuet', 'MmeHucheloup', 'Bossuet', 'Combeferre', 'Courfeyrac', 'Enjolras', 'Valjean', 'Marius', 'Eponine', 'Marius', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Enjolras', 'Valjean', 'Marius', 'Gillenormand', 'MlleGillenormand', 'MmePontmercy', 'MlleGillenormand', 'Gillenormand', 'Cosette', 'Thenardier', 'Brujon', 'Gavroche', 'MmeHucheloup', 'Gavroche', 'Combeferre', 'Feuilly', 'Prouvaire', 'Bossuet', 'Enjolras', 'Valjean', 'Thenardier', 'MmeThenardier', 'Cosette', 'Valjean', 'MmeDeR'] ['Feuilly', 'Bossuet', 'Bahorel', 'Prouvaire', 'Enjolras', 'Marius', 'Cosette', 'Javert', 'Valjean', 'Cosette', 'Valjean', 'Marguerite', 'Fantine', 'Dahlia', 'Favourite', 'Listolier', 'Blacheville', 'Fantine', 'Marguerite', 'Fantine', 'Zephine', 'Listolier', 'Tholomyes', 'Blacheville', 'Fameuil', 'Fantine', 'Marguerite', 'Fantine', 'Javert', 'Thenardier', 'Valjean', 'Enjolras', 'Claquesous', 'Thenardier', 'Marius', 'Cosette', 'MlleGillenormand', 'Gillenormand', 'Valjean', 'Thenardier', 'Boulatruelle', 'Thenardier', 'Cosette', 'Marius', 'Eponine', 'Claquesous', 'Javert', 'Valjean', 'Javert', 'Thenardier', 'Javert', 'Enjolras', 'Grantaire', 'Combeferre', 'Gavroche', 'Joly', 'Marius', 'Cosette', 'Valjean', 'Javert', 'Babet', 'Claquesous', 'Enjolras', 'Feuilly', 'Combeferre', 'Bahorel', 'Courfeyrac', 'Enjolras', 'Marius', 'Thenardier', 'Javert', 'Valjean', 'Isabeau', 'Valjean', 'Fauchelevent', 'Gribier', 'Fauchelevent', 'Javert', 'Enjolras', 'Marius']

可以看到第一條隨機游走路徑是以節點MmeBurgon開始的，第二條是從節點Feuilly開始的，兩條路徑長度都為$l$。

有了walks之后，我們利用gensim庫中的Word2Vec進行訓練，進而得到所有節點的向量表示：

model = Word2Vec(sentences=walks, vector_size=self.d, window=self.k, min_count=0, sg=1, workers=3)

其中：

sentences是我們要分析的語料，在node2vec中就是隨機游走路徑的集合。

vector_size是節點向量的維度，這里為$d$。

window是詞向量上下文最大距離，即Skip-Gram和CBOW中窗口的長度，默認值為5。

min_cout：可以對字典做截斷，詞頻少于min_count次數的單詞會被丟棄掉，默認值為5，這里設置為0。

sg：模型選擇，sg=1表示采用Skip-Gram模型，sg=0表示采用CBOW模型，默認為0，這里選擇Skip-Gram模型。

workers：訓練并行數，這里選擇3。

最終，f中存儲著所有節點的長度為$d$的向量表示，任意輸出一個：

print(f['MmeBurgon'])

MmeBurgon節點的向量表示為：

[-0.05092877 -0.02686426 -0.2292252 0.11856086 0.02136412 0.01406081-0.26274496 -0.15402426 0.1976506 -0.03906344 -0.1944654 0.03440150.17913733 0.08412573 0.14779484 -0.00783093 -0.17162482 -0.28095236-0.32425568 0.2492605 0.14210573 -0.06607451 0.40488595 -0.15641351-0.01836408 0.0923218 -0.07496541 0.1163046 0.01180712 0.24809936-0.04660206 -0.36390662 -0.20256323 -0.07164664 -0.03223448 0.06946431-0.28120005 -0.14545655 0.2894095 -0.00597684 -0.2806793 -0.025172080.21234442 -0.35515746 0.03860907 0.12777379 0.31198564 -0.04142399-0.06592249 -0.01730651 0.06897946 -0.26776454 -0.00844726 -0.137025740.23738769 -0.23513325 0.05750211 0.01762778 -0.03779545 -0.290608820.1997382 0.012223 -0.23850201 -0.16767174 0.0212742 0.117177730.08926564 0.10213668 -0.07187556 -0.02068917 0.07960241 -0.150149390.1681073 0.12445314 0.13363989 -0.23188415 -0.17411086 0.23457739-0.13661143 0.3249664 -0.07310021 0.24981983 -0.01397824 0.28996238-0.02117981 -0.12742186 0.33266178 0.07946197 0.29308477 0.05445471-0.00712562 -0.06370848 0.16291171 -0.04468412 0.33400518 -0.19028513-0.2808339 0.01152208 -0.13062981 -0.27341706 -0.20656888 0.22132947-0.20722346 -0.05620798 -0.33125588 0.05310262 -0.17866907 0.203493030.09851206 0.03873271 -0.20351988 0.15531495 -0.09796275 -0.20567754-0.16734612 0.04089455 0.22214974 0.29019567 -0.0675301 -0.25800622-0.19473355 0.30337527 -0.3567541 0.11847463 0.00324172 -0.10936202-0.07167141 -0.01137679]

4.參數選擇

參數為DeepWalk和LINE的典型值：

返回參數$p$和出入參數$q$的選擇：$p=1,q=0.5$

if __name__ == '__main__':p, q = 1, 0.5d, r, l, k = 128, 10, 80, 10G = nx.les_miserables_graph()node2vec = node2vec(G, p, q, d, r, l, k)model = node2vec.learning_features()

5.完整代碼

我把數據和代碼放在了GitHub上：完整代碼，原創不易，下載時請隨手給個follow和star，感謝！

總結

以上是生活随笔為你收集整理的node2vec代码实现及详细解析的全部內容，希望文章能夠幫你解決所遇到的問題。

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