title

图论

aliases

Graph Theory

图论（Graph Theory）：从离散关系到 AI 结构归纳偏置

上帝视角：如果线性代数处理的是“量”，拓扑与几何处理的是“形”，那么图论处理的就是“关系”。现实世界里，大量 AI 对象并不是整齐排列在欧几里得网格上的，而是由节点与连接构成的关系系统：社交网络、知识图谱、分子结构、代码调用图、交通网络、推荐系统都属于这一类。图论提供了描述这些结构的最小语言，而图神经网络、谱方法、知识图谱推理则把这种语言变成了现代 AI 的可学习框架。

1. 上帝视角：为什么 AI 需要图论

很多 AI 教科书默认数据是向量、矩阵、张量，因此天然适合放进欧几里得空间里处理。但现实中的很多任务并不是“一个样本 = 一个定长向量”，而是：

对象之间本身有显式关系，例如用户与商品、蛋白质与蛋白质、论文与引用；
结构是稀疏的，只有少数局部连接真正重要；
节点数量可变，且顺序通常没有语义；
任务目标并不只依赖单个对象本身，还依赖它与邻域、社区、路径和整体结构的关系。

图论正好回答这些问题。一个图 $G = (V, E)$ 用极简的方式把“对象”写成节点，把“关系”写成边，于是 AI 可以显式建模：

局部交互：一个节点主要受哪些邻居影响；
全局结构：网络是否分成社区、是否存在桥接节点、是否呈现层级结构；
关系组合：两步关系、三步关系是否暗含更深层语义；
离散归纳偏置：模型应当对节点重排不敏感，而对连边变化敏感。

1.1 一个直观例子：推荐系统为什么天然是图问题

设想一个电影推荐系统。把“用户”与“电影”分别看作两类节点，把“看过 / 点赞 / 收藏”看作边，就得到一个二部图（bipartite graph）：

用户 A ── 喜欢 ── 电影 1
用户 A ── 喜欢 ── 电影 3
用户 B ── 喜欢 ── 电影 2
用户 B ── 喜欢 ── 电影 3

如果只看用户 A 的向量，很难知道他是否会喜欢电影 2；但如果把关系图考虑进来，就会发现：

A 和 B 都喜欢电影 3；
B 喜欢电影 2；
因而电影 2 对 A 可能是潜在推荐。

这不是传统“样本独立同分布”视角下自然出现的信息，而是图结构额外提供的关系推断能力。

1.2 图论带给 AI 的四种核心价值

价值	图论语言	AI 中的体现
关系表达	节点、边、路径、子图	知识图谱、分子图、社交网络
结构归纳偏置	置换不变、局部传播	GNN、图 Transformer、消息传递
组合推理	多跳路径、连通性、图匹配	推荐、问答、程序分析
可解释结构	社区、桥、中心性、割	网络分析、风险传播、故障诊断

2. 历史脉络

图论的历史很像 AI 自身的缩影：先从一个看似玩具化的离散问题出发，再逐步演化为连接算法、网络、学习和推理的通用语言。

2.1 Euler 与图论的起点（1736）

Leonhard Euler 在研究柯尼斯堡七桥问题时，第一次把现实中的连通问题抽象成节点与边：

陆地被视为顶点（vertex）
桥被视为边（edge）
问题被化为“是否存在经过每条边恰好一次的路径”

Euler 证明了答案是否定的。更重要的是，他展示了一个方法论转折：很多关于空间和路径的问题，真正重要的不是精确长度，而是连接关系本身。

这一思想后来在 19 世纪与 20 世纪上半叶逐步发展为欧拉路径、欧拉回路及系统化图论研究，并被普遍视为图论的历史起点。

2.2 19 世纪：树、网络与电路

19 世纪的图论开始与更具体的工程问题结合：

Kirchhoff (1847) 用生成树与矩阵方法分析电路网络；
Cayley (1857) 系统研究树（tree），为化学结构与枚举问题提供工具；
Hamilton 研究哈密顿路径问题，推动了遍历类问题的发展。

这里已经能看到后来 AI 会反复重演的结构：图不只是数学对象，它还是复杂系统的抽象骨架。

2.3 20 世纪：算法图论成熟

20 世纪图论从“有趣的问题集合”走向“有系统的方法论”：

