第1章：图神经网络导论：概念、历史与核心挑战 / Chapter 1: Introduction to Graph Neural Networks: Concepts, History, and Core Challenges

图结构数据（graph-structured data）是现实世界复杂系统的基础表示形式。从社交网络中的人际关系、生物网络中的蛋白质相互作用，到交通网络中的道路连接和推荐系统中的用户-物品交互，图无处不在。然而，这些数据具有非欧几里得（non-Euclidean）和不规则（irregular）的特性，传统的机器学习算法，尤其是深度学习模型，大多设计用于规则网格数据（如图像）或序列数据（如文本），难以直接应用。图神经网络（Graph Neural Networks, GNNs）作为一种专门处理图数据的神经网络架构，近年来取得了突破性进展，成为机器学习领域的热点方向。其核心思想是通过消息传递（message passing）机制，让节点通过聚合邻居信息来更新自身表示，从而捕捉图的结构依赖关系。自2016年图卷积网络（Graph Convolutional Network, GCN）被提出以来，GNN已在节点分类、链接预测、图分类等任务上展现出强大能力，并逐步扩展到物理模拟、程序分析、组合优化等新领域。然而，随着应用场景的复杂化，GNN仍面临可扩展性、动态性、泛化能力等多重挑战。本章将系统阐述GNN的基本概念、发展历程与核心挑战，为读者构建整体认知框架，并指引后续章节的阅读路径。

图数据的本质与表示学习需求

图结构数据的特殊性

图是由节点（vertices）和边（edges）组成的数据结构，通常表示为 $G = (\mathcal{V}, \mathcal{E})$，其中 $\mathcal{V}$ 是节点集合，$\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ 是边集合。每个节点 $v_i \in \mathcal{V}$ 可能伴随特征向量 $\mathbf{x}_i \in \mathbb{R}^d$，边也可能具有属性（如权重、类型）。与表格数据或图像数据不同，图数据具有三个关键特性： 1. 非欧几里得性（Non-Euclidean）：节点没有固定的顺序或坐标，图的拓扑结构由邻接关系定义，无法直接嵌入到向量空间中。 2. 不规则性（Irregular）：节点的邻居数量可变，导致传统卷积核（如CNN中的固定大小核）难以直接应用。 3. 置换不变性（Permutation Invariance）：节点的标签或顺序不影响图的语义，即对节点进行任意排列后，图本身保持不变。因此，任何图学习模型必须满足置换不变性：对于任意节点排列 $\pi$，输出应满足 $f_\theta(\mathbf{X}, \mathbf{A}) = f_\theta(\mathbf{X}_\pi, \mathbf{A}_\pi)$，其中 $\mathbf{X}$ 是特征矩阵，$\mathbf{A}$ 是邻接矩阵。

这些特性使得传统深度学习模型无法直接处理图数据。例如，卷积神经网络（CNN）依赖于网格结构的平移不变性，循环神经网络（RNN）依赖于序列顺序，而图数据既无网格也无固定顺序。

表示学习的必要性

表示学习（Representation Learning）旨在将离散对象（如图节点、整个图）映射到连续向量空间，使得语义相似的对象在向量空间中距离相近。对于图数据，表示学习的目标是学习一个编码函数 $f_\theta: G \mapsto \mathbf{h}_i$（节点级）或 $f_\theta: G \mapsto \mathbf{h}_G$（图级），使得学到的嵌入（embedding）能够保留图的结构信息和节点/边特征，并适用于下游任务（如分类、聚类）。

早期图表示学习方法主要分为两类：

• **基于矩阵分解的方法**：如图正则化非负矩阵分解（GNMF），利用图拉普拉斯矩阵保持局部结构，但难以扩展到大规模图。
• **基于随机游走的方法**：如DeepWalk和node2vec，通过随机游走生成节点序列，再用Skip-gram模型学习嵌入。这些方法虽然高效，但仅利用拓扑结构，难以融合节点特征，且为浅层模型，表达能力有限。

表示学习的关键优势在于端到端优化：GNN能够同时学习表示和任务预测器，通过反向传播联合优化，使表示更贴合具体任务。相比之下，传统方法通常分两步（先学习通用表示，再训练分类器），可能导致表示与任务不匹配。

GNN的通用框架

