图与网络：数学基础与计算范式

图（Graph）作为描述实体间关系的基本数学结构，其历史可追溯至1736年欧拉对柯尼斯堡七桥问题的解决，彼时图论作为拓扑学的分支诞生。然而，在过去的二十年间，图已从纯粹的数学抽象演变为一种普适的数据表示范式，广泛应用于社交网络、分子化学、知识图谱、推荐系统乃至神经科学等领域。这种范式转换的核心在于：现实世界中大量高价值数据本质上是关系型的（relational），其信息不仅蕴含于个体实体（顶点）的属性中，更关键地编码于实体间的复杂交互（边）模式里。例如，在社交网络中，用户的兴趣预测不仅依赖于其个人资料，更受其好友圈层的影响；在分子图中，化合物的药理活性由其原子构成与化学键拓扑共同决定。这种“关系即数据”的认知，推动了计算范式从传统的欧几里得空间（如图像、语音、文本序列）向非欧几里得空间的根本性拓展。

本章旨在为全书奠定坚实的数学与概念基础。我们将系统性地阐述图论的核心概念与符号体系，包括顶点（Vertex）、边（Edge）、邻接矩阵（Adjacency Matrix）、拉普拉斯矩阵（Laplacian Matrix）及其变体，并深入分析这些表示法的计算特性与存储开销。继而，我们将展开一场范式层面的思辨：对比图数据与序列（Sequence）、网格（Grid）等经典欧几里得数据在结构同质性、平移不变性及局部性假设上的本质差异，从而阐明为何传统的深度学习架构（如CNN、RNN）难以直接迁移至图结构。在此基础上，本章将构建图的类型学（Taxonomy），辨析有向/无向、加权/无权、同质/异质、静态/动态等图形态，并论证这些结构性差异对后续图神经网络模型设计的决定性影响。最后，本章将回顾图分析的传统计算方法，包括基于矩阵分解的谱方法、随机游走（Random Walk）模型以及以社区检测（Community Detection）为代表的启发式算法，并客观评述其在可扩展性、表达能力及端到端学习框架方面的固有局限，从而为第2章引入图神经网络这一统一的学习范式做好理论铺垫。

---

2.1 图论基本概念与符号体系

2.1.1 图的数学定义与核心元素

在数学上，一个图 $G$ 被定义为一个有序对 $G = (V, E)$，其中 $V$ 是顶点（Vertex）或节点（Node）的集合，$E$ 是边（Edge）的集合，每条边连接两个顶点。若顶点 $u$ 与 $v$ 之间存在边，则记作 $(u, v) \in E$。顶点数 $|V| = n$ 称为图的阶（Order），边数 $|E| = m$ 称为图的大小（Size）。为精确描述，我们引入以下标准符号：

• 顶点集：$V = \{v_1, v_2, ..., v_n\}$
• 边集：$E \subseteq V \times V$ （对于无向图，$(u,v)$ 与 $(v,u)$ 等价）
• 图的表示：$G = (V, E)$

顶点（Vertex） 是图的基本组成单元，代表现实世界中的实体，如社交网络中的用户、分子图中的原子、知识图谱中的实体。每个顶点可关联一个特征向量（Feature Vector） $\mathbf{x}_v \in \mathbb{R}^d$，描述其属性（如用户年龄、原子类型、实体描述嵌入）。当所有顶点特征组织成矩阵 $\mathbf{X} \in \mathbb{R}^{n \times d}$ 时，$\mathbf{X}$ 成为图神经网络处理的核心输入之一。

边（Edge） 定义了顶点间的二元关系。边的方向性是图分类的首要维度：若边 $(u, v)$ 具有方向（即 $u$ 指向 $v$），则图称为有向图（Directed Graph）；若关系无方向，则为无向图（Undirected Graph）。边的权重（Weight）可量化关系的强度或距离，如社交网络中的互动频率、物理网络中的连接阻抗。加权图中，边集定义为 $E \subseteq V \times V \times \mathbb{R}$，每条边为一个三元组 $(u, v, w_{uv})$，其中 $w_{uv}$ 为权重。此外，边可携带类型（Type），在异构图（Heterogeneous Graph）中，不同语义的边（如“引用”、“合作”、“属于”）被明确区分。

