图嵌入与图神经网络：把图变成向量

在前面的文章中，我们已经积累了丰富的图算法工具箱——BFS/DFS（Art. 1）让我们遍历图，最短路径（Art. 6）和中心性（Art. 7）帮我们度量距离和重要性，社区发现（Art. 8）找到群组结构，相似性与同构（Art. 9）比较图的结构。但这些算法都有一个共同的局限：它们的输出是图上的离散结构（路径、社区、标签），而不是机器学习管线需要的固定维度数值向量。

本文的核心问题：图结构不是规则的网格（不像图像有像素矩阵，文本有词序列）——节点数量不固定，邻居数量不统一，没有自然的空间排序。传统机器学习模型（逻辑回归、SVM、神经网络）需要固定维度的输入向量。怎么把一张图、一个节点、或一条边变成一个向量，同时保留关键的结构信息？

这就是图嵌入（Graph Embedding）要解决的问题——把图中的实体映射到低维连续向量空间，使得图中的结构关系（邻近性、相似性）在向量空间中得到保持。

算法范式：消息传递（GNN）、穷举搜索（随机游走采样）

核心思路：从图到向量的两条路

解决”图 → 向量”问题有两大类方法：

1. 浅层嵌入（Shallow Embedding）：给每个节点直接分配一个可学习的向量，通过优化目标函数让相邻/相近的节点向量接近。代表方法：DeepWalk、Node2Vec、LINE。思想类似 NLP 中的 Word2Vec——先生成”上下文”，再学习嵌入。

2. 图神经网络（GNN）：用参数共享的神经网络作为编码器，通过消息传递机制逐层聚合邻域信息，输出每个节点的表示向量。代表方法：GCN、GAT、GraphSAGE。思想类似 CNN 对图像的卷积——但在不规则的图结构上。

两类方法的核心直觉完全一致：图中相邻 / 相近的节点，在向量空间中也应该接近。 区别在于编码器的设计：浅层方法用查找表，深度方法用神经网络。

Section A: 浅层嵌入——随机游走 + 自监督学习

DeepWalk：Graph 上的 Word2Vec

DeepWalk（Perozzi et al., 2014）是第一个将 NLP 中的词嵌入思想迁移到图上的方法。核心洞察来自一个有趣的类比：

NLP	图
文档	图
句子	随机游走序列
词	节点
上下文窗口中的共现	游走序列中的共现
Word2Vec	DeepWalk

算法步骤：

1. 随机游走采样：从每个节点 $v$ 出发，进行 $\gamma$ 次长度为 $t$ 的随机游走。在每一步，从当前节点的邻居中均匀随机选择下一个节点。
2. 生成序列：每次游走产生一个节点序列 $(v_0, v_1, v_2, \ldots, v_t)$，类似于一个”句子”。
3. 训练 Word2Vec：将这些序列输入 Skip-Gram 模型，优化目标是：对于序列中的每个节点 $v_i$，最大化预测其上下文窗口（大小为 $w$）中其他节点的概率：

$\max \sum_{v_i \in \text{walk}} \sum_{-w \leq j \leq w, j \neq 0} \log P(v_{i+j} \mid v_i)$

逐项拆解：

• 外层求和遍历游走序列中的每个节点 $v_i$
• 内层求和遍历 $v_i$ 的上下文窗口（前后各 $w$ 个节点）
• $P(v_{i+j} \mid v_i)$ 使用 softmax（或负采样近似）计算
• 优化的结果：频繁共现在同一游走中的节点对，其向量会接近

为什么随机游走有效？ 随机游走序列携带了图的拓扑信息——如果两个节点 $u$ 和 $v$ 在图上距离很近（或处于同一个紧密社区），它们就更可能出现在同一个随机游走中，因而在 Skip-Gram 训练中被推向相近的向量。这与 Art. 7 PageRank 中的随机冲浪者直觉异曲同工。

复杂度：

