??DeepWalk是一種用來學習圖（網絡）中頂點的潛在表示的一種基于簡單神經網絡的算法颂砸。DeepWalk 算法第一次將深度學習中的技術引入到圖（網絡）表示學習領域噪奄，且充分利用了圖（網絡）結構中的隨機游走序列的信息。
??DeepWalk的主要思想來源于Word2Vec人乓，作者首先介紹了自然語言中的詞頻滿足統計學中的冪律分布（Power Laws）勤篮，而在網絡中對每個頂點進行指定深度的隨機游走得到的頂點序列也同樣滿足冪律分布，如下圖所示色罚。因此可以相應地將NLP中的word2vec運用在圖（網絡）中的頂點表示上碰缔，故而有了DeepWalk算法。
Language Modeling
??在詳細介紹DeepWalk之前戳护，我們先介紹一下語言模型金抡。語言模型的目標是估計一個特定的單詞序列在語料庫中的似然。例如腌且，給定一個如下的單詞序列
其中
（
表示詞匯表）梗肝，針對以上單詞序列，語言模型的目標是想要在現有的訓練語料庫上最大化
目前的表示學習工作铺董，在語言模型的基礎上巫击，更關注使用概率神經網絡模型去構建單詞的一般表示。在這偏論文里精续，作者在隨機游走的基礎上坝锰，提出了一種通用的語言模型來學習圖中每個頂點的一半表示。圖中的每一次隨機游走都可以認為是語言模型中的一條語句驻右，然后直接模擬語言模型，估計每個頂點在歷史訪問的頂點條件下的似然：
由于最終的學習目標是學習每個頂點的一般表示崎淳，于是上述問題可以轉換為：
然而隨著游走深度的增長堪夭，計算上述目標函數代價會變得非常大。于是NLP領域又出現了使用上下文預估當前單詞的方式拣凹，這種方式很好的消除了單詞在句子中順序的影響森爽，對應的方法有CBOW和SkipGram，然后本文中使用了SkipGram語言模型嚣镜。于是我們的目標函數就變成了：
??DeepWalk算法主要分成兩個部分：隨機游走（Random Walks）和SkipGram建模爬迟。下面會分兩個部分進行詳細介紹。DeepWalk算法的具體描述如下所述菊匿。
Random Walks
??作者定義了一次Random Walk的過程付呕，假設以頂點為起點的一次隨機游走結果為
计福，那么針對該隨機游走序列
，那么
是從頂點
的所有鄰接頂點中隨機選擇的一個頂點徽职。上面說過象颖，這個隨機游走序列中的各頂點出現的頻率滿足冪律分布，因此針對每個頂點隨機游走的若干個指定長度的頂點串可以組成接下來模型訓練環(huán)節(jié)的“語料庫”姆钉。
以上算法展示了Deepwalk的核心內容说订，外層循環(huán)指定了對于每個頂點的隨機游走的次數。在內層循環(huán)中潮瓶，遍歷圖中的每個頂點陶冷，然后對每個頂點進行一次深度為
的隨機游走過程，然后使用該隨機游走序列毯辅，使用SkipGram模型針對之前提出的目標函數更新當前頂點的表示
Skip-Gram Modeling
??Skip-Gram Modeling是一種基于神經網絡結構的Word2Vec模型埂伦，主要利用Word2Vec的思想將Random Walks中拿到的隨機游走的頂點序列作為語料庫，訓練神經網絡模型悉罕，進而學習每個頂點的向量表示赤屋。
首先，該算法以滑動窗口的方式遍歷隨機游走的頂點序列壁袄，窗口的大小為类早，在每個窗口內，針對當前中心頂點嗜逻，使用上文的目標函數更新當前頂點的表示
涩僻，從而學得每個頂點的一般表示
。
另外針對該目標函數在大規(guī)模圖網絡場景下面臨的計算復雜度栈顷，作者提出了一種優(yōu)化方法叫Hierarchical Softmax逆日。使得目標函數的計算時間復雜度從降到了 。另外作者還給出了并行計算框架下的實現范例萄凤，具體可以參考原論文室抽。
應用場景
??通過DeepWalk我們可以學習得到所有頂點的連續(xù)性特征表示，然后利用這些特征靡努，我們可以做聚類坪圾，異常檢測，半監(jiān)督分類等惑朦。由于SkipGram的特性兽泄，窗口內相鄰的頂點會得到相似的一般表示，因此漾月，利用DeepWalk學習到的網絡特征進行無監(jiān)督聚類病梢，可以得到效果比較好的社區(qū)發(fā)現結果，通沉褐祝可以在風控場景下用來做群組分析蜓陌。以上就是DeepWalk的全部內容觅彰。
參考：
https://arxiv.org/pdf/1403.6652
http://www.perozzi.net/projects/deepwalk/
