引论：图结构数据与图神经网络的诞生

第 1 章 引论：图结构数据与图神经网络的诞生

图结构数据是真实世界最普遍、也最具挑战性的数据形态之一。从社交网络中数十亿用户的"好友-关注"关系到生物体内蛋白质分子的三维折叠结构，从城市交通路网的几何连接到金融系统中企业之间的股权穿透链条——当我们审视这些数据时，会发现它们共享一个本质特征：信息不仅存在于节点自身的属性中，更存在于节点之间的拓扑连接里。然而，过去十年主导深度学习的两大架构——CNN 与 RNN——都是为具有规则几何或顺序结构的数据设计的。CNN 利用欧氏空间的平移等变性在图像上滑动卷积核，RNN 沿着时间轴递归传递隐藏状态；这两者在面对图时都会立即失效，因为图既没有"左上角"和"右下角"这样的全局坐标系，也没有"上一时刻"和"下一时刻"这样的天然顺序。正是这一根本错配催生了图神经网络（GNN, Graph Neural Network）这一独立的深度学习分支，并在过去十五年里从一种小众的循环网络变体，发展成与 Transformer 并驾齐驱的通用结构学习范式。本章回答的核心问题是：图结构数据为什么需要专门设计的神经网络？GNN 的发展脉络与技术驱动力是什么？

1.1 规则数据与图结构数据的本质差异

要理解为什么图需要专门的神经网络，必须先在数据结构层面把规则数据（grid-like data）与图结构数据（graph-structured data）的差异讲清楚。我们用三类典型代表来对比：图像（2D 网格）、文本（1D 序列）、图（任意拓扑），它们可被视为"几何规则性"这一连续谱上的三个采样点。

图像是欧氏空间中的规则网格。一幅 RGB 图像 $X \in \mathbb{R}^{H \times W \times 3}$ 具有两个本质属性：(1) 空间局部性——每个像素的邻域由固定半径的方形或矩形定义，对中心像素的左上、右上、左下、右下四个角各有完全确定的几何含义；(2) 平移等变性（translation equivariance）——将图像平移后再卷积，等价于先卷积再平移，即 $T(f * g) = (T f) * g$。这两个属性让卷积神经网络（CNN）可以使用一个参数共享的卷积核在整个图像上滑动，并以局部感受野（receptive field）的层次堆叠实现从局部到全局的建模。

文本是离散符号序列。一段长度为 $L$ 的文本可表示为 token 序列 $(w_1, w_2, \ldots, w_L)$，每个 $w_i$ 来自一个固定词表 $\mathcal{V}$。序列的核心属性是因果或顺序依赖：位置 $i$ 的语义强烈依赖于其前序上下文，且这种依赖具备方向性。RNN 通过隐藏状态 $h_t = f(h_{t-1}, w_t)$ 的递归传递天然地建模了这种顺序依赖；Transformer 则通过位置编码（positional encoding）显式注入顺序信息，再以自注意力机制（self-attention）实现全局 token 间的成对交互。

图是任意拓扑的非欧数据结构。一个图 $G = (V, E)$ 由节点集 $V$（通常 $|V| = n$）和边集 $E \subseteq V \times V$ 构成，节点可携带属性矩阵 $X \in \mathbb{R}^{n \times d}$，边可携带属性矩阵 $E \in \mathbb{R}^{|E| \times c}$。与前两类数据相比，图具有三个根本不同的结构属性：

• **排列不变性（permutation invariance）**：给定任意一个双射 $\pi: V \to V$，将所有节点的编号按 $\pi$ 重排，得到的新图与原图在拓扑上完全等价。换句话说，图没有"第一个节点"和"最后一个节点"的概念——节点编号只是一种人为的存储约定。这一性质意味着任何作用于图的函数 $f$ 都应当满足 $f(\pi(X), \pi(A)) = f(X, A)$，其中 $A$ 是邻接矩阵。形式上，$f$ 必须与节点排列的对称群 $\mathfrak{S}_n$ 的作用对易。

• **邻居数量可变（variable neighborhood size）**：在图像中，每个像素恰好有 8 个邻居；在文本中，每个 token 至多有 2 个上下文方向。但在图中，节点的度（degree）可以从 0 跨越到 $n-1$——分子图中的氢原子可能只有 1 个邻居，而社交网络中的"网红"可能有上千万粉丝。这使得"卷积核大小"这一 CNN 的核心超参数在图上完全失去意义：固定大小的卷积核无法应对度分布的剧烈差异。