• 采样阶段：$O(\gamma \cdot |V| \cdot t)$（$\gamma$ 次游走 × $|V|$ 个起点 × 每次 $t$ 步）
• 训练阶段：$O(\gamma \cdot |V| \cdot t \cdot w \cdot d)$（$d$ 是嵌入维度）
• 典型参数：$\gamma = 10$，$t = 80$，$w = 10$，$d = 128$

Node2Vec：有偏随机游走

DeepWalk 使用均匀随机游走——在每一步等概率选择下一个邻居。Node2Vec（Grover & Leskovec, 2016）的核心创新是引入有偏随机游走，通过两个参数 $p$ 和 $q$ 控制游走的行为，平衡两种不同的结构信息探索策略。

假设上一步从节点 $t$ 走到了节点 $v$，现在要从 $v$ 选择下一个节点 $x$。Node2Vec 定义的转移概率为：

$P(x \mid v, t) \propto \alpha_{pq}(t, x) \cdot w_{vx}$

其中 $w_{vx}$ 是边权（无权图为 1），$\alpha_{pq}$ 是偏置因子：

$\alpha_{pq}(t, x) = \begin{cases} 1/p & \text{if } d_{tx} = 0 \text{（回到 } t \text{）} \\ 1 & \text{if } d_{tx} = 1 \text{（$x$ 是 $t$ 的邻居）} \\ 1/q & \text{if } d_{tx} = 2 \text{（$x$ 不是 $t$ 的邻居）} \end{cases}$

逐项拆解：

• $d_{tx}$ 是节点 $t$ 到节点 $x$ 的最短距离（只能是 0、1 或 2，因为 $x$ 是 $v$ 的邻居，$t$ 也是 $v$ 的邻居）
• $p$ 控制回退概率：$p$ 越大，$1/p$ 越小，越不倾向回到刚来的节点 $t$
• $q$ 控制探索策略：
  • $q < 1$（即 $1/q > 1$）：倾向走向离 $t$ 更远的节点 → DFS 倾向，探索图的远处区域
  • $q > 1$（即 $1/q < 1$）：倾向留在 $t$ 附近 → BFS 倾向，探索局部邻域

两种策略对应两种不同类型的结构信息：

• BFS 倾向（大 $q$）→ 捕获结构等价性（structural equivalence）：功能角色相似的节点（如两个不同社区中的”桥梁节点”）会获得相近的嵌入
• DFS 倾向（小 $q$）→ 捕获同质性（homophily）：同一社区/群组中的节点会获得相近的嵌入

这给了实践者一个灵活的旋钮——根据下游任务的需要选择合适的 $p$ 和 $q$。

LINE：显式建模一阶和二阶邻近性

LINE（Tang et al., 2015）从不同的角度切入同一个问题：显式地定义要保持的”邻近性”，然后直接优化。

一阶邻近性（First-order proximity）：直接相连的节点应该有相似的嵌入。对于边 $(u, v)$，定义联合概率：

$p_1(u, v) = \frac{1}{1 + \exp(-\mathbf{z}_u^\top \mathbf{z}_v)}$

最小化经验分布 $\hat{p}_1$ 与模型分布 $p_1$ 之间的 KL 散度。

二阶邻近性（Second-order proximity）：共享很多邻居的节点应该有相似的嵌入（即使它们自身未直接相连）。为每个节点维护两个向量——作为”中心”的向量 $\mathbf{z}_v$ 和作为”上下文”的向量 $\mathbf{z}'_v$，优化：

$p_2(u \mid v) = \frac{\exp(\mathbf{z}_u'^\top \mathbf{z}_v)}{\sum_k \exp(\mathbf{z}_k'^\top \mathbf{z}_v)}$

LINE 的优势在于可扩展性——使用 edge sampling 和负采样，可以处理百万节点级别的网络。

浅层嵌入的本质与局限

三种方法的共同本质：把图的拓扑信息压缩到低维向量，保持邻近性。 它们都属于”浅层”方法，因为编码器只是一个查找表——每个节点有一行独立的向量，没有参数共享。