Hall (1935) 的婚配定理推动匹配理论；
König (1936) 的专著帮助图论系统化；
Dijkstra (1959) 提出最短路径算法；
Ford-Fulkerson (1956) 建立最大流框架；
Fiedler (1973) 推动谱图理论，让拉普拉斯特征值与图结构性质建立联系。

从这里开始，图论不再只是离散数学的一支，而成为算法设计、网络分析、组合优化的基础语言。

2.4 互联网与知识网络时代

1990 年代以后，大规模网络数据让图论重新站到中心位置：

Web 被看作超大有向图；
PageRank (1998) 用随机游走和谱思想衡量网页重要性；
社交网络分析引入中心性、社区发现、传播动力学；
生物信息学把蛋白质相互作用、代谢网络和分子结构都写成图。

这一阶段的关键变化是：图不再只是“需要偶尔求解的结构”，而是数据本身的自然形态。

2.5 图学习时代

进入深度学习时代后，研究者开始尝试把卷积、表示学习和关系推理推广到图结构：

Bruna et al. (2014) 提出早期谱图卷积框架；
Defferrard et al. (2016) 用 Chebyshev 多项式近似谱滤波器；
Kipf & Welling (2017) 提出图卷积网络（GCN）；
Gilmer et al. (2017) 将分子学习统一为消息传递神经网络（MPNN）；
Veličković et al. (2018) 提出图注意力网络（GAT）。

从此，图论不再只是“为 AI 提供算法工具”，而是直接决定模型架构如何设计。

3. 核心知识点详解

3.1 图的基本对象与矩阵表示

一个图记作：

$$ G = (V, E) $$

其中：

$V$ 是节点集合；
$E$ 是边集合；
若边有方向，则为有向图；
若边带权重，则为加权图；
若节点可分成不同类型，则形成异构图；
若一条关系可同时连接多个节点，则可扩展到超图。

在 AI 中，最常用的是矩阵化表示。

邻接矩阵

若图有 $n$ 个节点，其邻接矩阵 $A \in \mathbb{R}^{n \times n}$ 定义为：

$$ A_{ij} = \begin{cases} 1, & (i,j) \in E \\ 0, & \text{otherwise} \end{cases} $$

加权图中，$A_{ij}$ 可以直接写成边权。

度矩阵

节点 $i$ 的度定义为：

$$ d_i = \sum_j A_{ij} $$

对应的度矩阵 $D$ 是对角矩阵：

$$ D = \operatorname{diag}(d_1, d_2, \dots, d_n) $$

其中：

$A_{ij}$ 表示节点 $i$ 与节点 $j$ 之间是否有边或边权大小；
$d_i$ 表示节点 $i$ 的连接数；
$D$ 把每个节点的局部连接强度压缩到对角线上。

一个极小示例

考虑 4 篇论文的引用关系，其中 1 与 2 都引用 3，3 又连接 4。可写成无向简化图：

1 ─ 3 ─ 4
2 ─┘

邻接矩阵为：

$$ A = \begin{bmatrix} 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{bmatrix} $$

这里节点 3 的度最高，因此它在传播信息时天然更像一个中介节点。这正是很多图学习任务里“结构重要性”比“单点特征”更关键的原因。

直觉理解

矩阵表示的价值在于：它把“谁和谁相连”从一张关系图，变成了可以直接送进线性代数与机器学习流程的对象。换句话说，图论把关系结构离散化，线性代数再把这种离散结构转成可计算对象。

AI 中的角色

图输入统一接口：知识图谱、分子图、推荐二部图都能统一成节点-边矩阵表示；
结构特征工程：度、邻居、子图、邻接关系常直接进入模型输入；
图算法前处理：很多图学习系统先做子图提取、采样或稀疏化，再进入训练。

3.2 路径、连通性与组合问题

图论的很多经典问题，后来都直接转化成 AI 系统中的基础算子。

路径与最短路

一条路径是节点序列：

$$ v_0 \to v_1 \to \cdots \to v_k $$

其中相邻节点之间都存在边。若每条边有代价 $w_{ij}$，则路径总代价为：

$$ \operatorname{cost}(P) = \sum_{(i,j)\in P} w_{ij} $$

最短路径问题广泛出现在：

