0. 前言

DeepWalk 是機器學習 (machine learning, ML) 技術在圖數據中的成功應用之一，其引入了嵌入等重要概念，這些概念是圖神經網絡 (Graph Neural Network, GNN) 的核心。與傳統的神經網絡不同，這種架構的目標是產生表示 (representations)，然后將其傳遞給其他模型執行下游任務(例如節點分類)時使用。
在本節中，我們將了解 DeepWalk 架構及其兩個主要組件： Word2Vec 和隨機游走 (random walks)。首先介紹 Word2Vec 架構的工作原理，并重點介紹 skip-gram 模型，并在自然語言處理 (natural language processing, NLP) 任務中使用 gensim 庫實現 skip-gram 模型，以了解其使用方法。然后，我們將重點研究 DeepWalk 算法，學習如何使用分層 softmax (hierarchical softmax, H-Softmax) 提高性能。然后在圖上實現隨機游走，最后使用 “Zachary’s Karate Club” 數據集實現一個端到端的監督節點分類模型。

1. Word2Vec

理解 DeepWalk 算法的第一步是了解其主要組成部分： Word2Vec。Word2Vec 是 NLP 領域最具影響力的深度學習技術之一，該技術由 Tomas Mikolov 等人于 2013 年提出，是一種利用大規模文本數據集將單詞轉化為向量( vectors，也稱為嵌入，embeddings )表示的技術，這種單詞表示可用于情感分類等下游任務。
使用 Word2Vec 將單詞轉化為向量的示例如下：
$$\begin{gathered} vec(king)=[?2.0,4.2,0.5] \\ vec(queen)=[?1.8,2.7,1.4] \\ vec(man)=[2.9,?1.0,?1.9] \\ vec(woman)=[2.8,?2.6,?1.0] \end{gathered}$$

在以上例子中，就歐氏距離而言，king 和 queen 的詞向量比 king 和 woman 的詞向量更接近。在實踐中，我們通常會使用其他更精確的度量方法來衡量這些詞的相似度，例如常用的余弦相似度 (cosine similarity)。余弦相似度關注的是向量之間的角度，而不考慮它們的大小(長度)：
$$cosinesimilarity(\vec{A},\vec{B})=cos(\theta )=\frac{\vec{A}?\vec{B}}{||\vec{A}||?||\vec{B}||}$$
Word2Vec 能夠解決類比問題，最著名的例子是，它可以回答 "man is to woman, what king is to ___?"的問題。計算方法如下：
$$vec(king)?vec(man)+vec(woman)\approx vec(queen)$$
當然這種性質并不適用于所有類比問題，但這一特性可以為嵌入算術運算帶來有趣的應用。

1.1 CBOW 與 skip-gram

為了生成這些向量，模型必須在一個前置任務上進行訓練。任務本身并不需要有實際意義，其唯一目標就是生成高質量的嵌入向量。在實踐中，這個任務通常與根據特定上下文預測單詞相關。通常，可以使用兩種具有類似任務的架構：

• 連續詞袋 (continuous bag-of-words, CBOW) 模型： 模型的訓練目標是利用周圍上下文(目標單詞前后的單詞)預測一個單詞。上下文單詞的順序并不重要，因為它們的嵌入向量會在模型中求和。實踐表明，使用預測單詞前后的四個單詞進行預測時，可以獲得更好的結果
• 連續 skip-gram (continuous skip-gram, skip-gram)模型： 模型的訓練目標是根據一個輸入單詞預測其上下文單詞。增加上下文單詞的范圍可以獲得更好的嵌入向量，但也會增加訓練時間

兩種模型的輸入和輸出如下所示：

通常，CBOW 模型的訓練速度更快，但是由于 skip-gram 模型具有學習不常見單詞的能力，因此更加準確。

1.2 構建 skip-gram 模型

由于 DeepWalk 采用的是 skip-gram 架構，因此我們現在將重點學習 skip-gram 模型。skip-gram 使用具有以下結構的單詞對：(target word, context word)，其中 target word 是輸入詞，context word 是要預測的詞。同一目標詞的 skip-gram 數量取決于參數上下文大小 (context size)，如下圖所示：