度（Degree） 是描述顶点局部连通性的基本指标。对于无向图，顶点 $v$ 的度 $d_v$ 定义为与其相连的边数：$d_v = |\{ (u,v) \in E \}|$。对于有向图，需区分入度（In-degree） $d_v^{in} = |\{ (u,v) \in E \}|$ 和出度（Out-degree） $d_v^{out} = |\{ (v,u) \in E \}|$。度分布（Degree Distribution） $P(d)$ 是图的重要全局统计量，许多真实网络（如社交网络、互联网）呈现幂律分布（Power-law Distribution），即少数顶点拥有极高度数（“枢纽”或“影响者”），而大多数顶点度数很低，这种无标度（Scale-free）特性对网络鲁棒性与信息扩散有深刻影响。

2.1.2 邻接矩阵：图的全局代数表示

邻接矩阵（Adjacency Matrix）是将图结构编码为矩阵形式的最直接方式。对于 $n$ 个顶点的图，其邻接矩阵 $\mathbf{A} \in \mathbb{R}^{n \times n}$ 定义如下：

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

其中 $w_{ij}$ 为边 $(v_i, v_j)$ 的权重。对于无权无向图，$\mathbf{A}$ 是对称矩阵，且对角线元素通常为0（除非允许自环，即 $ (v_i, v_i) \in E $）。对于有向图，$\mathbf{A}$ 一般非对称，$\mathbf{A}_{ij} = 1$ 表示从 $v_i$ 到 $v_j$ 存在有向边。

邻接矩阵的优势在于其全局性与代数兼容性：图的几乎所有全局性质（如连通分量、路径计数、谱性质）均可通过 $\mathbf{A}$ 的运算（如幂、特征分解）揭示。例如，$[\mathbf{A}^k]_{ij}$ 表示从 $v_i$ 到 $v_j$ 长度为 $k$ 的路径数目。然而，$\mathbf{A}$ 的主要缺陷是空间复杂度：存储一个 $n \times n$ 矩阵需要 $O(n^2)$ 空间，对于大规模稀疏图（$m \ll n^2$），这是不可接受的。实践中，图通常非常稀疏（如社交网络中每个用户仅连接数百人），因此邻接矩阵以稀疏矩阵（Sparse Matrix）格式（如压缩稀疏行格式 CSR）存储，空间复杂度降至 $O(m)$。

邻接矩阵也是定义图卷积等运算的起点。在频域图卷积中，卷积定理要求将信号（顶点特征）从顶点域转换到图拉普拉斯的谱域，而邻接矩阵是构建拉普拉斯矩阵的基础。

2.1.3 拉普拉斯矩阵与图谱理论

拉普拉斯矩阵（Laplacian Matrix）是图论与谱图理论（Spectral Graph Theory）的核心工具，它综合了邻接矩阵与顶点度信息，刻画了图的全局结构特性。最常见的组合拉普拉斯矩阵（Combinatorial Laplacian）定义为：

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

其中 $\mathbf{D} \in \mathbb{R}^{n \times n}$ 是度矩阵（Degree Matrix），是一个对角矩阵，对角线元素 $D_{ii} = d_i$ 为顶点 $v_i$ 的度，非对角线元素为0。因此，$\mathbf{L}$ 的每个元素为：

$$ \mathbf{L}_{ij} = \begin{cases} d_i & \text{if } i = j \\ -1 & \text{if } i \neq j \text{ and } (v_i, v_j) \in E \\ 0 & \text{otherwise} \end{cases} $$

拉普拉斯矩阵 $\mathbf{L}$ 具有若干关键数学性质： 1. 对称半正定性：对于无向图，$\mathbf{L}$ 是对称矩阵，且对所有非零向量 $\mathbf{x} \in \mathbb{R}^n$，满足 $\mathbf{x}^\top \mathbf{L} \mathbf{x} \geq 0$。这使其特征值均为非负实数。 2. 零特征值关联连通分量：$\mathbf{L}$ 的最小特征值为0，其代数重数等于图的连通分量（Connected Component）数目。特征向量 $\mathbf{1} = [1, ..., 1]^\top$ 总是对应于特征值0的右特征向量。 3. 谱 Gap 与代数连通度：次小特征值 $\lambda_2$（称为代数连通度，Algebraic Connectivity）衡量图的整体连通紧密程度。$\lambda_2$ 越大，图越难被分割；$\lambda_2 \to 0$ 表示图接近断开。

