图神经网络导论：演进、范式与全景

图数据（Graph Data）的普遍性及其对传统机器学习范式的根本性挑战，构成了我们进入图神经网络（Graph Neural Networks, GNNs）世界的起点。从社交网络中复杂的好友关系到生物体内精密的蛋白质相互作用网络，从互联网的链接拓扑到知识图谱中实体间的语义关联，这些非欧几里得结构（non-Euclidean structures）所蕴含的丰富关系信息，无法被处理网格状数据（如图像）的卷积神经网络（CNN）或处理序列数据（如文本）的循环神经网络（RNN）直接有效建模。早期尝试通常将图结构“flatten”为向量表示（例如通过图嵌入），但这种预处理方式割裂了结构信息与节点/边特征的学习过程，导致信息损失且无法进行端到端的联合优化。图神经网络的兴起，标志着一个新范式的确立：通过可微的消息传递（Message Passing）机制，直接在图上进行深层特征传播与聚合，从而实现了对拓扑结构及其属性信息的统一、迭代式学习。本章将系统梳理这一演进脉络，定义核心概念，剖析统一框架，并展望其跨领域的变革性应用，为全书奠定坚实的认知基础。

1.1 历史演进：从图嵌入到图神经网络的范式革命

图表示学习的历史可追溯至21世纪初，其发展并非一蹴而就，而是经历了一个从“浅层嵌入”到“深度图网络”的清晰演进过程。这一过程不仅是技术上的迭代，更是对“如何为图结构数据设计学习算法”这一核心问题认知的深化。

1.1.1 图嵌入时代：随机游走与矩阵分解的奠基

在深度学习主导之前，图表示学习主要依赖于浅层嵌入（Shallow Embedding） 方法。其核心思想是为图中的每个节点（或边）学习一个固定维度的低维向量，使得在向量空间中相近的节点在原始图中也具有相近的结构角色或连接模式。关键突破源于将自然语言处理中的词嵌入思想迁移至图领域。

DeepWalk (Perozzi et al., 2014) 是里程碑式的工作。它通过在图结构上执行截断随机游走（Truncated Random Walk） 生成节点序列，将这些序列视为“句子”，从而将图问题转化为语料库上的无监督学习问题。随后，使用Skip-Gram模型（Mikolov et al., 2013）来学习节点嵌入，其目标函数为： $$ \max_{\mathbf{v}} \sum_{v \in \mathcal{V}} \sum_{c \in N_R(v)} \log p(c | v) $$ 其中，$N_R(v)$ 表示节点 $v$ 在随机游走中生成的上下文节点集合，$p(c|v)$ 通常通过softmax函数计算。DeepWalk巧妙地将图的局部结构（通过随机游走捕获）与全局嵌入联系起来，但其嵌入一旦训练完成即固定不变，无法在具体下游任务（如节点分类）中根据任务需求进行微调。

Node2Vec (Grover & Leskovec, 2016) 在此基础上引入了有偏随机游走，通过调整参数 $p$ 和 $q$ 在广度优先（BFS） 和深度优先（DFS） 游走之间进行权衡，从而更好地平衡同质性（homophily，相似节点相连）和结构性（structural equivalence，具有相似邻居的节点）的捕获。这展示了通过设计采样策略来影响嵌入质量的早期思想。

同时期，基于矩阵分解的方法也占有一席之地，如HOPE (Ou et al., 2016) 通过分解高阶图 proximities 矩阵（如 Katz 指数）来保留全局结构。然而，这些浅层方法存在根本性局限： 1. 不可微与无法端到端训练：嵌入是独立学习的，无法与下游任务的损失函数联合优化。 2. 无法融合节点特征：通常仅利用图拓扑结构，难以有效整合节点自身的属性特征（如用户资料、分子原子类型）。 3. 计算与存储开销：对于百万级节点的大图，存储所有节点的嵌入矩阵可能成为瓶颈，且重新训练成本高昂。 4. 无法处理动态图：图结构变化时，需完全重新训练。

这些局限催生了对一种新的、统一的、可微的图学习范式的迫切需求。

1.1.2 GNN范式的形成：从谱图卷积到空间聚合

