图神经网络中的DeepWalk算法原理与随机游走机制
字数 3220 2025-12-08 15:11:38

图神经网络中的DeepWalk算法原理与随机游走机制

题目描述：DeepWalk是一种用于图结构数据的无监督学习算法，它将图中的节点表示为低维向量（嵌入）。它通过从每个节点出发进行随机游走来生成节点序列，然后将这些序列视为“句子”，利用自然语言处理中的Word2Vec技术（特别是Skip-Gram模型）来学习节点的向量表示。题目要求详细解释DeepWalk算法的核心思想、随机游走生成过程、如何将图数据转化为序列数据，以及通过Skip-Gram模型训练节点嵌入的完整流程。

解题过程：

  1. 问题背景与核心思想

    • 在许多实际问题中，数据可以表示为图（Graph），例如社交网络、引文网络、蛋白质相互作用网络。图中的节点代表实体（如用户、论文、蛋白质），边代表实体间的关系。
    • 目标是为每个节点学习一个低维的连续向量表示（称为嵌入，embedding），使得在原始图中相似（例如连接紧密或有相似连接结构）的节点，在向量空间中的表示也相似。
    • 传统方法（如邻接矩阵特征值分解）计算复杂度高，难以处理大规模图。DeepWalk的创新在于：它将图数据与自然语言处理（NLP）中的文本数据类比。具体来说：
      • 将图中的节点类比为词汇表中的一个单词。
      • 将从节点出发的随机游走生成的节点序列类比为一个句子。
      • 这样，整个图就变成了由许多“句子”（随机游走序列）组成的“语料库”。
    • 然后，直接应用NLP中成熟的Word2Vec（Skip-Gram）模型来从这些“句子”中学习每个“单词”（节点）的向量表示。其核心思想是：在随机游走序列中共现的节点，它们在原始图中的距离也应该较近，因此它们的向量表示也应该相似。

  2. 第一步：生成随机游走序列

    • 这是将图结构数据转化为序列数据的关键步骤。
    • 输入：一个图 \(G = (V, E)\)，其中 \(V\) 是节点集，\(E\) 是边集。设定两个超参数：游走长度 \(l\)（每个序列的长度）和每个节点开始的游走次数 \(\gamma\)。
    • 过程：
      a. 算法外循环执行 \(\gamma\) 次。每一次循环，都将节点集合 \(V\) 随机打乱（shuffle）。这保证了遍历节点的随机性，避免因节点顺序引入偏差。
      b. 对于打乱后的节点列表中的每一个节点 \(v_i \in V\)，执行一次随机游走（Random Walk）。
    • 随机游走的具体实现：
      • 从当前节点 \(v_i\) 开始，初始化序列 \(walk = [v_i]\)。
      • 然后进行 \(l-1\) 步迭代。在每一步，查看当前节点的邻居节点集合。均匀随机地选择一个邻居节点作为下一步移动到的节点，并将其添加到序列 \(walk\) 末尾。
      • 这个过程可以看作一个一阶马尔可夫过程，下一步节点只依赖于当前节点。
    • 输出：最终我们会得到 \(\gamma \times |V|\) 条随机游走序列，每条序列长度为 \(l\)。这些序列构成了我们的“语料库”。

  3. 第二步：使用Skip-Gram模型学习嵌入

    • 现在我们有了“句子”（随机游走序列），目标是学习每个节点的向量表示。DeepWalk采用Word2Vec中的Skip-Gram模型来完成这个任务。
    • Skip-Gram模型的目标：对于一个序列中的中心节点，模型的目标是预测其上下文节点（即在其前后一定窗口内出现的节点）。
    • 模型设置：
      a. 每个节点 \(v\) 对应两个向量表示：作为中心节点时的向量 \(\mathbf{u}_v\) 和作为上下文节点时的向量 \(\mathbf{v}_v\)。通常，我们最终使用 \(\mathbf{u}_v\) 作为节点的嵌入。
      b. 设定一个上下文窗口大小 \(w\)。对于一个给定序列 \(... , v_{i-w}, ..., v_{i-1}, v_i, v_{i+1}, ..., v_{i+w}, ...\)，中心节点为 \(v_i\)，其上下文节点集合为 \(C(v_i) = \{ v_{i-w}, ..., v_{i-1}, v_{i+1}, ..., v_{i+w} \}\)。
    • 优化目标（损失函数）：
      • 对于给定的中心节点 \(v_i\) 和一个上下文节点 \(v_j \in C(v_i)\)，我们希望其共现概率（用softmax函数计算）尽可能大。
      • 形式化地，Skip-Gram模型旨在最大化以下对数似然函数：

\[ \max \sum_{i=1}^{|V|} \sum_{j \in C(v_i)} \log p(v_j | v_i) \]

   其中，条件概率 $p(v_j | v_i)$ 通过softmax函数定义：