机器人路径规划；
知识图谱多跳推理；
网络路由与资源调度；
程序分析中的依赖追踪。

连通性与社区

如果任意两个节点之间都有路径，则图是连通的。现实网络常常不是完全均匀连通，而是存在：

社区（community）
桥接节点（bridge node）
枢纽节点（hub）

这类结构在社交网络传播、风险扩散、推荐系统冷启动中都非常关键。

匹配、流与资源分配

许多看似“工程问题”的任务，其实是标准图论问题：

用户和服务器的分配是匹配问题；
物流、带宽、算力调度常可转写为最大流 / 最小割；
任务依赖图中的关键路径决定系统吞吐上限。

因此，图论不仅提供结构表示，也提供可执行的优化骨架。

直觉理解

如果说矩阵表示回答的是“图长什么样”，那么路径、流和匹配回答的是“图上能做什么”。很多 AI 系统中的搜索、调度和多跳推理，本质上都是在图上寻找一条可行且代价合理的结构路径。

AI 中的角色

搜索与规划：A*、最短路、路径约束查询直接支撑机器人与知识推理；
推荐与检索：多跳邻域扩展、候选召回和关系传播常依赖路径结构；
系统调度：资源分配、任务编排与依赖分析可转写为流和匹配问题。

3.3 图拉普拉斯与谱图方法

图学习里最核心的矩阵之一是图拉普拉斯矩阵：

$$ L = D - A $$

它把“局部连接关系”变成了一个可做线性代数分析的对象。

归一化拉普拉斯常写为：

$$ L_{\text{sym}} = I - D^{-1/2} A D^{-1/2} $$

为什么它重要

对任意向量 $f \in \mathbb{R}^n$，有：

$$ f^\top L f = \frac{1}{2}\sum_{i,j} A_{ij}(f_i-f_j)^2 $$

其中：

$f_i$ 表示节点 $i$ 上的信号值；
$A_{ij}$ 表示节点之间的连接强度；
当相邻节点的信号差异很大时，这个二次型会增大。

这个式子非常关键，因为它说明：

如果相邻节点取值相近，则该项更小；
如果相邻节点差异很大，则代价更高。

换句话说，$L$ 天然刻画了“图上的平滑性”。这使它成为：

谱聚类；
图正则化；
图信号处理；
谱图卷积

的统一入口。

直觉理解

图拉普拉斯可以粗略理解为“比较一个节点与其邻居是否协调”的算子。若一个信号在相邻节点之间变化很平缓，它更像图上的低频结构；若相邻节点差异剧烈，它更像高频扰动或噪声。

一个直觉例子

在论文引用图中，如果两篇相邻论文的主题表示差异极大，那么图拉普拉斯对应的平滑代价会变大。谱方法因此倾向于把高频噪声压下去，保留更符合图结构的低频信号。

AI 中的角色

谱聚类：利用拉普拉斯特征向量发现社群和簇结构；
图正则化：约束相邻节点表示不要无端剧烈波动；
图卷积基础：谱方法是早期 GNN 与图信号处理的重要理论来源。

3.4 从图卷积到消息传递

图神经网络的核心思想并不神秘：节点通过边从邻居那里接收信息，再更新自己的表示。

GCN 的基本形式

Kipf 与 Welling (2017) 的图卷积网络写成：

$$ H^{(l+1)} = \sigma\left(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)}\right) $$

其中：

$\tilde{A}=A+I$ 表示加入自环；
$\tilde{D}$ 是对应的度矩阵；
$H^{(l)}$ 是第 $l$ 层节点表示；
$W^{(l)}$ 是可学习参数。

这可以理解为三步：

每个节点把自己的表示和邻居表示汇总；
用归一化避免高度节点过度放大；
用线性变换和非线性激活得到下一层表示。

MPNN 的统一表达

更一般地，消息传递神经网络可写成：

$$ m_i^{(l+1)}=\sum_{j\in\mathcal{N}(i)} M^{(l)}(h_i^{(l)}, h_j^{(l)}, e_{ij}) $$

$$ h_i^{(l+1)} = U^{(l)}(h_i^{(l)}, m_i^{(l+1)}) $$

这里：

$M$ 是消息函数；
$U$ 是更新函数；
$e_{ij}$ 可包含边类型、权重或时间信息。

