图神经网络基础：图论、信号处理与深度学习融合

现实世界中的大量数据天然呈现为图结构：从社交网络、分子化学、知识图谱到交通系统、脑神经连接和推荐系统，实体间复杂的关系无法用传统的欧氏空间数据（如网格图像或序列文本）有效表征。深度学习在这一领域面临的根本挑战在于：如何将基于网格数据的成功模型（如卷积神经网络）的核心思想——局部性、平移不变性和层次化特征学习——迁移到拓扑不规则、节点无序且规模可变的图结构上。图神经网络（Graph Neural Networks, GNNs）正是为应对这一挑战而发展出的范式，其本质是在图的拓扑约束下进行节点表示学习。本章将系统构建GNN的形式化基础，从图论的基本表示出发，引入图信号处理的理论框架，揭示图数据与欧氏数据的本质差异，并最终通过一个完整的图分类案例，展示GNN从数学原理到实践应用的端到端流程。这一基础不仅解释了GNN为何有效，也为理解后续章节中更复杂的架构设计、理论分析和应用拓展提供了统一的视角。

1.1 图的结构化数据表示

图作为描述对象及其关系的基本数学结构，由节点（顶点）和边组成。为在计算机中处理并进行梯度优化，必须将其转化为离散的、可微分的代数形式。核心表示包括邻接矩阵、拉普拉斯算子以及节点特征矩阵。

1.1.1 图的形式化定义与邻接矩阵

给定一个无向图 $G = (\mathcal{V}, \mathcal{E})$，其中 $\mathcal{V} = \{v_1, v_2, \dots, v_n\}$ 是包含 $n$ 个节点的集合，$\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$ 是边的集合。若边具有权重，则图是加权的，权重通常表示为实数 $w_{ij} \geq 0$。图的邻接矩阵 $A \in \mathbb{R}^{n \times n}$ 是最基本的表示，其元素定义为： $$ A_{ij} = \begin{cases} w_{ij} & \text{如果 } (v_i, v_j) \in \mathcal{E} \\ 0 & \text{否则} \end{cases} $$ 对于无向图，$A$ 是对称矩阵，即 $A_{ij} = A_{ji}$。若图为二部图或存在方向性，$A$ 可能非对称。邻接矩阵直接编码了图的连接关系，但未考虑节点自身的度信息。

节点的度（degree）是与其相连的边的数量（加权图中为权重和），度矩阵 $D \in \mathbb{R}^{n \times n}$ 是一个对角矩阵，其中 $D_{ii} = d_i = \sum_{j=1}^n A_{ij}$。度矩阵反映了节点的“连接活跃度”，是后续定义拉普拉斯算子的关键。

1.1.2 拉普拉斯算子：图的微分几何基础

在欧氏空间中，拉普拉斯算子 $\Delta = \nabla^2$ 是二阶微分算子，用于测量函数相对于周围环境的平滑度。在图这种离散域上，拉普拉斯矩阵 $L$ 扮演了类似角色，是图信号处理的核心。最常见的定义是组合拉普拉斯矩阵（Combinatorial Laplacian）： $$ L = D - A $$ $L$ 是对称半正定矩阵，具有如下关键性质：

• 对于任意向量 $x \in \mathbb{R}^n$，二次型 $x^\top L x = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2$。这直观地衡量了 $x$ 在连接节点间的差异总和，值越小表示 $x$ 在图上越平滑。
• $L$ 的特征值非负，且 $L \mathbf{1} = 0$（$\mathbf{1}$ 是全1向量），对应特征值0的特征空间由常数向量张成，反映了图的连通分量数（对于连通图，0特征值重数为1）。

然而，$L$ 的行和（即度）不恒定，这导致其谱性质受节点度分布影响。为获得更均匀的谱行为，常使用归一化拉普拉斯矩阵：

• **对称归一化拉普拉斯**：$L_{\text{sym}} = I - D^{-1/2} A D^{-1/2}$
• **随机游走归一化拉普拉斯**：$L_{\text{rw}} = I - D^{-1} A$

$L_{\text{sym}}$ 是对称的，保证特征向量正交；$L_{\text{rw}}$ 与随机游走过程直接相关。归一化操作使得拉普拉斯矩阵的谱集中在 $[0, 2]$ 区间，便于频谱分析。在实践中，GNN模型常使用添加自环的归一化邻接矩阵 $\tilde{A} = A + I$ 及其对应的度矩阵 $\tilde{D}$，以保留节点自身信息并改善梯度流动，例如 $\hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2}$ 是GCN中的关键矩阵。