• **缺乏全局顺序（no canonical ordering）**：图像有自然的行列索引，文本有自然的时间索引，但图没有。在不同的存储实现中，同一个图可以以深度优先顺序、宽度优先顺序或任意其他顺序序列化，得到的邻接矩阵可以截然不同。任何依赖"第 $i$ 个节点"的算法都必然受到这种任意性的影响。

我们用一个具体例子来强化这一对比。考虑预测一个分子是否具有水溶性——这是药物发现（drug discovery）中的基础任务。输入是一个分子图 $G$，原子为节点（带元素类型、电荷等属性），化学键为边。图像方法显然不适用：分子没有规则形状。文本方法（如 SMILES 字符串上的 RNN）可以勉强工作，但会丢失二维结构信息——例如环状结构在 SMILES 中需要通过环闭合数字来编码，对 RNN 而言这相当于在序列两端建立长距离依赖。直接以图作为输入、并在节点与边的拓扑上进行学习，是更自然也更强力的方案。Kipf & Welling（2017）的实验表明，在 ZINC 分子数据集上，一个简单的 GCN 即能达到与传统分子指纹（Morgan fingerprint）相当甚至更好的预测准确率。

> 小结判断：图像、文本、图三者在结构上的差异可量化为"几何规则性"这一连续谱——图像处于最规则一端，文本次之，图处于最不规则一端。CNN 与 RNN 之所以成功，是因为它们的归纳偏置（inductive bias）与各自数据结构的规则性高度匹配；GNN 的诞生，本质上是为图这种不规则数据设计相匹配的归纳偏置——具体而言，是 permutation invariance 与局部连接的组合。

1.2 为什么 CNN 和 RNN 不能直接迁移到图上

让我们更严格地考察 CNN 与 RNN 在图上的失败模式。这不是简单的"性能不够好"的问题，而是结构上不可能的问题。

CNN 的迁移障碍。CNN 的核心运算是离散卷积： $$(f * g)[i, j] = \sum_{p, q} f[p, q] \cdot g[i-p, j-q]$$ 这个运算依赖三个前提：(1) 输入域是离散网格 $\mathbb{Z}^2$；(2) 存在平移群 $\mathbb{Z}^2$ 的群作用；(3) 卷积核在这个群作用下参数共享。图上不存在这三条中的任何一条。最朴素的尝试是"将邻接矩阵视作图像"——但邻接矩阵的排列任意性意味着同一个图会产生无穷多种"图像"，而 CNN 对这些图像的预测结果必须保持一致，这在实践中几乎不可能实现。另一个尝试是"将图 embedding 到欧氏空间再卷积"——但任何 embedding 都不可避免地引入失真，特别是高维图嵌入到低维欧氏空间时，距离关系会被破坏。

RNN 的迁移障碍。RNN 的递归结构 $h_t = \sigma(W_h h_{t-1} + W_x x_t)$ 依赖于一维时间序列。但图上节点的"遍历顺序"是任意的：以不同的顺序遍历同一个图，RNN 会得到完全不同的隐藏状态序列，进而得到不同的图级表示。更糟的是，RNN 的链式结构无法自然地表达节点的分支结构（如一棵树或一个有环图）。一些早期工作（如 Graph RNN, You et al. 2018）尝试将图生成建模为节点与边的序列预测，但本质上是把图压扁成序列，丢失了原始拓扑；且这种序列化会引入额外的"顺序偏置"——模型会倾向于学习序列中相邻节点的边，而忽略真实图中的非局部边。

手工特征工程的局限。在 GNN 出现之前，处理图数据的主流方法是"特征工程 + 传统机器学习"。例如在节点分类任务中，研究者会手工提取节点的度、聚类系数（clustering coefficient）、Katz 中心性、PageRank 等拓扑特征，再喂给 SVM 或随机森林。这种方法有两个根本局限：(1) 手工特征的设计依赖于领域知识，难以迁移到新任务；(2) 拓扑特征与节点属性之间无法进行深度的非线性交互，端到端学习能力受限。一个典型的例子是：在蛋白质功能预测中，单纯使用节点度根本无法区分具有相似度分布但功能完全不同的蛋白质。

