绪论：图结构数据与学习范式演进 / Introduction: Graph-Structured Data and the Evolution of Learning Paradigms

图结构数据（Graph-Structured Data）作为离散关系系统的数学表达，广泛存在于自然与社会科学领域，其本质是对实体（节点）及其关系（边）的拓扑描述。与欧几里得空间中的规则网格数据（如图像、序列）不同，图数据具有排列不变性（Permutation Invariance）与不规则拓扑（Irregular Topology）两大核心特征，这导致了传统深度学习模型（如卷积神经网络CNN、循环神经网络RNN）在直接应用时面临根本性挑战。图神经网络（Graph Neural Networks, GNNs）正是在这一背景下兴起，成为处理复杂关系数据的范式性突破。本章旨在确立全书理论框架，系统追溯GNN从图核方法、谱图理论到深度学习时代的演进脉络，批判性剖析早期图表示学习方法的局限性，并论证深度学习如何通过端到端（End-to-End）的消息传递（Message Passing）机制实现根本性超越。最终，我们将明确GNN的数学本质——一种在图上定义的、具有置换不变性的神经网络——并预览全书15章的逻辑架构，为后续深入探讨奠定基础。

1.1 研究范畴界定：何为图神经网络？

图神经网络是一个广义术语，泛指所有以图结构数据为输入、旨在学习节点、边或图级表示（Representation）的深度学习模型。其研究范畴可明确界定如下：

1. 输入与输出：输入为图 $G = (\mathcal{V}, \mathcal{E}, \mathbf{X})$，其中 $\mathcal{V}$ 是节点集（$|\mathcal{V}| = n$），$\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ 是边集，$\mathbf{X} \in \mathbb{R}^{n \times d}$ 是节点特征矩阵（$d$ 为特征维度）。输出可以是：