这导致了关键的局限：

1. 直推式（Transductive）：只能嵌入训练时见过的节点。如果图中新增了一个节点，必须重新训练
2. 不利用节点特征：只利用图结构（边），忽略了节点可能携带的特征信息（如用户属性、论文文本）
3. 参数量与节点数线性：嵌入矩阵 $Z \in \mathbb{R}^{n \times d}$，$n$ 是节点数，大图上参数量巨大

这些局限催生了下一代方法——图神经网络。

Section B: 图神经网络（GNN）——消息传递范式

消息传递框架

现代 GNN 的核心是消息传递（Message Passing）框架（Gilmer et al., 2017）。它用一个统一的语言描述了几乎所有主流 GNN 架构：

一层消息传递包含三个步骤：

步骤 1 — Aggregate（聚合）：每个节点 $v$ 收集其邻居 $N(v)$ 的表示：

$\mathbf{m}_v^{(l)} = \text{AGG}^{(l)}\big(\big\{\!\big\{ \mathbf{h}_u^{(l-1)} : u \in N(v) \big\}\!\big\}\big)$

逐项拆解：

• $\mathbf{h}_u^{(l-1)}$ 是节点 $u$ 在第 $l-1$ 层的表示向量
• $\big\{\!\big\{ \cdot \big\}\!\big\}$ 表示多重集（multiset）——保留重复，与 Art. 9 WL test 中的颜色细化一致
• AGG 是聚合函数：可以是 SUM、MEAN、MAX，或更复杂的函数
• $\mathbf{m}_v^{(l)}$ 是聚合后的”消息”

步骤 2 — Update（更新）：结合自身表示和聚合消息，生成新表示：

$\mathbf{h}_v^{(l)} = \text{UPD}^{(l)}\big(\mathbf{h}_v^{(l-1)}, \mathbf{m}_v^{(l)}\big)$

UPD 通常是一个神经网络层（线性变换 + 非线性激活）。

步骤 3 — Readout（读出，可选）：如果任务是图级的（如图分类），需要将所有节点表示汇总为一个图表示：

$\mathbf{h}_G = \text{READOUT}\big(\big\{\!\big\{ \mathbf{h}_v^{(L)} : v \in V \big\}\!\big\}\big)$

READOUT 可以是简单的求和/均值/最大值，或更复杂的 hierarchical pooling。

初始化：$\mathbf{h}_v^{(0)} = \mathbf{x}_v$，即节点的初始特征向量。如果节点没有特征，可以用度数、one-hot 编码等替代。

堆叠：将多层消息传递串联。$L$ 层 GNN 意味着每个节点最终聚合了 $L$ 跳邻域的信息——这与 BFS（Art. 1） 的层次展开直觉完全对应。

消息传递 = 矩阵乘法视角：对于整张图，一层聚合操作可以写成矩阵形式 $H^{(l)} = f(A \cdot H^{(l-1)} \cdot W^{(l)})$，其中 $A$ 是邻接矩阵，$W^{(l)}$ 是可学习权重矩阵。邻接矩阵乘以特征矩阵，本质上就是”收集邻居特征的加权和”——这与线性代数中的矩阵-向量乘法含义一致。

GCN：图卷积网络

GCN（Graph Convolutional Network，Kipf & Welling, 2017）是最经典的 GNN 架构。它的更新公式为：

$H^{(l+1)} = \sigma\big(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)}\big)$

逐项拆解：

• $\tilde{A} = A + I_n$ 是加了自环（self-loop）的邻接矩阵——每个节点在聚合时包含自身
• $\tilde{D}$ 是 $\tilde{A}$ 的度矩阵，$\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$
• $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 是对称归一化——防止高度节点的特征在聚合时主导结果
• $H^{(l)} \in \mathbb{R}^{n \times d_l}$ 是第 $l$ 层所有节点的特征矩阵
• $W^{(l)} \in \mathbb{R}^{d_l \times d_{l+1}}$ 是可学习的权重矩阵
• $\sigma$ 是非线性激活函数（通常为 ReLU）

