參考文章：Alias Method離散分布隨機取樣 | 天空的城在圖的隨機游走中，有一塊需要隨機取樣， 比如當前到達v節點，那么下一次隨機會到達哪個節點。這種問題其實就是離散分布的隨機變量的取樣問題。 查了一些資料， 發現Alias Method 是一種很高效的方式。https://shomy.top/2017/05/09/alias-method-sampling/

【Graph Embedding】node2vec:算法原理，實現和應用_淺夢的學習筆記-CSDN博客_node2vec前面介紹過基于DFS鄰域的DeepWalk和基于BFS鄰域的LINE。node2vec則是一種綜合考慮dfs鄰域和bfs鄰域的graph embedding方法。DeepWalk：算法原理，實現和應用LINE：算法原理，實現和應用簡單來說，node2vec是deepwalk的一種擴展，可以看作是結合了dfs和bfs隨機游走的deepwalk。nodo2vec 算法原理優化目標設f(u)...https://blog.csdn.net/u012151283/article/details/87081272?spm=1001.2014.3001.5502

參考視頻：【圖神經網絡】GNN從入門到精通_嗶哩嗶哩_bilibili課程已經更新完畢，PPT，論文，代碼在置頂評論下載。結合論文和源碼，才能到達最好效果https://www.bilibili.com/video/BV1K5411H7EQ?p=5

Code：

論文鏈接：

---

DeepWalk可以認為是random walk + skip_gram的模型

random walk本質上是一個DFS（深度優先探索）的過程，丟失了BFS（廣度優先探索）的鄰居結構信息；而node2vec可以簡單的解釋為對deepwalk的隨機過程優化，綜合考慮了DFS和BFS的游走方式，提出了一個biased random walk，訓練仍然是skip_gram

node2vec 使用了一個變量a來控制節點的走向，而a是由參數p,q控制的

?在上圖中，我們已經從 t 節點走到了 V節點。然后我們要，求下一次游走到其他節點的概率，我們定義V節點到下一個節點的概率為，從公式里我們可以看出節點v到節點x的概率? π vx= 上一個節點 t?游走到節點 x?的概率? *? Wvx。Wvx表示節點V到節點x的邊的權重大小，這里我著重看一下αpq（t,x）

?我們可以看到α（pq）總共分為三種情況（說明一下，下面的x和上面圖中的x1,2,3節點沒什么關系，下面的x表示一個未知節點）：

（1）如果距離d(tx) = 0：我們從上面圖中可以看到，距離t節點距離為0的節點只有 t 節點本身，或者我們從t節點出發到 x節點 然后再返回到t節點，即（t? - x - t）,那么我們αpq（t,x）的概率此時為為 1/ p，那我們 節點 v 到 節點 t 的概率π vx就為

?（2）如果距離d(tx) = 1:我們從上圖中可以看到? ，距離t節點距離為1的節點有z節點和x1節點，也就是說我們t節點游走到v節點之后在走到z和x1節點的概率αpq（t,x）是等于1的，那么我們 節點v到節點x1的概率π vx =?，但是節點v到節點z的概率 = 0，因為節點v和節點z之間沒有節點相連接，即Wvz = 0

?（3）如果距離d(tx) = 2:我們從上圖中可以看到? ，距離 t節點距離為2的節點有x2節點和x3節點，也就是說我們 t節點 游走到 v節點 之后在走到x2和x3節點的概率αpq（t,x）是等于1 / q 的，那么我們 節點v到節點x2，x3的概率 π vx =

---

?上面我們說了，α是由參數p和q來控制的

• 參數??：表示節點之間的最短路徑，取值為0,1,2

• 參數 p ：返回參數，控制重新采樣上一步已訪問節點的概率。

  參數p并不直接控制整個游走過程時DFS還是BFS，只控制游走的區域是一直接近起點還是逐漸遠離起點
• q：出入參數，控制采樣的方向。

  • 當參數 q > 1 時，接下來采樣的節點傾向于向? t 靠近，偏向于bfs；

  • 當參數? q < 1時，接下來采樣的節點傾向于向? t 遠離，偏向于dfs；

?可以發現，當 p = q = 1? 時，node2vec就是一個deepwalk模型了

?學習算法

