第1章：图神经网络导论 / Introduction to Graph Neural Networks

图结构数据（graph-structured data）无处不在——从社交网络中的用户关系到万维网的超链接，从蛋白质相互作用网络到知识图谱中的实体关联，再到分子化学中的原子键合。传统深度学习模型（如卷积神经网络、循环神经网络）依赖于欧几里得空间中的规则网格或序列结构，而图数据则呈现非欧几里得、不规则、拓扑关系复杂的特性。图神经网络（Graph Neural Networks, GNNs）的核心问题，正是为这种离散、非结构化的图数据学习连续、低维、且富含结构语义的节点、边或整个图的向量表示（vector representations），使得下游的机器学习任务（如分类、聚类、预测）能够高效进行。 这一表示学习过程，本质上是在将图的结构信息与节点/边的特征信息编码到一个共享的嵌入空间中。The core problem of Graph Neural Networks (GNNs) is to learn continuous, low-dimensional, and semantically rich vector representations for nodes, edges, or entire graphs from discrete, unstructured graph data, enabling efficient downstream machine learning tasks such as classification, clustering, and prediction. This representation learning process fundamentally encodes both the structural information of the graph and the feature information of nodes/edges into a shared embedding space.

**1.1 核心问题定义与形式化**

给定一个图 $ \mathcal{G} = (\mathcal{V}, \mathcal{E}) $，其中 $ \mathcal{V} $ 是节点集合，$ |\mathcal{V}| = N $；$ \mathcal{E} \subseteq \mathcal{V} \times \mathcal{V} $ 是边集合。每个节点 $ v_i \in \mathcal{V} $ 关联一个特征向量 $ \mathbf{x}_i \in \mathbb{R}^d $，图的整体结构由邻接矩阵 $ \mathbf{A} \in \{0,1\}^{N \times N} $ 描述（对于加权图，$ \mathbf{A} \in \mathbb{R}^{N \times N} $）。GNN的目标是学习一个映射函数 $ f_\theta: \mathcal{G} \rightarrow \mathbb{R}^p $，该函数能够为每个节点（节点级任务）、每条边（边级任务）或整个图（图级任务）生成一个任务相关的表示向量（representation vector）$ \mathbf{h}_i, \mathbf{h}_{(i,j)} $ 或 $ \mathbf{h}_\mathcal{G} $。这个映射 $ f_\theta $ 必须满足以下关键属性： 1. 置换等价性（Permutation Equivariance）：节点的表示输出顺序应与输入节点顺序一致，且不依赖于节点在输入中的具体索引顺序。形式化地，若 $ \pi $ 是节点的一个置换，则 $ f_\theta(\pi(\mathcal{G})) = \pi(f_\theta(\mathcal{G})) $。这确保了模型对图节点的任意排列保持不变性，是GNN区别于其他模型的根本设计约束。 2. 结构敏感性（Structural Sensitivity）：不同拓扑位置（如中心节点与边缘节点）或不同连接模式的节点应获得不同的表示。模型必须能够捕捉局部图结构（如一阶/多阶邻居）和全局图结构（如图的直径、社区结构）。 3. 特征融合（Feature Fusion）：表示必须同时编码节点自身的属性特征（$ \mathbf{x}_i $）和其所在的图上下文结构信息（通过邻居聚合获得）。

因此，GNN可以被视为一种结构感知的嵌入函数（structure-aware embedding function），它通过迭代地聚合邻居信息来构建每个节点的上下文感知表示。其通用计算范式可抽象为： $$ \mathbf{h}_i^{(l+1)} = \phi^{(l)} \left( \mathbf{h}_i^{(l)}, \bigoplus_{j \in \mathcal{N}(i)} \psi^{(l)} (\mathbf{h}_j^{(l)}, \mathbf{e}_{ji}) \right) $$ 其中，$ \mathbf{h}_i^{(l)} $ 是节点 $ i $ 在第 $ l $ 层的表示，$ \mathcal{N}(i) $ 是其邻居集合，$ \mathbf{e}_{ji} $ 是边 $ (j,i) $ 的特征（若有），$ \psi^{(l)} $ 是消息函数（message function），$ \bigoplus $ 是置换不变的聚合函数（如求和、均值、最大值），$ \phi^{(l)} $ 是更新函数（update function）。这一消息传递（Message Passing）框架构成了几乎所有现代GNN的基石。