单节点视角（拆开矩阵形式）：

$\mathbf{h}_v^{(l+1)} = \sigma\bigg(W^{(l)} \sum_{u \in N(v) \cup \{v\}} \frac{\mathbf{h}_u^{(l)}}{\sqrt{\tilde{d}_v \cdot \tilde{d}_u}}\bigg)$

其中 $\tilde{d}_v = |\tilde{N}(v)|$ 是加自环后的度。这就是一个归一化的邻居特征均值，然后线性变换再激活。

GCN 的名字由来：这个操作在谱图理论中可以解释为图信号的低通滤波——类似于 CNN 中的卷积平滑了图像的局部区域，GCN 平滑了图上的节点信号。不同之处在于，CNN 的卷积核是固定大小的规则网格，而 GCN 的”卷积核”适应每个节点不同的邻域结构。

GCN 消息传递走查

下面的交互组件展示了一层 GCN 在一个 5 节点图上的完整过程。逐步点击，观察 Aggregate → Update → Activate 三个阶段如何将初始特征变换为新的节点表示。

← 上一步步骤 0 / 3[初始]下一步 →

初始状态：每个节点有一个特征值 h⁰。A=1.0, B=2.0, C=3.0, D=4.0, E=5.0

走查要点：

• Aggregate：每个节点将邻居（含自身）的特征取平均。例如节点 A 有邻居 B、C，聚合 mean(1.0, 2.0, 3.0) = 2.0
• Update：聚合结果乘以权重矩阵 $W$（这里简化为标量 0.5）。2.0 × 0.5 = 1.0
• Activate：应用 ReLU。所有值为正，不变
• 注意特征值如何在节点间”流动”——初始差异很大的特征在聚合后变得更接近（这就是 over-smoothing 的萌芽）

GAT：注意力加权的邻居聚合

GCN 对所有邻居一视同仁（权重仅由度决定）。但直觉上，不同邻居的”信息量”是不同的——有的邻居与当前节点高度相关，有的则噪声更多。

GAT（Graph Attention Network，Veličković et al., 2018）引入注意力机制，让模型自动学习每个邻居的重要性权重。

注意力系数计算：

$e_{ij} = \text{LeakyReLU}\big(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_i \,\|\, \mathbf{W}\mathbf{h}_j]\big)$

$\alpha_{ij} = \text{softmax}_j(e_{ij}) = \frac{\exp(e_{ij})}{\sum_{k \in N(i) \cup \{i\}} \exp(e_{ik})}$

逐项拆解：