1.1.3 特征矩阵：节点属性与图信号

图上的节点通常伴随属性（attributes），如社交网络中用户的年龄、兴趣，或分子中原子的类型、电荷。这些属性可组织成特征矩阵 $X \in \mathbb{R}^{n \times d}$，其中 $n$ 是节点数，$d$ 是特征维度，$X_{i,:}$ 是节点 $v_i$ 的特征向量。在GNN语境下，$X$ 常被视为定义在节点上的图信号（graph signal）：每个节点位置有一个 $d$ 维信号值。这一视角将图视为定义在离散域上的信号载体，从而可借用信号处理工具进行分析。

综合上述，图 $G$ 的完整代数表示为三元组 $(A, D, X)$。在计算时，$A$ 和 $D$ 通常以稀疏矩阵形式存储，因为真实图往往非常稀疏（边数 $m \ll n^2$），这极大提升了大规模图的可扩展性。

1.2 图信号处理核心概念

图信号处理（Graph Signal Processing, GSP）是将经典信号处理概念（如傅里叶变换、滤波）推广到图结构上的理论框架。它为理解GNN的卷积操作提供了坚实基础。

1.2.1 图傅里叶变换

在欧氏空间中，傅里叶变换将函数分解为不同频率的正弦波叠加，其基函数是拉普拉斯算子的特征函数（复指数）。类似地，在图上，图傅里叶变换（Graph Fourier Transform, GFT）将图信号投影到拉普拉斯矩阵的特征向量构成的基上。

设拉普拉斯矩阵 $L$ 的特征分解为 $L = U \Lambda U^\top$，其中 $U = [u_1, u_2, \dots, u_n] \in \mathbb{R}^{n \times n}$ 是正交特征向量矩阵（$U^\top U = I$），$\Lambda = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_n)$ 是按特征值升序排列的对角阵（$0 = \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$）。特征向量 $u_k$ 可视为图上的“振荡模式”，特征值 $\lambda_k$ 衡量该模式的“频率”——越大表示在相邻节点间变化越剧烈。

给定图信号 $x \in \mathbb{R}^n$（为简化先考虑单通道），其图傅里叶变换定义为： $$ \hat{x} = U^\top x $$ $\hat{x}_k = \langle u_k, x \rangle$ 是信号 $x$ 在第 $k$ 个频率基上的系数。逆图傅里叶变换为： $$ x = U \hat{x} $$ 因此，$x$ 可表示为所有特征向量的线性组合：$x = \sum_{k=1}^n \hat{x}_k u_k$。低频特征向量（对应小 $\lambda$）在相连节点间取值相似，代表图的平滑分量；高频特征向量（对应大 $\lambda$）在相邻节点间振荡剧烈，代表图的细节或噪声分量。

> 侧边栏：图傅里叶变换的几何直观 > 考虑一个简单的环形图（cycle graph），其拉普拉斯特征向量本质是离散余弦/正弦波。低频特征向量在环上缓慢变化，类似长波；高频特征向量在环上快速振荡，类似短波。对于任意图，特征向量虽无显式函数形式，但保持了“平滑性”与特征值大小的关联：特征值小的特征向量在连接紧密的节点间符号变化少。

1.2.2 图滤波与图卷积

在信号处理中，滤波是在频域修改信号频谱（乘以滤波器响应）再逆变换回时域的过程。在图信号处理中，图滤波器 $g: \mathbb{R} \to \mathbb{R}$ 作用于图信号 $x$ 定义为： $$ y = U g(\Lambda) U^\top x $$ 其中 $g(\Lambda) = \text{diag}(g(\lambda_1), \dots, g(\lambda_n))$。这相当于将 $x$ 的GFT系数 $\hat{x}$ 乘以滤波器响应 $g(\lambda_k)$，再通过逆GFT得到输出 $y$。若 $g(\lambda_k) \approx 0$ 对高频，则滤波器是低通，保留平滑分量；若 $g(\lambda_k) \approx 0$ 对低频，则是高通。

