DeepWalk#

與詞嵌入類似，圖嵌入基本理念是基于相鄰頂點的關系，將目的頂點映射為稠密向量，以數值化的方式表達圖中的信息，以便在下游任務中運用。

Word2Vec根據詞與詞的共現關系學習向量的表示，DeepWalk受其啟發。它通過隨機游走的方式提取頂點序列，再用Word2Vec模型根據頂點和頂點的共現關系，學習頂點的向量表示。可以理解為用文字把圖的內容表達出來，如下圖所示。

DeepWalk訓練圖表示的整個過程大致可以分為2步：

隨機游走提取頂點序列

使用skip-gram學習頂點嵌入

訓練時采用層次Softmax（Hierarchical Softmax）優化算法，避免計算所有詞的softmax。

https://www.hankcs.com/nlp/word2vec.html

https://www.cnblogs.com/pinard/p/7243513.html

Node2Vec#

DeepWalk不適用于有權圖，它無法學習邊上的權重信息。Node2Vec可以看作DeepWalk的擴展，它學習嵌入的過程也可以分兩步：

二階隨機游走（2ndorderrandomwalk2ndorderrandomwalk）

使用skip-gram學習頂點嵌入

可以看到與DeepWalk的區別就在于游走的方式，在二階隨機游走中，轉移概率?πvxπvx?受權值?wvxwvx?影響（無權圖中wvxwvx為1）：

算法通過pp、qq兩個超參數來控制游走到不同頂點的概率。以下圖為例，圖中闡述了從上一頂點?tt?游走到當前頂點?vv，準備估計如何游走到下一個頂點的過程。

• qq：控制“向內”還是“向外”游走。若q>1q>1，傾向于訪問與?tt?接近的頂點，若?q<1q<1?則傾向于訪問遠離?tt?的頂點。
• pp：控制重復訪問剛剛訪問過的頂點的概率。若設置的值較大，就不大會剛問剛剛訪問過的頂點。若設置的值較小，那就可能回路返回一步。

還有一個值得注意的地方，與DeepWalk不同，Node2Vec在提取頂點序列時，不再是簡單地隨機取鄰居頂點，而是采用了Alias算法。

Alias采樣是為了加快采樣速度，初始化后的采樣時間復雜度為O(1)O(1)，但需要存儲 accept 和 alias 兩個數組，空間復雜度為O(2N)O(2N)。這里簡單介紹一下。

給定如下離散概率分布，有?NN個 （這里是4）可能發生的事件。每列矩形面積表示該事件發生的概率，柱狀圖中所有矩形的面積之和為 1。

將每個事件的發生的概率乘以?NN，此時會有部分矩形的面積大于1，部分矩形的面積小于1。切割面積大于1的矩形，填補到面積小于1的矩形上，并且每一列至多由兩個事件的矩形構成，最終組成一個面積為?1×N1×N?的矩形。

再根據這個矩形，轉換成相應的Accept表和Alias表。

Node2Vec在隨機游走之前會進行初始化，獲取 alias_nodes 和 alias_edges 。alias_nodes 存儲每個頂點決定下一個訪問的點所需要的alias表，alias_edges則存儲由(t,v)(t,v)邊訪問到頂點vv的時候決定下一個訪問點所需要的alias表。

alias_nodes與alias_edges的差別在于，alias_nodes不考慮當前頂點之前訪問的頂點，它用在游走最開始的時候，此時沒有“上一個頂點”。

關于 alias 采樣算法更詳細的內容，可以參考下面兩個鏈接。

https://shomy.top/2017/05/09/alias-method-sampling/

https://blog.csdn.net/manmanxiaowugun/article/details/90170193

后面就跟DeepWalk一樣了，但是原作者在訓練Word2Vec模型的時候，沒有采用層次Softmax。

代碼#

Copy

https://gitee.com/dogecheng/python/blob/master/graph/DeepWalk_and_Node2Vec.ipynb

DeepWalk 可視化

Node2Vec 可視化

參考資料#

騰訊安全威脅情報中心“明廚亮灶”工程：基于域名圖譜嵌入的惡意域名挖掘

DeepWalk: Online Learning of Social Representations

node2vec: Scalable Feature Learning for Networks

【Graph Embedding】DeepWalk：算法原理，實現和應用

【Graph Embedding】node2vec：算法原理，實現和應用

node2vec隨機游走實現思路

Alias Method離散分布隨機取樣

理解node2vec

node2vec

?

總結

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

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