网络表示学习：谱嵌入与随机游走嵌入

编码器–解码器框架

网络嵌入（network embedding，图表示学习）把每个节点 $v$ 映射为一个低维向量 $z_v\in\mathbb{R}^d$，使得向量之间的几何关系（内积、距离）反映网络中的关系（邻接、多步可达、结构角色）。Hamilton（2020）用统一的编码器–解码器框架描述这类方法：

• 编码器 $\mathrm{ENC}(v)=z_v$：对“浅层嵌入”就是查表，每个节点一个自由参数向量；
• 解码器 $\mathrm{DEC}(z_u,z_v)$：给出一个相似度估计，例如内积 $z_u^{\top}z_v$；
• 目标：让 $\mathrm{DEC}(z_u,z_v)$ 逼近某个网络相似度 $S[u,v]$（邻接、共同邻居数、随机游走共现概率等）。

不同方法的差别主要在于选择哪个 $S$ 和哪个损失函数。

谱嵌入：拉普拉斯特征映射

Belkin 与 Niyogi（2003）的拉普拉斯特征映射要求相连节点的嵌入彼此接近：

$$\min_{Y}\ \sum_{i,j}W_{ij}\,\|y_i-y_j\|^2=2\,\mathrm{tr}(Y^{\top}LY)\quad\text{s.t.}\quad Y^{\top}DY=I .$$

约束排除了全部节点坍缩到同一点的平凡解。拉格朗日条件给出广义特征值问题 $Ly=\lambda Dy$，取除常向量外最小的 $d$ 个特征向量作为坐标。它与谱聚类（见谱方法与层次聚类）同源：Fiedler 向量就是一维的拉普拉斯嵌入。谱嵌入是确定性的、可解释的，但只编码一阶邻近关系，且对大规模网络需要稀疏特征值求解。

随机游走嵌入：DeepWalk 与 node2vec

DeepWalk（Perozzi 等，2014）把网络上的截断随机游走当作“句子”、节点当作“词”，用自然语言处理中的 skip-gram 模型学习嵌入：在同一游走中、窗口距离不超过 $w$ 的节点对被视为“共现”，目标是让共现节点的内积大、随机负样本的内积小。带负采样的目标函数为

$$\max\ \sum_{(u,v)\in\mathcal{D}}\Big[\log\sigma(z_u^{\top}z_v)+k\,\mathbb{E}_{n\sim P_{\text{neg}}}\log\sigma(-z_u^{\top}z_n)\Big].$$

node2vec（Grover 与 Leskovec，2016）把游走改为二阶有偏随机游走：从 $t$ 刚走到 $v$，下一步走向 $v$ 的邻居 $x$ 的非归一化概率为 $\pi_{vx}=\alpha_{pq}(t,x)\,w_{vx}$，

$$\alpha_{pq}(t,x)=\begin{cases}1/p, & d_{tx}=0\ (\text{回到 } t)\\ 1, & d_{tx}=1\ (x \text{ 与 } t \text{ 相邻})\\ 1/q, & d_{tx}=2\end{cases}$$

返回参数 $p$ 控制折返的倾向；进出参数 $q$ 控制向外探索的倾向：$q<1$ 时游走更像深度优先，倾向于捕捉社团（同质性）；$q>1$ 时更像广度优先，停留在局部，倾向于捕捉结构角色。

算例：游走从 $t$ 走到 $v$，$v$ 的邻居为 $t$、$x_1$（与 $t$ 相邻）、$x_2$（与 $t$ 不相邻），无权网络，$p=1,q=0.5$。非归一化概率依次为 $1,1,2$，归一化后为 $0.25,0.25,0.5$：游走更可能离开 $t$ 的邻域。

嵌入即矩阵分解

Qiu 等（2018）证明，DeepWalk 在负采样下隐式地分解一个矩阵，近似为

$$\log\Big(\frac{\mathrm{vol}(G)}{bT}\Big(\sum_{r=1}^{T}(D^{-1}A)^r\Big)D^{-1}\Big),$$

其中 $T$ 是窗口大小、$b$ 是负样本数、$\mathrm{vol}(G)=\sum_i d_i$。也就是说，随机游走嵌入本质上是对“多步转移概率”做对数变换后的低秩分解，与谱方法属于同一家族。代码示例就用“随机游走共现矩阵 → 正点互信息（PPMI）→ 截断 SVD”实现了一个 node2vec 式嵌入，避免依赖深度学习库。

浅层嵌入的局限

1. 转导式：只能为训练时见过的节点产生嵌入，新加入的节点（新药、新患者）需要重新训练；
2. 不使用节点特征：基因表达、分子结构、影像特征等信息无法自然纳入；
3. 参数随节点数线性增长，不同节点之间不共享参数；
4. 嵌入的坐标没有直接含义，且不同次训练得到的嵌入只在旋转意义下等价，不能跨次比较坐标。

这些局限正是图神经网络的动机。对多关系的知识图谱，还有专门的嵌入方法（把关系建模为向量空间中的平移或双线性变换），见 Hamilton（2020）第 4 章。