图神经网络（GNN）全面指：从基础到高级应用

引言

在数据爆炸的时代，传统深度学习模型如CNN和RNN在处理结构化数据（如图像和序列）上取得了巨大成功，但现实世界中的许多数据都具有图结构（Graph Structure），例如社交网络、分子结构、知识图谱、交通网络等。这些数据是非欧几里德的（Non-Euclidean），节点之间存在复杂的拓扑关系，无法直接用网格或序列表示。这就是**图神经网络（Graph Neural Networks, GNN）**登场的原因。

GNN 通过模拟节点间的消息传递机制，捕捉图的局部和全局结构，实现对图数据的表示学习。它已在推荐系统、药物发现、蛋白质折叠预测等领域大放异彩。本文将从基础概念入手，逐步深入GNN的核心原理、经典模型、实现技巧和实际应用，帮助你全面掌握这一技术。无论你是初学者还是有经验的从业者，这篇指南都能提供实用价值。

图数据基础

图的定义与表示

图 $ G = (V, E) $ 由节点集 $ V $（Vertices）和边集 $ E $（Edges）组成：

节点（Nodes）：实体，如用户、原子。
边（Edges）：关系，如友谊、化学键。
类型：
- 无向图：边无方向（e.g., 社交网络）。
- 有向图：边有方向（e.g., 网页链接）。
- 加权图：边有权重 $ w_{uv} $（e.g., 相似度分数）。
- 异构图：节点/边有多种类型（e.g., 知识图谱）。

图的常见表示方法：

邻接矩阵（Adjacency Matrix） $ A \in \mathbb{R}^{|V| \times |V|} $：$ A_{uv} = 1 $ 如果存在边 $ (u, v) $，否则为0。适合小图，但空间复杂度 $ O(|V|^2) $。
边列表（Edge List）：稀疏表示，如 $[ (u_1, v_1), (u_2, v_2), \dots ] $，适合大图。
度矩阵（Degree Matrix） $ D $，对角线 $ D_{ii} = \sum_j A_{ij} $（节点i的度）。
拉普拉斯矩阵（Laplacian Matrix） $ L = D - A $，用于谱分析：它是半正定的，特征分解 $ L = U \Lambda U^T $，其中 $ U $ 是傅里叶基。

图任务类型

GNN 针对不同粒度的数据设计：

节点级任务：节点分类（e.g., 预测论文类别）、节点回归（e.g., 预测节点影响力）。
边级任务：链接预测（e.g., 推荐朋友）。
图级任务：图分类（e.g., 判断分子是否毒性）、图回归（e.g., 预测分子能量）。

数据集示例：

节点分类：Cora（论文引用网络，2708节点，5429边）。
图分类：MUTAG（188个分子图）。

GNN 核心原理

GNN 的本质是**消息传递神经网络（Message Passing Neural Network, MPNN）**框架，由Scarselli等人在2009年提出。它通过多层迭代，让每个节点从邻居聚合信息，逐步捕捉多跳（multi-hop）依赖。

消息传递机制

假设初始节点特征 $ h_v^{(0)} = x_v $（节点v的输入特征）。在第 $ k $ 层：

消息生成（Message Generation）：对于每条边 $ (u, v) $，生成消息 $ m_{uv}^{(k)} = f(h_u^{(k-1)}, h_v^{(k-1)}, e_{uv}) $，其中 $ f $ 是可学习函数（如MLP），$ e_{uv} $ 是边特征。
聚合（Aggregation）：节点v聚合邻居消息 $ \tilde{h}v^{(k)} = \text{AGGREGATE}({ m{uv}^{(k)} : u \in \mathcal{N}(v) }) $。
- 常见AGG：Sum（求和）、Mean（平均）、Max（最大）、Attention（注意力）。
更新（Update）：$ h_v^{(k)} = \text{UPDATE}(\tilde{h}_v^{(k)}, h_v^{(k-1)}) $，UPDATE 如GRU、MLP + ReLU。
读出（Readout）（仅图级任务）：全局池化 $ \hat{y} = \text{READOUT}({ h_v^{(K)} : v \in V }) $，如mean pooling或sum。

数学上，整个过程可并行化，使用稀疏矩阵运算。关键假设：同质性（Homophily），相连节点相似。

