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

图神经网络：算法原理与实践

第 1 章：图神经网络导论

图（Graph）是一种古老而强大的数据结构，它用节点（Node）和边（Edge）来描述实体之间的关系。从数学角度看，图论的历史可以追溯到欧拉在1736年发表的"哥尼斯堡七桥问题"，这标志着图论作为一门独立数学分支的诞生。然而，真正让图数据结构焕发新生的，是21世纪以来深度学习技术的蓬勃发展。图神经网络（Graph Neural Network，简称GNN）作为深度学习与图论结合的产物，正在变革性地改变我们处理关系数据的方式。

1.1 图数据：现实世界的通用表示

在深入讨论图神经网络之前，我们需要首先理解图数据为何如此重要。图之所以能够成为描述现实世界的通用语言，根本原因在于：现实世界中大量的问题本质上都是关系问题，而图正是关系结构最自然的数学表示。

1.1.1 图的基本定义与数学表示

形式上，一个图 $G$ 可以定义为一个二元组 $G = (V, E)$，其中 $V$ 表示节点集合，$E$ 表示边集合。对于有向图，$E \subseteq V \times V$；对于无向图，$E \subseteq \{\{u, v\} : u, v \in V, u \neq v\}$。每个节点 $v_i \in V$ 可以关联一组特征 $\mathbf{x}_i$，每条边 $(v_i, v_j) \in E$ 也可以关联特征 $\mathbf{e}_{ij}$。

在实际应用中，我们通常用邻接矩阵（Adjacency Matrix）来表示图的结构。对于包含 $n$ 个节点的图，其邻接矩阵 $\mathbf{A} \in \mathbb{R}^{n \times n}$ 定义为：

$$ \mathbf{A}_{ij} = \begin{cases} 1 & \text{if } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases} $$

邻接矩阵是图数据处理中最基础也最重要的数据结构之一。许多图神经网络算法都基于邻接矩阵进行设计。

1.1.2 社交网络：关系的艺术

社交网络是图数据最直观的应用场景之一。在微博、微信、LinkedIn、Facebook等平台上，用户之间的关注、好友、互动关系都可以自然地建模为图结构。节点代表用户，边代表社交关系（关注、好友、点赞、转发等）。

以Twitter为例，其社交图谱包含数亿用户和数百亿条关系边。这种规模的图数据带来了独特的挑战：传统的深度学习方法难以直接处理，因为数据不再是独立的同分布（i.i.d.）样本，而是存在复杂的依赖关系。

社交网络分析中的典型任务包括：

节点分类（Node Classification）是预测图中节点属性的基础任务。例如，在Twitter上预测用户是否为机器人账户，或者预测用户的兴趣标签。这涉及到利用节点自身的特征以及其邻居节点的信息来进行推断。经典的社交网络分析算法如标签传播（Label Propagation）已经在这类任务上有所应用，而图神经网络则能更深入地捕获多跳邻居的信息。

链接预测（Link Prediction）用于预测两个节点之间是否存在某种关系。在社交网络中，这可以应用于"你可能认识的人"推荐、好友推荐等场景。从图神经网络的角度看，链接预测可以通过学习节点的低维嵌入表示，然后计算节点对之间嵌入的相似度来实现。

社区检测（Community Detection）旨在发现网络中紧密连接的节点群体。社交网络中的社区往往对应着真实世界的社交圈、兴趣群体或组织机构。图神经网络通过端到端的方式学习社区划分，比传统的基于模块度优化的方法更加灵活。

1.1.3 推荐系统：从用户-物品交互中学习

推荐系统是图神经网络的另一个重要应用领域。在电子商务平台（如亚马逊、淘宝）、内容平台（如抖音、B站）和服务平台（如美团、大众点评）上，用户与物品的交互行为天然形成了一张二分图（Bi-partite Graph）：一侧是用户节点，另一侧是物品节点，边表示交互行为（购买、点击、收藏、评分等）。

传统推荐算法如协同过滤（Collaborative Filtering）虽然有效，但面临着稀疏性问题和冷启动问题。当用户-物品交互矩阵非常稀疏时，学习有效的用户和物品表示变得困难。对于新用户或新物品，由于缺乏历史交互数据，协同过滤难以给出准确的推荐。