這一單詞對結構可以從單個句子擴展至整個文本語料庫。為了節省內存，我們將同一目標詞的所有上下文詞存儲在一個列表中。接下來，我們以整個段落為例構建單詞對，為存儲在 text 變量中的整個段落創建 skip-gram 單詞對。將 CONTEXT_SIZE 變量設置為 2，即查看目標單詞前后的兩個單詞。

(1) 導入所需庫：

import numpy as np

(2) 將 CONTEXT_SIZE 變量設置為 2，并導入要分析的文本 text：

CONTEXT_SIZE = 2
text = """Tears came to my eyes as I realized what I had been a fool to judge Al as a failure. He had not left any material possessions behind. But he had been a kind loving father, and left behind his best love.""".split()

(3) 通過一個簡單的 for 循環創建 skip-gram 單詞對，以考慮 text 中的每個單詞。使用列表推導式生成上下文單詞，并存儲在 skipgrams 列表中：

# Create skipgrams
skipgrams = []
for i in range(CONTEXT_SIZE, len(text) - CONTEXT_SIZE):array = [text[j] for j in np.arange(i - CONTEXT_SIZE, i + CONTEXT_SIZE + 1) if j != i]skipgrams.append((text[i], array))

(4) 使用 print() 函數查看生成的 skipgrams：

print(skipgrams[0:2])

輸出結果如下，觀察這兩個目標單詞及其相應的上下文可以了解 Word2Vec 的輸入-輸出形式：

[('to', ['Tears', 'came', 'my', 'eyes']), ('my', ['came', 'to', 'eyes', 'as'])]

1.3 skip-gram 模型

Word2Vec 的目標是生成高質量的單詞嵌入。為了學習這些嵌入，skip-gram 模型的訓練目標是根據目標詞預測正確的上下文單詞。
假設，我們有一個由 $N$ 個單詞組成的序列 $w_1,w_2,...,w_N$。在給定單詞 $w_2$ 的情況下，得到單詞 $w_2$ 的概率為 $p(w_2|w_1)$。我們的目標是最大化整個文本中給定目標單詞時得到每個上下文單詞的概率之和：
$$\frac{1}{N}\sum _{n=1}^N\sum _{?c\le j\le c,j\ne 0}\log p(w_{n+j}|w_n)$$
其中 $c$ 是上下文向量的大小。那么，為什么我們要在以上等式中使用對數概率？將概率轉換為對數概率是機器學習中的常用技術，主要有兩個原因：

• 乘法的計算成本比加法高，而使用對數可以將乘法轉換為加法(除法轉換為減法)，因此計算對數概率更快：
  $$\log (A\times B)=\log (A)+\log (B)$$
• 計算機存儲非常小的數字(如 3.14e-128 )的方式并不完全準確，當事件發生的可能性極小時，這些微小的誤差就會累積起來，使最終結果產生偏差。而使用對數則不同，當結果同樣為 3.14e-128 時，使用對數后結果為 -127.5 (log3.14e-128=-127.5)

總的來說，將概率轉換為對數概率可以在不改變初始目標的情況下提高速度和準確性。

原始 skip-gram 模型使用 softmax 函數來計算給定目標單詞嵌入 $h_t$ 的情況下，上下文單詞嵌入 $h_c$ 的概率：
$$p(w_c|w_t)=\frac{\exp (h_c{h}_t^T)}{{\sum }_{i=1}^{|V|}\exp (h_i{h}_t^T)}$$
其中，$V$ 是大小為 $|V|$ 的詞匯表，詞匯表 (vocabulary) 是指在一個文本語料庫中出現的所有單詞的集合。可以使用集合數據結構去除重復的單詞，獲得詞匯表：

vocab = set(text)
VOCAB_SIZE = len(vocab)
print(f"Length of vocabulary = {VOCAB_SIZE}")
# Length of vocabulary = 33

