图神经网络导论 / Introduction to Graph Neural Networks

图数据（Graph Data）无处不在——从社交网络中的好友关系到分子结构中的原子键，从交通网络的路径规划到知识图谱中的实体关联，这些非欧几里得结构（non-Euclidean structures）承载着复杂的关系信息，却难以被传统深度学习模型有效处理。图神经网络（Graph Neural Networks, GNNs）应运而生，作为专门针对图结构数据的表示学习框架，它通过迭代地聚合邻居信息来学习节点、边乃至整个图的分布式表示，在节点分类、链接预测、图分类等任务上取得了突破性进展。本章将系统性地介绍GNN的研究范畴、历史演进、核心表示方法与通用计算框架，并为读者提供本书的阅读路线图及多格式使用指南。

1.1 研究范畴与历史演进：从图信号处理到深度表示学习

图神经网络的研究范畴可定义为利用神经网络模型对图结构数据进行表示学习与推理的机器学习范式。其核心目标在于学习一个映射函数 $f: \mathcal{G} \rightarrow \mathbb{R}^d$，其中 $\mathcal{G}$ 代表图结构数据（包括节点特征、边结构等），$\mathbb{R}^d$ 是低维连续向量空间，使得在该空间中，图的结构信息与特征信息得以保留，并适用于下游任务（如分类、回归、生成）。这一范畴涵盖了从节点级（node-level）、边级（edge-level）到图级（graph-level）的各种预测问题，以及图生成、图编辑等生成式任务。

GNN的历史演进并非一蹴而就，而是经历了从图信号处理到深度表示学习的范式转变。早期工作可追溯至2005年，Gori等人提出的图神经网络（Graph Neural Network）使用递归神经网络（Recurrent Neural Networks, RNNs）来传播节点信息，其核心思想是通过迭代收敛到一个固定点来表示节点状态。2009年，Scarselli等人进一步系统化了这一框架，提出了图神经网络（GNN）的通用架构，利用循环机制聚合邻居信息，并在化学分子数据集上展示了初步效果。然而，受限于当时深度学习基础设施与优化技术的不足，这些早期方法在计算效率和可扩展性上面临挑战，未能引起广泛关注。

真正的转折点出现在2016年。Kipf与Welling提出的图卷积网络（Graph Convolutional Network, GCN） 将卷积操作从欧几里得空间（如图像）推广到图结构，提出了基于一阶近似的谱图卷积（Spectral Graph Convolution），其简洁的层间传播公式（$\mathbf{H}^{(l+1)} = \sigma(\tilde{\mathbf{D}}^{-1/2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1/2} \mathbf{H}^{(l)} \mathbf{W}^{(l)})$）迅速成为GNN领域的基准模型。同年，Hamilton等人提出的图采样聚合（GraphSAGE） 则从空间角度出发，通过采样邻居并聚合其特征（如均值、LSTM、池化）来实现可扩展的节点表示学习，解决了GCN在大型图上的内存瓶颈。2017年，Veličković等人引入图注意力网络（Graph Attention Network, GAT），将注意力机制（Attention Mechanism）嵌入消息传递过程，为不同邻居分配自适应权重，显著提升了模型对异质邻居的建模能力。

此后，GNN领域进入爆炸式增长阶段。研究方向主要沿着三个轴线拓展：1) 表达能力增强：通过更高阶邻域聚合（如GCN2、GPRGNN）、子图结构编码（如GNN-AK）、图同构测试（如GIN）来提升模型区分能力；2) 可扩展性优化：采用聚类（如Cluster-GCN）、历史嵌入（如GraphSAINT）、分布式训练等技术处理超大规模图（十亿级节点）；3) 任务泛化：将GNN应用于图生成（如GraphRNN）、图翻译（如GTrans）、时空图（如STGCN）、异构图（如HGT）等复杂场景。关键论文时间线（见本章末Mermaid图）清晰地勾勒出这一演进脉络：从2005年的递归框架，到2016年卷积与采样的双轮驱动，再到2017年后注意力机制与多层架构的深化，最终在2020年后涌现出预训练（如GraphBERT）、对比学习（如GraphCL）、神经架构搜索（如AutoGNN）等新范式。

1.2 传统深度学习与图数据的适配挑战

