DeepWalk演算法詳解

一、DeepWalk演算法缺點

DeepWalk演算法是一種用於圖嵌入的無監督學習演算法，它在學習圖的低維表示方面表現出色。然而，它也有一些缺點：

1、DeepWalk演算法基於隨機遊走，對於大圖，這個方法可能會帶來較高的計算複雜度。

2、DeepWalk演算法依賴於節點的鄰居關係，在節點之間存在高度長距離的圖上時，DeepWalk效果可能不佳。

3、DeepWalk演算法不能捕獲節點的全局結構信息。

二、DeepWalk演算法詳解劉建平

DeepWalk演算法是由加拿大蒙特利爾大學的Jian Tang等人在2015年提出的一種無監督學習演算法。它通過把每個節點看做一個詞，將圖轉換成一個句子，然後通過Word2Vec模型學習每個節點的低維表示。

DeepWalk演算法之所以能夠有效地學習節點的低維表示，是因為它利用了本質上與自然語言處理相同的思路：圖是一種高維數據，很難直接處理，但是可以將其映射到低維空間中，這樣可以更好地進行處理。

其中，DeepWalk演算法的核心是隨機遊走過程。該過程從某個節點開始，依次按照一定的策略，選擇這個節點的鄰居節點進行移動，最終形成一個遊走路徑。重複執行該過程，就可以得到一系列遊走路徑，這些路徑就是DeepWalk演算法中的「句子」。Word2Vec對「句子」進行學習，得到每個節點的低維表示。

三、DeepWalk演算法的用處

DeepWalk演算法可以幫助應用程序中節點之間的相似性計算、節點分類、社區檢測等領域。因為在圖中，通常節點之間的相似性是由它們在圖上的結構相似性決定的，而DeepWalk演算法可以有效地捕捉這種結構信息。

可以利用DeepWalk演算法幫助數據挖掘的應用：對於大規模的有標籤和無標籤網路數據集，DeepWalk通過將節點映射到低維向量空間，形成對節點的嵌入表示，彌補了淺層方法的局限性並成功將節點嵌入進向量空間。

可以利用嵌入向量在下游機器學習任務，例如節點分類、邊預測、社區發現、數據可視化、相似性計算等等。

四、DeepWalk演算法譜聚類

DeepWalk演算法可以利用得到的節點嵌入向量進行譜聚類。譜聚類是一種標準的無監督分類技術，可以將相似的數據劃分成同一組。

譜聚類之所以能夠在各種分類問題中表現良好，是因為它能夠有效地從數據的內在特徵中提取信息。相似特徵具有相似的嵌入向量，因此可以通過譜聚類將節點分組。

#deepwalk譜聚類代碼示例
import networkx as nx
from gensim.models.word2vec import Word2Vec
from sklearn.cluster import KMeans
from sklearn.decomposition import PCA
from sklearn.mixture import GaussianMixture

graph=nx.read_edgelist("email-Eu-core.txt",nodetype=int)
walks=[]
for node in graph.nodes():
    for i in range(5):
        walk=nx.random_walk(graph, [node], length=20)
        walks.append([str(node) for node in walk])
model=Word2Vec(walks,size=128,window=10,min_count=0,sg=1,workers=8)
embeddings=model.wv
X=list(embeddings.values())
km=KMeans(n_clusters=42,n_init=20,tol=1e-12)
km.fit(X)

gmm=GaussianMixture(n_components=42, covariance_type='diag',tol=1e-8,min_covar=1e-8)
gmm.fit(X)

pca=PCA(n_components=2)
pca.fit(X)
reduced_X=pca.fit_transform(X)

五、DeepWalk演算法以及實現

DeepWalk演算法的核心是對圖進行隨機遊走，得到遊走序列，然後使用Skip-gram模型訓練節點的嵌入向量。下面是DeepWalk演算法的實現步驟：

1、構造圖的鄰接矩陣。

2、利用任意節點開始的隨機遊走演算法，生成一系列遊走路徑，稱為「句子」。

3、利用Word2Vec模型，對「句子」進行學習，得到每個節點的低維表示，即嵌入向量。

在Python中，可以使用Gensim庫提供的Word2Vec函數實現DeepWalk演算法。下面是DeepWalk演算法的實現代碼：

#DeepWalk演算法代碼示例
from gensim.models import Word2Vec
from gensim.models.word2vec import LineSentence
from sklearn.neighbors import NearestNeighbors
import networkx as nx

#載入圖
G=nx.read_edgelist("email-Eu-core.txt", nodetype=int)

#生成遊走路徑
sentences=[]
num_walks=10 
walk_length=80 
for _ in range(num_walks):              
    for node in G.nodes():
        sentence=[node]
        for _ in range(walk_length-1):
            neighbors=list(G.neighbors(sentence[-1]))
            sentence.append(np.random.choice(neighbors))
        sentences.append([str(i) for i in sentence])
            
#訓練Word2Vec模型
model=Word2Vec(sentences, size=128, window=5, min_count=0, sg=1, iter=1)

#保存節點的嵌入向量
embeddings={}
for node in G.nodes():
    embeddings[node]=model.wv[str(node)]

#尋找最近的節點
knn=NearestNeighbors(n_neighbors=10)
knn.fit(embeddings.values())
print(knn.kneighbors([embeddings[0]])[1])

六、DeepWalk演算法基本原理

DeepWalk演算法通過將圖轉化為文本序列，然後利用Word2Vec模型學習每個節點的嵌入向量。下面是DeepWalk演算法的基本原理：

1、生成節點鄰接矩陣A。

2、從一個初始節點開始，按照隨機遊走策略，不斷移動到與它鄰接的節點。

3、重複上面的步驟生成多個遊走路徑，這些路徑就是DeepWalk演算法中的「句子」。

4、利用Word2Vec模型訓練「句子」，得到每個節點的嵌入向量。

通過生成節點的嵌入向量，我們可以將圖中節點的低維信息捕捉到。在得到節點的嵌入向量後，可以使用這些向量進行節點分類、社區檢測等任務。