现代GNN大多遵循消息传递神经网络（Message Passing Neural Networks, MPNNs）框架，由一系列消息传递层组成。每层中，节点通过以下步骤更新表示： 1. 消息构造（Message）：对于每条边 $(i, j)$，基于发送节点 $j$ 的当前状态和边特征构造消息 $\mathbf{m}_{j \rightarrow i}$。 2. 消息聚合（Aggregate）：对节点 $i$ 的所有入边消息进行聚合，常用函数有求和（sum）、均值（mean）、最大值（max）。 3. 节点更新（Update）：结合聚合后的消息和节点 $i$ 的旧状态，更新为新状态 $\mathbf{h}_i^{(l)}$。

数学上，第 $l$ 层的更新可表示为： $$ \mathbf{m}_{j \rightarrow i}^{(l)} = \text{MSG}^{(l)}(\mathbf{h}_j^{(l-1)}, \mathbf{x}_{j,i}), \quad \mathbf{M}_i^{(l)} = \bigoplus_{j \in \mathcal{N}(i)} \mathbf{m}_{j \rightarrow i}^{(l)}, \quad \mathbf{h}_i^{(l)} = \text{UPD}^{(l)}(\mathbf{M}_i^{(l)}, \mathbf{h}_i^{(l-1)}), $$ 其中 $\mathcal{N}(i)$ 是节点 $i$ 的邻居集合，$\bigoplus$ 是置换不变的聚合函数（如求和），$\text{MSG}$ 和 $\text{UPD}$ 是可学习函数（通常为神经网络）。经过 $L$ 层后，节点 $i$ 的表示 $\mathbf{h}_i^{(L)}$ 理论上捕获了其 $L$-跳邻居内的结构信息。

对于图级任务，还需一个读出函数（Readout）将所有节点表示聚合成图表示，如 $\mathbf{h}_G = \text{READOUT}(\{ \mathbf{h}_i^{(L)} \mid i \in \mathcal{V} \})$，常用求和、均值或基于注意力的聚合。

这一框架统一了早期GNN变体，并强调了局部性和置换不变性——GNN仅通过邻居交互更新状态，不依赖全局节点顺序，从而保证了对图结构的尊重。

图神经网络的发展历程

GNN的发展可大致分为四个阶段，每个阶段都伴随着对表达能力、效率和适用范围的突破。

萌芽期（2005-2012）：递归图神经网络

最早的系统性工作可追溯至2005年Scarselli等人提出的图神经网络（Graph Neural Networks, 原始名称）。该模型使用递归神经网络（RNN）处理图：节点状态通过递归方程更新，直到达到固定点。形式化地，节点 $i$ 的状态更新为： $$ \mathbf{h}_i(t+1) = \sum_{j \in \mathcal{N}(i)} f_\theta(\mathbf{x}_i, \mathbf{x}_{j,i}, \mathbf{h}_j(t), \mathbf{h}_i(t)), $$ 其中 $f_\theta$ 是前馈网络。训练通过梯度下降优化，但存在收敛不稳定、计算成本高（需多次迭代直至收敛）等问题。尽管思想超前，但由于计算资源限制和深度学习的低谷，这一阶段研究未引起广泛关注。

谱方法兴起（2013-2016）：图卷积的奠基

2013年，Bruna等人首次将卷积操作推广到图，基于图拉普拉斯矩阵（Laplacian matrix）的谱分解定义图卷积。图拉普拉斯 $\mathbf{L} = \mathbf{D} - \mathbf{A}$（$\mathbf{D}$ 为度矩阵）的特征向量构成正交基，谱卷积在频域进行： $$ \mathbf{H} \star \mathbf{X} = \mathbf{U} g(\mathbf{\Lambda}) \mathbf{U}^\top \mathbf{X}, $$ 其中 $\mathbf{U}$ 是特征向量矩阵，$\mathbf{\Lambda}$ 是特征值对角阵，$g$ 是频域滤波器。但该操作计算复杂度 $O(n^2)$，且依赖于完整的拉普拉斯特征分解，难以扩展到大规模图。

2014年，Defferrard等人提出切比雪夫图卷积网络（ChebNet），使用切比雪夫多项式 $T_k(\mathbf{\Lambda})$ 近似滤波器 $g(\mathbf{\Lambda})$，将卷积限制在 $K$ 阶邻域内： $$ g(\mathbf{\Lambda}) \approx \sum_{k=0}^{K} \theta_k T_k(\mathbf{\tilde{\Lambda}}), \quad \text{其中 } \mathbf{\tilde{\Lambda}} = \frac{2}{\lambda_{\max}} \mathbf{\Lambda} - \mathbf{I}. $$ 从而避免特征分解，计算复杂度降至 $O(K|\mathcal{E}|)$。ChebNet 为高效图卷积奠定基础。

