一.引言

前面介紹了如何生成帶權的圖:?GraphEmbedding - networkx獲取圖結構

從帶權的圖隨機游走生成序列:?GraphEmbedding - DeepWalk 隨機游走

embedding 向量的評估與可視化:?GraphEmbedding - embedding 向量的降維與可視化

以及復雜度O(1)的采樣算法 Alias:?GraphEmbedding - Alias 采樣圖文詳解

還有二叉樹搜索的 DFS 與 BFS:?二叉樹的遍歷 DFS 與 BFS

結合上面5個知識點，今天引出 Node2vec 算法，Node2vec 結合了上面幾篇文章的內容，同時也引進了自己的創新，比 DeepWalk 更常見也更有效。

二.Node2vec 算法

1.Node2vec 簡介

說起 Node2vec 還是要提一下?DeepWalk，DeepWalk 基于圖隨機游走，默認各個邊的權重為1，其更偏向于 DFS 即深度優先搜索，DFS 的好處是搜索的全局性好，但是對于較遠的鄰居的 embedding 表征作用不大，這時還有 BFS 廣度優先搜索，其對周圍鄰居的覆蓋程度較高，但是搜索偏局部，無法感知稍遠的鄰居節點，Node2vec 的出現就是結合 DFS 與 BFS 的優點，從而對局部和全局進行了折中，得到了質量更高的采樣序列。

2.Node2vec 理論

A.基于 Edge 的轉移概率

? ? ? ?

上面提到了DFS 和 BFS，在 Node2vec 中，通過 p,q 參數控制游走更偏向于全局搜索 DFS 還是局部搜索 BFS，假設當前節點從 t 走到 v 點，從 v 選擇下一個鄰居節點時，不再是等概率隨機選擇，而是對原始權重進行 P,Q修正，最終歸一化得到選擇不同節點的概率。

?代表v的鄰居與上一個起始點t的關系

=0 代表v又重新返回起始點t，其邊權重的修正參數為 α=1/p

=1 代表從新起點v出發到達的下一個鄰居和上一個起始點t也存在邊的關系，此時距離為1,α=1

=2 代表從新起點v出發到達的下一個鄰居與上一個起始點t不存在關系，所以距離為2, α=1/q

基于調節參數 ?和邊的原始權重???可以得到上一條路徑為 t -> v，v向其鄰居??的整體轉移概率，我們稱之為基于edge的轉移概率:

?????????????????????????????????

B.基于 Node 的轉移概率?????????????????????????

除了基于 edge 的轉移概率，還有最基礎的基于節點的轉移概率，此時不考慮p,q參數，因為不涉及距離問題，從頂點 u 出發到任意u的鄰居其距離均為1，所以??均為1，此時 α=1，原始權重為?，對于任意一點 v，v向其鄰居??的整體轉移概率，我們稱之為基于 node 的轉移概率:

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?

?C.采樣

基于圖中所有 Node 的轉移概率與 Edge 的轉移概率，結合 Alias 生成 AliasTable，后續按概率 AliasSample 即可，通過調整 p,q 參數，調整游走序列在 DFS 和 BFS 的偏重：

P: 采樣中 p 控制從 v 回到起始點 t 的概率，所以是回撤概率，p越大，回撤的概率越小

Q: 采樣中 q 控制 t->v-> 新節點的概率，如果 q > 1 游走偏向于訪問局部的節點(BFS)，因為此時 1>1/q ，如果 q < 1，游走偏向于訪問全局的節點(DFS)，因為此時 1 < 1/q

3.Node2vec 偽代碼

A.node2vecWalk

這部分負責隨機游走生成關注關系序列，需要用到原始node u，游走長度 l，對當前節點進行 AliasSample 獲取游走序列

B.LearnFeatures

除了初始化游走長度外，定義向量維度 d，回撤概率 p，轉出概率 q，最后通過?stochastic gradient descent 隨機梯度下降的學習器對 walk 得到的的多個序列 walks 訓練，得到每個節點的 embedding，這里常用的是 Word2vec

?三.Node2vec 實踐

根據上面的 node2vevWalk 與 leranFeatures 我們大致理一下需要哪些步驟:

A.生成一個帶權的關注關系圖，并獲取圖中節點，邊以及對應的權重

B.為每一個點，每一條邊生成基于 Node 和基于 Edge 的轉移概率并生成 Alias Table

C.根據epoch和walk length 以及 Alias Table 進行 Alias Sample 獲取游走序列