传统深度学习模型（如卷积神经网络CNN、循环神经网络RNN、全连接网络MLP）在图像、文本、语音等欧几里得数据上取得了巨大成功，其成功依赖于数据内在的规则结构与统计平稳性。然而，图数据具有三大根本特性，导致这些模型直接应用时面临严峻挑战：

1. 拓扑不规则性（Topological Irregularity）：图像数据具有规则的网格拓扑（如 $28 \times 28$ 像素），文本序列具有线性的时序拓扑，而图的节点度分布（degree distribution）通常遵循幂律（Power Law），即少数节点拥有大量邻居（枢纽节点），多数节点邻居稀疏。这种不规则性意味着：

• **卷积核无法直接定义**：CNN的卷积核依赖于固定大小的局部感受野（如 $3 \times 3$），但图中节点的邻居数量可变，且邻居间无序。
• **平移等变假设失效**：CNN的平移等变性（translation equivariance）依赖于网格的均匀性，图中不存在全局坐标系统，节点“位置”由拓扑关系定义。
• **池化操作难以设计**：图像池化（如最大池化）依赖于规则的子区域划分，而图的子图划分（如k-核分解）是NP难问题。

2. 规模与动态可变性（Scale and Dynamic Variability）：图的大小（节点数）和结构在不同样本间可能差异巨大。例如，一个分子图可能仅有十几个原子，而社交网络图可能包含数百万用户。传统全连接层要求固定输入维度，无法处理可变尺寸输入；RNN虽能处理变长序列，但序列有自然顺序，而图节点无固有排列（Permutation Invariance），RNN对顺序敏感的特性会导致模型对节点排列产生偏见。

3. 缺乏全局坐标与顺序（Lack of Global Coordinates and Order）：图像中像素的 $(x, y)$ 坐标提供了空间位置信息；文本中词的位置编码（Positional Encoding）提供了序列顺序信息。图中节点没有全局坐标，其“位置”完全由邻接关系定义。这意味着：

• **位置编码缺失**：需要显式设计位置编码（如Laplacian特征向量、随机漫步位置编码）来注入结构信息。
• **排列不变性需求**：理想的GNN应对节点排列保持不变（Permutation Invariant），即对节点重新编号，输出不应改变。传统模型（如MLP）若直接输入邻接矩阵，会因输入顺序变化而输出不同。

案例对比：图像 vs. 图 考虑一个简单的社交网络图，其中节点为用户，边为好友关系。用户特征可能包括年龄、兴趣等。传统CNN若强行将用户特征排列为向量（如按用户ID排序），会丢失拓扑信息：用户A与用户B是好友（边连接），但若在向量中相隔很远，CNN的局部卷积无法捕捉这种关系；且若重新排列用户ID，特征向量完全改变，CNN输出会剧变。而GNN通过消息传递，自然地基于实际连接聚合信息，无论节点如何排列，同一拓扑结构的图应产生相同的节点表示（在相同初始化下）。

1.3 图结构数据的表示：邻接矩阵与特征矩阵

在图深度学习中，图 $\mathcal{G} = (\mathcal{V}, \mathcal{E})$ 通常由节点集 $\mathcal{V}$（$|\mathcal{V}| = N$）和边集 $\mathcal{E}$ 定义。为适配神经网络输入，需将其转换为矩阵形式。最核心的表示是邻接矩阵（Adjacency Matrix） 和特征矩阵（Feature Matrix）。

邻接矩阵 $\mathbf{A} \in \{0,1\}^{N \times N}$ 是描述图拓扑的基础。其定义如下： $$ \mathbf{A}_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{otherwise} \end{cases} $$ 对于无向图，$\mathbf{A}$ 是对称矩阵；有向图则不对称。若边有权重（如社交网络中互动频率），$\mathbf{A}_{ij} \in \mathbb{R}^+$ 表示权重。邻接矩阵可进一步扩展：自环（Self-loop） 常被添加（即 $\mathbf{A}_{ii}=1$），使节点能保留自身信息；对称归一化 $\tilde{\mathbf{A}} = \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$（其中 $\mathbf{D}$ 是度矩阵）用于缓解度数差异导致的数值不稳定，这在GCN中是关键步骤。

