Ch12 §02 图论 · 讲解稿¶
章节定位: Ch12 数学地基。教"图 = 节点 + 边"的代数表示 (邻接矩阵 / 度矩阵 / 拉普拉斯) 与图论核心算法 (BFS / Dijkstra / PageRank / 谱方法)。 承接: §01 GDL 范式 → §02 图的数学表示 走向: §03 GNN 用本节拉普拉斯做谱图卷积, §04 GAT 在此基础上加注意力 篇幅: ~4200 字 / 阅读 12 分钟 / 讲解 25-30 分钟
一 · 一句话总览¶
图论 = 用矩阵 (邻接矩阵 \(A\)、度矩阵 \(D\)、拉普拉斯 \(L=D-A\)) 与算法 (BFS、Dijkstra、PageRank、谱方法) 描述"实体 + 关系"的非欧数据结构。
二 · 心智模型¶
把图想成两种视角:
- 组合视角: \(G = (V, E)\), 节点 + 边 (适合算法)
- 代数视角: 邻接矩阵 \(A\) + 度矩阵 \(D\) + 拉普拉斯 \(L\) (适合矩阵运算 / GNN)
两种视角互通。组合 → 代数 (邻接矩阵); 代数 → 性质 (\(A^k\) 计数 \(k\) 跳路径数)。
三 · 章节主线 (5 段)¶
第 1 段 · 图的基本概念 (8 分钟)¶
3.1.1 节点与边¶
- 节点 (vertex) = 实体: 人、原子、城市、网页、神经元
- 边 (edge) = 关系: 友谊、化学键、道路、超链接、突触
3.1.2 邻接矩阵¶
三角图 (3 个节点, 全连接) 的 \(A\):
关键: 节点编号 1, 2, 3 → 第 1 行表示节点 1 与其他节点的连接。
幂运算: \(A^2_{ij}\) = 节点 \(i\) 到 \(j\) 经过 2 跳的路径数。
特征矩阵: \(X \in \mathbb{R}^{n \times d}\), 每行是一个节点的 \(d\) 维特征向量。
边特征: 边 \((i,j)\) 可有特征 \(e_{ij} \in \mathbb{R}^{d_e}\), 例如化学键类型、距离、关系类型。
第 2 段 · 图的类型 (8 分钟)¶
| 类型 | 描述 | 例子 |
|---|---|---|
| 无向图 | 边对称, \(A = A^T\) | 友谊、化学键 |
| 有向图 | 边有方向, \(A\) 不对称 | Twitter 关注、网页超链接 |
| 加权图 | \(A_{ij} = w_{ij}\) 实数 | 道路距离、相关性 |
| 二部图 | 节点分两组, 仅组间有边 | 用户-商品 (推荐) |
| 多图 | 两节点可有多个边 | 知识图谱 (多关系) |
| 超图 | 边连 > 2 节点 | 论文-作者 (多对一) |
| 完全图 \(K_n\) | 每对节点都连 | Transformer 全连接 |
完全图 ≈ Transformer: \(K_n\) 是 \(n\) 节点完全连接, 每个节点关注所有其他节点 — 等价于 Transformer 全连接注意力。
二部图:
块对角结构, 用于推荐 (用户-商品) 等。
第 3 段 · 度、路径与连通性 (8 分钟)¶
3.3.1 度¶
度矩阵 \(D\) = 对角矩阵, \(D_{ii} = d_i\)。
高 \(d_i\) = 节点 \(i\) 是 hub (中心节点, 社交网络中"网红")。
3.3.2 路径与最短路¶
路径 \(i \to v_1 \to v_2 \to \dots \to j\) = 节点序列, 每相邻对有边。
最短路 = 边数最少 (或权重总和最低) 的路径。
Dijkstra: 单源最短路, \(O((|V|+|E|) \log |V|)\) (用堆)。
3.3.3 连通性¶
- 连通图: 任意两节点都有路径
- 连通分量: 极大连通子图
- 直径: 最长最短路径长度
- 六度分隔: 社交网络直径 ≈ 6
3.3.4 中心性 (Centrality)¶
| 度量 | 定义 | 应用 |
|---|---|---|
| 度中心性 | \(d_i\) | Twitter 网红 |
| 介数中心性 | 经过 \(i\) 的最短路数 | 交通枢纽 |
| 特征向量中心性 | \(A \mathbf{x} = \lambda \mathbf{x}\) | 学术引用 |
| PageRank | 修正的特征向量中心性 | Google 搜索 |
PageRank 公式:
其中 \(d = 0.85\) (阻尼系数)。
PageRank 是 GNN 的特例: 邻居归一化求和 + 多次迭代 = K 层 GNN。
3.3.5 树与圈¶
- 圈 (cycle): 起点 = 终点的路径
- 树: 无圈连通图, \(n\) 节点 \(n-1\) 边
第 4 段 · 图拉普拉斯矩阵 (10 分钟)¶
图拉普拉斯是 GNN 数学基础。
3.4.1 定义¶
三角图:
3.4.2 性质¶
| 性质 | 说明 |
|---|---|
| 对称 | \(L^T = L\) (实对称) |
| 半正定 | \(x^T L x \geq 0\), 特征值 \(\geq 0\) |
| 零特征值数 = 连通分量数 | 反映图连通性 |
| 每行和 = 0 | \(L \mathbf{1} = \mathbf{0}\) |
二次型 \(x^T L x\) = \(\sum_{(i,j) \in E} (x_i - x_j)^2\), 衡量节点值的"平滑度"。
3.4.3 归一化拉普拉斯¶
特征值 \(\in [0, 2]\)。GCN (§03) 用 \(\tilde L\) 作为卷积算子。
3.4.4 谱图理论¶
\(L\) 特征分解: \(L = U \Lambda U^T\), \(U\) 是特征向量矩阵, \(\Lambda\) 是特征值对角。
| 特征值 | 含义 |
|---|---|
| \(\lambda_0 = 0\) | 常数特征向量 (连通图) |
| 小 \(\lambda\) | 平滑 (邻居值相近) |
| 大 \(\lambda\) | 振荡 (邻居值差异大) |
谱图卷积 (Ch12 §03 ChebNet 用): \(f\) 在图上的"卷积" = \(U g(\Lambda) U^T f\), 其中 \(g\) 是频域滤波器。
第 5 段 · 实践 (10 分钟)¶
3.5.1 Python 计算图的中心性¶
import networkx as nx
G = nx.karate_club_graph()
# 度中心性
deg_cent = nx.degree_centrality(G)
top_deg = sorted(deg_cent.items(), key=lambda x: -x[1])[:5]
# 介数中心性
bet_cent = nx.betweenness_centrality(G)
top_bet = sorted(bet_cent.items(), key=lambda x: -x[1])[:5]
# PageRank
pr = nx.pagerank(G, alpha=0.85)
top_pr = sorted(pr.items(), key=lambda x: -x[1])[:5]
print("Top 5 by degree:", top_deg)
print("Top 5 by PageRank:", top_pr)
3.5.2 拉普拉斯与谱分解¶
import numpy as np
import scipy.sparse as sp
# 邻接矩阵
A = np.array([[0, 1, 1], [1, 0, 1], [1, 1, 0]])
D = np.diag(A.sum(axis=1))
L = D - A
# 归一化拉普拉斯
D_inv_sqrt = np.diag(1.0 / np.sqrt(D.diagonal()))
L_norm = np.eye(3) - D_inv_sqrt @ A @ D_inv_sqrt
# 特征分解
eigenvalues, eigenvectors = np.linalg.eigh(L_norm)
print("Eigenvalues:", eigenvalues)
# 应在 [0, 2] 范围
3.5.3 谱图卷积示意¶
import torch
# 简单谱卷积: 给定低频滤波器
def spectral_filter(x, U, lambda_threshold=0.5):
"""只保留低频分量"""
lambda_ = torch.tensor([0.1, 0.3, 1.5]) # 假设特征值
g_lambda = (lambda_ < lambda_threshold).float()
# 频域滤波
x_freq = U.T @ x
x_filtered = U @ (g_lambda.unsqueeze(-1) * x_freq)
return x_filtered
# 物理意义: 滤掉"邻居值差异大"的高频信号, 保留"邻居值相近"的低频
3.5.4 Dijkstra 验证¶
import heapq
def dijkstra(graph, start):
"""graph: {node: [(neighbor, weight), ...]}"""
dist = {node: float('inf') for node in graph}
dist[start] = 0
pq = [(0, start)]
while pq:
d, u = heapq.heappop(pq)
if d > dist[u]:
continue
for v, w in graph[u]:
if d + w < dist[v]:
dist[v] = d + w
heapq.heappush(pq, (dist[v], v))
return dist
# 测试
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('C', 2), ('D', 5)],
'C': [('D', 1)],
'D': []
}
print(dijkstra(graph, 'A'))
# {'A': 0, 'B': 1, 'C': 3, 'D': 4}
四 · 易错点 (6 条)¶
- 邻接矩阵对角线: 默认 0 (无自环), 加自环用 \(\tilde A = A + I\)。
- 拉普拉斯符号: \(L = D - A\), 不是 \(A - D\)。
- PageRank 阻尼: \(d = 0.85\) 是经验值, 太大会震荡, 太小会不收敛。
- 特征向量中心性 vs PageRank: 后者用有向图 + 阻尼, 前者直接用 \(A \mathbf{x} = \lambda \mathbf{x}\)。
- 完全图 \(K_n\) 的边数: \(\binom{n}{2} = n(n-1)/2\), 不是 \(n\)。
- 图谱分解: \(L\) 谱半径 ≤ 2 (归一化), 不是任意大。
五 · 跨章连接¶
| 章节 | 关联 |
|---|---|
| Ch02 §04 矩阵论 | 邻接矩阵、特征分解、二次型 \(x^T L x\) |
| Ch04 §04 假设检验 | 随机游走 / PageRank 收敛检验 |
| Ch05 §04 贝叶斯 | 图模型 (Bayesian Network) |
| Ch07 §04 Transformer | 完全图注意力 |
| Ch14 §04 图算法 | Dijkstra, Bellman-Ford, BFS/DFS 详解 |
六 · 自测 5 题¶
- 邻接矩阵 \(A\) 与度矩阵 \(D\) 的关系?
- 拉普拉斯 \(L = D - A\), 它有什么性质?
- Dijkstra 与 BFS 的复杂度?
- PageRank 公式与 GNN 关系?
- 归一化拉普拉斯特征值范围?
七 · 一句话总结¶
图论 = 用矩阵 + 算法描述非欧关系数据。邻接矩阵 \(A\)、度矩阵 \(D\)、拉普拉斯 \(L = D-A\) 是三个核心矩阵; BFS、Dijkstra、PageRank、谱方法是四个核心算法。Ch12 §03 GNN 将用这套数学工具定义"图卷积"。
八 · 板书建议¶
[板书 1: 图的代数表示]
A = 邻接 (n×n, 对称当无向)
D = 度 (对角)
L = D - A (拉普拉斯)
[板书 2: PageRank]
p_i = (1-d)/N + d Σ p_j / d_j^out
d = 0.85, 阻尼
[板书 3: 归一化拉普拉斯]
L̃ = I - D^{-1/2} A D^{-1/2}
λ ∈ [0, 2]
[板书 4: 谱分解]
L = UΛU^T
谱图卷积 = U g(Λ) U^T
九 · 参考资料¶
- "Networks, Crowds, and Markets" (Easley & Kleinberg)
- Ch02 矩阵论 (本套书)
- "Spectral Graph Theory" (Dan Spielman, Yale 教材)
- PageRank 原始论文: Brin & Page, 1998
- PyTorch Geometric 文档
- Ch14 §04 图算法 (本套书)