D.通過 Word2vec 方法對數據訓練并獲得向量 Embedding

跟隨上面的思路操作一下

1.生成帶權圖

1-1?構造圖通過 Random 隨機模擬關注關系圖的原始節點與權重，node_num 控制節點數，sample_num 控制該關系圖的邊的大致數量

1-2?獲取帶權圖，通過 networkx 讀取 1.1 生成的圖并加載權重 weight

1-3?通過 .nodes() 和 .edges() 方法獲取模擬圖的節點與邊

# 1-1 構造圖edge_file = "./data/test_edges.txt"node_num = 100sample_num = 1000def createGraph():f = open(edge_file, "w")for i in range(sample_num):from = random.randint(0, node_num)to = random.randint(0, node_num)weight = random.random()if from != to:f.write("%s %s %s\n" % (from, to, weight))f.close()createGraph()# 1-2 獲取帶權圖def loadGraph(fileName):G = nx.read_edgelist(fileName, create_using=nx.DiGraph(), nodetype=None, data=[('weight', float)])return GG = loadGraph(edge_file)# 1-3 獲取圖的節點與邊nodes = G.nodes()edges = G.edges()nodes_list = list(nodes)

2.生成Alias Table

2.1?create_alias_table 方法通過將轉移概率歸一化并生成對應的 Alias Table，建表復雜度 O(n)，這里再重復一下之前的需求，Node2vec 在概率游走前需要進行初始化，獲取 Node 的轉移概率表 alias_nodes 和 Edge 的轉移概率表 alias_edge，前者決定當前頂點需要訪問的下一個節點的 Alias Table，后者則決定條件概率下 (t,v) 邊訪問到 v 點時，v 的下一個節點的 Alias Table

import numpy as npdef create_alias_table(transform_prob):print("歸一化前:", transform_prob)# 當前node的鄰居的nbr的轉移概率之和norm_const = sum(transform_prob)# 當前node的鄰居的nbr的歸一化轉移概率normalized_prob = [float(u_prob) / norm_const for u_prob in transform_prob]print("歸一化后:", normalized_prob)length = len(transform_prob)# 建表復雜度o(N)accept, alias = [0] * length, [0] * length# small,big 存放比1小和比1大的索引small, big = [], []# 歸一化轉移概率 * 轉移概率數transform_N = np.array(normalized_prob) * lengthprint("歸一化 * N 后:", transform_N)# 根據概率放入small largefor i, prob in enumerate(transform_N):if prob < 1.0:small.append(i)else:big.append(i)while small and big:small_idx, large_idx = small.pop(), big.pop()accept[small_idx] = transform_N[small_idx]alias[small_idx] = large_idxtransform_N[large_idx] = transform_N[large_idx] - (1 - transform_N[small_idx])if np.float32(transform_N[large_idx]) < 1.:small.append(large_idx)else:big.append(large_idx)while big:large_idx = big.pop()accept[large_idx] = 1while small:small_idx = small.pop()accept[small_idx] = 1return accept, alias

2.2 計算 Edge 的條件轉移概率

這里 p，q 即為回撤概率和深度搜索概率，可以進行調節，內部 for 循環就是根據上圖和??的距離進行節點間的權重生成

def get_alias_edge(G, t, v, p=1.0, q=1.0):G = Gp = pq = qunnormalized_probs = []# T -> V 對于V的鄰居 nbr=T dtx=0 | 1步到位 dtx=1 | T -> V -> V-nbr dtx=2for x in G.neighbors(v):weight = G[v][x].get('weight', 1.0) # w_vxif x == t: # d_tx == 0unnormalized_probs.append(weight / p)elif G.has_edge(x, t): # d_tx == 1unnormalized_probs.append(weight)else: # d_tx = 2unnormalized_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)

2.3 統一生成 Node Alias Table 和 Edge Alias Table

這里通過傳入的參數 Graph 獲取圖的節點與邊，節點直接調用 create_alias_table 制表，邊則通過 get_alias_edge 加工制表

def preprocess_transition_probs(G):alias_nodes = {}for node in G.nodes():# 當前node的鄰居nbr的轉移概率unnormalized_probs = [G[node][nbr].get('weight', 1.0)for nbr in G.neighbors(node)]# 當前node的鄰居的nbr的轉移概率之和norm_const = sum(unnormalized_probs)# 當前node的鄰居的nbr的歸一化轉移概率normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]# 獲取 Accept Alias: 前者為當前方式事件I的概率 后者為另一個事件的編號alias_nodes[node] = create_alias_table(normalized_probs)alias_edges = {}for edge in G.edges():alias_edges[edge] = get_alias_edge(G, edge[0], edge[1], p=0.25, q=4)return alias_nodes, alias_edges(alias_nodes, alias_edges) = preprocess_transition_probs(G)