得到詞匯表大小后，還需要定義參數 $N$，用于表示單詞向量的維度。通常情況下，這個值設置在 100 到 1000 之間。在本節中，由于數據集的規模有限，將其設置為 10。
skip-gram 模型僅由兩層組成：

• 權重為 $W_{embed}$ 的投影層 (projection layer)，將獨熱 (one-hot) 編碼詞向量作為輸入，并返回相應的 $N$ 維詞嵌入。它就像一個簡單的查找表，存儲預定維度的嵌入
• 權重為 $W_{output}$ 的全連接層 (fully connected layer)，將詞嵌入作為輸入，并輸出 $|V|$ 維 logits。對預測結果應用 softmax 函數，將 logits 轉換為概率

在 skip-gram 中沒有激活函數：Word2Vec 是一種線性分類器，可以模擬單詞之間的線性關系。
將獨熱編碼的單詞向量稱為輸入 $x$，相應的單詞嵌入可以通過簡單的投影計算得出：
$$h=W_{embed}^T?x$$
利用 skip-gram 模型，可以將以上概率改寫如下：
$$p(w_c|w_t)=\frac{\exp (W_{output}^T?x)}{{\sum }_{i=1}^{|V|}\exp (W_{outpu{t}_{(i)}}?h)}$$
skip-gram 模型會輸出一個 $|V|$ 維向量，它是詞匯表中每個單詞的條件概率：
$$word2vec(w_t)=\left[\begin{array}{c}p(w_1|w_t)\\ p(w_2|w_t)\\ ?\\ p(w_{|v|}|w_t)\end{array}\right]$$
在訓練過程中，這些概率會與正確的獨熱編碼目標單詞向量進行比較。這些值之間的差異(由損失函數計算，如交叉熵損失)通過網絡反向傳播，以更新權重并獲得更好的預測結果。

1.4 實現 Word2Vec 模型

Word2Vec 的整體架構如下所示，包括兩個權重矩陣(包括 $W_{embed}$ 和 $W_{output} )和最后的 softmax 層：

接下來，使用 gensim 庫實現 Word2Vec 模型，然后根據上一小節的文本構建詞匯表并訓練模型。gensim 庫的安裝和其他第三方庫一樣，可以在 shell 中執行以下命令進行安裝：

pip install gensim

(1) 導入 Word2Vec 類：

from gensim.models.word2vec import Word2Vec

(2) 使用對象 Word2Vec 和參數 sg=1 (skip-gram = 1) 初始化 skip-gram 模型：

