第1章：图论基础与数学 preliminaries (Chapter 1: Fundamentals of Graph Theory and Mathematical Preliminaries)
图（Graph）是描绘事物之间关系的最自然、最通用的数学结构。从社交网络中的好友关系、万维网的链接结构，到分子中的原子连接、交通网络中的路径规划，图数据无处不在。理解图的基本概念与数学工具，是掌握图神经网络（Graph Neural Networks, GNNs）的基石。本章将系统性地构建这一基石，我们将从图的最基本定义出发，逐步深入其矩阵表示、核心算子（如拉普拉斯矩阵）的谱性质，再到经典的图遍历算法，最后触及图嵌入的初步思想。我们的目标不仅是定义这些概念，更是通过数学推导、代码实现和可视化，让你真切地理解图结构的内在数学语言，为后续GNN模型的学习扫清障碍。
---
1.1 图的定义与基本术语
1.1.1 图的数学定义
在图论中，一个图 $G$ 被定义为一个有序对 $G = (V, E)$，其中：
- $V$ 是**顶点**（Vertex）或**节点**（Node）的集合，$|V| = n$ 表示图的节点数量。
- $E$ 是**边**（Edge）的集合，$|E| = m$ 表示图的边数量。每条边 $e \in E$ 连接两个顶点，表示为无序对 $e = (u, v)$（无向图）或有序对 $e = (u, v)$（有向图）。
形式化定义：
- **无向图**：$G = (V, E)$，其中 $E \subseteq \{ \{u, v\} | u, v \in V, u \neq v \}$。边没有方向，$\{u, v\}$ 与 $\{v, u\}$ 表示同一条边。
- **有向图**：$G = (V, E)$，其中 $E \subseteq \{ (u, v) | u, v \in V, u \neq v \}$。边有方向，从源节点 $u$ 指向目标节点 $v$。
- **加权图**：每条边 $e$ 关联一个**权重** $w_e \in \mathbb{R}$，表示连接的强度或成本。权重可以是正数、负数或零。
示例：一个简单的社交网络可以建模为无向图，节点代表人，边代表“好友关系”。一个网页链接网络则是有向图，节点代表网页，边代表超链接。一个分子结构图可以是加权图，边代表化学键，权重代表键能或距离。
1.1.2 节点的度与邻域
- **度**（Degree）：对于无向图中的节点 $v$，其度 $d_v$ 是与 $v$ 相连的边的数量。对于有向图，分为**出度**（Out-degree，从 $v$ 发出的边数）和**入度**（In-degree，指向 $v$ 的边数）。
- **邻域**（Neighborhood）：节点 $v$ 的邻域 $N(v)$ 是与 $v$ 直接相连的所有节点的集合。在加权图中，有时会考虑加权邻域。
公式表示： 对于无向图的邻接矩阵 $A$（后文详述），节点 $i$ 的度可计算为： $$d_i = \sum_{j=1}^{n} A_{ij}$$ 即邻接矩阵第 $i$ 行的和（或列和，因为无向图 $A$ 对称）。
1.1.3 图的类型
- **简单图**（Simple Graph）：无自环（self-loop，即 $(v, v) \notin E$）且无多重边（multiedge，即任意两个节点间最多一条边）。
- **多重图**（Multigraph）：允许两个节点之间存在多条边。
- **自环图**（Graph with Self-loops）：允许边连接同一节点。
- **连通图**（Connected Graph）：无向图中任意两个节点间都存在路径。
- **强连通图**（Strongly Connected Graph）：有向图中任意两个节点 $u$ 和 $v$，都存在从 $u$ 到 $v$ 和从 $v$ 到 $u$ 的路径。
- **二分图**（Bipartite Graph）：节点集可划分为两个不相交子集 $U$ 和 $W$，使得每条边都连接一个 $U$ 中的节点和一个 $W$ 中的节点。
理解要点：GNN 通常处理的是简单图或带自环的图，但现代GNN设计（如GAT、Graph Transformer）也能处理带边权重的图。识别图的类型直接影响后续矩阵表示和算法选择。
---
1.2 图的矩阵表示
将图结构转化为矩阵形式是进行代数运算和算法实现的关键。最核心的矩阵包括邻接矩阵、度矩阵和拉普拉斯矩阵。
1.2.1 邻接矩阵
邻接矩阵 $A$ 是描述图结构最直接的矩阵表示。它是一个 $n \times n$ 的矩阵，其中元素 $A_{ij}$ 表示节点 $i$ 和节点 $j$ 之间边的存在性及权重。
定义： $$ A_{ij} = \begin{cases} w_{ij} & \text{if } (i, j) \in E \text{ (或 } \{i, j\} \in E \text{ for undirected)} \\ 0 & \text{otherwise} \end{cases} $$
性质：
- 无向图：$A$ 是对称矩阵，$A = A^\top$。
- 有向图：$A$ 一般不对称。
- 无权图：$A_{ij} \in \{0, 1\}$。
- 自环：若允许自环，则对角线元素 $A_{ii}$ 可能非零。
- 多重边：标准邻接矩阵不直接表示多重边，通常需要扩展（如用数值表示边数）。
代码示例：使用 NetworkX 创建图并获取邻接矩阵。 ```python import networkx as nx import numpy as np
创建一个无向图
G = nx.Graph() G.add_nodes_from([1, 2, 3, 4]) G.add_edges_from([(1, 2), (1, 3), (2, 3), (3, 4)])
获取邻接矩阵（以NumPy数组形式）
A = nx.adjacency_matrix(G).toarray() print("邻接矩阵 A:\n", A)
输出:
[[0. 1. 1. 0.]
[1. 0. 1. 0.]
[1. 1. 0. 1.]
[0. 0. 1. 0.]]
```
可视化：邻接矩阵可以可视化为热力图，直观显示节点间的连接模式。 ```mermaid graph TD A[节点1] --> B[节点2] A --> C[节点3] B --> C C --> D[节点4] ``` *图 1.1: 示例无向图结构，对应上述邻接矩阵。*
1.2.2 度矩阵
度矩阵 $D$ 是一个对角矩阵，其对角线元素为对应节点的度。
定义： $$D = \text{diag}(d_1, d_2, \dots, d_n)$$ 其中 $d_i = \sum_{j=1}^{n} A_{ij}$。
性质：
- 无向图：$D$ 是对角矩阵。
- 有向图：通常使用出度矩阵或入度矩阵，或分别构建。
- 在加权图中，度是邻接权重之和：$d_i = \sum_{j} A_{ij}$。
代码示例： ```python
计算度矩阵
degrees = np.sum(A, axis=1) # 按行求和得到度 D = np.diag(degrees) print("度矩阵 D:\n", D)
输出:
[[2. 0. 0. 0.]
[0. 2. 0. 0.]
[0. 0. 3. 0.]
[0. 0. 0. 1.]]
```
1.2.3 拉普拉斯矩阵
拉普拉斯矩阵（Laplacian Matrix）是图论和谱图理论的核心，它综合了邻接矩阵和度矩阵的信息，其谱性质（特征值、特征向量）深刻反映了图的结构特性。
标准拉普拉斯矩阵 $L$ 定义为： $$L = D - A$$
性质： 1. 对称性：对于无向图，$L$ 是对称矩阵。 2. 行和为零：$L \mathbf{1} = \mathbf{0}$，其中 $\mathbf{1}$ 是全1向量。这意味着 $\mathbf{1}$ 是 $L$ 的一个特征值为0的特征向量。 3. 半正定性：$L$ 是半正定矩阵，所有特征值 $\lambda_i \ge 0$。 4. 零特征值的重数：等于图的连通分量数量。若图连通，则 $\lambda_1 = 0$ 是单重特征值。
代码示例： ```python L = D - A print("拉普拉斯矩阵 L:\n", L)
输出:
[[ 2. -1. -1. 0.]
[-1. 2. -1. 0.]
[-1. -1. 3. -1.]
[ 0. 0. -1. 1.]]
```
归一化拉普拉斯矩阵：为了消除节点度差异的影响，常使用归一化版本。
- **对称归一化拉普拉斯矩阵**：
$$L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}$$
- **随机游走归一化拉普拉斯矩阵**：
$$L_{rw} = D^{-1} L = I - D^{-1} A$$
性质：
- $L_{sym}$ 对称，特征值在 $[0, 2]$ 区间。
- $L_{rw}$ 非对称，但与 $L$ 有相同的特征值（相似变换）。
代码示例： ```python
对称归一化
D_inv_sqrt = np.diag(1.0 / np.sqrt(degrees)) L_sym = np.eye(n) - D_inv_sqrt @ A @ D_inv_sqrt
随机游走归一化
D_inv = np.diag(1.0 / degrees) L_rw = np.eye(n) - D_inv @ A
print("对称归一化拉普拉斯矩阵 L_sym:\n", L_sym) print("随机游走归一化拉普拉斯矩阵 L_rw:\n", L_rw) ```
1.2.4 拉普拉斯矩阵的谱性质
谱（Spectrum）指矩阵的所有特征值。拉普拉斯矩阵的谱蕴含丰富的图结构信息。
关键定理： 1. 特征值非负：$\lambda_i(L) \ge 0$。 2. 零特征值：$\lambda_1 = 0$，对应特征向量 $\mathbf{1}$。 3. 代数连通度（Algebraic Connectivity）：第二小特征值 $\lambda_2$（称为Fiedler值）衡量图的连通性。$\lambda_2 > 0$ 当且仅当图连通。$\lambda_2$ 越大，图越“紧密”连通。 4. 连通分量数：零特征值的重数等于图的连通分量数 $k$。 5. 图分割：对应于 $\lambda_2$ 的特征向量（Fiedler向量）可用于将图二分（如谱聚类）。
示例分析：考虑两个图——一个连通环图（Cycle）和一个断开的两部分图。 ```python
环图（6个节点成环）
G_cycle = nx.cycle_graph(6) A_cycle = nx.adjacency_matrix(G_cycle).toarray() D_cycle = np.diag(np.sum(A_cycle, axis=1)) L_cycle = D_cycle - A_cycle eigvals_cycle = np.linalg.eigvalsh(L_cycle) # 计算对称矩阵特征值，排序 print("环图拉普拉斯特征值:", np.sort(eigvals_cycle))
断开的两部分（每部分3个节点完全连接，两部分间无连接）
G_disconnected = nx.disjoint_union(nx.complete_graph(3), nx.complete_graph(3)) A_disc = nx.adjacency_matrix(G_disconnected).toarray() D_disc = np.diag(np.sum(A_disc, axis=1)) L_disc = D_disc - A_disc eigvals_disc = np.linalg.eigvalsh(L_disc) print("断开图拉普拉斯特征值:", np.sort(eigvals_disc)) ``` 输出分析：
- 环图（连通）：特征值近似为 $[0, 1, 1, 2, 3, 4]$（精确值取决于节点数）。$\lambda_2 \approx 0.585$（对于6环）。
- 断开图：特征值为 $[0, 0, 3, 3, 6, 6]$。零特征值重数为2，对应两个连通分量。
可视化：绘制拉普拉斯特征值分布图。 ```mermaid xychart-beta title "拉普拉斯矩阵特征值分布对比" x-axis "特征值索引" [1, 2, 3, 4, 5, 6] y-axis "特征值大小" 0 --> 6 line "连通环图" [0, 0.585, 1, 2, 3, 4] line "断开图" [0, 0, 3, 3, 6, 6] ``` *图 1.2: 两个图的拉普拉斯特征值排序对比。断开图在索引1和2处有零特征值，表明两个连通分量。*
实践意义：在GNN中，拉普拉斯矩阵的谱分解常用于设计图卷积滤波器（如ChebNet）、理解图信号平滑性，以及设计图池化（Pooling）操作。
---
1.3 图遍历算法：BFS与DFS
图遍历是探索图结构的基础算法，为许多图算法（如最短路径、连通分量检测）提供基础。两种经典遍历方法是广度优先搜索（BFS）和深度优先搜索（DFS）。
1.3.1 广度优先搜索
BFS 从起始节点出发，逐层访问其所有邻居，再访问邻居的邻居，依此类推。它使用队列（先进先出）来管理待访问节点。
算法步骤： 1. 将起始节点 $s$ 入队，标记为已访问。 2. 当队列非空：
- 出队一个节点 $u$。
- 访问 $u$。
- 将 $u$ 所有未访问的邻居入队，并标记为已访问。
性质：
- 找到的路径是从起始节点到目标节点的**最短路径**（边数最少），前提是边权为1。
- 时间复杂度：$O(n + m)$，其中 $n$ 为节点数，$m$ 为边数。
- 空间复杂度：$O(n)$（队列和访问标记）。
代码示例： ```python from collections import deque
def bfs(graph, start): visited = set() queue = deque([start]) visited.add(start) order = [] # 记录访问顺序
while queue: node = queue.popleft() order.append(node) for neighbor in graph.neighbors(node): if neighbor not in visited: visited.add(neighbor) queue.append(neighbor) return order
在之前的图G上运行
G = nx.Graph() G.add_edges_from([(1,2), (1,3), (2,3), (3,4)]) print("BFS访问顺序（从节点1开始）:", bfs(G, 1))
输出可能为 [1, 2, 3, 4] 或 [1, 3, 2, 4]，取决于邻居遍历顺序
```
可视化：BFS的层次结构。 ```mermaid graph TD A[1: 第0层] --> B[2: 第1层] A --> C[3: 第1层] B --> D[4: 第2层] C --> D ``` *图 1.3: BFS从节点1开始的层次遍历示意图。节点1为第0层，节点2、3为第1层，节点4为第2层。*
1.3.2 深度优先搜索
DFS 从起始节点出发，沿着一条路径深入探索，直到到达末端，然后回溯到上一个分叉点继续探索。它使用栈（后进先出）实现，通常用递归。
算法步骤（递归版）： 1. 访问当前节点 $u$，标记为已访问。 2. 对 $u$ 的每个未访问邻居 $v$，递归调用 DFS($v$)。
性质：
- 不保证最短路径。
- 常用于检测环、拓扑排序、寻找连通分量。
- 时间复杂度：$O(n + m)$。
- 空间复杂度：$O(n)$（递归栈深度）。
代码示例： ```python def dfs(graph, node, visited=None, order=None): if visited is None: visited = set() order = [] visited.add(node) order.append(node) for neighbor in graph.neighbors(node): if neighbor not in visited: dfs(graph, neighbor, visited, order) return order
print("DFS访问顺序（从节点1开始）:", dfs(G, 1))
可能输出 [1, 2, 3, 4] 或 [1, 3, 4, 2] 等，取决于邻居顺序
```
可视化：DFS的一条可能路径。 ```mermaid graph TD A[1] --> B[2] B --> C[3] C --> D[4] ``` *图 1.4: DFS可能的一条路径：1 → 2 → 3 → 4。*
1.3.3 BFS与DFS对比
| 特性 | BFS | DFS | | :--- | :--- | :--- | | 数据结构 | 队列 | 栈（递归） | | 路径 | 最短路径（无权图） | 不保证最短 | | 内存 | 可能较宽，存储整层节点 | 可能较深，存储一条路径 | | 典型应用 | 最短路径、层次遍历 | 环检测、拓扑排序、连通分量 | | 完成时间 | 可能较早找到目标（