\[ p(v_j | v_i) = \frac{\exp(\mathbf{u}_{v_i}^T \mathbf{v}_{v_j})}{\sum_{k=1}^{|V|} \exp(\mathbf{u}_{v_i}^T \mathbf{v}_{v_k})} \]

 - 这里，$\mathbf{u}_{v_i}$ 是中心节点 $v_i$ 的向量，$\mathbf{v}_{v_j}$ 是上下文节点 $v_j$ 的向量。分母的计算需要对所有节点求和，在节点数 $|V|$ 很大时计算成本极高。
  • 训练技巧：负采样（Negative Sampling）
    • 为了高效计算，DeepWalk在实际训练时使用负采样来近似上述目标。
    • 新的优化目标变为：对于每个（中心节点，正上下文节点）对 \((v_i, v_j)\)，我们同时采样 \(K\) 个“负样本”节点（即图中随机抽取的、通常不在 \(v_i\) 上下文中的节点）。
    • 目标函数变为最大化正样本对的相似度，同时最小化负样本对的相似度：

\[ \log \sigma(\mathbf{u}_{v_i}^T \mathbf{v}_{v_j}) + \sum_{n=1}^{K} \mathbb{E}_{v_n \sim P_n(v)} [\log \sigma(-\mathbf{u}_{v_i}^T \mathbf{v}_{v_n})] \]

   其中 $\sigma$ 是sigmoid函数，$P_n(v)$ 是一个噪声分布（通常为节点频率的3/4次幂），用于采样负样本节点 $v_n$。
 - 负采样极大地降低了计算复杂度，从 $O(|V|)$ 降至 $O(K)$，使得模型能处理大规模图。
  1. 第三步：模型训练与输出
    • 将第一步生成的所有随机游走序列作为输入数据，通过带有负采样的Skip-Gram模型进行训练。
    • 训练可以使用随机梯度下降（SGD）或其变体（如Mikolov原始Word2Vec实现中使用的自适应学习率方法）。
    • 训练完成后，我们得到每个节点 \(v\) 的向量表示 \(\mathbf{u}_v \in \mathbb{R}^d\)，其中 \(d\) 是预设的嵌入维度（通常远小于节点总数 \(|V|\)）。
    • 这些向量捕获了图中的社区结构信息：在随机游走中经常一起出现的节点，它们的向量在低维空间里距离很近。例如，在社交网络中，同一个社群（community）的用户，其嵌入向量会很相似。

总结：
DeepWalk算法的核心贡献在于巧妙地通过随机游走将图结构数据转化为序列数据，从而可以借用成熟的NLP模型（Skip-Gram with Negative Sampling）来高效学习节点嵌入。整个过程是无监督的，只需输入图结构，不需要节点标签。其成功的关键在于随机游走序列的局部共现性能够有效反映原始图中的节点相似性。这个算法简单、有效，为后续许多图嵌入和图神经网络方法奠定了基础。

