随机游走与图嵌入：DeepWalk/Node2Vec

本文是两条子线的交汇点。Part 2 一路走来，我们先在 Art. 15 马尔可夫链中学到了转移矩阵 $P$ 如何编码状态之间的跳转概率，然后在 PageRank 中看到了这套工具在网页排序上的应用。同时，Part 1 的 Art. 11 Word2Vec 揭示了一个深刻的事实：Word2Vec 的 skip-gram with negative sampling（SGNS）本质上在隐式分解一个 PMI 矩阵。

现在，这两条线汇合了。DeepWalk 和 Node2Vec 做的事情是：在图上执行随机游走产生节点序列，然后把这些序列喂给 Word2Vec 来学习节点嵌入。 这意味着图嵌入的本质是——用随机游走把图的拓扑信息编码到”句子”中，再用矩阵分解把”句子”中的统计信息压缩到向量里。

为什么这个交汇重要？因为它把三个看似不同的概念统一在一个数学框架下：

图的转移矩阵 $P$ （Art. 15 的核心工具）
Word2Vec 的隐式矩阵分解（Art. 11 的核心定理）
图嵌入 = 图转移矩阵的隐式分解（本文的核心结论）

从直觉出发：把图”读”成句子

为什么需要图嵌入？

许多现实数据天然是图结构的：社交网络中的用户关系、蛋白质之间的相互作用、论文的引用网络。但大多数机器学习算法需要的输入是固定长度的向量——你不能直接把一个图的邻接矩阵丢给分类器。

图嵌入（graph embedding）的目标是：为图中的每个节点学习一个低维向量 $\mathbf{z}_v \in \mathbb{R}^d$ ，使得图中”相近”的节点在嵌入空间中也相近。

但”相近”在图上意味着什么？直接相连的节点当然相近，但两步可达、三步可达的节点呢？我们需要一种方式来度量图上节点之间的多跳相似性——这正是随机游走的用武之地。

随机游走 = 图上的马尔可夫链

回忆 Art. 15 马尔可夫链中马尔可夫链的定义：系统在有限状态空间上，每一步按转移概率跳转，下一步只取决于当前状态。

在图上做随机游走，就是把图中的节点当作状态，把边当作可能的转移。 设无向图 $G = (V, E)$ 有 $n$ 个节点，定义转移矩阵 $P \in \mathbb{R}^{n \times n}$ ：

$P_{uv} = \begin{cases} \frac{1}{\deg(u)} & \text{if } (u,v) \in E \\ 0 & \text{otherwise} \end{cases}$

其中 $\deg(u)$ 是节点 $u$ 的度（degree，即与 $u$ 相连的边数）。

逐项理解：

每一行是一个概率分布（行和为 1）—— $P$ 是行随机矩阵，与 Art. 15 的框架完全一致
从节点 $u$ 出发，等概率地跳转到 $u$ 的任一邻居
没有边连接的节点之间转移概率为 0

用矩阵语言， $P = D^{-1}A$ ，其中 $A$ 是邻接矩阵（adjacency matrix， $A_{uv} = 1$ if $(u,v) \in E$ ）， $D = \text{diag}(\deg(v_1), \ldots, \deg(v_n))$ 是度矩阵（degree matrix）。

从节点 $v_0$ 出发的一条长度为 $T$ 的随机游走产生一个节点序列：

$v_0 \to v_1 \to v_2 \to \cdots \to v_T$

其中每一步 $v_{t+1}$ 从 $v_t$ 的邻居中按转移概率随机选取。这个序列就是图上的一条”路径”——它隐含了图的拓扑信息。

核心洞察：随机游走序列 $(v_0, v_1, \ldots, v_T)$ 和自然语言中的句子 $(w_1, w_2, \ldots, w_T)$ 在形式上完全类似——都是从一个离散词汇表中按某种概率规则采样出的序列。如果我们把节点当作”词”，把游走序列当作”句子”，就可以直接用 Word2Vec 来学习节点的”嵌入向量”。

DeepWalk：图上的 Word2Vec

算法

Perozzi 等人在 2014 年提出的 DeepWalk（见 Perozzi et al., 2014）正是基于上述洞察。算法极其简洁：

DeepWalk 算法：

随机游走采样：对图中每个节点 $v$ ，执行 $\gamma$ 次长度为 $T$ 的均匀随机游走，产生序列集合
Word2Vec 训练：把所有游走序列当作”语料库”，用 skip-gram with negative sampling（SGNS）训练节点嵌入