特征矩阵 $\mathbf{X} \in \mathbb{R}^{N \times F}$ 存储每个节点的初始特征。$F$ 是特征维度，例如在分子图中，$F$ 可能是原子类型（one-hot编码）、电负性等物理化学属性；在论文引用网络中，$F$ 可能是论文的TF-IDF向量或摘要嵌入。$\mathbf{X}$ 的每一行 $\mathbf{x}_i$ 对应节点 $v_i$ 的特征向量。对于无特征图（如某些社交网络），可初始化 $\mathbf{X}$ 为随机向量或使用结构编码（如节点度）。

联合表示：图 $\mathcal{G}$ 在GNN中通常表示为元组 $(\mathbf{A}, \mathbf{X})$。有时还需边特征矩阵 $\mathbf{E} \in \mathbb{R}^{|\mathcal{E}| \times F_e}$，但多数基础GNN仅使用节点特征。值得注意的是，$\mathbf{A}$ 和 $\mathbf{X}$ 共同定义了图信号（Graph Signal）——即定义在节点上的特征向量场。图卷积操作可视为对图信号的滤波（filtering），类似于CNN对图像像素信号的滤波。

示例：Cora引文网络 Cora数据集包含2708篇机器学习论文，每条边表示引用关系。邻接矩阵 $\mathbf{A}$ 大小为 $2708 \times 2708$，是稀疏的（平均度约7）；特征矩阵 $\mathbf{X}$ 大小为 $2708 \times 1433$，每篇论文的特征是其词袋（bag-of-words）表示（1433个词是否存在）。节点标签是7个研究领域。GNN任务是根据论文内容和引用结构预测其领域。

扩展表示：

• **超图（Hypergraph）**：边可连接多于两个节点，用超邻接矩阵 $\mathbf{H} \in \{0,1\}^{N \times |\mathcal{E}|}$ 表示，$\mathbf{H}_{i e}=1$ 若节点 $i$ 属于超边 $e$。
• **多图（Multigraph）**：允许多重边，邻接矩阵可为整数（边数）。
• **动态图（Dynamic Graph）**：随时间演化，需用时序邻接矩阵序列 $\mathbf{A}^{(1)}, \mathbf{A}^{(2)}, \dots$ 表示。

1.4 GNN的通用框架：消息传递、聚合与更新

2017年，Gilmer等人提出的消息传递神经网络（Message Passing Neural Network, MPNN） 框架统一了当时多种GNN模型（如GCN、GraphSAGE、GAT）。该框架将GNN层定义为在节点间传递消息的迭代过程，包含三个关键函数：消息函数（Message Function）、聚合函数（Aggregation Function） 和更新函数（Update Function）。这一抽象使得不同GNN变体可视为MPNN的特例。

设 $h_i^{(l)}$ 为节点 $v_i$ 在第 $l$ 层的隐藏表示。第 $l+1$ 层的计算分为两步：

1. 消息传递（Message Passing）：对每条边 $(v_i, v_j) \in \mathcal{E}$，计算从邻居 $v_j$ 发送到中心节点 $v_i$ 的消息 $m_{ij}^{(l+1)}$： $$ m_{ij}^{(l+1)} = \text{MSG}^{(l)}(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{e}_{ij}) $$ 其中 $\text{MSG}^{(l)}$ 是可学习的消息函数（通常为MLP），$\mathbf{e}_{ij}$ 是边特征（可选）。若边无特征，简化为 $m_{ij}^{(l+1)} = \text{MSG}^{(l)}(\mathbf{h}_j^{(l)})$。消息函数决定了邻居信息如何编码。

2. 聚合（Aggregation）：中心节点 $v_i$ 收集所有邻居发来的消息，并聚合成单一消息 $M_i^{(l+1)}$： $$ M_i^{(l+1)} = \text{AGG}^{(l)}(\{ m_{ij}^{(l+1)} \mid j \in \mathcal{N}_i \}) $$ 其中 $\mathcal{N}_i$ 是 $v_i$ 的邻居集合（通常包含自环，即 $i \in \mathcal{N}_i$），$\text{AGG}^{(l)}$ 是聚合函数（如求和、均值、最大值）。聚合函数需满足置换不变性（permutation invariant），即对邻居顺序不敏感。这是GNN满足图排列不变性的关键。