GNN的现代范式诞生于两个平行但最终汇合的思想流：谱方法（Spectral Methods） 和空间方法（Spatial Methods）。

谱图卷积的兴起（2013-2016）：受信号处理中傅里叶变换的启发，研究者将图卷积定义为图拉普拉斯矩阵（Graph Laplacian） 特征基上的滤波操作。Bruna et al. (2013) 首次将卷积神经网络引入图结构数据，其卷积核在傅里叶域定义，依赖于拉普拉斯矩阵的特征分解 $\mathbf{L} = \mathbf{U} \Lambda \mathbf{U}^T$，其中 $\mathbf{U}$ 是特征向量矩阵，$\Lambda$ 是特征值对角阵。卷积操作可写为： $$ \mathbf{x} * \mathbf{g} = \mathbf{U} (\mathbf{U}^T \mathbf{x} \odot \mathbf{U}^T \mathbf{g}) $$ 其中 $\mathbf{x}$ 是图信号（节点特征），$\mathbf{g}$ 是滤波器。这一定义在数学上优雅，但存在致命缺陷：计算特征分解的复杂度为 $O(n^3)$，且滤波器依赖于全局图结构，不具备归纳式学习（Inductive Learning） 能力——无法泛化到训练时未见的新节点。

GCN的简化与普及（2016）：Kipf & Welling (2016) 做出了关键简化。他们使用一阶切比雪夫多项式近似来规避特征分解，并限制滤波器为仅依赖一阶邻域的形式，提出了图卷积网络（GCN）。其核心传播层为： $$ \mathbf{H}^{(l+1)} = \sigma\left( \tilde{\mathbf{D}}^{-1/2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1/2} \mathbf{H}^{(l)} \mathbf{W}^{(l)} \right) $$ 其中 $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}_N$ 是添加自环的邻接矩阵，$\tilde{\mathbf{D}}$ 是其度矩阵，$\mathbf{H}^{(l)}$ 是第 $l$ 层的节点特征矩阵，$\mathbf{W}^{(l)}$ 是可学习权重，$\sigma$ 是激活函数。这一形式高效、可微，且通过邻接矩阵的乘法天然实现了消息聚合，迅速成为GNN的基准模型（De Facto Baseline）。然而，GCN的聚合方式固定为归一化求和，且对所有邻居一视同仁，缺乏对邻居重要性的区分。

空间聚合与归纳式学习的确立（2017）：Hamilton et al. (2017) 提出的GraphSAGE 从空间（Spatial） 视角彻底重构了GNN。其核心洞见是：GNN的核心操作是邻居信息的聚合与节点自身的更新，而不必拘泥于谱域。GraphSAGE 明确提出了一个可训练的聚合函数框架： $$ \mathbf{h}_v^{(k)} = \sigma\left( \mathbf{W}^{(k)} \cdot \text{CONCAT}\left( \mathbf{h}_v^{(k-1)}, \text{AGGREGATE}^{(k)}(\{ \mathbf{h}_u^{(k-1)}, \forall u \in \mathcal{N}(v) \}) \right) \right) $$ 其中 $\mathcal{N}(v)$ 是节点 $v$ 的邻居集合，$\text{AGGREGATE}$ 可以是均值、LSTM或池化操作。GraphSAGE 的革命性贡献在于：在训练时，它采样固定数量的邻居，使得每层计算复杂度与采样大小相关而非与整个图相关，从而首次实现了真正意义上的大规模图归纳式学习——训练好的模型可以直接应用于未见过的、更大的图。这一定义成为后来绝大多数空间GNN的标准范式。

1.1.3 注意力机制与异质性处理（2017至今）