model = Word2Vec([text],sg=1,   # Skip-gramvector_size=10,min_count=0,window=2,workers=1)

(3) 檢查權重矩陣 W_embed 的形狀，其應該與詞匯量大小和詞嵌入維度相對應：

print(f'Shape of W_embed: {model.wv.vectors.shape}')
# Shape of W_embed: (33, 10)

(4) 對模型訓練 10 個 epoch：

model.train([text], total_examples=model.corpus_count, epochs=10)

(5) 最后，打印一個單詞嵌入，觀察訓練結果：

print('\nWord embedding =')
print(model.wv[0])

輸出結果如下：

Word embedding =
[-0.00495417 -0.00025058  0.05408746  0.08913884 -0.09218638 -0.071533940.06835324  0.09274287 -0.05681597 -0.04169786]

雖然這種方法在處理小詞匯量時效果很好，但在大多數情況下，對數百萬個單詞(詞匯量)應用完整 softmax 函數的計算成本太高，這一直是開發精確語言模型的限制因素之一，但我們可以通過其他方法來解決這個問題。
Word2Vec 和 DeepWalk 通過實現 H-Softmax 技術解決此問題。與直接計算每個單詞的概率的 softmax 不同，H-Softmax 技術采用二叉樹結構，其中葉子節點是單詞。此外，還可以使用哈夫曼樹，將不常見的單詞存儲在比常見單詞更深的層次上。在大多數情況下，這種方法可以將單詞預測速度提高至少 50 倍。在 gensim 中，可以通過指定 hs=1 使用 H-Softmax。

2. DeepWalk 和隨機行走

DeepWalk 于 2014 年由 Perozzi 等人提出，并很快在圖學習中大受歡迎，它在多個數據集上的表現始終優于其他方法。雖然之后研究人員又提出了其他性能更高的架構，但 DeepWalk 作為一種簡單可靠的基準方法，能夠快速實現并解決大量問題。
DeepWalk 的目標是以無監督的方式生成高質量的節點特征表示。這一架構在很大程度上受到了 NLP 中 Word2Vec 的啟發。但 DeepWalk 所用的數據集由節點組成，而不是單詞，因此我們想要使用隨機游走來生成類似句子的有意義的節點序列。句子和圖之間的聯系如下所示：

隨機游走是通過在每一步隨機選擇一個相鄰節點而生成的節點序列。因此，節點可以在同一序列中出現多次。
即使節點是隨機選擇的，但它們經常一起出現在一個序列中，就意味著它們彼此接近。根據網絡同質性 ( network homophily) 假說，相互接近的節點是相似的。這在社交網絡中尤為明顯，因為在社交網絡中，人們會傾向于與朋友和家人建立聯系。
DeepWalk 算法的核心理念在于：當節點彼此接近時，我們希望相似度得分較高；相反，當節點之間距離較遠時，我們希望相似度得分較低。接下來，我們使用 networkx 庫實現隨機游走函數。

(1) 導入所需的庫：

import networkx as nx
import matplotlib.pyplot as plt
import random

(2) 利用 erdos_renyi_graph 函數生成一個隨機圖，圖中節點數量固定 (10)，節點之間建立邊的概率為 0.3：

G = nx.erdos_renyi_graph(10, 0.3, seed=1, directed=False)

(3) 繪制所生成的隨機圖：

nx.draw_networkx(G, pos=nx.spring_layout(G))
plt.axis('off')
plt.show()

(4) 實現隨機游走函數，函數使用兩個參數：起始節點 (start) 和游走長度 (length)。每走一步，我們都會使用 np.random.choice 隨機選擇一個相鄰節點，直到游走完成：

def random_walk(start, length):walk = [str(start)]  # starting nodefor i in range(length):neighbors = [node for node in G.neighbors(start)]next_node = np.random.choice(neighbors, 1)[0]walk.append(str(next_node))start = next_nodereturn walk

(5) 打印函數執行結果，起始節點為 0，長度為 10：

print(random_walk(0, 10))

輸出結果如下：

['0', '9', '0', '4', '3', '4', '3', '6', '2', '5', '6']

可以看到某些節點，如 0 和 9 經常出現在一起。考慮到這是一個同構圖，這意味著它們是相似的，這正是 DeepWalk 試圖捕捉的關系類型。

3. 實現 DeepWalk

了解了 DeepWalk 架構中的每個組件后，實現 DeepWalk 解決一個實際的機器學習問題。我們使用 Zachary’s Karate Club 數據集，它簡單地表示了 Wayne W. Zachary 研究的一個空手道俱樂部內部的關系。這是一種社交網絡，其中的每個節點都是一個成員，而在俱樂部之外進行互動的成員則被連接在一起。
在本例中，俱樂部被分為兩組：我們希望通過查看每個成員的連接，將每個成員分配到正確的組中(即節點分類，node classification)。

(1) 使用 nx.karate_club_graph() 導入數據集：

G = nx.karate_club_graph()

(2) 將字符串類標簽轉換成數值 (Mr. Hi = 0，Officer = 1)：

labels = []
for node in G.nodes:label = G.nodes[node]['club']labels.append(1 if label == 'Officer' else 0)

(3) 使用新標簽繪制圖：

plt.axis('off')
nx.draw_networkx(G, pos=nx.spring_layout(G, seed=0), node_color=labels)
plt.show()

(4) 接下來，生成隨機游走數據集，為圖中的每個節點創建 80 個長度為 10 的隨機游走序列：

walks = []
for node in G.nodes:for _ in range(80):walks.append(random_walk(node, 10))

(5) 打印一個隨機游走序列，驗證其正確性：

print(walks[0])
# ['0', '1', '30', '1', '3', '12', '3', '7', '3', '0', '17']

(6) 實現 Word2Vec，使用 skip-gram 模型，可以調整其他參數，以提高嵌入質量：

model = Word2Vec(walks,hs=1,   # Hierarchical softmaxsg=1,   # Skip-gramvector_size=100,window=10,workers=1)

(7) 在生成的隨機游走序列上對模型進行簡單的訓練：

# Build vocabulary
model.build_vocab(walks)
# Train model
model.train(walks, total_examples=model.corpus_count, epochs=30, report_delay=1)

(8) 模型訓練完成后，可以將其應用在不同任務中。例如，查找與給定節點最相似的節點(根據余弦相似度)：

print('Nodes that are the most similar to node 0:')
for similarity in model.wv.most_similar(positive=['0']):print(f'   {similarity}')

輸出結果如下所示：

另一個重要應用是計算兩個節點之間的相似度得分：

print(f"\nSimilarity between node 0 and 4: {model.wv.similarity('0', '4')}")
# Similarity between node 0 and 4: 0.6553224921226501

可以使用 t-distributed stochastic neighbor embedding (t-SNE) 繪制嵌入結果，從而將這些高維向量可視化為二維圖像：

(1) 從 sklearn 中導入 TSNE 類：

from sklearn.manifold import TSNE

(2) 創建兩個數組：一個用于存儲單詞嵌入，另一個用于存儲標簽：

nodes_wv = np.array([model.wv.get_vector(str(i)) for i in range(len(model.wv))])
labels = np.array(labels)

(3) 在嵌入上訓練 2 維 (n_components=2) t-SNE 模型：

tsne = TSNE(n_components=2,learning_rate='auto',init='pca',random_state=0).fit_transform(nodes_wv)

(4) 將訓練好的 t-SNE 模型生成的二維向量與相應的標簽繪制成二維圖像：

plt.figure(figsize=(6, 6))
plt.scatter(tsne[:, 0], tsne[:, 1], s=100, c=labels)
plt.show()

可以看到使用一條簡單的線就能夠將兩個類別區分開來。只要有足夠的訓練數據，簡單的機器學習算法就能對這些節點進行分類。接下來，我們實現一個分類器，并對節點嵌入進行訓練。

(1) 從 sklearn 中導入隨機森林 (Random Forest) 模型，使用準確率作為模型評估的指標：

from sklearn.ensemble import RandomForestClassifier
from sklearn.metrics import accuracy_score

(2) 將嵌入數據分成兩組：訓練數據和測試數據。一個簡單的方法是創建如下掩碼：

train_mask = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24]
test_mask = [0, 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 26, 27, 28, 29, 30, 31, 32, 33]

(3) 在訓練數據上訓練隨機森林分類器：

clf = RandomForestClassifier(random_state=0)
clf.fit(nodes_wv[train_mask], labels[train_mask])

(4) 在測試數據上根據準確率評估訓練好的模型：

y_pred = clf.predict(nodes_wv[test_mask])
acc = accuracy_score(y_pred, labels[test_mask])
print(f'Accuracy = {acc*100:.2f}%')
# Accuracy = 95.45%

可以看到，模型準確率為 95.45%，雖然仍有改進的余地，但本例展示了 DeepWalk 的兩個應用：

• 使用嵌入和余弦相似性發現節點之間的相似性(無監督學習)
• 將嵌入數據集用作節點分類等監督任務

學習節點表示可以為設計更深入、更復雜的架構提供了更大的靈活性。

小結

在本節中，我們了解了 DeepWalk 架構及其主要組件。然后，使用隨機游走將圖數據轉化為序列，并應用了 Word2Vec 算法，使用圖的拓撲信息創建節點嵌入，得到的嵌入結果可用于發現節點間的相似性，或作為其他算法的輸入。最后，我們使用監督方法解決了節點分類問題。

系列鏈接

圖神經網絡實戰——圖神經網絡(Graph Neural Networks, GNN)基礎
圖神經網絡實戰——圖論基礎