3. 更新（Update）：中心节点结合聚合消息与自身当前表示，更新为新表示： $$ \mathbf{h}_i^{(l+1)} = \text{UPDATE}^{(l)}(M_i^{(l+1)}, \mathbf{h}_i^{(l)}) $$ 更新函数通常为MLP，也可设计为门控机制（如GRU）以控制信息流。若使用残差连接，可加入 $\mathbf{h}_i^{(l)}$ 到更新后。

MPNN伪代码： ``` for layer l in 1..L: for each node i: for each neighbor j in N(i): m_ij = MSG_l(h_i^(l-1), h_j^(l-1), e_ij) # 消息计算 M_i = AGG_l({m_ij for j in N(i)}) # 聚合 h_i^(l) = UPDATE_l(M_i, h_i^(l-1)) # 更新 ```

MPNN与经典GNN的对应：

• **GCN**：MSG为线性变换 $(\mathbf{W} \mathbf{h}_j^{(l)})$，AGG为带归一化的求和（$\sum_{j \in \mathcal{N}_i} \tilde{\mathbf{A}}_{ij} \cdot$），UPDATE为非线性激活 $\sigma(\cdot)$。其聚合步骤可写为 $\mathbf{H}^{(l+1)} = \sigma(\tilde{\mathbf{A}} \mathbf{H}^{(l)} \mathbf{W}^{(l)})$。
• **GraphSAGE**：MSG为线性变换 $(\mathbf{W} \mathbf{h}_j^{(l)})$，AGG可选均值、LSTM或池化，UPDATE为非线性激活。
• **GAT**：MSG为 $\alpha_{ij} \mathbf{W} \mathbf{h}_j^{(l)}$，其中注意力系数 $\alpha_{ij} = \frac{\exp(\text{LeakyReLU}(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_i^{(l)} \| \mathbf{W}\mathbf{h}_j^{(l)}]))}{\sum_{k \in \mathcal{N}_i} \exp(\text{LeakyReLU}(\mathbf{a}^\top [\mathbf{W}\mathbf{h}_i^{(l)} \| \mathbf{W}\mathbf{h}_k^{(l)}]))}$，AGG为加权和，UPDATE为非线性激活。

MPNN的表达能力：理论上，MPNN在满足适当条件下是 Weisfeiler-Lehman (WL) 测试的图同构检验能力的上界。GIN（Graph Isomorphism Network）通过设计 $\text{AGG}$ 为多集（multiset）上的可学习求和，并配合 $\text{UPDATE}$ 为MLP，达到了与WL测试同等的表达能力，是MPNN框架中最强的模型之一。

超越MPNN的扩展：部分GNN模型超越了局部消息传递，如：

• **子图GNN**：在子图上运行MPNN，再聚合子图表示（如GNN-AK）。
• **全局注意力GNN**：使用Transformer-style全连接注意力（如GTN、Graphormer），计算复杂度高但能捕获长程依赖。
• **虚拟节点（Virtual Node）**：添加一个全局节点连接所有节点，促进跨节点信息交流。

1.5 本书章节逻辑与三件套格式使用指南

本书共15章，旨在系统性地构建图神经网络的深度知识体系，从基础理论到前沿应用，覆盖表示学习、模型架构、训练策略及跨领域扩展。章节设计遵循“基础→核心→高级→应用” 的螺旋上升逻辑：

• **第1-4章（基础与核心）**：本章（第1章）奠定基础，定义范畴、表示与框架；第2章深入数学基础（图信号处理、谱方法）；第3章详解经典模型（GCN、GraphSAGE、GAT）；第4章讨论训练技术（过平滑、过挤压、归一化）。
• **第5-8章（高级架构）**：第5章超图与异构图GNN；第6章图Transformer与注意力机制；第7章几何深度学习（流形、辛几何）；第8章自监督与对比学习。
• **第9-12章（扩展任务）**：第9章图生成模型；第10章时空图网络；第11章图解释性与公平性；第12章图神经网络的理论边界。
• **第13-15章（应用与未来）**：第13章生物与化学应用；第14章社会科学与推荐系统；第15章挑战、未来方向与伦理考量。

三件套出版理念与使用指南： 本书创新性地同