就是这么简单——随机游走 + Word2Vec，两步完成图嵌入。 下图展示了完整的流水线以及它背后的数学本质。

DeepWalk 流水线：图 → 随机游走 → Word2Vec → 嵌入

形式化地，DeepWalk 的优化目标是最大化：

$\max_{\Phi} \sum_{v \in V} \sum_{c \in \mathcal{N}_R(v)} \log P(c \mid \Phi(v))$

其中：

$\Phi: V \to \mathbb{R}^d$ 是节点嵌入映射（将节点 $v$ 映射到 $d$ 维向量 $\Phi(v)$ ）
$\mathcal{N}_R(v)$ 是通过随机游走定义的节点 $v$ 的”上下文”——在长度为 $T$ 的游走序列中， $v$ 的窗口 $w$ 内出现的其他节点
$P(c \mid \Phi(v))$ 用 softmax（或 SGNS 近似）定义，形式与 Word2Vec 完全相同

与 Word2Vec 的精确对应

让我们把 DeepWalk 和 Word2Vec 的对应关系明确写出来：

Word2Vec	DeepWalk
词汇表 $\mathcal{V}$	节点集 $V$
语料库中的句子	随机游走产生的节点序列
词 $w_i$	节点 $v_i$
上下文窗口内的词 $c_j$	游走序列中窗口内的节点
词向量 $\mathbf{w}_i \in \mathbb{R}^d$	节点嵌入 $\Phi(v_i) \in \mathbb{R}^d$
PMI 矩阵 $M$	图上的”节点-上下文”统计矩阵

由 Art. 11 Word2Vec 中 Levy & Goldberg 的定理，SGNS 的最优解满足 $\mathbf{w}_i^T \mathbf{c}_j = \text{PMI}(w_i, c_j) - \log k$ 。将这个结论直接搬到 DeepWalk 上：

$\Phi(u)^T \Phi'(v) = \text{PMI}_{\text{graph}}(u, v) - \log k$

其中 $\Phi(u)$ 是节点 $u$ 的嵌入， $\Phi'(v)$ 是节点 $v$ 的”上下文嵌入”， $\text{PMI}_{\text{graph}}$ 是基于随机游走共现统计计算的 PMI。

关键问题：这个”图上的 PMI”到底和图的转移矩阵 $P$ 有什么关系？

图嵌入 = 图转移矩阵的隐式分解

DeepWalk 隐式分解的矩阵

Qiu 等人在 2018 年的论文（见 Qiu et al., 2018）给出了精确的回答。他们证明了：

定理（Qiu et al., 2018, Theorem 1）：DeepWalk 使用窗口大小 $w$ 时，等价于分解以下矩阵：

$M = \log\left(\frac{\text{vol}(G)}{w} \left(\sum_{r=1}^{w} P^r\right) D^{-1}\right) - \log k \cdot \mathbf{1}\mathbf{1}^T$

其中 $P = D^{-1}A$ 是图的转移矩阵， $D$ 是度矩阵， $\text{vol}(G) = \sum_v \deg(v)$ 是图的体积（volume）， $k$ 是负采样数。

逐项理解这个矩阵：

$P^r$ ：转移矩阵的 $r$ 次幂—— $(P^r)_{uv}$ 是从节点 $u$ 出发经过 $r$ 步随机游走到达节点 $v$ 的概率。回忆 Art. 15 中 $P^n$ 的含义。
$\sum_{r=1}^{w} P^r$ ：窗口大小 $w$ 内所有步数的转移概率之和——这衡量了节点 $u$ 和 $v$ 之间通过 1 步到 $w$ 步游走的”可达性”。
$D^{-1}$ ：按目标节点的度做归一化——高度节点自然有更多的随机游走经过，需要修正。
$\frac{\text{vol}(G)}{w}$ ：全局归一化常数。
$\log(\cdot)$ ：取对数，与 PMI 的对数形式对应。
$-\log k$ ：负采样的偏移量，与 Art. 11 中的偏移完全一致。

核心推论

这个定理的核心含义是：

$\boxed{\text{DeepWalk 嵌入} \approx \text{图转移矩阵多次幂的对数的低秩分解}}$

节点嵌入向量 $\Phi(u)$ 和 $\Phi'(v)$ 满足 $\Phi(u)^T\Phi'(v) \approx M_{uv}$ ，其中 $M$ 完全由转移矩阵 $P$ 决定。图的拓扑信息（编码在 $P$ 中）通过随机游走和 Word2Vec 的双重机制，被隐式分解到了低维节点向量中。

