图神经网络导论：从图论到深度学习

在现实世界中，图结构数据无处不在。社交网络中的用户关系、分子结构中的原子连接、交通网络中的路线规划、知识图谱中的实体关联，这些复杂系统都可以自然地表示为图——一种由节点（顶点）和边（连接）组成的数据结构。这种表示方式不仅捕捉了对象之间的成对关系，还隐含了丰富的结构信息与拓扑模式，使得图成为描述复杂交互系统的理想数学工具。然而，传统机器学习方法在处理图数据时面临根本性挑战：大多数经典算法假设数据点独立同分布，而图数据中的节点通过边相互关联，打破了这一假设，导致信息在节点间传播、聚合的过程难以用标准向量空间操作直接建模。正是这一矛盾推动了图神经网络（Graph Neural Networks, GNNs）的诞生与发展——一类专门设计用于学习图结构数据表示的新型深度学习架构。本章将系统性地构建图神经网络的理论基础，从图论的基本概念出发，逐步深入到谱图理论，进而剖析传统图表示学习方法的内在局限，最终引出图神经网络的核心思想、学习范式与发展脉络，为后续各章的深入探讨奠定坚实基础。

图的基本概念与数学表示

图的定义与基本类型

图（Graph）是数学中描述离散对象间关系的基本结构，形式化定义为 $G = (V, E)$，其中 $V = \{v_1, v_2, \dots, v_n\}$ 是节点（或顶点）集合，$n = |V|$ 表示节点数量；$E \subseteq V \times V$ 是边集合，描述节点之间的连接关系。若边 $(u, v) \in E$ 具有方向性，即从节点 $u$ 指向节点 $v$，则图称为有向图（Directed Graph）；否则为无向图（Undirected Graph）。每条边可附加权重 $w_{uv} \in \mathbb{R}$ 表示连接强度，形成加权图（Weighted Graph）。此外，若图中存在节点连接自身（即 $(v, v) \in E$），则称该边为自环（Self-loop）。图可能包含多个连通分量（Connected Component），即节点间无法通过路径相互访问的子图集合。这些基本属性共同刻画了图的拓扑结构，为后续数学表示提供了清晰的概念框架。

在实际应用中，图的形态千差万别。社交网络通常表示为无向加权图，其中节点代表用户，边的权重可基于互动频率或亲密度；分子结构则常用无向图建模，节点对应原子，边代表化学键，可能包含键类型（单键、双键等）作为边属性；交通网络往往采用有向图，节点为交叉路口或站点，边表示单向道路或路线方向。理解这些具体场景有助于把握图表示的本质差异，也为设计针对性的GNN架构提供了实践依据。

邻接矩阵与度矩阵

图的矩阵表示是将离散图结构转化为连续代数对象的关键桥梁，其中最基础的是邻接矩阵（Adjacency Matrix）。对于含 $n$ 个节点的图，邻接矩阵 $A \in \mathbb{R}^{n \times n}$ 定义为： $$ A_{ij} = \begin{cases} w_{ij} & \text{若边 } (v_i, v_j) \in E \\ 0 & \text{否则} \end{cases} $$ 其中 $w_{ij}$ 为边权重（无向图中 $w_{ij} = w_{ji}$，故 $A$ 对称；有向图则不一定）。邻接矩阵直接编码了图的连接模式，其第 $i$ 行（或列）的非零元素位置指示节点 $v_i$ 的邻居集合。例如，在社交网络中，$A_{ij}$ 可量化用户 $i$ 与 $j$ 的互动强度，矩阵的幂 $A^k$ 则蕴含路径信息——$(A^k)_{ij}$ 表示从 $i$ 到 $j$ 长度为 $k$ 的路径数目（未加权图）或累积权重（加权图）。

与邻接矩阵紧密相关的是度矩阵（Degree Matrix）$D \in \mathbb{R}^{n \times n}$，这是一个对角矩阵，其对角元素 $D_{ii}$ 为节点 $v_i$ 的度（Degree）： $$ D_{ii} = \sum_{j=1}^n A_{ij} $$ 对于无向图，度表示与该节点相连的边数；有向图中则区分入度（列和）与出度（行和）。度矩阵刻画了节点的局部重要性——高度数节点（Hub）在图结构中常扮演关键角色。邻接矩阵与度矩阵的组合衍生出若干核心矩阵，如归一化邻接矩阵 $\tilde{A} = D^{-1/2} A D^{-1/2}$（对称归一化）或随机游走矩阵 $P = D^{-1}A$，这些形式在谱图理论与图卷积操作中具有基础地位。