图核方法（graph kernel）。另一类传统方法是图核，例如 Weisfeiler-Lehman（WL）核（Shervashidze et al., 2011）。WL 核通过迭代地聚合邻居标签来构造节点的特征向量，再用这些向量之间的内积定义图之间的相似度。这种方法在数学上等价于 1 维 WL 测试，是 GNN 表达能力分析的重要参照（详见第 2 章）。但图核方法的特征是预定义的，无法端到端学习，且在大型图上计算昂贵——计算 $n$ 个图之间的核矩阵需要 $O(n^2)$ 次图对比较，每次比较都需要多次 WL 迭代。在节点数超过 10 万的工业级图上，这种方法几乎不可行。

形式化证明：permutation invariance 是必要条件。设 $f: \mathbb{R}^{n \times d} \times \{0,1\}^{n \times n} \to \mathbb{R}^k$ 是我们要学习的函数，目标是处理图数据。定义置换矩阵 $P_\pi$（其元素 $P_\pi[i, \pi(i)] = 1$，其他为 0）。如果 $f$ 不是 permutation invariant 的，那么存在某个 $\pi$ 使得 $f(P_\pi X, P_\pi A P_\pi^T) \neq f(X, A)$。但根据定义，$P_\pi X$ 和 $P_\pi A P_\pi^T$ 与 $X, A$ 代表的是同一个图（只是节点编号不同），因此任何"合理"的函数 $f$ 必须给出相同的输出。这一论证说明：任何在图上工作的模型，permutation invariance 都是数学上的必要条件，而非可选优化。

> 判断依据：GNN 的必要性不在于"图任务很难"，而在于图数据具有其他数据类型所没有的结构对称性（permutation symmetry），这一对称性必须被显式地编码到网络架构中。任何不具有 permutation invariance 的模型，理论上都不可能在图任务上达到最优。这一观察为后续 GNN 架构设计提供了第一性原理。

1.3 GNN 的十五年演进：从循环 GNN 到图基础模型

GNN 的发展可划分为五个主要阶段，每个阶段都有标志性的工作和理论突破。理解这条演进线，对于把握后续章节的内容至关重要。

1.3.1 阶段一：循环 GNN（Recurrent GNN, 2005-2014）

标志性工作：Scarselli 等人 2008 年在 IEEE Transactions on Neural Networks 上发表的 *"The Graph Neural Network Model"*，是 GNN 的奠基性工作。Gori et al. (2005) 在 *International Journal of Neural Systems* 上独立提出了类似架构，可视为 GNN 思想的并行起点。

循环 GNN 的核心思想是把每个节点 $v$ 的状态 $h_v$ 视为一个不动点（fixed point）求解问题。给定节点属性 $x_v$、边属性 $e_{uv}$ 和邻居状态 $\{h_u : u \in \mathcal{N}(v)\}$，节点状态通过下式迭代更新直至收敛： $$h_v^{(t+1)} = f_w\left(x_v, x_{\mathcal{N}(v)}, \sum_{u \in \mathcal{N}(v)} g_w(h_v^{(t)}, h_u^{(t)}, e_{uv})\right)$$ 其中 $f_w$ 和 $g_w$ 是参数化的神经网络，$w$ 在所有节点之间共享。节点状态收敛后，再通过一个 readout 函数得到图级表示。这种"不动点传播"的思路具有理论上的优雅性——如果 $f_w$ 是收缩映射（contraction mapping），由 Banach 不动点定理保证唯一解。但在实践中面临三个挑战：(1) 不动点迭代收敛慢，每个图需要数十次甚至上百次迭代；(2) 收敛后无法再做深度堆叠，因为状态已饱和；(3) 表达能力受限于 WL 测试（见第 2 章的形式化分析）。

同期工作：Li et al. (2016) 的 Gated Graph Neural Network (GGNN) 用 GRU 替换不动点更新，缓解了收敛问题，将迭代次数从"直到收敛"改为固定 $T$ 步，并通过时间反向传播（BPTT）训练。这一阶段的 GNN 主要在小规模图（节点数 $< 1000$）上验证，未能扩展到工业级数据。

1.3.2 阶段二：谱图卷积（Spectral GCN, 2013-2017）

标志性工作：Bruna 等人 2013 年在 ICLR 上发表的 *"Spectral Networks and Locally Connected Networks on Graphs"*，首次将图信号处理（Graph Signal Processing, GSP）的数学工具引入深度学习。