图注意力网络（GAT） (Veličković et al., 2018) 将自注意力机制（Self-Attention） 引入GNN，解决了GCN聚合方式固定的问题。GAT为每个邻居 $u$ 学习一个注意力系数 $\alpha_{vu}$，表示 $v$ 在聚合邻居 $u$ 信息时应赋予的权重： $$ \alpha_{vu} = \frac{\exp\left(\text{LeakyReLU}\left( \mathbf{a}^T [\mathbf{W} \mathbf{h}_v^{(l)} || \mathbf{W} \mathbf{h}_u^{(l)}] \right)\right)}{\sum_{i \in \mathcal{N}(v)} \exp\left(\text{LeakyReLU}\left( \mathbf{a}^T [\mathbf{W} \mathbf{h}_v^{(l)} || \mathbf{W} \mathbf{h}_i^{(l)}] \right)\right)} $$ 其中 $\mathbf{W}$ 是共享线性变换，$\mathbf{a}$ 是注意力向量，$||$ 表示拼接。聚合时采用加权和： $$ \mathbf{h}_v^{(l+1)} = \sigma\left( \sum_{u \in \mathcal{N}(v)} \alpha_{vu} \mathbf{W} \mathbf{h}_u^{(l)} \right) $$ GAT无需依赖图结构预处理（如归一化），能自动学习不同邻居的重要性，且计算可并行，性能显著优于GCN。多头注意力（Multi-head Attention） 的引入进一步稳定了学习过程。

随着应用场景的复杂化，研究者将GNN扩展至异构图（Heterogeneous Graph），其中包含多种节点类型和边类型（如学术图中的“作者-写-论文”、“论文-引用-论文”）。RGCN (Schlichtkrull et al., 2018) 为每种边类型学习特定的变换权重，HGT (Hu et al., 2020) 则引入基于元路径的注意力机制，动态聚合不同类型邻居。此外，针对动态图（Dynamic Graph）、超图（Hypergraph）、几何图（Geometric Graph） 等，也衍生出TGAT、HyperGNN、PointNet++等变体。

范式总结：从DeepWalk的随机游走嵌入，到GCN的简化谱卷积，再到GraphSAGE的空间归纳式聚合与GAT的注意力机制，演进的主线是从离散、静态、浅层的表示，走向连续、可微、深层、且能自适应处理异质性与动态性的统一消息传递框架。消息传递被确立为GNN的核心抽象，它统一了上述所有模型：不同GNN的区别仅在于聚合函数（AGGREGATE） 和更新函数（UPDATE） 的具体设计。

1.2 基本概念与统一框架：消息传递机制

在深入具体模型前，必须建立一套精确的数学语言来描述图结构及其上的学习过程。

1.2.1 图的数学定义

一个图（Graph） $\mathcal{G}$ 定义为节点集 $\mathcal{V}$ 和边集 $\mathcal{E}$ 的二元组，即 $\mathcal{G} = (\mathcal{V}, \mathcal{E})$。设 $N = |\mathcal{V}|$ 为节点数，$M = |\mathcal{E}|$ 为边数。

• **节点（Node/Vertex）** $v \in \mathcal{V}$：图的基本单元，通常伴随一个**特征向量** $\mathbf{x}_v \in \mathbb{R}^d$，其中 $d$ 是特征维度。所有节点特征可堆叠为矩阵 $\mathbf{X} \in \mathbb{R}^{N \times d}$。
• **边（Edge）** $e = (u, v) \in \mathcal{E}$：连接两个节点的关系。边可以是**有向（Directed）** 或**无向（Undirected）**，**加权（Weighted）** 或**无权（Unweighted）**。
• **邻接矩阵（Adjacency Matrix）** $\mathbf{A} \in \{0,1\}^{N \times N}$：若 $(u,v) \in \mathcal{E}$，则 $A_{uv}=1$，否则为0。对于无向图，$\mathbf{A}$ 对称。加权图中 $A_{uv}$ 为权重。
• **度矩阵（Degree Matrix）** $\mathbf{D} \in \mathbb{R}^{N \times N}$：对角矩阵，$D_{ii} = \sum_j A_{ij}$，即节点 $i$ 的度数。
• **图拉普拉斯矩阵（Graph Laplacian）** $\mathbf{L} = \mathbf{D} - \mathbf{A}$。其归一化形式 $\mathbf{L}_{\text{norm}} = \mathbf{D}^{-1/2} (\mathbf{D} - \mathbf{A}) \mathbf{D}^{-1/2}$ 在谱方法中至关重要。

图可进一步分类：