值得注意的是，自环的引入会改变度矩阵的计算：若节点 $v_i$ 存在自环权重 $a_{ii}$，则 $D_{ii}$ 需包含该值。在GNN实践中，自环常被显式添加以确保节点保留自身信息，这在消息传递机制中尤为重要。

拉普拉斯矩阵及其谱性质

拉普拉斯矩阵（Laplacian Matrix）是连接图论与谱分析的核心工具，定义为 $L = D - A$。其变体包括对称归一化拉普拉斯矩阵 $L_{\text{sym}} = I - D^{-1/2} A D^{-1/2}$ 和随机游走归一化拉普拉斯矩阵 $L_{\text{rw}} = I - D^{-1}A$。这些矩阵虽形式各异，但共享关键性质：半正定性、零特征值对应常数向量、特征值分布反映图连通性。

拉普拉斯矩阵的谱分解（Spectral Decomposition）揭示了图的深层结构。设 $L = U \Lambda U^\top$，其中 $U = [u_1, \dots, u_n]$ 为正交特征向量矩阵，$\Lambda = \text{diag}(\lambda_1, \dots, \lambda_n)$ 为升序排列的特征值（$0 = \lambda_1 \leq \lambda_2 \leq \dots \leq \lambda_n$）。特征值 $\lambda_2$（代数连通度，Algebraic Connectivity）衡量图的整体连通强度——值越大，图越难被分割；特征向量 $u_2$ 则对应图的最优二分方案（谱分割，Spectral Bisection）。这一性质使拉普拉斯谱成为图聚类与社区检测的理论基础。

在信号处理领域，拉普拉斯矩阵可视为图上的“离散拉普拉斯算子”。定义图信号（Graph Signal）为 $x \in \mathbb{R}^n$，其第 $i$ 个分量 $x_i$ 表示节点 $v_i$ 上的标量值（如社交网络中的用户活跃度）。图上的梯度可定义为 $\nabla x = A x$，而拉普拉斯平滑操作 $L x$ 衡量信号在相邻节点间的差异：若 $x$ 在连接紧密的节点间变化平缓，则 $L x$ 的范数较小。因此，最小化 $x^\top L x$ 等价于寻找图上的平滑函数，这在半监督学习中被广泛用于标签传播。

谱图理论进一步将傅里叶变换推广到图域。图傅里叶变换（Graph Fourier Transform, GFT）以拉普拉斯特征向量为基：对图信号 $x$，其频谱表示为 $\hat{x} = U^\top x$；逆变换为 $x = U \hat{x}$。这种变换将空间域操作转化为频谱域操作，为定义图卷积提供了可能——图卷积可视为在频谱域对信号进行滤波，再变换回空间域。具体而言，图卷积核 $g_\theta$ 作用于信号 $x$ 的输出为： $$ x *_{\mathcal{G}} g = U g(\Lambda) U^\top x $$ 其中 $g(\Lambda)$ 为对角矩阵，对角元素为 $g(\lambda_i)$，表示对第 $i$ 个频率分量的增益。然而，直接计算涉及 $U$ 的稠密矩阵乘法，复杂度为 $O(n^2)$，难以扩展至大规模图。这一计算瓶颈催生了后续的近似方法，如切比雪夫多项式展开（Chebyshev Polynomials）和局部一阶近似，成为GCN等模型的理论起点。

传统图表示学习及其局限性

矩阵分解方法

在深度学习兴起之前，图表示学习主要依赖矩阵分解技术，其核心思想是将高维稀疏的图结构映射到低维连续向量空间，使得向量空间中的几何关系（如距离、角度）反映图的结构相似性。谱聚类（Spectral Clustering）是典型代表：它通过对拉普拉斯矩阵的特征向量进行聚类，将图分割为内部连接紧密、外部连接稀疏的社区。具体而言，取 $L$ 的前 $k$ 个最小非零特征向量组成矩阵 $U_k \in \mathbb{R}^{n \times k}$，每行视为一个 $k$ 维节点嵌入，随后在嵌入空间应用 $k$-means聚类。该方法假设理想聚类下，同一社区内节点在图距离上相近，而谱方法的优势在于能处理非凸形状的簇，但其本质是线性投影，难以捕获图的高阶非线性结构。

拉普拉斯特征映射（Laplacian Eigenmaps, LE）则专注于非线性降维，通过优化目标函数： $$ \sum_{i,j} A_{ij} \|y_i - y_j\|^2 $$ 在保持局部邻接关系的同时将节点映射到低维空间 $y_i \in \mathbb{R}^d$。该问题等价于求解广义特征值问题 $L y = \lambda D y$，其解为 $L$ 的最小非零特征值对应的特征向量。LE 的局限性在于：1）仅利用一阶邻接信息，忽略高阶结构；2）嵌入维度受限于特征值数量；3）无法直接用于预测任务，需额外分类器。这些方法虽在特定任务（如可视化、聚类）中有效，但缺乏灵活性，难以适应多任务学习与端到端训练范式。

