DeepWalk
Background
使用機(jī)器學(xué)習(xí)的算法解決問題需要有大量的信息，但是現(xiàn)實(shí)世界中的網(wǎng)絡(luò)中的信息往往比較少，這就導(dǎo)致傳統(tǒng)機(jī)器學(xué)習(xí)算法不能在網(wǎng)絡(luò)中廣泛使用。
（Ps: 傳統(tǒng)機(jī)器學(xué)習(xí)分類問題是學(xué)習(xí)一種假設(shè)，將樣本的屬性映射到樣本的類標(biāo)簽，但是現(xiàn)實(shí)網(wǎng)絡(luò)中的結(jié)點(diǎn)屬性信息往往比較少，所以傳統(tǒng)機(jī)器學(xué)習(xí)方法不適用與網(wǎng)絡(luò)。）
Introduce
deepWalk是網(wǎng)絡(luò)表征學(xué)習(xí)的比較基本的算法，用于學(xué)習(xí)網(wǎng)絡(luò)中頂點(diǎn)的向量表示（即學(xué)習(xí)圖的結(jié)構(gòu)特征即屬性，并且屬性個(gè)數(shù)為向量的維數(shù)），使得能夠應(yīng)用傳統(tǒng)機(jī)器學(xué)習(xí)算法解決相關(guān)的問題。
Algorithm Theory
-
input：鄰接表
每行代表一個(gè)頂點(diǎn)的所有邊
輸入格式 -
output：
第一行為結(jié)點(diǎn)個(gè)數(shù)和向量維數(shù)，后面每行為一個(gè)結(jié)點(diǎn)的向量表示，第一列為nodeId**
輸出格式 -
innovation：
借助語言建模word2vec中的一個(gè)模型，skip-gram來學(xué)習(xí)結(jié)點(diǎn)的向量表示。將網(wǎng)絡(luò)中的結(jié)點(diǎn)模擬為語言模型中的單詞，而結(jié)點(diǎn)的序列（可由隨機(jī)游走得到）模擬為語言中的句子，作為skip-gram的輸入。
-
feasibility：
以上假設(shè)的可行性證明，當(dāng)圖中結(jié)點(diǎn)的度遵循冪律分布（通俗講即度數(shù)大的節(jié)點(diǎn)比較少，度數(shù)小的節(jié)點(diǎn)比較多）時(shí)，短隨機(jī)游走中頂點(diǎn)出現(xiàn)的頻率也將遵循冪律分布（即出現(xiàn)頻率低的結(jié)點(diǎn)多），又因?yàn)?strong>自然語言中單詞出現(xiàn)的頻率遵循類似的分布，因此以上假設(shè)可行。（Ps: 為證明有效性，作者針對(duì)YouTube的社交網(wǎng)絡(luò)與Wikipedia的文章進(jìn)行了研究，比較了在短的隨機(jī)游走中節(jié)點(diǎn)出現(xiàn)的頻度與文章中單詞的頻度進(jìn)行了比較，可以得出二者基本上類似。（冪率分布））
-
process：
隨機(jī)游走+skip-gram 語言模型
DeepWalk
通過隨機(jī)游走得到短的結(jié)點(diǎn)序列，通過skip-gram更新結(jié)點(diǎn)向量表示。 -
Random Walk
Random Walk從截?cái)嗟碾S機(jī)游走序列中得到網(wǎng)絡(luò)的局部信息，并以此來學(xué)習(xí)結(jié)點(diǎn)的向量表示。
deepwalk中的實(shí)現(xiàn)是完全隨機(jī)的，根據(jù)Random Walk的不同，后面又衍生出了node2vec算法，解決了deepwalk定義的結(jié)點(diǎn)相似度不能很好反映原網(wǎng)絡(luò)結(jié)構(gòu)的問題。
-
skip-gram 語言模型
skip-gram 是使用單詞來預(yù)測(cè)上下文的一個(gè)模型，通過最大化窗口內(nèi)單詞之間的共現(xiàn)概率來學(xué)習(xí)向量表示，在這里擴(kuò)展之后便是使用結(jié)點(diǎn)來預(yù)測(cè)上下文，并且不考慮句子中結(jié)點(diǎn)出現(xiàn)的順序，具有相同上下文的結(jié)點(diǎn)的表示相似。（Ps:兩個(gè)node同時(shí)出現(xiàn)在一個(gè)序列中的頻率越高，兩個(gè)node的相似度越高。）
結(jié)點(diǎn)相似性度量： 上下文的相似程度（LINE中的二階相似度）
共現(xiàn)概率根據(jù)獨(dú)立性假設(shè)可以轉(zhuǎn)化為各條件概率之積即
共現(xiàn)概率對(duì)序列中的每個(gè)頂點(diǎn)，計(jì)算條件概率，即該結(jié)點(diǎn)出現(xiàn)的情況下序列中其他結(jié)點(diǎn)出現(xiàn)的概率的log值并借助隨機(jī)梯度下降算法更新該結(jié)點(diǎn)的向量表示。
SkipGram
Φ(vj)為當(dāng)前結(jié)點(diǎn)的向量表示。Hierarchical Softmax用于分解并加快計(jì)算第三行的條件概率。
Advantage
- 并行性：同時(shí)進(jìn)行多個(gè)隨機(jī)游走。
- 適應(yīng)性：當(dāng)圖變化后，不需要全局重新計(jì)算，可迭代更新，因此可以為大規(guī)模、稀疏的圖創(chuàng)建有意義的表示。
Experiment
本次實(shí)驗(yàn)在人工網(wǎng)絡(luò)上進(jìn)行(平均度為20，最大度為50，一個(gè)社區(qū)小包含結(jié)點(diǎn)數(shù)minc為10，最大maxc為100)，deepwalk參數(shù)為默認(rèn)值，訓(xùn)練向量維數(shù)為64。分別在mu（混合度）為0.1，0.2，0.3，0.4，0.5，0.6，并且節(jié)點(diǎn)規(guī)模N為2k，4k，6k，8k，10k上進(jìn)行。使用sklearn庫的K-means進(jìn)行聚類,K進(jìn)行人工調(diào)整在實(shí)際值，計(jì)算每個(gè)實(shí)驗(yàn)的NMI值。
存在問題：
聚類參數(shù)k的確定問題對(duì)實(shí)驗(yàn)的影響很大。
本實(shí)驗(yàn)未探究deepwalk參數(shù)即訓(xùn)練的向量維數(shù)，隨機(jī)游走長度，迭代次數(shù)，skip-gram窗口大小對(duì)聚類精度的影響。