图卷积可视为一种特殊滤波。在欧氏空间中，卷积定理指出卷积等价于频域乘法。在图上，定义图卷积算子 $\star_G$ 为： $$ x \star_G g = U g(\Lambda) U^\top x $$ 因此，图卷积本质是图滤波。但直接计算需完整特征分解 $U$，复杂度 $O(n^3)$，不可扩展到大规模图。实践中，滤波器 $g(\Lambda)$ 常被参数化为多项式：$g(\Lambda) = \sum_{k=0}^{K} \theta_k \Lambda^k$。代入得： $$ y = \sum_{k=0}^{K} \theta_k L^k x $$ 由于 $L^k$ 的 $(i,j)$ 元素与节点 $i$ 到 $j$ 的长度为 $k$ 的路径数相关，这等价于节点 $i$ 的输出是其 $K$-跳邻居的线性组合。例如，$L x$ 的第 $i$ 元素为 $d_i x_i - \sum_{j \in \mathcal{N}(i)} A_{ij} x_j$，正是节点 $i$ 与一阶邻居的差值。多项式滤波将频谱操作转化为局部邻域聚合，为GNN的消息传递机制提供了理论依据。

1.2.3 从图滤波到图神经网络

将多项式滤波器参数化为可学习系数 $\theta_k$，并限制阶数 $K$（通常很小，如1或2），就得到了图卷积网络（GCN）的简化形式： $$ H^{(l+1)} = \sigma\left( \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} H^{(l)} \Theta^{(l)} \right) $$ 其中 $\tilde{A} = A + I$，$\tilde{D}$ 是其度矩阵，$\Theta^{(l)}$ 是层内可训练参数，$\sigma$ 是非线性激活。这本质是谱图卷积的一阶近似（Chebyshev多项式 $K=1$ 的切比雪夫展开）。更一般地，消息传递神经网络（Message Passing Neural Networks, MPNNs）将图滤波的局部聚合思想抽象为： $$ h_v^{(l+1)} = \text{UPDATE}^{(l)} \left( h_v^{(l)}, \text{AGGREGATE}^{(l)} \left( \{ h_u^{(l)} : u \in \mathcal{N}(v) \} \right) \right) $$ 其中 $h_v^{(l)}$ 是节点 $v$ 在层 $l$ 的表示，AGGREGATE 是邻居信息的对称聚合函数（如求和、平均、最大池化），UPDATE 融合自身状态。这种形式直接体现了图滤波的局部性，同时通过参数化AGGREGATE和UPDATE实现灵活性。图傅里叶变换因此成为理解GNN频谱视角与顶点域视角之间联系的桥梁。

1.3 图与欧氏空间数据的本质差异

将图像（网格图）或文本（序列图）的成功模型直接套用于一般图结构失败的根本原因，在于两类数据存在本质差异。认识这些差异是设计有效GNN归纳偏置的前提。

1.3.1 平移不变性 vs 置换不变性

在图像中，卷积核在空间平移下共享参数，这称为平移不变性（translation invariance）：识别边缘的滤波器无论出现在图像左上角还是右下角，都使用同一组参数。这种不变性源于网格的全局坐标系和规则结构。

在一般图上，节点没有全局有序坐标，图的拓扑由邻接关系定义。两个图结构可能同构但节点标签不同，模型应给出相同输出。因此，GNN必须满足置换不变性（permutation invariance）：对节点任意重排列，图级输出不变；同时满足置换等变性（permutation equivariance）：节点表示随节点排列同步重排列。形式化地，设 $\pi$ 是节点置换，$A' = P_\pi A P_\pi^\top$，$X' = P_\pi X$（$P_\pi$ 是置换矩阵），则图级预测 $f(G)$ 应满足 $f(G) = f(G')$，节点级预测 $g(G)_v$ 应满足 $g(G')_{\pi(v)} = g(G)_v$。这一约束要求GNN的聚合函数对邻居集合对称（如sum/mean/max），且消息函数不依赖节点顺序。

1.3.2 规则的局部邻域 vs 可变的图邻居

图像中每个像素有固定数目的邻居（如4或8），且邻居位置相对中心像素有固定方向关系（上、下、左、右）。这种规则的局部结构使得卷积核能高效捕获空间层次模式。

在一般图中，节点的邻居数量（度）可能从1到数千不等，且邻居间无固定几何关系。一个节点可能同时连接高度不同的节点（如社交网络中的枢纽节点）。这种度分布异质性和结构不规则性导致：

• 固定大小的卷积核无法直接定义。
• 邻居信息的聚合需要处理可变大小的输入。
• 远距离节点可能通过短路径连接（小世界现象），需要多层传播捕获长程依赖，但过深会导致过平滑（over-smoothing）。

1.3.3 全局坐标缺失与谱域视角