2016年，Kipf 和 Welling 提出图卷积网络（Graph Convolutional Network, GCN），进一步简化：仅使用一阶近似，并假设聚合函数为归一化的邻接矩阵 $\mathbf{\hat{A}} = \mathbf{\tilde{D}}^{-1/2} \mathbf{\tilde{A}} \mathbf{\tilde{D}}^{-1/2}$（$\mathbf{\tilde{A}} = \mathbf{A} + \mathbf{I}$ 添加自环）。GCN 层的前向传播为： $$ \mathbf{H}^{(l+1)} = \sigma\left( \mathbf{\hat{A}} \mathbf{H}^{(l)} \mathbf{W}^{(l)} \right), $$ 其中 $\mathbf{W}^{(l)}$ 是可训练权重矩阵，$\sigma$ 为激活函数。GCN 因其简洁性和有效性迅速成为基准模型，但本质上是谱方法的简化，依赖于对称归一化的邻接矩阵，且为直推式学习（transductive），无法泛化到未见节点。

空间方法发展（2017-2019）：归纳学习与灵活性

谱方法的一大局限是依赖于固定的图拉普拉斯，当图结构变化时（如新节点加入），需重新计算特征分解，不利于归纳学习（inductive learning）。2017年，Hamilton 等人提出图采样与聚合（GraphSAGE），首次实现了归纳式GNN。GraphSAGE 通过采样固定数量的邻居，并定义聚合函数（如均值、LSTM、最大池化），使训练好的模型能泛化到未见节点： $$ \mathbf{h}_i^{(l)} = \sigma\left( \mathbf{W}^{(l)} \cdot \text{CONCAT}\left( \mathbf{h}_i^{(l-1)}, \text{AGGREGATE}^{(l)}(\{ \mathbf{h}_j^{(l-1)}, \forall j \in \mathcal{N}(i) \}) \right) \right). $$ GraphSAGE 在大规模图（如Reddit）上展示了可扩展性。

同年，Veličković 等人提出图注意力网络（Graph Attention Network, GAT），引入注意力机制动态加权邻居重要性： $$ \alpha_{ij} = \frac{\exp\left( \text{LeakyReLU}\left( \mathbf{a}^\top [\mathbf{W}\mathbf{h}_i \| \mathbf{W}\mathbf{h}_j] \right) \right)}{\sum_{k \in \mathcal{N}(i)} \exp\left( \text{LeakyReLU}\left( \mathbf{a}^\top [\mathbf{W}\mathbf{h}_i \| \mathbf{W}\mathbf{h}_k] \right) \right)}, $$ $$ \mathbf{h}_i' = \sigma\left( \sum_{j \in \mathcal{N}(i)} \alpha_{ij} \mathbf{W} \mathbf{h}_j \right). $$ GAT 无需预定义图结构，能学习邻居权重，且支持多头注意力增强表达能力。

空间方法直接在节点空间操作，不依赖全局谱分解，更灵活、可扩展，并自然支持归纳学习，成为GNN的主流范式。

表达能力强化与多样化（2018-2020）

研究逐渐深入GNN的理论表达能力。2018年，Weisfeiler-Lehman（WL）图同构测试被引入作为GNN表达能力的上界：GNN的表达能力至多与WL测试相同。Xu 等人证明，若聚合函数是单射的，GNN可达到WL测试能力，并提出了图同构网络（Graph Isomorphism Network, GIN）： $$ \mathbf{h}_i^{(l)} = \text{MLP}^{(l)}\left( (1 + \epsilon) \mathbf{h}_i^{(l-1)} + \sum_{j \in \mathcal{N}(i)} \mathbf{h}_j^{(l-1)} \right), $$ 其中 $\epsilon$ 为可学习参数。GIN 被证明是最具表达力的MPNN之一。

同时，GNN应用场景扩展至异构图（heterogeneous graphs）、超图（hypergraphs）、动态图（dynamic graphs）等。例如，RGCN 处理多关系图，HyperGNN 处理超边连接多个节点，DyGNN 处理时序演化。