• **节点级表示** $\mathbf{h}_v \in \mathbb{R}^{d'}$，用于节点分类、链接预测等。
• **边级表示** $\mathbf{h}_{uv}$，用于边分类或关系预测。
• **图级表示** $\mathbf{h}_G \in \mathbb{R}^{d''}$，用于图分类、回归等。

2. 核心原则：任何GNN模型必须满足置换不变性（Permutation Invariance）。即，对节点索引的任意置换 $\pi: \mathcal{V} \rightarrow \mathcal{V}$，模型的输出在节点级层面应相应置换，而在图级层面保持不变。形式化地，对于节点级输出： $$ f_{\theta}(G) = \mathbf{H} \quad \Rightarrow \quad f_{\theta}(G^{\pi}) = \mathbf{P}_{\pi} \mathbf{H} $$ 其中 $G^{\pi}$ 表示节点按 $\pi$ 置换后的图，$\mathbf{P}_{\pi}$ 是对应的置换矩阵。对于图级输出 $s = f_{\theta}(G)$，有 $f_{\theta}(G^{\pi}) = s$。这一原则是GNN区别于传统神经网络的根本，确保了模型输出仅依赖于图的结构与特征，而非人为的节点排序。

3. 与相关领域的边界：

• **图嵌入（Graph Embedding）**：通常指无监督的浅层方法（如DeepWalk、Node2Vec），将节点映射到低维向量空间，但缺乏深度神经网络的非线性变换能力和端到端优化框架。现代GNN可视为深度图嵌入的演进。
• **图核方法（Graph Kernels）**：基于核技巧的统计方法，通过计算图间相似度（如随机游走核、最短路径核）支持核方法分类器。它们本质上是特征工程，无法学习层次化表示。
• **几何深度学习（Geometric Deep Learning）**：GNN是几何深度学习在离散图结构上的核心实例，后者还包括处理连续空间数据（如点云、网格）的模型。本书聚焦于离散图结构。

因此，本书所讨论的GNN特指基于深度神经网络、通过可微分消息传递机制实现置换不变性表示学习的模型家族。

1.2 演进脉络：从图核到深度消息传递

GNN的发展并非一蹴而就，而是经历了从手工特征到自动学习、从线性到非线性、从浅层到深层的三次范式跃迁。

1.2.1 图核方法与早期图表示学习（1990s-2010s）

在深度学习兴起前，图表示学习主要依赖图核方法。其核心思想是设计一个映射 $\phi: \mathcal{G} \rightarrow \mathbb{R}^D$，将图 $G$ 映射为特征向量，使得结构相似的图在特征空间中距离相近，然后使用核方法（如SVM）进行分类。

• **随机游走核（Random Walk Kernel）**：通过比较两图上随机游走序列的相似性定义核函数。例如，给定图 $G_1, G_2$，核值 $k(G_1, G_2) = \sum_{i,j} \mathbf{w}_i^{\top} \mathbf{w}_j$，其中 $\mathbf{w}_i$ 是 $G_1$ 上长度为 $l$ 的游走计数向量。这类方法计算昂贵（$O(n^2)$）且对噪声敏感。
• **最短路径核（Shortest-Path Kernel）**：基于所有节点对间最短路径长度的分布构建直方图作为特征。它忽略了节点属性，且对大规模图不实用。
• **图let核（Graphlet Kernel）**：枚举小规模图（图let）作为基元，统计其出现频率。能捕捉局部结构，但枚举爆炸且难以扩展。

这些方法的共同局限在于：1）特征工程依赖强，需要领域知识设计图let或游走策略；2）无法端到端优化，特征提取与下游任务分离；3）表示能力有限，通常是浅层、线性组合，难以捕获复杂高阶结构；4）计算效率低，尤其对大规模图。

同期，谱图理论（Spectral Graph Theory） 为图分析提供了强大数学工具。核心是图拉普拉斯矩阵（Graph Laplacian） $\mathbf{L} = \mathbf{D} - \mathbf{A}$，其中 $\mathbf{A}$ 是邻接矩阵，$\mathbf{D}$ 是度矩阵。其谱分解 $\mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^{\top}$ 定义了图的傅里叶基。谱聚类（Spectral Clustering） 利用 $\mathbf{L}$ 的最优非平凡特征向量进行降维和聚类，展现了图结构信息提取的潜力。然而，谱方法本质是线性、静态、全局的：它处理的是整个图的矩阵特征分解，计算复杂度 $O(n^3)$，无法自然扩展到大规模图，且难以与节点特征深度融合。

1.2.2 深度学习时代的黎明：谱域图卷积（2013-2016）

2013年，Bruna等人首次将卷积操作引入图结构，提出谱图卷积（Spectral Convolution）。在信号处理领域，图上的卷积定义为：$\mathbf{x} * \mathbf{g} = \mathbf{U} (\mathbf{U}^{\top} \mathbf{g} \odot \mathbf{U}^{\top} \mathbf{x})$，其中 $\mathbf{g}$ 是滤波器，$\mathbf{U}$ 是傅里叶基矩阵。这一定义在数学上优美，但存在致命缺陷：1）计算昂贵，需对 $\mathbf{U}$ 进行特征分解；2）缺乏局部性，滤波器在频域定义，对应空域是全局的；3）难以泛化，滤波器依赖于完整的图拉普拉斯谱，训练好的模型无法直接应用于结构稍有不同的图。

2016年，Kipf与Welling在Bruna工作基础上，提出图卷积网络（Graph Convolutional Network, GCN），实现了关键简化。他们假设滤波器 $\mathbf{g}_{\theta}$ 是 $\mathbf{\Lambda}$ 的多项式：$\mathbf{g}_{\theta}(\mathbf{\Lambda}) = \sum_{k=0}^{K-1} \theta_k \mathbf{\Lambda}^k$。利用切比雪夫多项式近似，并进一步限制 $K=1$，得到简洁的卷积形式： $$ \mathbf{H}^{(l+1)} = \sigma\left( \mathbf{\tilde{D}}^{-1/2} \mathbf{\tilde{A}} \mathbf{\tilde{D}}^{-1/2} \mathbf{H}^{(l)} \mathbf{W}^{(l)} \right) $$ 其中 $\mathbf{\tilde{A}} = \mathbf{A} + \mathbf{I}$ 是添加自环的邻接矩阵，$\mathbf{\tilde{D}}$ 是其度矩阵，$\mathbf{W}^{(l)}$ 是可学习权重，$\sigma$ 是激活函数。这一公式将谱域卷积近似为空域的局部聚合：节点 $v$ 的新表示是其自身与一阶邻居特征的加权和。GCN的成功在于：1）计算高效，避免了特征分解；2）具有局部性，仅需一阶邻居；3）可泛化，滤波器参数 $\mathbf{W}$ 独立于图结构。它首次实现了端到端、可微分的图表示学习，成为GNN复兴的里程碑。

1.2.3 消息传递框架的统一与深化（2017-至今）

GCN之后，研究焦点从“如何定义图卷积”转向“如何设计更强大的消息传递机制”。2017年，图注意力网络（Graph Attention Network, GAT） 引入注意力机制，为不同邻居分配不同权重，解决了GCN中固定归一化（$\mathbf{\tilde{D}}^{-1/2} \mathbf{\tilde{A}} \mathbf{\tilde{D}}^{-1/2}$）的局限性。其核心是计算注意力系数： $$ e_{uv} = \text{LeakyReLU}(\mathbf{a}^{\top} [\mathbf{W} \mathbf{h}_u \| \mathbf{W} \mathbf{h}_v]) $$ $$ \alpha_{uv} = \frac{\exp(e_{uv})}{\sum_{k \in \mathcal{N}(v)} \exp(e_{kv})} $$ $$ \mathbf{h}_v' = \sigma\left( \sum_{u \in \mathcal{N}(v)} \alpha_{uv} \mathbf{W} \mathbf{h}_u \right) $$ 这使模型能自适应地关注重要邻居，尤其适用于异质图。

几乎同时，Hamilton等人提出图采样与聚合网络（GraphSAGE），旨在解决GNN在大规模图上的可扩展性问题。其核心思想是邻居采样与聚合函数设计。对于节点 $v$，固定采样大小 $k$，从 $\mathcal{N}(v)$ 中采样 $k$ 个邻居，然后使用聚合器（如Mean、LSTM、Pooling）聚合邻居信息： $$ \mathbf{h}_v^{(k)} = \sigma\left( \mathbf{W} \cdot \text{CONCAT}(\mathbf{h}_v^{(k-1)}, \text{AGGREGATE}(\{\mathbf{h}_u^{(k-1)}, \forall u \in \mathcal{N}(v)\}) ) \right) $$ GraphSAGE展示了GNN可以通过采样实现归纳式（Inductive） 学习，即训练好的模型可泛化到从未见过的节点。

2019年，图同构网络（Graph Isomorphism Network, GIN） 从理论上探讨了GNN的表达能力上限。Xu等人证明，GCN、GAT等模型最多能区分与Weisfeiler-Lehman（WL） 测试同等复杂的图结构。而GIN通过设计更强的聚合函数（$\text{MLP}(\cdot)$ 而非线性组合），理论上达到WL测试的判别能力，即能区分几乎所有非同构图。其更新规则为： $$ \mathbf{h}_v^{(k)} = \text{MLP}^{(k)}\left( (1 + \epsilon^{(k)}) \cdot \mathbf{h}_v^{(k-1)} + \sum_{u \in \mathcal{N}(v)} \mathbf{h}_u^{(k-1)} \right) $$ $\epsilon$ 为可学习或固定参数。这标志着GNN研究从工程实践走向理论分析。

至此，消息传递神经网络（Message Passing Neural Network, MPNN） 框架被正式提出（Gilmer等人，2017），统一了GCN、GAT、GraphSAGE等模型。MPNN将GNN步骤抽象为： 1. 消息函数（Message Function） $m_{\theta}(\mathbf{h}_v, \mathbf{h}_u, \mathbf{e}_{uv})$：计算从邻居 $u$ 到中心节点 $v$ 的消息，可依赖于节点特征与边特征。 2. 聚合函数（Aggregation Function） $\text{AGGREGATE}(\{m_{uv} | u \in \mathcal{N}(v)\})$：将来自不同邻居的消息聚合为单一向量，通常为置换不变操作（如求和、均值、最大值）。 3. 更新函数（Update Function） $u_{\theta}(\mathbf{h}_v, \mathbf{m}_v)$：结合聚合消息与节点自身旧状态，生成新表示。

形式化地，第 $k$ 层： $$ \mathbf{m}_v^{(k)} = \sum_{u \in \mathcal{N}(v)} m_{\theta}^{(k)}(\mathbf{h}_u^{(k-1)}, \mathbf{h}_v^{(k-1)}, \mathbf{e}_{uv}) $$ $$ \mathbf{h}_v^{(k)} = u_{\theta}^{(k)}(\mathbf{h}_v^{(k-1)}, \mathbf{m}_v^{(k)}) $$ MPNN框架的提出，标志着GNN研究进入模块化、可组合的新阶段，后续几乎所有GNN变体均可在此框架下理解。

1.3 图结构数据的独特挑战

图数据的非欧特性带来了深度学习必须直面的四大挑战，这些挑战贯穿全书。

1.3.1 排列不变性（Permutation Invariance）

图的节点没有天然顺序。给定同一图 $G$ 的两个不同邻接矩阵表示 $\mathbf{A}$ 和 $\mathbf{P} \mathbf{A} \mathbf{P}^{\top}$（$\mathbf{P}$ 为置换矩阵），它们是同一图的不同“视角”。任何有效的GNN必须满足 $f_{\theta}(\mathbf{A}, \mathbf{X}) = f_{\theta}(\mathbf{P} \mathbf{A} \mathbf{P}^{\top}, \mathbf{P} \mathbf{X})$（对节点特征矩阵 $\mathbf{X}$ 做相应置换）。传统CNN依赖于输入网格的固定空间顺序（如图像像素的左上到右下），RNN依赖于时间步顺序，均不满足此要求。

案例：社交网络用户节点。在Facebook好友图中，用户“Alice”的节点ID可能是“1000”，但在另一数据副本中可能被随机打乱为“0543”。模型预测Alice的兴趣标签时，结果不应因ID变化而改变。GNN通过在每个节点上独立应用相同的变换函数（权重共享），并仅使用置换不变的聚合操作（如求和、最大值）来天然满足此性质。

1.3.2 不规则拓扑（Irregular Topology）

图的结构由邻接关系定义，节点度数（邻居数量）可变且无界。这与图像（固定尺寸、规则卷积核）或序列（固定或可变长度、一维卷积）形成鲜明对比。不规则性导致：

• **邻居数量不等**：一个分子图中的原子可能有2个键（如氧）或4个键（如碳），无法像图像那样使用固定大小的卷积核。
• **长程依赖捕获困难**：信息需通过多跳消息传递才能从远距离节点传播，但随跳数增加，信息可能过平滑或消失。
• **计算不规整**：无法使用高度优化的稠密矩阵运算（如图像的im2col），通常需要稀疏矩阵乘法或邻接表遍历，效率较低。

案例：生物分子图。在药物发现中，分子表示为原子（节点）和化学键（边）的图。原子类型（C、O、N等）是特征，键的类型（单、双、三键）是边特征。不同分子的拓扑千差万别：苯环是高度连接的环，而直链烷烃是树状结构。GNN必须能处理这种结构多样性。

1.3.3 尺度与规模（Scale and Size）

真实世界图规模巨大：社交网络（数十亿节点）、知识图谱（数亿实体）、通信网络（数万亿边）。这带来三大问题： 1. 内存瓶颈：全批量训练需将整图加载到GPU内存，对超大图不可行。 2. 计算瓶颈：邻居指数增长（如2跳邻居），导致单次前向传播计算量巨大。 3. 过平滑（Over-smoothing）：随着层数增加，所有节点表示趋于收敛到同一向量，丧失区分性。理论上，超过 $O(\log n)$ 层的GNN在极限下无法区分非正则图。

案例：Pinterest社交图。Pinterest有超过4亿用户，平均好友数数百。训练一个10层GNN意味着每个节点需聚合其10跳内所有邻居，计算量呈指数爆炸。这催生了图采样（Graph Sampling）（如GraphSAGE的邻居采样、Cluster-GCN的聚类采样）和分布式训练技术。

1.3.4 动态性与异质性（Dynamics and Heterogeneity）

许多图是动态演化的（如社交关系新增、撤销），且包含多种节点/边类型（如学术知识图谱有作者、论文、会议等节点，有“撰写”、“发表于”等边）。这要求GNN具备：

• **时序建模能力**：处理图随时间变化，如TGN（Temporal Graph Networks）。
• **类型感知**：对不同类型节点/边使用不同变换参数，如**异构图神经网络（Heterogeneous GNN）** 通过元路径（Meta-path）或关系特定权重进行聚合。

**案