node2vec: Scalable Feature Learning for Networks

Github整理代碼鏈接，歡迎討論和交流，覺得有用的可以Star一下。

1.主要思想

???????目的：是將圖中的頂點映射到一個低維連續空間，并且能夠保存圖的空間結構。

???????論文的主要亮點，設計了與Deepwalk不同的隨機游走方式，每次隨機游走會選擇是進行寬度游走Breadth-first Sampling (BFS)還是深度游走Depth-first Sampling (DFS) ，如圖1所示 。
???????獲得游走路徑集合后，與Deepwalk類似使用Skip-Gram模型進行頂點的Embedding學習

圖1 兩種游走策略

2.流程

2.1 優化目標

???????設$f(u)$是將頂點$u$映射為Embedding向量的映射函數，$N_s(u)$為通過采樣策略$S$采樣出的頂點$u$的近鄰頂點集合。

???????將現有的Skip-gram模型擴展到網絡中來，優化以下目標函數

???????優化目標函數：給定一個頂點，令其近鄰頂點出現的概率最大
$$\underset{f}{\max }\sum _{u\in V}logPr(N_s(u)|f(u))$$
??????為了使公式1能夠得到很好的優化求解，提出了兩個假設：

??????1.條件獨立

??????給定一個頂點，其近鄰頂點出現的概率與近鄰集合中的其他頂點無關，得到公式2：
$$Pr(N_s(u)|f(u))=\prod _{n_i\in N_s(u)}Pr(n_i|f(u))$$
??????2.特征空間中的對稱性

?????源頂點和近鄰頂點在特征空間中具有對稱性，不管頂點是源頂點還是近鄰點Embedding表達是一樣的。（對比Line中的二階相似度有所不同），得到公式3：
$$Pr(n_i|f(u))=\frac{exp(f(n_i)?f(u))}{{\sum }_{v\in V}exp(f(v)?f(u))}$$
??????根據以上兩個假設條件，最終的目標函數公式1簡化為公式4，由于$Z_u={\sum }_{v\in V}exp(f(n_i)?f(u))$計算復雜度高，所以采用負采樣近似優化
$$\underset{f}{\max }\sum _{u\in V}[?log{Z}_u+\sum _{n_i\in N_s(u)}f(n_i)?f(u)]$$

2.2 采樣策略

2.2.1 路徑采樣策略

??????Node2vec依然延續了Deepwalk采用隨機游走的方式獲取頂點的近鄰序列，Node2vec不同的是采用的是一種有偏的隨機游走。