谱方法 vs 空间方法

谱方法（Spectral GNN）：基于图信号处理（Graph Signal Processing）。图卷积定义为 $ g_\theta * x = U g_\theta(\Lambda) U^T x $，其中 $ g_\theta(\lambda) $ 是滤波器（e.g., 多项式）。优点：理论基础强；缺点：计算 $ U $ 成本高（O(|V|^3)）。
- 示例：ChebNet（2017），用Chebyshev多项式近似滤波器，K阶多项式只需O(K)参数。
空间方法（Spatial GNN）：直接在节点邻域操作，更高效、可扩展。主流模型如GCN、GAT均属此类。

经典GNN模型详解

Graph Convolutional Network (GCN)

Kipf & Welling (2017) 的开创性工作，将CNN推广到图。

层公式：$ H^{(l+1)} = \sigma( \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} H^{(l)} W^{(l)} ) $。
- $ \hat{A} = A + I $（加自环，包含自身信息）。
- $ \hat{D} $ 是 $ \hat{A} $ 的度矩阵。
- 解释：$ \hat{D}^{-1/2} \hat{A} \hat{D}^{-1/2} $ 是归一化邻接矩阵，第一阶谱卷积近似（localized filter）。
推导简述：从谱卷积 $ g_\theta * x = U (g_\theta(\Lambda) \odot (U^T x)) U^T $ 简化为一阶Taylor展开，假设 $ g_\theta(\Lambda) = \sum_{k=0}^K T_k(\tilde{L}) \theta_k $（$ \tilde{L} = 2\lambda_{\max}^{-1} L - I $）。
优点：简单、参数共享；缺点：假设1-hop邻居同质，深层易过平滑。
应用：半监督节点分类，在Cora上准确率达81.5%。

Graph Attention Network (GAT)

Veličković等 (2018) 引入注意力机制，提升表达力。

注意力计算：$ \alpha_{vu} = \text{softmax}_u ( \text{LeakyReLU}( \mathbf{a}^T [ \mathbf{W} \mathbf{h}_v | \mathbf{W} \mathbf{h}_u ] ) ) $。
- $ | $ 是拼接，$ \mathbf{a} $ 是注意力向量。
- 动态权重，避免固定均值聚合。
更新：$ \mathbf{h}v’ = \sigma( \sum{u \in \mathcal{N}(v)} \alpha_{vu} \mathbf{W} \mathbf{h}_u ) $。
多头注意力：K个头并行，平均或拼接输出，提升稳定性（类似Transformer）。
优点：解释性强（可视化注意力权重）；缺点：O(|E| d^2)复杂度（d为特征维）。
变体：GATv2 (2021)，修复静态注意力问题。

GraphSAGE

Hamilton等 (2017) 针对大图设计，支持归纳学习。

采样聚合：随机采样固定大小的k-hop邻居，避免全图计算。
聚合函数：
- Mean：$ \text{AGG} = \text{mean}({ \mathbf{h}_u : u \in \text{sample}(\mathcal{N}(v)) }) $。
- Pool：每个邻居用MLP池化后sum。
- LSTM：顺序处理邻居消息。
更新：$ \mathbf{h}_v^{(k)} = \sigma( \mathbf{W}^{(k)} \cdot \text{CONCAT}( \mathbf{h}_v^{(k-1)}, \text{AGG} ) ) $。
优点：可扩展到百万节点图；缺点：采样引入方差。
应用：Pinterest的引脚推荐。

Graph Isomorphism Network (GIN)

Xu等 (2019) 提升图级表示的区分力。

公式：$ \mathbf{h}_v^{(k)} = \text{MLP}^{(k)} ( (1 + \epsilon^{(k)}) \mathbf{h}v^{(k-1)} + \sum{u \in \mathcal{N}(v)} \mathbf{h}_u^{(k-1)} ) $。
- $ \epsilon^{(k)} $ 可学习，控制自环权重。
- 读出：$ \mathbf{h}_G = \text{MLP}( \sum_v \mathbf{h}_v^{(K)} ) $。
理论：等价于Weisfeiler-Lehman (WL) 图同构测试，能区分更多非同构图。
优点：SOTA于图分类基准（如OGB）。