这正是 Part 1 和 Part 2 两条线的交汇：

Part 1 的工具（矩阵分解、低秩近似）
Part 2 的对象（转移矩阵 $P$ 、 $P^r$ 的概率含义）

数值例子：4 节点路径图

用一个最小的例子来完整展示从图到转移矩阵到共现矩阵的计算过程。

考虑 4 节点路径图 $1 - 2 - 3 - 4$ （节点 1 连 2，2 连 3，3 连 4）。

邻接矩阵和转移矩阵

$A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix}, \quad D = \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 1 \end{bmatrix}$

$P = D^{-1}A = \begin{bmatrix} 0 & 1 & 0 & 0 \\ 0.5 & 0 & 0.5 & 0 \\ 0 & 0.5 & 0 & 0.5 \\ 0 & 0 & 1 & 0 \end{bmatrix}$

验证行和：每行之和为 1 ✓。节点 1 只能走到节点 2（概率 1），节点 2 可以等概率走到 1 或 3，等等。

多步转移概率

$P^2 = \begin{bmatrix} 0.5 & 0 & 0.5 & 0 \\ 0 & 0.75 & 0 & 0.25 \\ 0.25 & 0 & 0.75 & 0 \\ 0 & 0.5 & 0 & 0.5 \end{bmatrix}$

$(P^2)_{13} = 0.5$ ：从节点 1 经过 2 步到达节点 3 的概率是 0.5（路径 $1 \to 2 \to 3$ ）。 $(P^2)_{14} = 0$ ：从节点 1 不可能恰好 2 步到达节点 4（因为路径长度必须为 3）。

$P^3 = \begin{bmatrix} 0 & 0.75 & 0 & 0.25 \\ 0.375 & 0 & 0.625 & 0 \\ 0 & 0.625 & 0 & 0.375 \\ 0.25 & 0 & 0.75 & 0 \end{bmatrix}$

$(P^3)_{14} = 0.25$ ：从节点 1 经过 3 步到达节点 4 的概率是 0.25。

窗口求和

取窗口大小 $w = 2$ ：

$\sum_{r=1}^{2} P^r = P + P^2 = \begin{bmatrix} 0.5 & 1 & 0.5 & 0 \\ 0.5 & 0.75 & 0.5 & 0.25 \\ 0.25 & 0.5 & 0.75 & 0.5 \\ 0 & 0.5 & 1 & 0.5 \end{bmatrix}$

观察这个矩阵的结构：

对角线上的值反映了节点”回到自身”的倾向——端点节点（1 和 4）的值较小（0.5），中间节点（2 和 3）较大（0.75）
$(P + P^2)_{14} = 0$ ：节点 1 和 4 在 2 步之内”看不到”对方——它们在嵌入空间中会距离较远
$(P + P^2)_{12} = 1$ ：节点 1 和 2 紧密相连——它们的嵌入会很接近

这个矩阵（取对数并做归一化后）就是 DeepWalk 隐式分解的目标。直觉上：矩阵中值越大的节点对，在嵌入空间中越接近。

Node2Vec：有偏随机游走

动机

DeepWalk 使用均匀随机游走——从当前节点等概率地选择一个邻居。但在许多图上，我们可能想捕获不同类型的”相似性”：

同质性（homophily）：相互连接的紧密社区中的节点应该有相似的嵌入（局部信息）
结构等价性（structural equivalence）：在图中扮演相似角色的节点（如不同社区的”桥梁”节点）应该有相似的嵌入（全局信息）

均匀随机游走对这两种信息没有偏好。Grover 和 Leskovec 在 2016 年提出的 Node2Vec（见 Grover & Leskovec, 2016）通过有偏随机游走来灵活控制探索策略。

Node2Vec 的 $p$ , $q$ 参数

Node2Vec 的核心创新是引入两个参数 $p$ （return parameter，返回参数）和 $q$ （in-out parameter，进出参数），控制游走的”偏向”。

设当前节点为 $v$ ，上一步来自节点 $t$ 。Node2Vec 定义从 $v$ 到邻居 $x$ 的非归一化转移概率为：

$\alpha_{pq}(t, x) = \begin{cases} \frac{1}{p} & \text{if } d_{tx} = 0 \quad (\text{即 } x = t \text{，返回上一个节点}) \\ 1 & \text{if } d_{tx} = 1 \quad (\text{即 } x \text{ 是 } t \text{ 的邻居，BFS 行为}) \\ \frac{1}{q} & \text{if } d_{tx} = 2 \quad (\text{即 } x \text{ 不是 } t \text{ 的邻居，DFS 行为}) \end{cases}$