3.概率游走獲取序列

通過前面的準備工作已經獲得了點與邊的轉移概率，下面開始概率游走:

3-1 alias_sample 負責從 alias_table 中 O(1) 的采樣

def alias_sample(accept, alias):N = len(accept)i = int(np.random.random() * N)r = np.random.random()if r < accept[i]:return ielse:return alias[i]

3-2 node2vec，鋪墊了這么多，Node2walk 主要步驟都在這里，這里需要通過 walk 的長度判斷是起始點還是中間點，起始點使用 alias_nodes，中間點使用 alias_edges

def node2vec_walk(G, _alias_nodes, _alias_edges, walk_length, start_node):G = G# 起始點walk = [start_node]while len(walk) < walk_length:# 獲取當前nodecur = walk[-1]# 獲取當前node的鄰居cur_nbrs = list(G.neighbors(cur))# 如果有鄰居if len(cur_nbrs) > 0:# 有鄰居且當前為初始點 無頂點情況 使用alias_nodesif len(walk) == 1:walk.append(cur_nbrs[alias_sample(_alias_nodes[cur][0], _alias_nodes[cur][1])])# 有鄰居且不是初始點 有頂點情況 使用alias_edgeselse: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

3-3 將上述兩者結合，定義 walk_length 和 迭代次數進行概率游走采樣。這里定義了迭代次數 num_walks = 10，walk_length = 30，具體數值可根據實際場景調整

# 獲取游走序列 Node2vecnum_walks = 10walks = []for _ in range(num_walks):random.shuffle(nodes_list)for node in nodes_list:walk = node2vec_walk(G, alias_nodes, alias_edges, 30, node)walks.append(walk)print("Node2vec Walk數目:", len(walks))# 統計游走序列去重詞個數word_set = set()for walk in walks:for word in walk:word_set.add(word)print("去重大小:", len(word_set))

經過上面一系列操作，終于獲取了游走序列:

4.Word2vec 訓練獲取向量

4-1 word2vec 訓練

前面提到了使用現有庫?from gensim.models import Word2Vec 直接訓練，相關參數之前有過介紹，注意 gensim 版本不同 Word2vec 的參數可能有出入

# sentences: 訓練語料# min_count: 最低詞頻# vector_size: 詞嵌入維度,老版本為 size# sg: 算法選擇 0-CBOW 1-skip-gram# hs: 是否使用層次softmax# workers: 訓練的并行度# window: 窗口大小# epochs: 訓練輪次，老版本也用為 iter，報錯的話可以換一下# alpha: 學習率# sample: 采樣閾值，出現次數過多的詞會被采樣，可以參考 softmax 采樣優化的方法# cbow_mean: 0-sum 1-mean 用于 CBOW 時對上下文詞向量的處理kwargs = {"sentences": walks, "min_count": 0, "vector_size": 64, "sg": 1, "hs": 0, "workers": 3, "window": 5,"epochs": 3}model = Word2Vec(**kwargs)

4-2 獲取訓練向量

通過模型獲取向量，由于模型參數設置 min_count ，所以所有 node 都可以獲取向量，實際場景中，詞頻較小的詞可能不會獲得向量表征

def get_embeddings(w2v_model, graph):count = 0invalid_word = []_embeddings = {}for word in graph.nodes():if word in w2v_model.wv:_embeddings[word] = w2v_model.wv[word]else:invalid_word.append(word)count += 1print("無效word", len(invalid_word))print("有效embedding", len(_embeddings))return _embeddingsembeddings = get_embeddings(model, G)

?有興趣也可以通過降維的方法對原始向量進行二維展示:

?如果有原始數據的真實類別，可視化效果更好:

?四.總結

Node2vec 相比 DeepWalk 優化了采樣方式與序列生成方式，提高效率的情況下也提升了效果，這里簡單介紹了使用的方法和過程，后續有時間繼續盤一下 Line，SDNE，Struc2vec，EGES 等 GraphEmbedding 算法。?

總結

以上是生活随笔為你收集整理的GraphEmbedding - Node2vec 图文详解的全部內容，希望文章能夠幫你解決所遇到的問題。

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