图神经网络为解决这些问题提供了新的思路。通过将用户-物品交互建模为图结构，GNN能够：

聚合高阶邻居信息——不仅考虑用户直接交互过的物品，还能通过多跳邻居捕获用户的间接偏好。例如，用户A购买过物品X，物品X被与用户A有相似偏好的用户B也购买过，那么物品X可能也会被推荐给用户B。这种高阶协同信号通过图上的消息传递机制得以有效捕获。

利用图结构增强表示学习——用户和物品的嵌入表示不仅取决于其自身的属性和直接交互，还受到图中其他相关节点的影响。这种结构感知的表示学习使得推荐系统能够更好地处理稀疏性问题和冷启动问题。

阿里巴巴提出的GRAPE（Graph Neural Networks for Recommendation）系统和 Pinterest 开发的 PinSage 是将图神经网络应用于推荐系统的典型案例。PinSage 在 Pinterest 的数十亿图片推荐场景中取得了显著效果，将用户参与度提升了约30%。

1.1.4 生物分子：图结构的天然领域

生物分子研究是图神经网络最具潜力的应用领域之一，原因很简单：分子本质上就是图结构。在分子图中，节点代表原子，边代表化学键。原子的属性（如元素类型、电负性、价电子数等）可以作为节点特征，键的属性（如键类型、键长、是否芳香环等）可以作为边特征。

药物发现是图神经网络在生物医药领域最令人振奋的应用。传统的新药研发周期长达10-15年，成本超过10亿美元。其中一个关键环节是预测分子属性（如溶解度、毒性、与其他分子的相互作用等），以筛选有潜力的候选药物。

Graph Convolutional Networks（GCN）和后续的图神经网络模型在分子属性预测任务上取得了state-of-the-art的结果。例如，在MoleculeNet基准数据集上，基于图神经网络的模型在多个任务上超越了传统的分子指纹（Molecular Fingerprint）方法。

分子生成是另一个活跃的研究方向。使用变分自编码器（VAE）或生成对抗网络（GAN）与图神经网络结合，可以从零开始生成具有特定属性的新分子结构。这种方法在设计新型药物分子、新材料等领域有重要价值。

蛋白质结构预测是2020年以来最引人注目的突破之一。DeepMind开发的AlphaFold2在蛋白质结构预测问题上取得了接近实验精度的结果。虽然AlphaFold2的核心架构是注意力机制而非传统的图卷积，但其本质上也利用了蛋白质残基之间的空间关系，这与图神经网络的思想一脉相承。

1.1.5 交通流量预测：时空图神经网络

交通流量预测是智慧城市建设的核心问题之一。在现代城市中，交通网络涵盖了道路、立交桥、地铁、公交等多个子系统，而车辆、行人、乘客在网络中的流动构成了复杂的时空数据。

交通网络天然适合用时空图（Spatio-Temporal Graph）来表示。空间维度上，道路网络是一个图结构，交叉口是节点，道路是边。时间维度上，交通状态随时间动态变化。因此，交通预测问题通常建模为：在给定历史交通状态序列的条件下，预测未来的交通状态。

形式化地，假设我们有 $n$ 个传感器布置在交通网络上，每个传感器在 $t$ 时刻观测到的交通状态（如车速、流量、 occupancy）为 $\mathbf{x}_t^i$。我们可以构建一个时空图 $G_t = (V, E, \mathbf{X}_t)$，其中 $V$ 是传感器节点集合，$E$ 是传感器之间的空间连接（通常基于路网拓扑），$\mathbf{X}_t = \{\mathbf{x}_t^1, \mathbf{x}_t^2, ..., \mathbf{x}_t^n\}$ 是 $t$ 时刻的特征矩阵。

DCRNN（Diffusion Convolutional Recurrent Neural Network）和 STGCN（Spatio-Temporal Graph Convolutional Network）是两个经典的时空图神经网络模型。DCRNN将交通流建模为扩散过程，使用双向随机游走捕获空间依赖；同时结合 seq2seq 架构和 GRU 单元捕获时间依赖。STGCN则使用图卷积捕获空间依赖，一维卷积捕获时间依赖，效率更高。

这些模型在城市交通预测任务中展现了显著优于传统方法的性能。例如，在METR-LA和PEMS-BAY两个公开数据集上，DCRNN将预测误差降低了约15-20%。

