原文：DeepWalk: Online Learning of Social Representations
基本目標：
-從網(wǎng)絡中提取特征
-具體來說，輸入圖G=(V,E)， V是節(jié)點集，E是邊集，輸出G的特征矩陣X ，d是特征的維度.
想法來源：在NLP中，對于一個句子，有CBOW(通過周邊詞預測一個詞)和Skip-Gram(通過一個詞來預測周邊詞)，來訓練詞向量。訓練出來的詞向量，相似的詞對應的詞向量的相似度會比較高。
在網(wǎng)絡結構中，可以通過randow walk構造一個序列，看作上述的sentence進行訓練。
Random Work：
從節(jié)點vi出發(fā)(vi為root)構造一個random walk序列，記為 Wvi，其中包含一系列隨機變量Wvi1,Wvi2,...,Wvik.
random walk有兩個非常好的性質(zhì)：
?并行性?？梢酝瑫r由多個不同的random walkers(多線程、多進程、多machine)對同一個圖G的不同部分同時進行探索。
?對于圖結構的微小改變，不需要再進行全局重新計算，對已經(jīng)學習好的模型在原圖的改變區(qū)域用新的random walkers進行迭代更新即可。
Connection：Power laws
圖a是YouTube的社交節(jié)點分布，圖b是Wiki的文本分布，可以看到它們具有類似的分布形式，都表現(xiàn)出了長尾效應(一部分非常集中，剩下的部分的形狀像一條尾巴)。由此說明，將用在NLP中的方法用到網(wǎng)絡分析中是具有合理性的。
Language Modeling
通常語言模型的目標為最大下面的likelihood(即用前n-1個詞作為條件，使第n個詞的概率最大)，w表示word。
對應到random walk中，likelihood如下(用前i-1個節(jié)點位置作為條件，使第i個節(jié)點位置的概率最大)，v表示節(jié)點。
我們的目標是學習圖G的presentation，因此引入mapping function如下，把節(jié)點映射成特征，通常φ是一個|V|*d的矩陣，|V|表示節(jié)點個數(shù)，d表示特征的維度。
至此，目標likelihood就變成了如下形式。
然而，隨著work length的增大，這個問題是intractable的。
于是考慮一些優(yōu)化：
?用一個節(jié)點去預測其他節(jié)點。
?其他節(jié)點由這個節(jié)點的左右節(jié)點構成。
?忽略其他節(jié)點的次序
(其實就是對應前面提到的NLP中的skip-gram)
于是，優(yōu)化目標變成了下面的形式。
DeepWalk算法
DeepWalk算法由兩個主要的模塊：
?random walk generator
?update procedure
random walk generator首先選取一個節(jié)點作為root，然后進行random walk直到達到最大length(t)。作者在實現(xiàn)這個算法時，確定了一個參數(shù)r，在每個root，開始r次不同的random walk。
對算法3-9的解釋：
(3,9)：循環(huán)r次，因為每個節(jié)點作為root要出發(fā)r次random walk。
4：對節(jié)點的次序進行隨機化，提高運行效率。
5-8：對每個節(jié)點vi，RandomWalk(G,vi,t)表示對于圖G，以vi為root，t為最大length進行random walk，返回walk sequence。 SkipGram(φ,Wvi,w)中，第一個參數(shù)為特征矩陣(算法的result，在每次迭代中不斷update)，第二個參數(shù)為walk sequence，第三個參數(shù)為window大小。
在SkipGram中，前面提到不考慮context的次序，于是有
具體來看SkipGram的代碼：
(1,6),(2,5)：從walk sequence 中選取一個vj，此時確定了用φ(vj)來預測context(window大小為w，context即為[j-w:j+w]并除去j本身，在作者的代碼中，并沒有除去j本身，可能是因為用j來預測自身并沒有什么影響)。對于vj，φ(vj)是它的feature vector，如下圖所示，在總體feature matrixφ中找到自己對應的一行即可。
3：目標是最大化likelihood Pr(uk|φ(vj))，也就是最小化-logPr(uk|φ(vj)) (加log是為了方便計算，加-是為了讓最大變最小，然后做梯度下降。其實不加也無所謂，那就做梯度上升就好了)。
4：確定學習率α，做梯度下降。
Hierarchical Softmax
在4.1最后有這樣一段話，
如果知道Pr(uk|φ(vj))具體是多少，那么就不需要進行下面的步驟。
大多數(shù)情況下，我們是不知道的，那么Pr(uk|φ(vj))的值就是難以計算的(partition function is intractable，我每次在learning中遇到partition function都是intractable的=.= ，在概率圖的inference中可以用Belief Propagation進行approximate，然后再做歸一化，倒不會有這個問題 )。于是考慮用Hierarchical Softmax對Pr(uk|φ(vj))進行分解。
構建一個二叉樹(使用關于節(jié)點頻率的Huffman樹可以有效提高效率)，二叉樹葉子節(jié)點為uk(有自己的feature vectorφ(uk))，非葉子節(jié)點為臨時節(jié)點，也有同樣形式的feature vector(需要learning)。
上圖中，uk對應的一個path(根節(jié)點到它自身)為b0,b1,b2,uk。
則Pr(uk|φ(vj))可以分解為path上各節(jié)點的概率乘積。
其中，
注意，乘積中是沒有包括root的。對應到我畫的那個圖，也就是
而Pr(bl|φ(vj))可以看做是它的parent節(jié)點做了一次二分類(往左或往右)，于是有
其中
是bl的parent節(jié)點的feature vector。其實就是一個sigmoid函數(shù)做二分類，和logistics regression中的是一樣的。
參數(shù)
通過隨機梯度下降來learning，即前面algorithm2中的Line4。