**1.2 历史演进：从谱方法到深度学习范式**

GNN的发展并非一蹴而就，而是经历了从图信号处理、谱图理论到深度学习范式的深刻演变。

**1.2.1 早期谱方法与图拉普拉斯**

在深度学习兴起之前，图上的表示学习主要根植于谱图理论（Spectral Graph Theory） 和图信号处理（Graph Signal Processing, GSP）。核心工具是图拉普拉斯矩阵（Graph Laplacian Matrix） $ \mathbf{L} = \mathbf{D} - \mathbf{A} $，其中 $ \mathbf{D} $ 是度矩阵。其归一化形式 $ \mathbf{L}_{sym} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} $ 是对称半正定的，其特征向量构成图上的“傅里叶基”。谱聚类（Spectral Clustering） 算法利用拉普拉斯矩阵的最优非平凡特征向量（对应最小特征值）对节点进行嵌入，再在嵌入空间中进行K-means聚类，这本质上是一种无监督的图表示学习方法。然而，谱方法面临计算瓶颈：对大规模图进行完整的特征分解复杂度为 $ O(N^3) $，且得到的嵌入是全局的、非参数化的，难以与深度学习端到端训练框架结合。

**1.2.2 开创性工作：GNN的诞生**

2005年，Gori等人提出的图神经网络（Graph Neural Network） 首次将神经网络应用于图结构数据，使用递归神经网络（RNN）沿图结构传播信息以生成节点表示。2009年，Scarselli等人进一步 formalized GNN 框架，使用固定点迭代（fixed-point iteration）来求解节点表示，但其训练依赖于梯度下降求解非线性方程组，计算效率低且不稳定，未能引起广泛关注。

真正的转折点出现在深度学习与谱图理论的交叉。2013年，Bruna等人首次将卷积运算引入图域，提出了谱卷积（Spectral Convolution）。其核心思想是在图傅里叶域定义卷积：$ g_\theta * \mathbf{x} = \mathbf{U} g_\theta (\Lambda) \mathbf{U}^T \mathbf{x} $，其中 $ \mathbf{U} $ 是拉普拉斯矩阵的特征向量矩阵，$ \Lambda $ 是特征值对角矩阵，$ g_\theta $ 是参数化的滤波器。这一方法在理论上优美，但存在致命缺陷：$ \mathbf{U} $ 依赖于图结构，计算成本高昂且无法泛化到未见过的图（因为新图的 $ \mathbf{U} $ 不同）。

**1.2.3 简化与实用化：ChebNet与GCN**

2016年，Defferrard等人提出ChebNet，使用切比雪夫多项式（Chebyshev Polynomials） 来近似谱滤波器 $ g_\theta (\Lambda) $，将卷积运算限制在 $ K $ 阶邻域内： $$ g_\theta * \mathbf{x} \approx \sum_{k=0}^{K-1} \theta_k T_k (\tilde{\mathbf{L}}) \mathbf{x} $$ 其中 $ T_k $ 是切比雪夫多项式，$ \tilde{\mathbf{L}} = \frac{2}{\lambda_{max}} \mathbf{L} - \mathbf{I} $ 是缩放后的拉普拉斯矩阵。ChebNet的关键贡献是将谱卷积的计算复杂度从 $ O(N^2) $ 降低到 $ O(K|\mathcal{E}|) $，并实现了局部化（localization）——卷积仅依赖于 $ K $ 跳邻居。这为在大型图上应用卷积操作铺平了道路。