1.1.6 其他应用领域

除了上述领域，图神经网络的应用还延伸到了许多其他方向：

知识图谱（Knowledge Graph）中，实体和关系分别对应图的节点和边。知识图谱补全、实体对齐、关系预测等任务都可以用图神经网络来处理。Google的Knowledge Graph、Microsoft的Satori以及阿里巴巴的电商知识图谱都采用了图神经网络技术。

金融风控中，用户与商户、用户与用户之间的交易关系构成了一张复杂的网络图。异常交易检测、洗钱行为识别、信用评估等问题都可以通过分析图结构来提升效果。例如，支付宝使用图神经网络实时检测欺诈交易，将资金损失降低了20%以上。

代码分析与软件工程中，程序的抽象语法树（AST）、函数调用图、程序依赖图等都可以建模为图结构。图神经网络可以用于代码相似性检测、bug定位、代码生成等任务。

自动驾驶中，场景中的车辆、行人、交通标志、道路设施等实体及其相互关系构成了复杂的场景图。图神经网络可以用于场景理解、运动预测、行为规划等关键任务。

1.2 图神经网络的历史演进

图神经网络的发展经历了从概念萌芽到理论成熟、从简单模型到复杂架构的演进过程。理解这段历史有助于我们把握图神经网络发展的内在逻辑和未来方向。

1.2.1 早期探索：基于循环神经网络的图神经网络

图神经网络的原始概念可以追溯到21世纪初。2005年，意大利学者 Franco Scarselli 等人在论文"The Graph Neural Network Model"中首次系统性地提出了图神经网络（Graph Neural Network）的概念。

Scarselli 等人提出的 GNN 模型基于迭代不动点理论（Fixed-Point Theory）。其核心思想是：对于图中的每个节点，其状态可以通过迭代更新来融合来自邻居节点的信息，直到达到稳定状态。形式化地，节点的更新规则为：

$$\mathbf{h}_v^{(t+1)} = f(\mathbf{x}_v, \mathbf{x}_{co[v]}, \mathbf{h}_{ne[v]}^{(t)}, \mathbf{x}_{ne[v]})$$

其中 $\mathbf{h}_v^{(t)}$ 是节点 $v$ 在第 $t$ 次迭代时的隐状态，$f$ 是一个神经网络，$\mathbf{x}_v$ 是节点特征，$\mathbf{x}_{co[v]}$ 是与 $v$ 相连的边的特征，$\mathbf{h}_{ne[v]}^{(t)}$ 是邻居节点的当前状态，$\mathbf{x}_{ne[v]}$ 是邻居节点的特征。

GNN 的输出（用于节点分类等任务）通过一个 readout 函数获得：

$$\mathbf{o}_v = g(\mathbf{h}_v, \mathbf{x}_v)$$

由于采用了不动点迭代机制，原始 GNN 模型存在几个明显的局限性：计算效率低——需要迭代直到收敛，对于大图来说开销很大；表达能力有限——基于收缩映射（Contraction Map）的更新机制限制了模型的表达能力；无法处理可变规模的图——虽然理论上可以，但实际应用中对于节点和边类型的处理不够灵活。

尽管存在这些局限，Scarselli 等人的开创性工作为后续研究奠定了重要基础。他们提出的"将神经网络的强大拟合能力与图结构数据的丰富关系信息相结合"的核心思想，至今仍是图神经网络研究的指导原则。

1.2.2 图卷积网络的兴起

2016年是图神经网络发展史上的重要转折点。这一年，Thomas N. Kipf 和 Max Welling 在国际学习表征会议（ICLR）上发表了里程碑式的论文"Semi-Supervised Classification with Graph Convolutional Networks"。这篇论文提出了图卷积网络（Graph Convolutional Network，GCN），将卷积操作从欧几里得空间（如图像、文本）推广到了图结构数据。

GCN 的核心思想源于谱图理论（Spectral Graph Theory）。在传统的信号处理中，傅里叶变换将信号分解为不同频率的叠加。对于图数据，谱图理论提供了类似的工具——图拉普拉斯矩阵（Graph Laplacian）的特征向量可以视为图的"傅里叶基"，图上的信号可以在这组基上展开。

图的规范化拉普拉斯矩阵定义为：