随机游走与嵌入方法

2010年代中后期，受词嵌入（Word2Vec）成功启发，基于随机游走的图嵌入方法成为主流。核心思想是：通过模拟图上的随机游走生成节点序列，将节点视为“词汇”，序列视为“句子”，再应用Skip-gram模型学习节点嵌入，使得在游走中频繁共现的节点在向量空间中接近。DeepWalk 是开创性工作，它执行固定长度的随机游走，生成节点序列后采用层次化Softmax优化目标： $$ \max_{f} \sum_{v \in V} \sum_{c \in N_R(v)} \log \sigma(f(c)^\top f(v)) $$ 其中 $N_R(v)$ 为游走上下文窗口内的节点，$f(\cdot)$ 为嵌入函数，$\sigma$ 为Sigmoid函数。该方法将图结构转化为序列数据，利用成熟的NLP技术，但随机游走过程与下游任务解耦，无法针对特定任务优化嵌入。

Node2Vec 进一步引入有偏随机游走，通过参数 $p$（返回参数）和 $q$（进出参数）控制游走策略，在深度优先搜索（DFS-like）与广度优先搜索（BFS-like）间权衡，从而同时捕获同质性（Homophily，相似节点相连）与结构性（Structural Equivalence，处于相似拓扑角色的节点）。实验表明，Node2Vec 在社群发现与链接预测任务上优于 DeepWalk，但其嵌入过程仍为静态，无法适应动态图变化，且超参数 $p, q$ 需针对具体图调优。此外，这些方法均基于浅层模型（通常仅一层投影），难以建模复杂非线性关系；嵌入后需训练额外分类器（如逻辑回归）进行预测，导致两阶段训练可能产生次优解。

传统方法的根本局限

综合上述分析，传统图表示学习方法存在以下共性缺陷：

浅层表示能力：矩阵分解与随机游走本质上学习节点的浅层特征，通常仅能捕获一阶或二阶邻域信息，难以建模多跳邻居的复杂交互。例如，在分子图中，原子间的远程相互作用（如共轭体系）可能对化学性质至关重要，但传统方法难以有效捕捉。

任务解耦问题：表示学习与下游预测任务分离，导致嵌入空间未必与任务目标对齐。例如，为聚类优化的嵌入可能不利于节点分类，而独立训练的嵌入无法通过梯度反向传播适应任务需求。

静态与离散局限：现有方法假设图结构固定不变，难以处理动态图（如社交网络演化）或连续图结构变化。同时，节点与边的离散表示限制了在向量空间中进行插值或生成操作，阻碍了图生成模型的发展。

可扩展性瓶颈：矩阵分解涉及稠密矩阵运算（如特征分解），时间复杂度常达 $O(n^3)$，难以处理百万级节点的大规模图。随机游走虽可并行，但需预计算所有节点嵌入，内存开销随节点数线性增长。

缺乏泛化能力：传统方法通常针对特定图训练，当出现新图或新节点时，需重新运行整个嵌入流程（如重新执行随机游走与Skip-gram训练），无法实现跨图泛化。这一缺陷限制了它们在动态环境中的应用。

这些局限性表明，需要一种能够端到端学习、灵活聚合多跳信息、适应动态图且可扩展的新范式，而深度学习的兴起为此提供了可能——通过神经网络参数化映射函数，利用反向传播实现端到端优化，并借助消息传递机制自然建模节点间信息交互，图神经网络应运而生。

图神经网络的学习范式

节点级预测任务

节点级预测是GNN最广泛的应用场景，其目标为图中每个节点分配标签或数值。节点分类（Node Classification）要求预测节点的离散类别，典型任务包括：社交网络中的用户兴趣标注（如政治倾向、爱好分类）、分子图中原子类型识别、论文引用网络中的主题预测。形式上，给定图 $G = (V, E)$ 与部分节点标签集 $Y_L \subseteq V$，任务学习映射 $f: V \rightarrow \mathcal{C}$（$\mathcal{C}$ 为类别空间），使未标记节点预测准确率最大化。由于图结构蕴含丰富关联信息，半监督学习成为主流：利用已标记节点的少量标签，通过图传播机制为未标记节点生成预测。例如，在Cora论文数据集中，每篇论文的特征向量（词频）与其引用关系共同输入GNN，模型聚合邻居论文的标签信息，显著提升分类精度。