网格数据有隐含的全局坐标（像素坐标），使得基于距离的核函数（如高斯核）易于定义。图上缺乏这种全局度量，节点间“距离”需通过最短路径长度等图距离度量，但这些度量计算昂贵且不满足平移不变性。图傅里叶变换提供的谱域（spectral domain）成为替代：图的频率成分由拉普拉斯特征向量定义，天然适应图结构。但谱域方法通常对图结构敏感（不同图有不同基），需通过多项式近似或切比雪夫展开在顶点域实现高效、结构自适应的卷积。

1.3.4 归纳偏置设计原则

基于上述差异，GNN的设计蕴含强烈的归纳偏置（inductive bias）： 1. 消息传递偏置：节点表示通过递归聚合邻居信息更新，假设图结构蕴含的局部关系是预测的关键。 2. 对称函数偏置：聚合函数对邻居集合对称，确保置换不变性。 3. 局部性偏置：每层仅融合直接邻居，深层GNN扩大感受野但保持局部性本质。 4. 结构敏感性偏置：参数不依赖具体节点编号，但依赖图拓扑（通过邻接矩阵影响聚合）。

这些偏置使GNN能泛化到未见过的图（归纳学习），但也限制了其表达能力：例如，无法区分某些非对称图（如三角形与星形图在某些浅层GNN下可能同构）。后续章节将探讨如何缓解这些限制。

1.4 端到端案例：分子图分类

为整合前述概念，我们展示一个完整的图分类任务：使用GNN预测分子性质。该案例贯穿数据表示、模型构建、训练与推理全流程，所有步骤均基于前述数学基础。

1.4.1 任务与数据描述

任务：给定分子图，预测其生物活性类别（如酶抑制剂、毒性等），属于多分类问题。采用公开数据集ENZYMES（TUDataset的一部分），包含600个分子图，节点为原子（共6种类型，用one-hot编码，$d=6$），边为化学键（类型包括单键、双键等，可编码为权重或作为多边处理），每个图有6个可能的酶类别标签。图大小从$n=10$到$n=100$节点不等。

图构建：每个分子表示为 $G = (A, X, y)$：

• 邻接矩阵 $A$：若原子 $i$ 与 $j$ 有化学键，则 $A_{ij}=1$（无向图，对称）；添加自环（$A_{ii}=1$）以包含节点自身信息。
• 特征矩阵 $X \in \{0,1\}^{n \times 6}$：每行是原子类型的one-hot向量。
• 标签 $y \in \{1,\dots,6\}$：分子类别。

1.4.2 模型架构：两层图卷积网络

我们设计一个简单的图卷积网络（GCN）作为分类器。模型包含： 1. 两层图卷积层：每层执行图滤波与非线性变换。 2. 图读出层（Readout）：将节点表示聚合成图级表示。 3. 全连接分类器：输出类别概率。

第一层：输入 $H^{(0)} = X \in \mathbb{R}^{n \times 6}$。计算： $$ \tilde{A} = A + I, \quad \tilde{D}_{ii} = \sum_j \tilde{A}_{ij} $$ $$ \hat{A} = \tilde{D}^{-1/2} \tilde{A} \tilde{D}^{-1/2} $$ $$ H^{(1)} = \sigma\left( \hat{A} H^{(0)} W^{(0)} \right) $$ 其中 $W^{(0)} \in \mathbb{R}^{6 \times 16}$ 是可训练权重矩阵，$\sigma$ 是ReLU激活。$\hat{A} H^{(0)}$ 执行归一化邻接聚合（相当于低通滤波），$W^{(0)}$ 是特征变换。输出 $H^{(1)} \in \mathbb{R}^{n \times 16}$ 是节点隐藏表示。

第二层： $$ H^{(2)} = \sigma\left( \hat{A} H^{(1)} W^{(1)} \right) $$ 其中 $W^{(1)} \in \mathbb{R}^{16 \times 32}$，输出 $H^{(2)} \in \mathbb{R}^{n \times 32}$。两层传播使每个节点感受野覆盖2跳邻居。

图读出：为获得图级表示 $h_G \in \mathbb{R}^{32}$，采用全局平均池化（Global Average Pooling）： $$ h_G = \frac{1}{n} \sum_{v=1}^n h_v^{(2)} $$ 该操作对节点置换不变，且保持平移不变性（在图上即节点顺序不变）。其他选择包括最大池化或可学习池化（如Set2Set）。

分类器：单层全