$$\mathbf{L} = \mathbf{D} - \mathbf{A}$$

其中 $\mathbf{D}$ 是度矩阵（对角线上是每个节点的度），$\mathbf{A}$ 是邻接矩阵。规范化后的对称拉普拉斯矩阵为：

$$\mathbf{L}_{sym} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$$

对拉普拉斯矩阵进行特征分解：$\mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T$，其中 $\mathbf{U}$ 是特征向量矩阵，$\mathbf{\Lambda}$ 是特征值对角矩阵。图上的信号 $\mathbf{x}$ 的傅里叶变换为 $\hat{\mathbf{x}} = \mathbf{U}^T \mathbf{x}$，逆变换为 $\mathbf{x} = \mathbf{U} \hat{\mathbf{x}}$。

图卷积可以定义为在谱域上的乘法：

$$\mathbf{x} *_{\mathcal{G}} \mathbf{y} = \mathbf{U} ((\mathbf{U}^T \mathbf{x}) \odot (\mathbf{U}^T \mathbf{y})) = \mathbf{U} \mathbf{\Theta} \mathbf{U}^T \mathbf{x}$$

其中 $\mathbf{\Theta}$ 是滤波器参数矩阵。如果将 $\mathbf{\Theta}$ 参数化为对角矩阵 $\mathbf{\Theta} = \text{diag}(\theta_0, \theta_1, ..., \theta_{n-1})$，即 $K$ 阶多项式滤波器：$\mathbf{\Theta}(\mathbf{\Lambda}) = \sum_{k=0}^{K} \theta_k \mathbf{\Lambda}^k$，则卷积可以局部化到每个节点的 $K$ 阶邻居。

Kipf 和 Welling 进一步提出了简化的谱图卷积（Simplified 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)})$$

其中 $\tilde{\mathbf{A}} = \mathbf{A} + \mathbf{I}$（添加自环），$\tilde{\mathbf{D}}$ 是对应的度矩阵，$\mathbf{H}^{(l)}$ 是第 $l$ 层的节点特征，$\mathbf{W}^{(l)}$ 是可学习的权重矩阵，$\sigma$ 是激活函数。

这个公式简洁而优雅：每个节点的新特征是通过聚合其邻居节点的特征并进行一次线性变换得到的。这正是后来图神经网络"消息传递"范式的雏形。

GCN 的优势在于：

• **计算效率高**——卷积操作可以通过稀疏矩阵乘法高效实现
• **可扩展性好**——相比原始 GNN 的不动点迭代，GCN 的前向传播更加高效
• **半监督学习友好**——可以自然地利用无标签节点的图结构信息

GCN 在多个基准数据集上取得了当时最好的半监督节点分类结果，引发了图神经网络的 研究热潮。

1.2.3 从空间视角看图卷积

与谱方法相对应的是空间方法（Spatial Methods）。谱方法从图信号处理的角度出发，在图的谱域上定义卷积；空间方法则直接在图的空间结构上定义卷积操作，核心思想是聚合节点邻居的信息。

Bruna 等人在 2014 年的开创性工作中提出了两种图卷积的定义方式：一种是基于谱图理论的非齐次卷积，另一种是基于邻居节点均匀聚合的齐次卷积。后者可以形式化为：

$$\mathbf{h}_v^{(l+1)} = \sigma(\mathbf{W}^{(l)} \sum_{u \in \mathcal{N}(v) \cup \{v\}} \mathbf{h}_u^{(l)})$$

其中 $\mathcal{N}(v)$ 是节点 $v$ 的邻居集合。

空间方法的关键挑战是如何定义"邻居"以及如何对邻居信息进行加权聚合。不同的加权方式催生了各种图神经网络变体：

图注意力网络（Graph Attention Network，GAT）使用注意力机制自适应地学习邻居节点的权重。GAT 的核心公式为：

$$\alpha_{ij} = \frac{\exp(\text{LeakyReLU}(\mathbf{a}^T [\mathbf{W}\mathbf{h}_i || \mathbf{W}\mathbf{h}_j]))}{\sum_{k \in \mathcal{N}(i) \cup \{i\}} \exp(\text{LeakyReLU}(\mathbf{a}^T [\mathbf{W}\mathbf{h}_i || \mathbf{W}\mathbf{h}_k]))}$$

$$\mathb