??????給定當前頂點$v$ ，訪問下一個頂點 $x$ 的概率為公式5，其中${\pi }_{vx}$為頂點$v$和頂點$x$為歸一化的轉移概率，$Z$為一個常量，設${\pi }_{vx}={\alpha }_{pq}(t,x)?w_{vx}$，${\alpha }_{pq}(t,x)$是$t$到$x$的游走策略生成的概率，$w_{vx}$是頂點$v$和頂點$x$之間的邊權。
$$P(c_i=x|c_{i?1}=v)=\{\begin{array}{cc}\frac{{\pi }_{vx}}{Z}& (v,x)\in V\\ 0& (v,x)\in /V\end{array}$$
??????Node2vec引入兩個超參數$p$和 $q$來控制隨機游走的策略。如圖2所示，假設當前隨機游走頂點$t$經過邊 $(t,v)$ 到達頂點$v$，頂點$v$的下一個訪問頂點$x$的概率根據公式6計算得到，公式6中$d_{tx}$為下一個訪問頂點$x$和當前頂點$v$的上一個頂點$t$之間的距離
$${\alpha }_{pq}(t,x)=?\begin{array}{cc}\frac{1}{p}& d_{tx}=0\\ 1& d_{tx}=1\\ \frac{1}{q}& d_{tx}=2\end{array}$$

圖2 p和q參數示意

• 返回參數$p$
  ??????僅作用于$d_{tx}=0$的情況，控制頂點$v$重復訪問上一步頂點的概率，如果$p$較大，則下一步游走訪問上一步頂點的概率越小，反之越大。
• 輸入輸出參數$q$
  僅作用于$d_{tx}=2$的情況，控制頂點$v$隨機游走下一步的游走策略類型，BFS和DFS

Breadth-first Sampling (BFS)
如果$q$較大，則頂點$v$下一步游走傾向于訪問頂點$v$上一步頂點近鄰頂點，構成了寬度游走策略

Depth-first Sampling (DFS)
如果$q$較小，則頂點$v$下一步游走傾向于訪問頂點$v$上一步頂點距離遠的頂點，構成了深度游走策略

2.2.2 頂點采樣策略

??????頂點采樣策略區別于Deepwalk，不是隨機采樣頂點，使用Alias Sample方法進行采樣。Alias Sample具體實現方式見Line論文整理3.3.4。本文中Alias Sample與Line中不同之處在于創建鄰居頂點的Node Alias Sample Table，而Line中是創建的全局Node Alias Sample Table。

3.向量學習

??????通過帶策略的隨機游走獲得路徑集合，根據所獲得的路徑集合，與Deepwalk類似使用Skip-Gram模型進行頂點的Embedding學習。具體Skip-Gram模型見Deepwalk論文整理。

4.代碼實現和實驗

4.1 游走策略代碼

?????Node2Vec中Edge Alias Sample根據公式6計算，給定一個頂點src，計算src的鄰居頂點訪問概率，為了在隨機游走下一個頂點中使用；Node Alias Sample根據頂點的出度歸一化生成概率計算得到

# _*_ coding: utf-8 _*_ """ Time: 2020/9/9 17:50 Author: Cheng Ding(Deeachain) Version: V 0.1 File: node2vec.py Describe: Write during the internship at Hikvison, Github link: https://github.com/Deeachain/GraphEmbeddings """ # Edge Alias Sample def get_alias_edge(self, src, dst):'''Get the alias edge setup lists for a given edge.'''G = self.Gp = self.pq = self.qunnormalized_probs = []for dst_nbr in sorted(G.neighbors(dst)):if dst_nbr == src: # dx=0unnormalized_probs.append(G[dst][dst_nbr]['weight'] / p)elif G.has_edge(dst_nbr, src): # dx=1unnormalized_probs.append(G[dst][dst_nbr]['weight'])else: # dx=2unnormalized_probs.append(G[dst][dst_nbr]['weight'] / q)norm_const = sum(unnormalized_probs)normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]return alias_setup(normalized_probs)''' Node Alias Sample ''' alias_nodes = {} for node in G.nodes():unnormalized_probs = [G[node][nbr]['weight'] for nbr in sorted(G.neighbors(node))]norm_const = sum(unnormalized_probs)normalized_probs = [float(u_prob) / norm_const for u_prob in unnormalized_probs]alias_nodes[node] = alias_setup(normalized_probs)

• 游走策略代碼

# _*_ coding: utf-8 _*_ """ Time: 2020/9/9 17:50 Author: Cheng Ding(Deeachain) Version: V 0.1 File: node2vec.py Describe: Write during the internship at Hikvison, Github link: https://github.com/Deeachain/GraphEmbeddings """ def node2vec_walk(self, walk_length, start_node):G = self.Galias_nodes = self.alias_nodesalias_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: # 路徑中只有一個頂點時，從鄰居頂點中根據邊權生成概率,使用alias采樣下一個頂點,不直接使用第二種情況采樣的原因是為了構成采樣策略walk.append(cur_nbrs[alias_sample(alias_nodes[cur][0], alias_nodes[cur][1])])else: # 路徑中大于一個頂點時，根據鄰居頂點p和q的采樣策略生成概率,使用alias采樣下一個頂點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

4.2 實驗

????????Node2Vec源碼^[1]中僅使用karate.edges數據集，該數據集是關于跆拳道俱樂部成員之間關系的社交網絡，節點沒有標簽，作者源碼沒有復現原文中的數據集。整理代碼采用了另外的三個公開數據集，分別是：Cora數據集由機器學習論文組成，總共有2708篇論文，應用關系有5429個，論文總共七類（基于案例、遺傳算法、神經網絡、概率方法、強化學習、規則學習、理論）；DBLP數據集也是引文網絡組成的圖，只選用了4類；BlogCatalog數據集是Blog用戶之間關系構成的社交網絡，相關詳細參數見表1

表1 整理代碼使用數據集 數據集coradblpBlogCatalog

V	2708	17725	10312
E	5429	105781	333983
Class	7	4	39

????????實驗參數：

• Deepwalk：詞向量維度$d=128$、每個頂點游走路徑數$\gamma =50$、游走路徑長度$t=20$、$Epoch=5$、SkipGram窗口大小$w=10$
• Line：詞向量維度$d=128$、二階相似度生成128維詞向量、$Epoch=150$、$lr=0.005$、$num\_negative=5$。（目前Line模型存在一定問題，不能復現論文效果。）
• Cora數據集有向圖實驗，一階相似度：節點分類$f1=0.44$，可視化能區分一部分節點，；二階相似度節點分類$f1=0.52$,，可視化能區分一部分節點
• COra數據集無向圖實驗，一階相似度：節點分類$f1=0.48$，可視化能區分一部分節點，；二階相似度節點分類$f1=0.62$,，可視化能區分一部分節點
• Node2vec：詞向量維度$d=128$、返回參數$p=0.25$、輸入輸出參數$q=0.25$（$p、q\in (0.25,0.5,1,2,4)$文中實驗證明$p$和$q$越小越好）、每個頂點游走路徑數$\gamma =50$、游走路徑長度$t=20$、$Epoch=5$、SkipGram窗口大小$w=10$

????????Node2Vec通過帶偏策略的游走得到路徑集合，接著SkipGram模型學習頂點的Embedding，最后使用Embedding設計頂點分類任務。數據集劃分80%的數據用于訓練，20%用于評估，分類任務使用SVM分類，得到頂點的分類指標f1-score如表2所示。

表2 頂點分類f1-score指標 coradblp

Deepwalk（f1-micro）	0.8542	0.8327
Line（f1-micro）	0.6218	0.6262
Node2vec（f1-micro）	0.8561	0.8386

????????節點Embedding表達在空間維度上，相同類別的節點距離會越靠近，最后將學習得到的Embedding進行可視化展示。可視化使用的是TSNE實現，將向量降維到二維平面上。可視化效果如圖3所示。

圖3 Embedding可視化

參考和引用

[1]. 論文源碼

總結

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

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