GCN、GraphSAGE、GAT、分子图网络都可以视为这个框架的特例。

一个具体例子：分子图

在分子性质预测中：

节点 = 原子；
边 = 化学键；
节点特征 = 原子序数、价电子、杂化状态；
边特征 = 单键 / 双键 / 芳香键等。

每一层消息传递都在做“局部化学环境汇总”，最后得到整个分子的图表示，用于预测毒性、溶解度或结合活性。

直觉理解

消息传递的本质很像“节点之间反复交换摘要”。每一层只看局部邻域，但层数叠起来以后，节点就能间接吸收更远处的结构信息。

AI 中的角色

分子学习：消息传递把局部键结构转成全局分子表示；
推荐系统：偏好信号沿用户-物品图传播；
程序与知识推理：调用图、实体图上的关系模式可被逐层聚合。

3.5 知识图谱与关系推理

图论对 AI 的另一条重要贡献，是把知识组织成可推理的关系网络。知识图谱中的基本单元通常是三元组：

$$ (\text{head}, \text{relation}, \text{tail}) $$

其中：

head 是关系起点实体；
relation 是边类型；
tail 是关系终点实体。

例如：

$$ (\text{Alan Turing}, \text{founded}, \text{Computability Theory}) $$

在图论语言里，这就是一条带类型的有向边。

它的 AI 价值在于：

可以进行多跳推理，例如沿路径寻找隐含关系；
可以做链路预测，例如补全缺失事实；
可以把文本、实体、规则、数据库统一成同一种结构接口。

这也是为什么图论经常出现在：

知识增强问答；
检索与推荐；
医学知识库；
代码依赖分析；
多智能体关系建模

直觉理解

知识图谱把“事实”从一句自然语言压缩成一条结构化关系边。这样做的好处是，模型不必只依赖文本共现，而可以沿着关系路径直接追踪谁与谁、通过什么关系、在几步之内发生联系。

AI 中的角色

知识增强问答：把实体关系作为检索和推理骨架；
链路预测：补全知识库中的缺失边；
结构化检索：把数据库、规则和文本知识统一到图接口。

之中。

4. 对 AI 的核心贡献

4.1 把“关系”提升为一等公民

很多 AI 失败并不是因为模型不会拟合，而是因为输入表示把关键关系丢掉了。图论的第一大贡献，就是让节点之间的相互作用被显式保留下来，而不必强行塞进定长向量。

4.2 提供结构归纳偏置

图学习模型天然满足一类关键约束：

对节点编号的重排应当不敏感；
对局部邻域结构应当敏感；
对多跳依赖应当可以逐层组合。

这种归纳偏置使模型在分子预测、推荐、程序分析等任务上，比纯粹的无结构 MLP 更有效。

4.3 连接算法图论与可学习系统

图论并不是被深度学习替代了，而是被重新吸收了：

最短路、流、匹配等经典算法继续负责精确求解；
GNN、图嵌入、图 Transformer 负责表示学习与泛化；
两者结合后，AI 才能在结构化任务里同时拥有“会算”与“会学”的能力。

4.4 为复杂系统提供可解释接口

与纯粹黑箱向量表示相比，图结构通常更容易解释：

哪些节点最关键，可以看中心性；
哪些区域形成社群，可以看社区划分；
信息沿哪些边传播，可以追踪路径；
哪些边让系统脆弱，可以分析割与瓶颈。

因此，图论不仅提高性能，也提高了结构透明度。

5. 前沿与开放问题

5.1 图基础模型

图学习正从任务专用模型走向更大规模的预训练与通用表示：

跨图迁移是否可能稳定成立；
图与文本、多模态如何统一预训练；
图 Transformer 是否能在长程依赖上系统超越传统消息传递。

5.2 动态图、异构图与超图

真实世界的图很少是静态同构的：

金融交易图随时间变化；
知识图谱包含多种实体与关系；
多体交互常需要超图或单纯复形表示。

如何在保留结构真实性的同时维持可扩展训练，仍是难点。

5.3 图学习的可扩展性与鲁棒性

大图任务经常遭遇：

邻域爆炸；
过平滑（oversmoothing）；
过压缩（oversquashing）；
对图扰动或错误边敏感。