采樣完頂點序列后，剩下的步驟就和deepwalk一樣了，用word2vec去學習頂點的embedding向量。
值得注意的是node2vecWalk中不再是隨機抽取鄰接點，而是按概率抽取，node2vec采用了Alias算法進行頂點采樣。下面這個鏈接對Alias的講解非常通俗易懂
Alias Method離散分布隨機取樣 | 天空的城在圖的隨機游走中，有一塊需要隨機取樣， 比如當前到達v節點，那么下一次隨機會到達哪個節點。這種問題其實就是離散分布的隨機變量的取樣問題。 查了一些資料， 發現Alias Method 是一種很高效的方式。https://shomy.top/2017/05/09/alias-method-sampling/

node2vecWalk

通過上面的偽代碼可以看到，node2vec和deepwalk非常類似，主要區別在于頂點序列的采樣策略不同，所以這里我們主要關注node2vecWalk的實現。

由于采樣時需要考慮前面2步訪問過的頂點，所以當訪問序列中只有1個頂點時，直接使用當前頂點和鄰居頂點之間的邊權作為采樣依據。 當序列多余2個頂點時，使用文章提到的有偏采樣。

def node2vec_walk(self, walk_length, start_node):G = self.G alias_nodes = self.alias_nodes alias_edges = self.alias_edgeswalk = [start_node]while len(walk) < walk_length: cur = walk[-1] cur_nbrs = list(G.neighbors(cur)) if len(cur_nbrs) > 0: if len(walk) == 1: walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])]) else: prev = walk[-2] edge = (prev, cur) next_node = cur_nbrs[alias_sample(alias_edges[edge][0],alias_edges[edge][1])] walk.append(next_node) else: breakreturn walk

構造采樣表

preprocess_transition_probs分別生成alias_nodes和alias_edges，alias_nodes存儲著在每個頂點時決定下一次訪問其鄰接點時需要的alias表（不考慮當前頂點之前訪問的頂點）。alias_edges存儲著在前一個訪問頂點為 t??，當前頂點為??V時決定下一次訪問哪個鄰接點時需要的alias表。

get_alias_edge方法返回的是在上一次訪問頂點 t??，當前訪問頂點為 v?時到下一個頂點 x?的未歸一化轉移概率?

def get_alias_edge(self, t, v):G = self.G p = self.p q = self.qunnormalized_probs = [] for x in G.neighbors(v): weight = G[v][x].get('weight', 1.0)# w_vx if x == t:# d_tx == 0 unnormalized_probs.append(weight/p) elif G.has_edge(x, t):# d_tx == 1 unnormalized_probs.append(weight) else:# d_tx == 2 unnormalized_probs.append(weight/q) norm_const = sum(unnormalized_probs) normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs]return create_alias_table(normalized_probs)def preprocess_transition_probs(self):G = self.Galias_nodes = {} for node in G.nodes(): unnormalized_probs = [G[node][nbr].get('weight', 1.0) for nbr in G.neighbors(node)] norm_const = sum(unnormalized_probs) normalized_probs = [float(u_prob)/norm_const for u_prob in unnormalized_probs] alias_nodes[node] = create_alias_table(normalized_probs)alias_edges = {}for edge in G.edges(): alias_edges[edge] = self.get_alias_edge(edge[0], edge[1])self.alias_nodes = alias_nodes self.alias_edges = alias_edgesreturn

node2vec應用

使用node2vec在wiki數據集上進行節點分類任務和可視化任務。 wiki數據集包含 2,405 個網頁和17,981條網頁之間的鏈接關系，以及每個網頁的所屬類別。 通過簡單的超參搜索，這里使用p=0.25,q=4的設置。

本例中的訓練，評測和可視化的完整代碼在下面的git倉庫中，

G = nx.read_edgelist('../data/wiki/Wiki_edgelist.txt',create_using=nx.DiGraph(),nodetype=None,data=[('weight',int)])model = Node2Vec(G,walk_length=10,num_walks=80,p=0.25,q=4,workers=1) model.train(window_size=5,iter=3) embeddings = model.get_embeddings()evaluate_embeddings(embeddings) plot_embeddings(embeddings)

總結

以上是生活随笔為你收集整理的Graph Embedding：Node2Vec的全部內容，希望文章能夠幫你解決所遇到的問題。

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