其中 $d_{tx}$ 是节点 $t$ 和 $x$ 之间的最短路径长度（在原图上）。因为 $x$ 是 $v$ 的邻居，所以 $d_{tx}$ 只可能是 0、1 或 2。

归一化后的转移概率为：

$P'(x \mid v, t) = \frac{\alpha_{pq}(t, x) \cdot \mathbf{1}[(v,x) \in E]}{Z}$

其中 $Z = \sum_{x' \in \mathcal{N}(v)} \alpha_{pq}(t, x')$ 是归一化常数。

下图展示了从节点 $t$ 到达 $v$ 后， $v$ 的各邻居节点如何根据它们与 $t$ 的距离被赋予不同的权重。三种颜色对应三种情况：返回（ $1/p$ ）、BFS 行为（权重 $1$ ）、DFS 行为（ $1/q$ ）。

$p$ 和 $q$ 的效果分析

逐项分析三种节点的权重（参照原论文 Grover & Leskovec, 2016, Section 2.3）：

$d_{tx} = 0$ （ $x = t$ ，返回上一节点）：权重 $1/p$ 。 $p$ 大 → 返回权重低（避免回头）； $p$ 小 → 返回权重高（倾向回溯）。
$d_{tx} = 1$ （ $x$ 同时是 $t$ 和 $v$ 的邻居，局部三角结构）：权重固定为 1。这代表 BFS 行为——停留在源节点的局部邻域。
$d_{tx} = 2$ （ $x$ 不是 $t$ 的邻居，离源节点更远）：权重 $1/q$ 。 $q$ 小 → 远离权重高（DFS 行为，探索远方）； $q$ 大 → 远离权重低（被”拴在”局部）。

总结：

参数设置	游走行为	捕获的信息
$p = 1, q = 1$	均匀随机游走（= DeepWalk）	平衡
$q$ 小	DFS 偏向：探索远方	结构等价性
$q$ 大	BFS 偏向：留在局部	同质性

注意：Node2Vec 的有偏游走不再是标准的马尔可夫链（因为转移概率取决于上一个节点 $t$ ，违反了无记忆性）。严格来说，它是一个二阶马尔可夫链——状态是节点对 $(t, v)$ 而非单个节点。

可视化：随机游走策略对比

下面的交互组件展示了一个 7 节点的无向图。你可以切换三种游走策略（均匀/BFS 偏向/DFS 偏向），观察不同策略产生的游走路径有什么区别。

随机游走路径可视化

p=1, q=1 — 等概率选择邻居（DeepWalk）

步:0/12

探索建议：

均匀随机游走：观察路径如何在图中”随意漫游”，没有明显的方向偏好
BFS 偏向（ $p=4, q=4$ ）：观察路径如何倾向于在局部邻域来回游走，较少远离出发点
DFS 偏向（ $p=0.25, q=0.25$ ）：观察路径如何倾向于快速远离出发点，探索图的不同区域
点击”换一条路径”多次，感受同一策略下不同路径的统计差异

图嵌入的矩阵分解视角：统一框架

从 Word2Vec 到 DeepWalk 的矩阵分解链

让我们把完整的推导链条串起来，展示图嵌入如何归结为矩阵分解。

第一环：Word2Vec = PMI 矩阵分解（Art. 11）

Levy & Goldberg (2014) 证明了 SGNS 的最优解满足：

$\mathbf{w}_i^T \mathbf{c}_j = \text{PMI}(w_i, c_j) - \log k$

第二环：DeepWalk 的”语料”来自随机游走

DeepWalk 的”语料”不是自然语言文本，而是随机游走序列。节点 $u$ 和 $v$ 的”共现次数”由它们在游走序列的窗口内共同出现的频率决定。

一个关键的概率计算：从节点 $u$ 出发，在窗口大小 $w$ 内”看到”节点 $v$ 的概率是什么？

$P(\text{see } v \text{ in window} \mid \text{start at } u) = \frac{1}{w}\sum_{r=1}^{w}(P^r)_{uv}$

这就是窗口内各步转移概率的平均。

第三环：代入 PMI 定义

随机游走的”词频”（节点 $v$ 被访问的频率）与稳态分布有关。对于无向图的均匀随机游走，稳态分布为：

$\pi_v^* = \frac{\deg(v)}{\text{vol}(G)}$

其中 $\text{vol}(G) = \sum_v \deg(v) = 2|E|$ 是图的体积。