节点回归（Node Regression）则预测连续值，如社交网络中的用户影响力评分、交通网络中节点的拥堵指数、分子图中原子的部分电荷。该任务通常采用均方误差（MSE）损失，但需注意图结构可能引入空间自相关——相邻节点值往往相似，导致标准回归假设（样本独立）失效，需在损失函数中考虑图平滑性约束。

边级预测任务

边级预测关注图中边的关系或存在性，主要包括链接预测（Link Prediction）与关系预测（Relation Prediction）。链接预测旨在估计节点对之间边的可能性，应用于推荐系统（预测用户-物品交互）、知识图谱补全（预测缺失实体关系）、社交网络好友推荐。形式上，对节点对 $(u, v)$，模型计算分数 $s(u, v) = f(u, v; \Theta)$，分数高则预测边存在。评估指标常用AUC-ROC、平均精确率（AP）。挑战在于：正负样本极度不平衡（实际边数远小于可能边数），需负采样策略；且需区分直接连接与高阶关系（如共同邻居）。

关系预测针对多关系图（Multigraph），每条边具有类型标签（如知识图谱中的“出生于”“工作于”）。任务预测节点间边的语义类型，形式化为多分类问题。例如，在Freebase知识图谱中，给定实体 $e_1$ 和 $e_2$，模型需预测关系 $r$ 使得 $(e_1, r, e_2)$ 成立。这要求模型同时编码节点特征与图结构上下文。

图级预测任务

图级预测将整个图映射到全局标签或属性，包括图分类（Graph Classification）与图回归（Graph Regression）。图分类为图分配离散类别，如分子活性分类（药物是否有效）、蛋白质功能预测、程序流程图漏洞检测。图回归预测连续图属性，如分子能量估计、图生成模型的真实性评分。这类任务需将图结构压缩为固定维度表示，常用图读出（Readout）函数，如全局均值池化、总和池化或更复杂的Set2Set注意力机制。

图级任务面临独特挑战：图大小可变，要求模型对不同规模图具有置换不变性（Permutation Invariance）——节点顺序改变不应影响输出。此外，图分类需区分细微结构差异（如两种分子仅一个官能团不同），要求模型具备强表达能力。

学习范式的形式化定义

统一而言，GNN学习范式可形式化为：给定图 $G = (V, E, X)$，其中 $X \in \mathbb{R}^{n \times d}$ 为节点特征矩阵（$d$ 为特征维数），任务目标学习参数化函数 $f_\Theta$ 映射图结构至预测输出。根据任务层级，输出形式不同：

• 节点级：$Y \in \mathbb{R}^{n \times c}$（$c$ 为类别数或回归维度）
• 边级：$Y \in \mathbb{R}^{m \times \cdot}$（$m = |E|$，边数）
• 图级：$Y \in \mathbb{R}^{k \times \cdot}$（$k$ 为图数，适用于图集合）

损失函数依任务而定：分类常用交叉熵，回归用MSE，链接预测用负对数似然或边缘排序损失。训练过程通过反向传播优化 $\Theta$，核心在于设计可微分消息传递层，使信息沿图结构传播与聚合。

GNN的发展历程与核心挑战

从谱方法到空间方法

GNN的演化可追溯至谱图理论对图卷积的早期定义。2013年，Bruna等人在论文《Spectral Networks and Locally Connected Networks on Graphs》中首次提出谱图卷积网络（Spectral CNN），将标准卷积推广到图域：通过图傅里叶变换将卷积转为频谱滤波，即 $y = U g(\Lambda) U^\top x$。但该方法依赖完整的拉普拉斯特征向量 $U$，计算与存储成本均为 $O(n^2)$，无法扩展。2014年，Henaff等人提出使用切比雪夫多项式近似滤波器 $g(\Lambda)$，将操作限制在局部邻域： $$ U g(\Lambda) U^\top x \approx \sum_{k=0}^{K} \theta_k T_k(\tilde{L}) x $$ 其中 $\tilde{L} = \frac{2}{\lambda_{\max}} L - I$ 为缩放拉普拉斯，$T_k$ 为切比雪夫多项式，$K$ 为多项式阶数。此近似使计算复杂度降至 $O(K|\mathcal{N}(v)|)$，仅依赖 $K$ 跳邻居，奠定了局部卷积的基础。

2016年，Defferrard等人提出Chebyshev Graph Convolutional Network (ChebNet)，系统化切比雪夫近似，并证明 $K$ 阶多项式对应 $K$ 跳邻域聚合。同年，Kipf与Welling在《Semi-Supervised Classification with Graph Convolutional Networks》中提出图卷积网络（GCN），进一步简化：假设 $K=1$ 且 $\lambda_{\max} \approx 2$，则卷积核退化为 $g(\Lambda) \approx \theta_0 I + \theta_1 \tilde{L}$。结合重新参数化技巧，GCN层前向