DeepWalk

與詞嵌入類似，圖嵌入基本理念是基于相鄰頂點(diǎn)的關(guān)系，將目的頂點(diǎn)映射為稠密向量，以數(shù)值化的方式表達(dá)圖中的信息，以便在下游任務(wù)中運(yùn)用。

Word2Vec根據(jù)詞與詞的共現(xiàn)關(guān)系學(xué)習(xí)向量的表示，DeepWalk受其啟發(fā)。它通過隨機(jī)游走的方式提取頂點(diǎn)序列，再用Word2Vec模型根據(jù)頂點(diǎn)和頂點(diǎn)的共現(xiàn)關(guān)系，學(xué)習(xí)頂點(diǎn)的向量表示。可以理解為用文字把圖的內(nèi)容表達(dá)出來(lái)，如下圖所示。

DeepWalk訓(xùn)練圖表示的整個(gè)過程大致可以分為2步：

隨機(jī)游走提取頂點(diǎn)序列
使用skip-gram學(xué)習(xí)頂點(diǎn)嵌入

訓(xùn)練時(shí)采用層次Softmax（Hierarchical Softmax）優(yōu)化算法，避免計(jì)算所有詞的softmax。

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

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

Node2Vec

DeepWalk不適用于有權(quán)圖，它無(wú)法學(xué)習(xí)邊上的權(quán)重信息。Node2Vec可以看作DeepWalk的擴(kuò)展，它學(xué)習(xí)嵌入的過程也可以分兩步：

二階隨機(jī)游走（(2^{nd} quad order quad random quad walk)）
使用skip-gram學(xué)習(xí)頂點(diǎn)嵌入

可以看到與DeepWalk的區(qū)別就在于游走的方式，在二階隨機(jī)游走中，轉(zhuǎn)移概率 (pi_{vx}) 受權(quán)值 (w_{vx}) 影響（無(wú)權(quán)圖中(w_{vx})為1）：

[pi_{vx}=alpha_{pq}(t,x) cdot w_{vx}
]

其中，

[alpha_{pq}(t,x)=left{
egin{aligned}
frac{1}{p}, quad & ifquad{d_{tx}=0} \
1, quad & ifquad{d_{tx}=1} \
frac{1}{q}, quad & ifquad{d_{tx}=2}
end{aligned}
ight.
]

(alpha_{pq}) 的取值由 (p) 和 (q) 決定，(d_{tx}) 是頂點(diǎn) (t) 和 (x) 的最短路徑。

(d_{tx}=0)說明(x)就是(t)，(d_{tx}=1)說明(x)和(t)鄰接，(d_{tx}=2)說明(x)和(t)不是鄰接的。

算法通過(p)、(q)兩個(gè)超參數(shù)來(lái)控制游走到不同頂點(diǎn)的概率。以下圖為例，圖中闡述了從上一頂點(diǎn) (t) 游走到當(dāng)前頂點(diǎn) (v)，準(zhǔn)備估計(jì)如何游走到下一個(gè)頂點(diǎn)的過程。

(q)：控制“向內(nèi)”還是“向外”游走。若(q > 1)，傾向于訪問與 (t) 接近的頂點(diǎn)，若 (q<1) 則傾向于訪問遠(yuǎn)離 (t) 的頂點(diǎn)。
(p)：控制重復(fù)訪問剛剛訪問過的頂點(diǎn)的概率。若設(shè)置的值較大，就不大會(huì)剛問剛剛訪問過的頂點(diǎn)。若設(shè)置的值較小，那就可能回路返回一步。

還有一個(gè)值得注意的地方，與DeepWalk不同，Node2Vec在提取頂點(diǎn)序列時(shí)，不再是簡(jiǎn)單地隨機(jī)取鄰居頂點(diǎn)，而是采用了Alias算法。

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

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

將每個(gè)事件的發(fā)生的概率乘以 (N)，此時(shí)會(huì)有部分矩形的面積大于1，部分矩形的面積小于1。切割面積大于1的矩形，填補(bǔ)到面積小于1的矩形上，并且每一列至多由兩個(gè)事件的矩形構(gòu)成，最終組成一個(gè)面積為 (1 imes N) 的矩形。

再根據(jù)這個(gè)矩形，轉(zhuǎn)換成相應(yīng)的Accept表和Alias表。

Node2Vec在隨機(jī)游走之前會(huì)進(jìn)行初始化，獲取 alias_nodes 和 alias_edges 。alias_nodes 存儲(chǔ)每個(gè)頂點(diǎn)決定下一個(gè)訪問的點(diǎn)所需要的alias表，alias_edges則存儲(chǔ)由((t, v))邊訪問到頂點(diǎn)(v)的時(shí)候決定下一個(gè)訪問點(diǎn)所需要的alias表。

alias_nodes與alias_edges的差別在于，alias_nodes不考慮當(dāng)前頂點(diǎn)之前訪問的頂點(diǎn)，它用在游走最開始的時(shí)候，此時(shí)沒有“上一個(gè)頂點(diǎn)”。

關(guān)于 alias 采樣算法更詳細(xì)的內(nèi)容，可以參考下面兩個(gè)鏈接。

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

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

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

代碼

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

DeepWalk 可視化

Node2Vec 可視化

參考資料

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

DeepWalk: Online Learning of Social Representations

node2vec: Scalable Feature Learning for Networks

【Graph Embedding】DeepWalk：算法原理，實(shí)現(xiàn)和應(yīng)用

【Graph Embedding】node2vec：算法原理，實(shí)現(xiàn)和應(yīng)用

node2vec隨機(jī)游走實(shí)現(xiàn)思路

Alias Method離散分布隨機(jī)取樣

理解node2vec

node2vec

總結(jié)

以上是生活随笔為你收集整理的【图嵌入】DeepWalk 和 Node2Vec的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。