拉普拉斯矩阵的二次型 $\mathbf{x}^\top \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{(i,j) \in E} (x_i - x_j)^2$ 揭示了其物理意义：它量化了定义在顶点上的信号 $\mathbf{x}$ 的平滑度（Smoothness）。若相邻顶点值差异小，则 $\mathbf{x}^\top \mathbf{L} \mathbf{x}$ 小，信号在图上平滑。这一性质是图正则化、图半监督学习以及图卷积网络（GCN）中邻域聚合机制的数学根源。

归一化拉普拉斯矩阵（Normalized Laplacian）通过度矩阵的归一化，使不同度数的顶点在谱分析中具有可比性：

• **对称归一化拉普拉斯**：$\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}_{rw} = \mathbf{D}^{-1} \mathbf{L} = \mathbf{I} - \mathbf{D}^{-1} \mathbf{A}$

$\mathbf{L}_{sym}$ 的特征值与 $\mathbf{L}_{rw}$ 的特征值相同，但特征向量不同。$\mathbf{L}_{rw}$ 与随机游走过程直接相关：从顶点 $i$ 出发，下一步转移到邻居 $j$ 的概率为 $[\mathbf{D}^{-1}\mathbf{A}]_{ij}$。在频域图卷积中，$\mathbf{L}_{sym}$ 因其对称性更受青睐。

2.1.4 图的存储与计算复杂度

图的表示法直接影响算法效率。主要存储策略包括： 1. 邻接矩阵：$O(n^2)$ 空间，支持 $O(1)$ 边查询，但遍历一个顶点的所有邻居需 $O(n)$ 时间。 2. 邻接表（Adjacency List）：为每个顶点维护一个列表，存储其所有邻居。空间 $O(n + m)$，遍历邻居 $O(d_v)$，是稀疏图的标准表示。 3. 边列表（Edge List）：仅存储所有边 $(u, v, w)$，空间 $O(m)$，适合边遍历操作（如随机游走初始化）。

对于大规模图（如十亿级顶点），分布式图存储（如GraphX、DGL）与图分区（Graph Partitioning）技术至关重要，旨在最小化跨分区通信。此外，子图采样（Subgraph Sampling）与邻居采样（Neighbor Sampling）是缓解内存瓶颈、实现小批量训练的关键工程技巧，这些技术将在后续章节详述。

---

2.2 范式转换：从欧几里得到非欧几里得数据

2.2.1 欧几里得数据的核心假设

传统深度学习（如CNN、RNN）的成功建立在欧几里得数据（Euclidean Data）的若干关键假设之上：

• **网格结构**（Grid-like Structure）：数据点排列在规则网格上（如图像的像素网格、语音/文本的时序网格）。
• **平移不变性**（Translation Invariance）：卷积核在网格上滑动，共享参数，捕获局部模式（如边缘、纹理）与位置无关。
• **固定维度**（Fixed Dimensionality）：每个样本具有预定义、统一的形状（如 $224 \times 224 \times 3$ 图像）。
• **局部相关性**（Local Correlation）：相邻数据点高度相关，而远距离点相关性弱，这支持了局部感受野的设计。

这些假设使得卷积操作（Convolution）和循环操作（Recurrence）成为高效的特征提取器。例如，CNN通过局部连接、权值共享和池化，实现了对网格数据的层次化表征学习。

2.2.2 图数据的非欧几里得特性

图数据从根本上违背了上述欧几里得假设，呈现出非欧几里得（Non-Euclidean）特性： 1. 不规则性（Irregularity）：顶点间连接关系任意，无全局坐标或顺序。两个相邻顶点在“图距离”（Graph Distance，即最短路径长度）上邻近，但在特征空间可能相距甚远。反之，特征相似的顶点可能因连接稀疏而图距离很远。这种结构-特征解耦是图学习的核心挑战。 2. 变大小与拓扑（Variable Size & Topology）：图规模（顶点数 $n$）与拓扑（连接模式）因样本而异。一个图分类任务中，不同分子图的顶点数可能从几十到数千不等。传统神经网络要求固定输入尺寸，无法直接处理这种排列不变性（Permutation Invariance）需求——图的顶点顺序无关紧要，但任意重排会改变输入矩阵的行序，而模型输出应保持不变。 3. 缺乏全局坐标：无法像图像那样定义“上/下/左/右”的绝对方向。图上的“邻域”仅由边定义，具有高度异质性：一个顶点的邻居数（度）可从1到数万不等。 4. 稀疏且长程依赖：尽管图通常稀疏，但信息可通过多跳路径传播，存在长程依赖（Long-range Dependencies）。例如，在社交网络中，一个用户可能受三度外好友的影响。传统CNN受限于感受野大小，难以直接捕获此类依赖。