前沿趋势（2020至今）：自监督、大规模与动态化

近年来，GNN研究聚焦于以下前沿方向：

• **自监督学习**：为缓解标注数据稀缺，利用图自身结构生成伪标签。如**深度图信息最大化**（DGI）通过对比学习最大化节点表示与图级表示的互信息；**图对比学习**（GraphCL）通过图增强（如节点丢弃、边扰动）构造正负样本对。
• **可扩展性突破**：针对亿级节点图，提出子图采样方法（如GraphSAINT随机采样子图训练）、历史嵌入缓存（如HIST避免重复计算）、图分区与分布式训练（如PGL、AliGraph）。
• **动态图神经网络**：处理连续时间事件流。**时序图注意力网络**（TGAT）将时间衰减融入注意力；**时序图网络**（TGN）结合记忆模块存储历史信息，支持实时预测。
• **图Transformer**：将Transformer架构引入图学习，使用全局注意力捕获长程依赖，如GraphTransformer、GTN。
• **跨模态图学习**：结合图像、文本等，如视觉推理中的场景图神经网络。

下图概括了GNN主要演进路径：

```mermaid graph LR A[2005-2012<br/>递归GNN] --> B[2013-2016<br/>谱方法：ChebNet, GCN] B --> C[2017-2019<br/>空间方法：GraphSAGE, GAT] C --> D[2018-2020<br/>表达能力：GIN, 异构/超图] D --> E[2020+<br/>自监督/大规模/动态/Transformer] ```

核心挑战剖析

尽管GNN取得显著进展，但在实际应用中仍面临若干核心挑战，这些挑战源于图数据的内在复杂性与应用场景的多样性。

可扩展性：从千级到亿级节点

问题本质：GNN的邻居聚合机制导致计算和内存开销随图规模增长而急剧上升。对于 $L$ 层GNN，节点表示依赖其 $L$-跳邻居，邻居数量可能指数级增长（尤其在高度节点密集图中）。例如，在两层GCN中，节点需聚合一阶和二阶邻居，若平均度为 $d$，则二阶邻居数约 $d^2$。当 $d=100$ 时，二阶邻居达10,000，全图训练内存难以承受。

现有解决方案：

• **邻居采样**：GraphSAGE 对每层固定采样 $K$ 个邻居，将复杂度从 $O(|\mathcal{E}|)$ 降至 $O(K^L |\mathcal{V}|)$。但采样引入偏差，可能丢失重要邻居或引入噪声。
• **子图采样**：Cluster-GCN 将图聚类为 $C$ 个子图，在每个子图上训练，避免跨子图边的影响；GraphSAINT 随机采样节点子集及其关联边形成子图，训练更稳定。
• **历史嵌入缓存**：HIST 为节点维护历史嵌入缓存，避免重复计算，适用于动态图。
• **分布式训练**：将图分区到多设备，如DistGNN 使用分区间通信聚合跨区邻居。

挑战与权衡：采样虽提升效率

4.1 可扩展性：从千级到亿级节点

问题本质：GNN的邻居聚合机制导致计算和内存开销随图规模增长而急剧上升。对于$L$层GNN，节点表示依赖其$L$-跳邻居，邻居数量可能指数级增长（尤其在高度节点密集图中）。例如，在两层GCN中，节点需聚合一阶和二阶邻居，若平均度为$d$，则二阶邻居数约$d^2$。当$d=100$时，二阶邻居达10,000，全图训练内存难以承受。以常见的OGBN-Arxiv数据集为例，约16万节点、80万边，单层GCN的邻接矩阵存储需约$1.28 \times 10^9$个浮点数（约4.8GB），两层则需存储两跳邻域，内存消耗呈爆炸式增长。

现有解决方案的深度剖析：

邻居采样（Neighbor Sampling）：GraphSAGE提出的固定数量邻居采样（如每层采样10-25个邻居）将复杂度从$O(|\mathcal{E}|)$降至$O(K^L |\mathcal{V}|)$。然而，采样策略对性能影响显著：

• **均匀采样**：简单但可能遗漏关键邻居（如高影响力节点）
• **重要性采样**：根据节点度或PageRank权重采样，但计算开销大
• **基于梯度的采样**：如FastGCN使用重要性加权，但方差问题突出

实验数据显示，在Reddit数据集（23万节点）上，GraphSAGE使用25邻居采样可在单卡GPU上训练，而全图GCN需3