2017年，Kipf与Welling在ChebNet基础上做出了一个极具影响力的简化：进一步限制 $ K=1 $，并假设 $ \lambda_{max} \approx 2 $，使得 $ \tilde{\mathbf{L}} \approx \mathbf{L} - \mathbf{I} $。最终，他们提出的图卷积网络（Graph Convolutional Network, 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}} $ 是 $ \tilde{\mathbf{A}} $ 的度矩阵，$ \mathbf{W}^{(l)} $ 是可学习权重矩阵，$ \sigma $ 是非线性激活函数。GCN的简洁性、高效性和在节点分类任务上的显著效果，使其成为GNN领域的“Hello World”模型，引发了研究热潮。然而，GCN的局限性也随之暴露：其聚合方式（对称归一化的邻接矩阵）是固定的，无法学习聚合权重；且堆叠多层会导致过平滑（over-smoothing）——所有节点表示收敛到同一向量。

**1.2.4 消息传递框架的统一**

在GCN之后，大量变体涌现，如图注意力网络（GAT）、GraphSAGE、GIN等。它们虽然设计各异，但都遵循一个共同的计算模式：消息传递（Message Passing） 或邻域聚合（Neighborhood Aggregation）。Gilmer等人于2017年正式提出消息传递神经网络（Message Passing Neural Networks, MPNNs） 框架，将此前所有GNN模型统一为消息传递的抽象范式，如上文公式所示。这一框架的提出具有里程碑意义： 1. 解耦设计：清晰分离了消息生成、聚合和更新三个步骤，为模型设计提供了系统化的思路。 2. 通用性：通过替换 $ \psi, \bigoplus, \phi $ 的不同实例，可以复现GCN（求和聚合+线性变换）、GAT（注意力加权求和+LeakyReLU）、GraphSAGE（均值/最大值池化）等众多模型。 3. 扩展性：为引入更复杂的消息函数（如考虑边特征、边方向）和聚合函数（如Set2Set、Multi-set attention）提供了自然接口。

自此，GNN的研究从“提出新模型”阶段，逐渐进入“理解其表达能力”、“提升其可扩展性”、“增强其鲁棒性”和“拓展其应用边界”的深化阶段。

**1.3 GNN的驱动作用：三大核心应用领域**

GNN的独特能力使其在众多需要关系推理的领域成为关键技术。

**1.3.1 社交网络与推荐系统**

社交网络天然是图结构：用户是节点，好友关系/关注关系是边。GNN在此领域的核心价值是利用关系信息增强用户/物品表示。

• **用户画像与影响力预测**：传统方法仅基于用户自身属性。GNN通过聚合邻居（朋友）的特征，可以捕捉“近朱者赤”效应。例如，一个用户的兴趣可能与其好友高度相关。模型如**GraphSAGE**通过采样和聚合邻居，可高效处理百万级用户网络。
• **社交推荐**：在电商或内容平台，用户-物品交互形成二部图。GNN（如**LightGCN**，其简化了GCN，仅保留邻域聚合，去掉特征变换和非线性，被证明已足够有效）可以同时学习用户和物品的嵌入，捕捉协同过滤信号（“喜欢物品A的用户也喜欢物品B”）和社交信号（“好友喜欢的物品”），显著提升推荐准确度和多样性。Pinterest的PinSage系统是工业界大规模GNN推荐的先驱，使用基于随机游走的邻居采样和高效的MapReduce训练，服务数亿用户。

**1.3.2 知识图谱与关系推理**

知识图谱（Knowledge Graph, KG）由实体（节点）和关系（边，具有类型）构成。核心任务是链接预测（预测缺失的实体-关系三元组） 和实体分类。

• ** translational Embedding Models (e.g., TransE) vs. GNNs**：早期方法如TransE将实体和关系嵌入到同一空间，要求 $ \mathbf{h} + \mathbf{r} \approx \mathbf{t} $。它们简单高效，但难以建模复杂关系（如1-to-N, N-to-1）。GNN（如**R-GCN**）通过为每种关系类型设计不同的权重矩阵，在消息传递中显式区分关系，能更好地捕捉多跳路径上的复杂依赖。例如，要推断“某药物的副作用”，可能需要沿着“药物-靶点-疾病-症状”等多跳关系路径推理，GNN能通过多层传播隐式地实现这种多跳推理。
• **问答系统（QA）**：在KBQA中，问题被解析为子图，GNN用于编码该子图并匹配答案实体。GNN的结构匹配能力使其优于仅基于文本的模型。

