Graph Embedding之DeepWalk

??DeepWalk是一種用來學(xué)習(xí)圖（網(wǎng)絡(luò)）中頂點(diǎn)的潛在表示的一種基于簡單神經(jīng)網(wǎng)絡(luò)的算法。DeepWalk 算法第一次將深度學(xué)習(xí)中的技術(shù)引入到圖（網(wǎng)絡(luò)）表示學(xué)習(xí)領(lǐng)域，且充分利用了圖（網(wǎng)絡(luò)）結(jié)構(gòu)中的隨機(jī)游走序列的信息。
??DeepWalk的主要思想來源于Word2Vec，作者首先介紹了自然語言中的詞頻滿足統(tǒng)計(jì)學(xué)中的冪律分布（Power Laws），而在網(wǎng)絡(luò)中對每個(gè)頂點(diǎn)進(jìn)行指定深度的隨機(jī)游走得到的頂點(diǎn)序列也同樣滿足冪律分布，如下圖所示。因此可以相應(yīng)地將NLP中的word2vec運(yùn)用在圖（網(wǎng)絡(luò)）中的頂點(diǎn)表示上，故而有了DeepWalk算法。

power-law

Language Modeling

??在詳細(xì)介紹DeepWalk之前，我們先介紹一下語言模型。語言模型的目標(biāo)是估計(jì)一個(gè)特定的單詞序列在語料庫中的似然。例如，給定一個(gè)如下的單詞序列
W_1^n=(w_0,w_1,\dots,w_n)其中w_i \in \nu （\nu表示詞匯表），針對以上單詞序列，語言模型的目標(biāo)是想要在現(xiàn)有的訓(xùn)練語料庫上最大化
Pr(w_n|w_0,w_1,\dots,w_{n-1})目前的表示學(xué)習(xí)工作，在語言模型的基礎(chǔ)上，更關(guān)注使用概率神經(jīng)網(wǎng)絡(luò)模型去構(gòu)建單詞的一般表示。在這偏論文里，作者在隨機(jī)游走的基礎(chǔ)上，提出了一種通用的語言模型來學(xué)習(xí)圖中每個(gè)頂點(diǎn)的一半表示。圖中的每一次隨機(jī)游走都可以認(rèn)為是語言模型中的一條語句，然后直接模擬語言模型，估計(jì)每個(gè)頂點(diǎn)在歷史訪問的頂點(diǎn)條件下的似然：
Pr(v_i|(v_1,v_2,\dots,v_{i-1}))由于最終的學(xué)習(xí)目標(biāo)是學(xué)習(xí)每個(gè)頂點(diǎn)的一般表示，于是上述問題可以轉(zhuǎn)換為：
Pr(v_i|(\Phi( v_1),\Phi( v_1),\dots,\Phi( v_{i-1})))然而隨著游走深度的增長，計(jì)算上述目標(biāo)函數(shù)代價(jià)會(huì)變得非常大。于是NLP領(lǐng)域又出現(xiàn)了使用上下文預(yù)估當(dāng)前單詞的方式，這種方式很好的消除了單詞在句子中順序的影響，對應(yīng)的方法有CBOW和SkipGram，然后本文中使用了SkipGram語言模型。于是我們的目標(biāo)函數(shù)就變成了：
min -\log Pr(\{v_{i-w},\dots,v_{i-1},v_{i+1},\dots,v_{i+w}\}|\Phi(v_i))??DeepWalk算法主要分成兩個(gè)部分：隨機(jī)游走（Random Walks）和SkipGram建模。下面會(huì)分兩個(gè)部分進(jìn)行詳細(xì)介紹。DeepWalk算法的具體描述如下所述。

Random Walks

??作者定義了一次Random Walk的過程，假設(shè)以頂點(diǎn)\small v_i為起點(diǎn)的一次隨機(jī)游走結(jié)果為\small W_{v_i}，那么針對該隨機(jī)游走序列\small \{ w_{v_i}^1,w_{v_i}^2,\dots,w_{v_i}^k\}，那么\small w_{v_i}^{k+1}是從頂點(diǎn)w_{v_i}^k的所有鄰接頂點(diǎn)中隨機(jī)選擇的一個(gè)頂點(diǎn)。上面說過，這個(gè)隨機(jī)游走序列中的各頂點(diǎn)出現(xiàn)的頻率滿足冪律分布，因此針對每個(gè)頂點(diǎn)隨機(jī)游走的若干個(gè)指定長度的頂點(diǎn)串可以組成接下來模型訓(xùn)練環(huán)節(jié)的“語料庫”。

Deep Walk

以上算法展示了Deepwalk的核心內(nèi)容，外層循環(huán)指定了對于每個(gè)頂點(diǎn)的隨機(jī)游走的次數(shù)\small \gamma。在內(nèi)層循環(huán)中，遍歷圖中的每個(gè)頂點(diǎn)，然后對每個(gè)頂點(diǎn)進(jìn)行一次深度為\small t的隨機(jī)游走過程，然后使用該隨機(jī)游走序列，使用SkipGram模型針對之前提出的目標(biāo)函數(shù)更新當(dāng)前頂點(diǎn)的表示\small \Phi

Skip-Gram Modeling

??Skip-Gram Modeling是一種基于神經(jīng)網(wǎng)絡(luò)結(jié)構(gòu)的Word2Vec模型，主要利用Word2Vec的思想將Random Walks中拿到的隨機(jī)游走的頂點(diǎn)序列作為語料庫，訓(xùn)練神經(jīng)網(wǎng)絡(luò)模型，進(jìn)而學(xué)習(xí)每個(gè)頂點(diǎn)的向量表示。
首先，該算法以滑動(dòng)窗口的方式遍歷隨機(jī)游走的頂點(diǎn)序列，窗口的大小為\small w，在每個(gè)窗口內(nèi)，針對當(dāng)前中心頂點(diǎn)，使用上文的目標(biāo)函數(shù)更新當(dāng)前頂點(diǎn)的表示\small \Phi，從而學(xué)得每個(gè)頂點(diǎn)的一般表示\small \Phi。

Skip Gram

另外針對該目標(biāo)函數(shù)在大規(guī)模圖網(wǎng)絡(luò)場景下面臨的計(jì)算復(fù)雜度，作者提出了一種優(yōu)化方法叫Hierarchical Softmax。使得目標(biāo)函數(shù)的計(jì)算時(shí)間復(fù)雜度從降到了 。另外作者還給出了并行計(jì)算框架下的實(shí)現(xiàn)范例，具體可以參考原論文。
Overview of DeepWalk

應(yīng)用場景

??通過DeepWalk我們可以學(xué)習(xí)得到所有頂點(diǎn)的連續(xù)性特征表示，然后利用這些特征，我們可以做聚類，異常檢測，半監(jiān)督分類等。由于SkipGram的特性，窗口內(nèi)相鄰的頂點(diǎn)會(huì)得到相似的一般表示，因此，利用DeepWalk學(xué)習(xí)到的網(wǎng)絡(luò)特征進(jìn)行無監(jiān)督聚類，可以得到效果比較好的社區(qū)發(fā)現(xiàn)結(jié)果，通?？梢栽陲L(fēng)控場景下用來做群組分析。以上就是DeepWalk的全部內(nèi)容。

參考：
https://arxiv.org/pdf/1403.6652
http://www.perozzi.net/projects/deepwalk/

最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容