下表对比了图数据与典型欧几里得数据的核心差异：

| 特性 | 图像（网格） | 文本（序列） | 图（非欧几里得） | | :--- | :--- | :--- | :--- | | 结构 | 规则2D/3D网格 | 1D序列 | 任意拓扑 | | 顺序 | 固定像素序 | 固定词序 | 顶点排列无关 | | 邻域定义 | 固定大小窗口（如3×3） | 前后固定窗口 | 由边定义的动态邻居集 | | 平移不变性 | 强（卷积核滑动） | 弱（位置编码） | 无（需图同构网络） | | 输入尺寸 | 固定（经裁剪/填充） | 可变（经填充/截断） | 天然可变 | | 核心操作 | 卷积（局部、平移） | 循环/自注意力（时序） | 消息传递（邻域聚合） |

2.2.3 范式转换的启示：从“数据驱动”到“结构驱动”

上述差异意味着，处理图数据不能简单套用CNN/RNN的“通用特征提取器”思路，而必须将图结构本身作为模型设计的核心约束。这引发了三重范式转换： 1. 从网格卷积到图卷积：CNN的卷积操作依赖于规则的网格邻接关系。在图语境下，“卷积”需重新定义为在图结构引导下的邻域聚合（Neighborhood Aggregation），即每个顶点将其邻居的特征信息变换、汇总，以更新自身表示。这催生了谱域图卷积（基于图傅里叶变换）与空域图卷积（基于消息传递）两大流派。 2. 从参数共享到结构共享：CNN的权值共享源于平移不变性。图中无平移操作，但存在图同构（Graph Isomorphism）下的结构不变性：若两个图同构，则任何结构感知的模型应产生同构的顶点表示。这引导出图同构网络（GIN）等模型，追求达到图同构测试的表达能力上限。 3. 从固定计算图到动态计算图：传统DNN的计算图（层间连接）是静态预定义的。在图神经网络中，聚合操作的计算图直接由输入图的拓扑结构决定——每个顶点的计算图是其多跳邻居子图。这意味着对于不同输入图，模型的前向传播计算图动态变化，这对自动微分与GPU并行计算提出了特殊挑战。

这一范式转换的深层意义在于：图神经网络将“结构”从背景数据提升为第一类对象，模型不仅学习特征表示，更学习如何根据给定的关系结构进行推理。这为处理关系密集型任务提供了统一的框架。

---

2.3 图的基本类型学及其对模型设计的影响

图的形态多样性直接影响模型架构的选择。本节系统分类图的属性，并分析其对GNN设计的约束。

2.3.1 有向图 vs. 无向图

• **无向图**：边无方向，邻接矩阵对称。大多数早期GNN（如GCN、GraphSAGE）默认处理无向图，简化了邻域聚合（邻居集合仅需去重）。对称性也利于谱方法中实特征值的计算。
• **有向图**：边具有方向，邻接矩阵非对称。方向编码了因果、流动或依赖关系（如引用网络、信息流图）。处理有向图的关键挑战在于：**如何定义“邻居”**。常见策略：
• 忽略方向，将出邻居与入邻居同等对待（可能丢失语义）。
• 分别聚合入邻居与出邻居信息，再融合（如RGCN、GAT variants）。
• 引入**边方向作为特征**，或为不同方向设计不同变换矩阵。
• 使用**随机游走**，其转移概率矩阵 $\mathbf{P} = \mathbf{D}^{-1}\mathbf{A}$ 天然处理有向图。

2.3.2 加权图 vs. 无权图

• **无权图**：边仅存在与否，邻接矩阵元素为0/1。聚合时通常对邻居特征取平均或求和。
• **加权图**：边权重 $w_{ij} > 0$ 量化关系强度。权重应如何融入聚合？
• **加权平均/求和**：$\mathbf{h}_v^{(k+1)} = \sigma\left( \sum_{u \in