• **同构图（Homogeneous Graph）**：所有节点和边属于同一类型。
• **异构图（Heterogeneous Graph）**：存在多种节点类型 $\mathcal{T}_V$ 和边类型 $\mathcal{T}_E$，每条边 $(u,v)$ 关联一个类型 $\tau_{uv} \in \mathcal{T}_E$。
• **动态图（Dynamic Graph）**：节点、边或其属性随时间变化。

1.2.2 消息传递：GNN的统一抽象

Gilmer et al. (2017) 在“Message Passing Neural Networks”中明确提出，绝大多数GNN可被统一到一个消息传递（Message Passing） 框架中。该框架定义了图上的迭代式信息传播过程，每一层（或一步）包含三个核心函数：

1. 消息函数（Message Function） $m_{uv}^{(l)} = \text{MSG}^{(l)}(\mathbf{h}_u^{(l-1)}, \mathbf{h}_v^{(l-1)}, \mathbf{e}_{uv})$：为每条边 $(u,v)$ 生成一条“消息”。它依赖于源节点 $u$ 的表示 $\mathbf{h}_u^{(l-1)}$、目标节点 $v$ 的表示 $\mathbf{h}_v^{(l-1)}$ 以及边特征 $\mathbf{e}_{uv}$（若存在）。最简单的形式忽略边特征，仅 $m_{uv}^{(l)} = \mathbf{h}_u^{(l-1)}$。

2. 聚合函数（Aggregation Function） $\mathbf{m}_v^{(l)} = \bigoplus_{u \in \mathcal{N}(v)} m_{uv}^{(l)}$：将目标节点 $v$ 的所有入邻居传递来的消息聚合成一个固定向量。常用聚合操作包括：

• **求和（Sum）**：$\sum$，保留多重边信息，但受度数影响大。
• **均值（Mean）**：$\text{mean}$，对度数归一化，常见于GCN。
• **最大值（Max）**：$\max$，捕捉最显著特征，但可能丢失信息。
• **注意力加权和（Attention-weighted Sum）**：如GAT，$\sum \alpha_{vu} m_{vu}$。

3. 更新函数（Update Function） $\mathbf{h}_v^{(l)} = \text{UPD}^{(l)}(\mathbf{h}_v^{(l-1)}, \mathbf{m}_v^{(l)})$：结合节点 $v$ 的上一隐藏状态 $\mathbf{h}_v^{(l-1)}$ 和聚合后的邻居信息 $\mathbf{m}_v^{(l)}$，生成新的节点表示。通常是一个神经网络（如MLP）： $$ \mathbf{h}_v^{(l)} = \sigma\left( \mathbf{W}^{(l)} \cdot \text{CONCAT}(\mathbf{h}_v^{(l-1)}, \mathbf{m}_v^{(l)}) \right) \quad \text{或} \quad \mathbf{h}_v^{(l)} = \sigma\left( \mathbf{W}^{(l)} \cdot \mathbf{h}_v^{(l-1)} + \mathbf{b}^{(l)} + \mathbf{m}_v^{(l)} \right) $$

经过 $K$ 层传播后，每个节点 $v$ 的最终表示 $\mathbf{h}_v^{(K)}$ 理论上感受野（Receptive Field） 覆盖了其 $K$ 跳（hop）内的所有邻居，即其$K$-阶子图（$K$-hop Subgraph） 的结构信息。这正是GNN能够捕获多跳关系、进行结构推理的关键。

```mermaid graph TD A[输入图 G = (V, E, X)] --> B[第1层消息传递] B --> C[消息函数: MSG<br/>为每条边生成消息] C --> D[聚合函数: AGGREGATE<br/>对邻居消息求和/均值/注意力] D --> E[更新函数: UPDATE<br/>结合自身上一状态与聚合信息] E --> F[输出节点表示 H^(1)] F --> G{是否达到层数 K?} G -- 否 --> B G -- 是 --> H[最终节点表示 H^(K)] H --> I[读出函数 READOUT<br/>生成图级别表示] ```

图级别预测（Graph-level Prediction） 通常需要一个读出函数（Readout Function） 将所有节点表示聚合成一个图向量 $\mathbf{y}_\mathcal{G}$，常用池化（Pooling） 操作，如**全局求和/均值池化*