**1.3.3 分子化学与药物发现**

分子可自然表示为图：原子是节点，化学键是边，节点特征包括原子类型、电荷等，边特征包括键类型、距离等。GNN在此领域取得了革命性进展，因为分子的许多关键性质（如毒性、溶解度、能隙）由其图结构直接决定。

• **性质预测（Property Prediction）**：给定分子图，预测其量子化学性质（如QM9数据集上的HOMO-LUMO能隙）或生物活性。GNN（如**MPNN**、**DimeNet**）通过精心设计消息函数（考虑键角、距离等几何信息）来学习分子表示。例如，DimeNet引入了方向性信息，能更好地捕捉三维空间结构，在QM9上达到了化学精度（误差 < 0.1 kcal/mol）。
• **药物-靶点相互作用（DTI）预测**：将药物分子图和蛋白质图（序列可视为路径图）分别用GNN编码，再通过交互网络预测结合亲和力。这比仅用分子指纹（fingerprint）的方法更能利用结构信息。
• **分子生成（Molecular Generation）**：GNN作为解码器，从潜在向量逐节点、逐边地生成新分子图，用于设计具有特定性质的新药候选物。

这些领域共同的特点是：数据本质上是图，且任务的成功高度依赖于对图结构（拓扑关系）的有效建模。GNN通过其消息传递机制，完美契合了这一需求。

**1.4 基本设计模式深度剖析：消息传递、聚合与更新**

如前所述，消息传递是GNN的通用计算引擎。我们将其分解为三个核心操作，并深入分析其设计空间与影响。

**1.4.1 消息函数（Message Function） $ \psi^{(l)} $**

该函数定义了如何从源节点 $ j $ 及其连接边 $ (j,i) $ 生成发送给目标节点 $ i $ 的“消息”。

• **最简单的形式**：$ m_{j\to i} = \mathbf{h}_j^{(l)} $，即仅传递源节点的当前表示。这是GCN的做法。
• **考虑边特征**：$ m_{j\to i} = \psi(\mathbf{h}_j^{(l)}, \mathbf{e}_{ji}) $。例如，在分子图中，边特征（键类型）对消息至关重要。一种常见实现是：$ m_{j\to i} = \mathbf{W}_e \mathbf{e}_{ji} + \mathbf{W}_v \mathbf{h}_j^{(l)} $，将节点和边特征线性变换后拼接或相加。
• **考虑方向性**：在有向图中，$ m_{j\to i} $ 可能与 $ m_{i\to j} $ 不同。可使用不同的权重矩阵或引入方向编码。
• **高阶消息**：不局限于一阶邻居，可设计函数聚合多跳路径上的信息，但计算成本增加。

**1.4.2 聚合函数（Aggregation Function） $ \bigoplus $**

该函数将目标节点 $ i $ 的所有入边消息 $ \{ m_{j\to i} \mid j \in \mathcal{N}(i) \} $ 聚合成一个固定大小的向量。置换不变性要求聚合函数本身必须是对称的（symmetric）。

• **求和（Sum）**：$ \mathbf{m}_i = \sum_{j \in \mathcal{N}(i)} m_{j\to i} $。这是最常用且理论性质好的选择，GCN、MPNN默认使用。它对多集（multi-set）具有置换不变性，且当消息是独立同分布时，求和近似于期望，统计性质稳健。
• **均值（Mean）**：$ \mathbf{m}_i = \frac{1}{|\mathcal{N}(i)|} \sum_{j \in \mathcal{N}(i)} m_{j\to i} $。对度大的节点进行归一化，可能有助于稳定训练，但可能稀释重要邻居的信号。
• **最大值（