这些问题说明：把图结构纳入模型不是终点，真正难的是怎样让结构偏置在大规模下仍然可靠。

5.4 图与因果、逻辑的结合

当前很多图模型能利用相关关系，但未必真正理解“为什么节点之间存在这种关系”。因此，图论与：

[[08-logic|逻辑学]]
[[09-causal-inference|因果推断]]

的结合，可能决定下一代结构推理系统能否从“关系拟合”走向“机制理解”。

6. 推荐阅读与参考文献

经典教材

West, D. B. (2001). Introduction to Graph Theory. Prentice Hall.
Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
Chung, F. R. K. (1997). Spectral Graph Theory. AMS.

关键论文与综述

Euler, L. (1736). Solutio problematis ad geometriam situs pertinentis.
Kirchhoff, G. (1847). Ueber die Auflösung der Gleichungen, auf welche man bei der Untersuchung der linearen Vertheilung galvanischer Ströme geführt wird.
Page, L., Brin, S., Motwani, R., & Winograd, T. (1998). The PageRank citation ranking: Bringing order to the web.
Bruna, J., Zaremba, W., Szlam, A., & LeCun, Y. (2014). Spectral networks and locally connected networks on graphs. ICLR Workshop.
Kipf, T. N., & Welling, M. (2017). Semi-supervised classification with graph convolutional networks. ICLR.
Gilmer, J., Schoenholz, S. S., Riley, P. F., Vinyals, O., & Dahl, G. E. (2017). Neural message passing for quantum chemistry. ICML.
Veličković, P., Cucurull, G., Casanova, A., Romero, A., Liò, P., & Bengio, Y. (2018). Graph attention networks. ICLR.

7. 本篇在全书中的位置

这篇位于“数学与形式基础”内部的结构层位置。前几篇文档更多处理连续数值与函数近似，本篇则把焦点转向离散关系结构。

[[02-linear-algebra|线性代数]] 负责把图转写为矩阵与谱对象；
[[07-topology-and-geometry|拓扑与几何]] 继续处理连续空间中的形状、流形与曲率；
[[10-computer-science|计算机科学]] 提供最短路、搜索、匹配等可执行算法；
[[09-causal-inference|因果推断]] 和 [[08-logic|逻辑学]] 则把关系进一步提升到机制与规则层。

因此，本篇最适合作为“结构化 AI”的入口之一。它告诉我们：当世界不是一张规则网格，而是一张关系网络时，AI 应该如何理解、学习并利用这种结构。

FilesExpand file tree

06-graph-theory.md

Latest commit

History

06-graph-theory.md

File metadata and controls

图论（Graph Theory）：从离散关系到 AI 结构归纳偏置

相关主题

1. 上帝视角：为什么 AI 需要图论

1.1 一个直观例子：推荐系统为什么天然是图问题

1.2 图论带给 AI 的四种核心价值

2. 历史脉络

2.1 Euler 与图论的起点（1736）

2.2 19 世纪：树、网络与电路

2.3 20 世纪：算法图论成熟

2.4 互联网与知识网络时代

2.5 图学习时代

3. 核心知识点详解

3.1 图的基本对象与矩阵表示

邻接矩阵

度矩阵

一个极小示例

直觉理解

AI 中的角色

3.2 路径、连通性与组合问题

路径与最短路

连通性与社区

匹配、流与资源分配

直觉理解

AI 中的角色

3.3 图拉普拉斯与谱图方法

为什么它重要

直觉理解

一个直觉例子

AI 中的角色

3.4 从图卷积到消息传递

GCN 的基本形式

MPNN 的统一表达

一个具体例子：分子图

直觉理解

AI 中的角色

3.5 知识图谱与关系推理

直觉理解

AI 中的角色

4. 对 AI 的核心贡献

4.1 把“关系”提升为一等公民

4.2 提供结构归纳偏置

4.3 连接算法图论与可学习系统

4.4 为复杂系统提供可解释接口

5. 前沿与开放问题

5.1 图基础模型

5.2 动态图、异构图与超图

5.3 图学习的可扩展性与鲁棒性

5.4 图与因果、逻辑的结合

6. 推荐阅读与参考文献

经典教材

关键论文与综述

延伸阅读

7. 本篇在全书中的位置