图神经网络中的DeepWalk算法原理与随机游走机制 题目描述 ：DeepWalk是一种用于图结构数据的无监督学习算法，它将图中的节点表示为低维向量（嵌入）。它通过从每个节点出发进行随机游走来生成节点序列，然后将这些序列视为“句子”，利用自然语言处理中的Word2Vec技术（特别是Skip-Gram模型）来学习节点的向量表示。题目要求详细解释DeepWalk算法的核心思想、随机游走生成过程、如何将图数据转化为序列数据，以及通过Skip-Gram模型训练节点嵌入的完整流程。 解题过程 ： 问题背景与核心思想 在许多实际问题中，数据可以表示为图（Graph），例如社交网络、引文网络、蛋白质相互作用网络。图中的节点代表实体（如用户、论文、蛋白质），边代表实体间的关系。 目标是为每个节点学习一个低维的连续向量表示（称为嵌入，embedding），使得在原始图中相似（例如连接紧密或有相似连接结构）的节点，在向量空间中的表示也相似。 传统方法（如邻接矩阵特征值分解）计算复杂度高，难以处理大规模图。DeepWalk的创新在于：它将图数据与自然语言处理（NLP）中的文本数据 类比 。具体来说： 将 图中的节点 类比为 词汇表中的一个单词 。 将从节点出发的 随机游走生成的节点序列 类比为 一个句子 。 这样，整个图就变成了由许多“句子”（随机游走序列）组成的“语料库”。 然后，直接应用NLP中成熟的Word2Vec（Skip-Gram）模型来从这些“句子”中学习每个“单词”（节点）的向量表示。其核心思想是：在随机游走序列中 共现 的节点，它们在原始图中的距离也应该较近，因此它们的向量表示也应该相似。 第一步：生成随机游走序列 这是将图结构数据转化为序列数据的关键步骤。 输入 ：一个图 \(G = (V, E)\)，其中 \(V\) 是节点集，\(E\) 是边集。设定两个超参数：游走长度 \(l\)（每个序列的长度）和每个节点开始的游走次数 \(\gamma\)。 过程 ： a. 算法外循环执行 \(\gamma\) 次。每一次循环，都将节点集合 \(V\) 随机打乱（shuffle）。这保证了遍历节点的随机性，避免因节点顺序引入偏差。 b. 对于打乱后的节点列表中的每一个节点 \(v_ i \in V\)，执行一次 随机游走 （Random Walk）。 随机游走的具体实现 ： 从当前节点 \(v_ i\) 开始，初始化序列 \(walk = [ v_ i ]\)。 然后进行 \(l-1\) 步迭代。在每一步，查看当前节点的邻居节点集合。 均匀随机 地选择一个邻居节点作为下一步移动到的节点，并将其添加到序列 \(walk\) 末尾。 这个过程可以看作一个 一阶马尔可夫过程 ，下一步节点只依赖于当前节点。 输出 ：最终我们会得到 \(\gamma \times |V|\) 条随机游走序列，每条序列长度为 \(l\)。这些序列构成了我们的“语料库”。 第二步：使用Skip-Gram模型学习嵌入 现在我们有了“句子”（随机游走序列），目标是学习每个节点的向量表示。DeepWalk采用Word2Vec中的Skip-Gram模型来完成这个任务。 Skip-Gram模型的目标 ：对于一个序列中的 中心节点 ，模型的目标是 预测其上下文节点 （即在其前后一定窗口内出现的节点）。 模型设置 ： a. 每个节点 \(v\) 对应两个向量表示：作为 中心节点 时的向量 \(\mathbf{u} v\) 和作为 上下文节点 时的向量 \(\mathbf{v} v\)。通常，我们最终使用 \(\mathbf{u} v\) 作为节点的嵌入。 b. 设定一个上下文窗口大小 \(w\)。对于一个给定序列 \(... , v {i-w}, ..., v {i-1}, v_ i, v {i+1}, ..., v_ {i+w}, ...\)，中心节点为 \(v_ i\)，其上下文节点集合为 \(C(v_ i) = \{ v_ {i-w}, ..., v_ {i-1}, v_ {i+1}, ..., v_ {i+w} \}\)。 优化目标（损失函数） ： 对于给定的中心节点 \(v_ i\) 和一个上下文节点 \(v_ j \in C(v_ i)\)，我们希望其共现概率（用softmax函数计算）尽可能大。 形式化地，Skip-Gram模型旨在最大化以下对数似然函数： \[ \max \sum_ {i=1}^{|V|} \sum_ {j \in C(v_ i)} \log p(v_ j | v_ i) \] 其中，条件概率 \(p(v_ j | v_ i)\) 通过softmax函数定义： \[ p(v_ j | v_ i) = \frac{\exp(\mathbf{u} {v_ i}^T \mathbf{v} {v_ j})}{\sum_ {k=1}^{|V|} \exp(\mathbf{u} {v_ i}^T \mathbf{v} {v_ k})} \] 这里，\(\mathbf{u} {v_ i}\) 是中心节点 \(v_ i\) 的向量，\(\mathbf{v} {v_ j}\) 是上下文节点 \(v_ j\) 的向量。分母的计算需要对所有节点求和，在节点数 \(|V|\) 很大时计算成本极高。 训练技巧：负采样（Negative Sampling） 为了高效计算，DeepWalk在实际训练时使用 负采样 来近似上述目标。 新的优化目标变为：对于每个（中心节点，正上下文节点）对 \((v_ i, v_ j)\)，我们同时采样 \(K\) 个“负样本”节点（即图中随机抽取的、通常不在 \(v_ i\) 上下文中的节点）。 目标函数变为最大化正样本对的相似度，同时最小化负样本对的相似度： \[ \log \sigma(\mathbf{u} {v_ i}^T \mathbf{v} {v_ j}) + \sum_ {n=1}^{K} \mathbb{E} {v_ n \sim P_ n(v)} [ \log \sigma(-\mathbf{u} {v_ i}^T \mathbf{v}_ {v_ n}) ] \] 其中 \(\sigma\) 是sigmoid函数，\(P_ n(v)\) 是一个噪声分布（通常为节点频率的3/4次幂），用于采样负样本节点 \(v_ n\)。 负采样极大地降低了计算复杂度，从 \(O(|V|)\) 降至 \(O(K)\)，使得模型能处理大规模图。 第三步：模型训练与输出 将第一步生成的所有随机游走序列作为输入数据，通过带有负采样的Skip-Gram模型进行训练。 训练可以使用随机梯度下降（SGD）或其变体（如Mikolov原始Word2Vec实现中使用的自适应学习率方法）。 训练完成后，我们得到每个节点 \(v\) 的向量表示 \(\mathbf{u}_ v \in \mathbb{R}^d\)，其中 \(d\) 是预设的嵌入维度（通常远小于节点总数 \(|V|\)）。 这些向量捕获了图中的社区结构信息：在随机游走中经常一起出现的节点，它们的向量在低维空间里距离很近。例如，在社交网络中，同一个社群（community）的用户，其嵌入向量会很相似。 总结 ： DeepWalk算法的核心贡献在于巧妙地通过 随机游走 将图结构数据转化为序列数据，从而可以借用成熟的NLP模型（Skip-Gram with Negative Sampling）来高效学习节点嵌入。整个过程是无监督的，只需输入图结构，不需要节点标签。其成功的关键在于 随机游走序列的局部共现性能够有效反映原始图中的节点相似性 。这个算法简单、有效，为后续许多图嵌入和图神经网络方法奠定了基础。