• $\mathbf{W} \in \mathbb{R}^{d' \times d}$ 是共享的线性变换矩阵
• $[\cdot \,\|\, \cdot]$ 表示向量拼接（concatenation）
• $\mathbf{a} \in \mathbb{R}^{2d'}$ 是注意力向量（可学习参数）
• $e_{ij}$ 是节点 $i$ 对邻居 $j$ 的原始注意力分数
• softmax 归一化保证对一个节点所有邻居的注意力权重之和为 1

聚合：

$\mathbf{h}_i' = \sigma\bigg(\sum_{j \in N(i) \cup \{i\}} \alpha_{ij} \mathbf{W}\mathbf{h}_j\bigg)$

GAT 还使用多头注意力（multi-head attention）增加稳定性：

$\mathbf{h}_i' = \|_{k=1}^{K} \sigma\bigg(\sum_{j \in N(i)} \alpha_{ij}^k \mathbf{W}^k\mathbf{h}_j\bigg)$

其中 $\|$ 表示 $K$ 个注意力头的输出拼接。

GraphSAGE：采样 + 聚合，支持归纳学习

GraphSAGE（Hamilton et al., 2017）的核心创新是解决了 GCN 和 GAT 的两个问题：

1. 可扩展性：GCN/GAT 需要全图的邻接矩阵，对大图（百万节点）内存不可承受。GraphSAGE 对每个节点只采样固定数量的邻居
2. 归纳学习（Inductive learning）：GCN 是直推式的——训练时需要整张图，不能处理新节点。GraphSAGE 学习的是一个聚合函数（而非节点的嵌入查找表），因此可以泛化到训练时未见过的节点或全新的图

算法：

$\mathbf{h}_{N(v)}^{(l)} = \text{AGG}^{(l)}\big(\big\{\!\big\{ \mathbf{h}_u^{(l-1)} : u \in \text{SAMPLE}(N(v), S) \big\}\!\big\}\big)$

$\mathbf{h}_v^{(l)} = \sigma\big(\mathbf{W}^{(l)} \cdot [\mathbf{h}_v^{(l-1)} \,\|\, \mathbf{h}_{N(v)}^{(l)}]\big)$

逐项拆解：

• $\text{SAMPLE}(N(v), S)$ 从 $v$ 的邻居中随机采样 $S$ 个（典型值 $S = 25$ 第一层，$S = 10$ 第二层）
• AGG 可以是 MEAN、LSTM（将邻居随机排列后输入 LSTM）、或 MAX-pooling
• 自身表示 $\mathbf{h}_v$ 与邻居聚合 $\mathbf{h}_{N(v)}$ 是拼接后线性变换的，而非像 GCN 那样混合在一起

三者对比总结

维度	GCN	GAT	GraphSAGE
聚合方式	对称归一化均值	注意力加权和	采样 + 可选聚合器
邻居权重	由度决定（固定）	由注意力学习（自适应）	等权 or 可学习
自环处理	$\tilde{A} = A + I$	注意力包含自身	拼接自身表示
学习模式	直推（Transductive）	直推	归纳（Inductive）
可扩展性	需要全图	需要全图	采样 → 可扩展
时间复杂度/层	$O(m \cdot d + n \cdot d^2)$	$O(m \cdot d + n \cdot d^2)$	$O(n \cdot S^L \cdot d^2)$

其中 $m$ 是边数，$n$ 是节点数，$d$ 是隐藏维度，$S$ 是每层采样数，$L$ 是层数。

Section C: 三种任务层次

有了节点表示 $\mathbf{h}_v^{(L)}$，可以应用到三种不同粒度的任务：

节点分类（Node Classification）

目标：预测每个节点的标签（如论文的主题、用户的兴趣类别）。

做法：在最后一层节点表示上接一个分类头：

$\hat{y}_v = \text{softmax}(\mathbf{W}_{cls} \mathbf{h}_v^{(L)})$

经典场景：Cora/CiteSeer/PubMed 引文网络——论文是节点，引用是边，任务是预测论文的研究领域。GCN 原论文在 Cora 上达到 81.5% 准确率。

链接预测（Link Prediction）

目标：预测两个节点之间是否应该有边（或预测边的类型/权重）。

做法：对节点对 $(u, v)$ 的表示做某种组合，然后预测：

$p(e_{uv}) = \sigma(\mathbf{h}_u^{(L)\top} \mathbf{h}_v^{(L)})$

或使用更复杂的解码器（如 MLP 对拼接向量做预测）。

经典场景：社交网络的好友推荐（回顾 Art. 9 中的链接预测）、知识图谱补全（预测缺失的三元组关系）。

图分类（Graph Classification）

目标：预测整张图的标签（如分子是否有毒、蛋白质的功能类别）。

做法：先用 Readout 将所有节点表示汇总为图表示，再分类：

$\hat{y}_G = \text{softmax}\big(\mathbf{W}_{cls} \cdot \text{READOUT}(\{\!\{\mathbf{h}_v^{(L)} : v \in V\}\!\})\big)$

经典场景：分子性质预测（如 OGBG-MolHIV 数据集——预测分子是否抑制 HIV）。

Section D: GNN 表达力上界——与 WL Test 的等价关系

在 Art. 9 中，我们学习了 1-WL test（颜色细化）作为图同构的必要条件检测。现在揭示一个深刻联系：消息传递 GNN 的表达力等价于 1-WL test。

定理（Xu et al., 2019；Morris et al., 2019）：

1. 上界：任何消息传递 GNN 的区分能力不超过 1-WL test。也就是说，如果 1-WL 无法区分两张图（它们的 WL 颜色直方图在所有迭代中都一致），那么没有任何消息传递 GNN 能在它们的图表示上给出不同的输出。

2. 可达：存在一种消息传递 GNN——GIN（Graph Isomorphism Network）——其区分能力等于 1-WL test。

GIN 的关键设计：

$\mathbf{h}_v^{(l)} = \text{MLP}^{(l)}\bigg((1 + \epsilon^{(l)}) \cdot \mathbf{h}_v^{(l-1)} + \sum_{u \in N(v)} \mathbf{h}_u^{(l-1)}\bigg)$

与 GCN/GAT 的区别：

• 使用 SUM 聚合（而非 MEAN 或 MAX）——SUM 能区分不同的多重集（例如 $\{1, 1, 1\}$ vs $\{1, 1, 1, 1\}$，MEAN 和 MAX 无法区分）
• $(1 + \epsilon)$ 因子保证自身和邻居的信息不被混淆
• MLP（而非单层线性变换）提供足够的非线性表达力

直觉：1-WL test 在每轮将（自身颜色, 邻居颜色多重集）映射为新颜色，使用的是一个 injective function（注入函数）。GIN 的 SUM + MLP 恰好能模拟这个注入映射。而 GCN 的 MEAN 或 GraphSAGE 的 MAX 不是注入的——它们丢失了多重集中的重复计数信息——所以表达力弱于 GIN/WL。

实际影响：

• 如果你的任务需要区分两张具有相同 WL 颜色序列的图（如某些正则图），消息传递 GNN 无能为力
• 要突破这个上界，需要高阶 GNN（如 k-GNN，对应 k-WL test），但复杂度从 $O(n)$ 增长到 $O(n^k)$

Section E: Over-Smoothing 问题

直觉上，GNN 层数越多，每个节点聚合的邻域范围越大，应该学到越丰富的信息。但实际实验中发现：GNN 层数超过 4-6 层后，性能反而下降。 这就是 over-smoothing（过度平滑）问题。

原因：每层消息传递将邻居信息混合到当前节点。$L$ 层之后，每个节点的表示是其 $L$ 跳邻域内所有节点特征的加权平均。当 $L$ 足够大，所有节点的感受野（receptive field）覆盖整张图，导致所有节点的表示趋于相同——节点的个性被抹平了。

从数学角度看，这与拉普拉斯平滑（Laplacian smoothing）的极限一致：$\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 的反复应用就是一个低通滤波器，多次应用后信号趋于常数（对应于图拉普拉斯的零特征值分量）。

缓解方法：

1. 残差连接（Residual connections）：$\mathbf{h}_v^{(l)} = \mathbf{h}_v^{(l)} + \mathbf{h}_v^{(l-1)}$，类似 ResNet，防止信息在层间丢失
2. JK-Net（Jumping Knowledge）：在最终表示中融合所有中间层的表示，而非只用最后一层
3. DropEdge：在每层训练时随机删除一些边，减缓信息的过度传播
4. 控制层数：实践中大多数 GNN 只用 2-3 层。这对应于 2-3 跳邻域——在多数图中已经覆盖了足够的局部结构信息

应用场景

社交网络：用户行为预测

Pinterest 使用 PinSage（GraphSAGE 的工业化版本）为其 30 亿+ 的 pin 和 board 生成嵌入，用于推荐系统。当用户对一个 pin 感兴趣时，系统找到向量空间中最近的 pins 推荐。PinSage 每次只采样少量邻居，使得训练和推理都能在工业规模上运行。

分子性质预测

药物发现中，分子被建模为图（原子 = 节点，化学键 = 边）。GNN 可以预测分子的物理化学性质（如溶解度、毒性、结合亲和力），大幅减少实验筛选的成本。在 OGB（Open Graph Benchmark）的 MolHIV 任务上，GIN 等方法的 AUC 超过 0.8。

复杂度对比表

方法	时间复杂度	空间复杂度	学习模式	核心优势
DeepWalk	$O(\gamma \cdot n \cdot t \cdot w \cdot d)$	$O(n \cdot d)$	直推	简单、快速
Node2Vec	$O(\gamma \cdot n \cdot t \cdot w \cdot d)$	$O(n \cdot d)$	直推	可调 BFS/DFS
LINE	$O(m \cdot d \cdot K)$	$O(n \cdot d)$	直推	大规模可扩展
GCN（$L$ 层）	$O(L \cdot (m \cdot d + n \cdot d^2))$	$O(n \cdot d + m)$	直推	端到端训练
GAT（$L$ 层）	$O(L \cdot (m \cdot d + n \cdot d^2))$	$O(n \cdot d + m)$	直推	自适应邻居权重
GraphSAGE（$L$ 层）	$O(n \cdot S^L \cdot d^2)$	$O(n \cdot d)$	归纳	可扩展 + 新节点
GIN（$L$ 层）	$O(L \cdot (m \cdot d + n \cdot d^2))$	$O(n \cdot d + m)$	直推	最强表达力

其中 $n$ = 节点数，$m$ = 边数，$d$ = 嵌入/隐藏维度，$\gamma$ = 游走次数，$t$ = 游走长度，$w$ = 上下文窗口，$S$ = 每层采样数，$L$ = GNN 层数，$K$ = 训练轮数。

总结

本文建立了”图 → 向量”的完整工具体系：

• 浅层嵌入（DeepWalk、Node2Vec、LINE）：通过随机游走或边采样产生训练信号，用查找表作为编码器，保持图的拓扑邻近性。简单高效但无法归纳
• 图神经网络（GCN、GAT、GraphSAGE）：通过消息传递框架（Aggregate → Update → Readout）逐层聚合邻域信息，参数共享使得能处理新节点/新图
• 三种任务层次：节点分类（用 $\mathbf{h}_v$）、链接预测（用 $(\mathbf{h}_u, \mathbf{h}_v)$）、图分类（用 READOUT）
• 表达力上界：消息传递 GNN ≤ 1-WL test；GIN 达到此上界
• Over-smoothing：层数过多导致节点表示趋同；实践中用 2-3 层

图嵌入和 GNN 是将传统图算法（Art. 1-17）与现代机器学习连接的桥梁。接下来的 Art. 19：案例集 将通过实际案例展示如何综合运用这些工具解决真实问题。

实现指引

算法	库	函数/方法
DeepWalk	gensim + NetworkX	nx.random_walk() → Word2Vec(sentences)
Node2Vec	node2vec (PyPI)	Node2Vec(G, p=1, q=2).fit()
LINE	OpenNE / PyTorch	LINE(graph, embed_size=128).train()
GCN	PyG	torch_geometric.nn.GCNConv(in, out)
GAT	PyG	torch_geometric.nn.GATConv(in, out, heads=8)
GraphSAGE	PyG	torch_geometric.nn.SAGEConv(in, out)
GIN	PyG	torch_geometric.nn.GINConv(nn.Sequential(...))
GCN	DGL	dgl.nn.GraphConv(in, out)
GAT	DGL	dgl.nn.GATConv(in, out, num_heads=8)
GraphSAGE	DGL	dgl.nn.SAGEConv(in, out, 'mean')
Node2Vec	PyG	torch_geometric.nn.Node2Vec(edge_index, ...)
图分类 Pipeline	PyG	torch_geometric.loader.DataLoader + global_mean_pool