因此节点对 $(u, v)$ 的 PMI 为：

$\text{PMI}(u, v) = \log\frac{P(u, v)}{P(u) \cdot P(v)}$

其中 $P(u, v)$ 正比于 $\frac{1}{w}\sum_{r=1}^{w}(P^r)_{uv}$ ， $P(u) = \pi_u^* = \frac{\deg(u)}{\text{vol}(G)}$ ， $P(v) = \pi_v^*$ 。

代入并整理（详细推导见 Qiu et al., 2018）后得到 DeepWalk 隐式分解的矩阵 $M$ 。

最终结果：

$\Phi(u)^T \Phi'(v) \approx M_{uv} = \log\left(\frac{\text{vol}(G)}{w} \cdot \frac{\left(\sum_{r=1}^{w}(P^r)_{uv}\right)}{\deg(v)}\right) - \log k$

Node2Vec 的矩阵分解

Node2Vec 的分析更复杂，因为有偏游走引入了二阶依赖。Qiu et al. (2018) 表明 Node2Vec 也等价于分解一个矩阵，但该矩阵由二阶转移矩阵决定，解析形式更复杂。

直觉上：不同的 $p, q$ 参数改变了随机游走的转移概率，从而改变了隐式分解的目标矩阵，最终导致学到的嵌入捕获不同类型的图信息。

方法谱系中的位置

把图嵌入放入 Part 1 和 Part 2 建立的方法谱系中：

方法	隐式分解的矩阵	数据来源
Word2Vec（Art. 11）	$\text{PMI}_{\text{text}} - \log k$	文本语料的词-上下文共现
DeepWalk	$\log\!\left(\frac{\text{vol}(G)}{w}\sum_{r=1}^{w}P^r D^{-1}\right) - \log k$	图上均匀随机游走
Node2Vec	类似，但用二阶转移矩阵	图上有偏随机游走

核心数学不变：都是某种统计矩阵的低秩分解。 变化的只是统计矩阵的来源——文本共现、均匀游走共现、有偏游走共现。

两条子线的交汇：回顾

让我们退后一步，审视本文在整条路径中的位置。

时序方法子线（Part 2）：

Art. 15 马尔可夫链：转移矩阵 $P$ ， $\boldsymbol{\pi}_{t+1} = \boldsymbol{\pi}_t P$ ，稳态分布 = 特征值 1 的特征向量
PageRank：在网页图上应用马尔可夫链，加入阻尼因子
Art. 19（本文）：在任意图上做随机游走，产生训练序列

矩阵分解子线（Part 1）：

Art. 3 SVD：矩阵的最优低秩近似
Art. 11 Word2Vec：SGNS = PMI 矩阵的隐式分解
Art. 19（本文）：图嵌入 = 图转移矩阵多次幂的对数的隐式分解

交汇点：本文把时序方法（随机游走产生序列）和矩阵分解方法（Word2Vec 分解 PMI）结合在一起，用于图数据。同一套数学工具——转移矩阵、矩阵幂、低秩分解——在全新的语境下产生了图嵌入这一实用方法。

总结与展望

本文展示了 Part 1 和 Part 2 两条线的一次优美交汇：

随机游走 = 图上的马尔可夫链：转移矩阵 $P = D^{-1}A$ ，每一步按概率跳转到邻居
DeepWalk = 随机游走 + Word2Vec：在图上做均匀随机游走产生序列，然后用 SGNS 训练节点嵌入
Node2Vec = 有偏随机游走 + Word2Vec：用 $p, q$ 参数控制 BFS vs DFS 倾向，灵活捕获同质性或结构等价性
图嵌入 = 图转移矩阵的隐式分解：DeepWalk 等价于分解 $\log\!\left(\frac{\text{vol}(G)}{w}\sum_{r=1}^{w}P^r D^{-1}\right) - \log k$
统一框架：Word2Vec 分解文本 PMI，DeepWalk 分解图的转移矩阵——核心操作（低秩分解）不变，变化的只是数据来源

下一篇我们从离散图转向连续空间。Art. 20 Kernel 矩阵引入核函数 $k(\mathbf{x}_i, \mathbf{x}_j)$ ——一种度量连续空间中任意两点相似度的方式，将数据”隐式”映射到高维特征空间。Kernel 矩阵是由数据定义的给定算子，它的半正定性和谱分解直接连接回 Part 1 的工具，同时为 Part 2 最后两站——图拉普拉斯与图神经网络——铺设数学基础。