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}\cdot \vec{B}}{||\vec{A}||\cdot ||\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\cdot x$$
利用 skip-gram 模型，可以将以上概率改写如下：
$$p(w_c|w_t)=\frac{\exp (W_{output}^T\cdot x)}{{\sum }_{i=1}^{|V|}\exp (W_{outpu{t}_{(i)}}\cdot 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-gram
                 vector_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.07153394
  0.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 node
    
    for 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_node
    
    return 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 softmax
                 sg=1,   # Skip-gram
                 vector_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)基础
图神经网络实战——图论基础