谱方法的数学基础是图拉普拉斯矩阵的特征分解。给定图 $G$ 的归一化拉普拉斯矩阵 $L = I - D^{-1/2} A D^{-1/2}$（其中 $D$ 是度矩阵），其特征分解 $L = U \Lambda U^T$ 给出一组正交基 $U$。类比于经典傅里叶变换，图上的"傅里叶变换"定义为 $\hat{x} = U^T x$，逆变换为 $x = U \hat{x}$。于是图卷积可以定义为： $$x *_G g = U((U^T g) \odot (U^T x))$$ 其中 $\odot$ 是逐元素乘积，$g$ 是定义在谱域上的卷积核。

Bruna 等人让谱域卷积核的参数是可学习的（即对每个特征值 $\Lambda_{ii}$ 学习一个权重），但这一设计有两个明显问题：(1) 需要显式做 $O(n^3)$ 的特征分解，对大图不可行；(2) 卷积核在空间域不是局部化的，违背了"图卷积应当是局部聚合"的直觉——一个在谱域全局定义的核，在空间域的影响范围会扩散到整个图。

关键简化：Defferrard et al. (2016) 提出了 ChebNet，使用切比雪夫多项式展开来近似谱卷积核，避免了显式特征分解： $$g *_G x \approx \sum_{k=0}^{K-1} \theta_k T_k(\tilde{L}) x$$ 其中 $T_k$ 是切比雪夫多项式，$\tilde{L} = 2L / \lambda_{\max} - I$ 是缩放后的拉普拉斯矩阵。这一设计的核心洞察是：$K$ 阶切比雪夫多项式的卷积核恰好对应 $K$ 跳邻居的局部聚合，从而把谱方法和空间方法统一起来。

最终简化：Kipf 和 Welling 2017 年在 ICLR 上发表了 *"Semi-Supervised Classification with Graph Convolutional Networks"*（GCN），将 ChebNet 进一步简化为 $K=1$ 的情形，并加入归一化技巧： $$H^{(l+1)} = \sigma\left(\tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} W^{(l)}\right)$$ 其中 $\tilde{A} = A + I$ 是加自环的邻接矩阵，$\tilde{D}$ 是对应的度矩阵，$W^{(l)}$ 是可学习参数矩阵，$\sigma$ 是激活函数。GCN 之所以成为"分水岭"工作，是因为它在简洁性和性能之间取得了极好的平衡——整个前向传播可以写成稀疏矩阵乘法，几十行代码即可实现，并在 Cora、Citeseer、Pubmed 等多个基准上显著超越传统方法。GCN 论文在 Google Scholar 上的引用数已超过 40000，是深度学习领域被引最多的论文之一。

1.3.3 阶段三：空间图卷积与注意力（Spatial GCN & Attention, 2017-2020）

GCN 之后，研究者意识到可以从空间视角直接设计卷积，跳过谱域的数学包袱。这一阶段涌现了 GraphSAGE（Hamilton et al., NeurIPS 2017）、GAT（Veličković et al., ICLR 2018）、GIN（Xu et al., ICLR 2019）等代表性架构。

• **GraphSAGE** 的贡献是提出"邻居采样 + 聚合函数"的范式，支持归纳学习（inductive learning），即在训练时未见过的节点上也能进行推理。具体做法是先对每个节点的邻居进行固定数量的采样，再以 mean、LSTM 或 pooling 等聚合函数聚合邻居信息。这一设计让 GNN 首次具备了处理动态图的能力——新增节点时无需重新训练整个模型。

• **GAT** 的贡献是将注意力机制引入图卷积，让邻居权重可学习。GAT 的注意力系数计算为：

$$\alpha_{ij} = \frac{\exp\left(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} h_i \| \mathbf{W} h_j]\right)\right)}{\sum_{k \in \mathcal{N}(i)} \exp\left(\text{LeakyReLU}\left(\mathbf{a}^T [\mathbf{W} h_i \| \mathbf{W} h_k]\right)\right)}$$ 再以 $\alpha_{ij}$ 为权重对邻居特征做加权求和。GAT 还引入了多头注意力（multi-head attention），类似 Transformer 的设计。这一架构让 GNN 具备了"软邻居选择"能力——模型可以根据内容动态决定关注哪些邻居。

• **GIN** 的贡献是从理论上证明，通过精心设计的聚合函数（sum + MLP），GNN 可以达到与 1-WL 测试相当的表达能力。Xu et al. 的工作给出了一个具有里程碑意义的判据：聚合函数的表达力序列是 **sum > mean > ma