图论¶
一句话总结：图论用节点与边描述实体间的关系，邻接矩阵、拉普拉斯矩阵与谱分解构成图神经网络 (Graph Neural Network, GNN) 一切算法的数学地基。
图论为描述实体之间的关系提供了一门数学语言。本节涵盖节点、边、邻接矩阵、图的类型、度与连通性、图拉普拉斯矩阵、谱图论以及真实世界的图应用。我们会在纯计算机科学的章节里对图做更深入的讨论。
-
到目前为止，本书里的数据都住在规则的结构上：第 1 章里的 \(\mathbb{R}^n\) 向量，第 2 章里作为数字网格的矩阵，第 8 章里作为像素网格的图像，第 7 章里作为有序列表的序列。但真实世界里的许多系统是不规则的：社交网络没有网格结构，分子没有从左到右的顺序，道路网络也没法整齐地铺成一行一列。
-
图 (graph) 就是用来表示这类不规则、关系型结构的数学工具。一张图刻画了实体 (节点) 与它们之间的关系 (边)。一旦数据被表示成图，我们就能把第 1 节里那套几何深度学习的原则搬过来学习它。
节点、边与邻接¶
-
一张图 \(G = (V, E)\) 由一组节点 (或称顶点) \(V = \{v_1, v_2, \ldots, v_n\}\) 和一组连接节点对的边 \(E \subseteq V \times V\) 构成。
-
节点代表实体：人、原子、城市、网页、神经元。边代表关系：友谊、化学键、道路、超链接、突触。
-
邻接矩阵 (adjacency matrix) \(A\) 是图的矩阵表示。对于一张有 \(n\) 个节点的图，\(A\) 是一个 \(n \times n\) 矩阵：若节点 \(i\) 到节点 \(j\) 有边，则 \(A_{ij} = 1\)；否则 \(A_{ij} = 0\)。
-
举个例子，三角形图 (3 个节点两两相连) 的邻接矩阵是:
-
对角线全为 0，因为节点默认不与自己相连 (没有自环)。邻接矩阵是第 2 章里布尔矩阵的直接应用：每个元素都是一个二元关系。
-
邻接矩阵完整地编码了图的结构。对 \(A\) 做矩阵运算能揭示图的性质：\(A^2_{ij}\) 数出了节点 \(i\) 到节点 \(j\) 长度为 2 的路径数 (回忆第 2 章的矩阵乘法：每个元素都是在中间节点上求和的乘积)。更一般地，\(A^k_{ij}\) 数出的是长度为 \(k\) 的路径数。
-
每个节点可以带一个特征向量 \(\mathbf{x}_i \in \mathbb{R}^d\)。对社交网络，它可能是用户的个人资料信息。对分子，它编码了原子类型、电荷等属性。所有节点特征拼起来是一个矩阵 \(X \in \mathbb{R}^{n \times d}\)，每一行就是一个节点的特征。
-
边也可以带特征：分子里的键类型，空间图里的距离，知识图谱里的关系类型。边 \((i, j)\) 的边特征是一个向量 \(\mathbf{e}_{ij} \in \mathbb{R}^{d_e}\)。
图的类型¶
-
无向图 (undirected graph) 的边是对称的：若 \(i\) 连到 \(j\)，那么 \(j\) 也连到 \(i\)。它的邻接矩阵是对称的：\(A = A^T\) (第 2 章的对称矩阵)。友谊关系与化学键都是无向的。
-
有向图 (directed graph, digraph) 的边带方向：从 \(i\) 到 \(j\) 有边并不意味着从 \(j\) 到 \(i\) 也有边。邻接矩阵不对称。推特的关注关系、网页超链接、论文引用网络都是有向的。
-
带权图 (weighted graph) 给每条边配一个数值权重。邻接矩阵不再是二值的，而是实数值：\(A_{ij} = w_{ij}\)。道路网络里的距离、脑连接里的相关强度、社交网络里的互动频次，都是带权的。
-
二部图 (bipartite graph) 有两组互不相交的节点，边只在两组之间跨接 (组内没有边)。用户与商品就构成一张二部图：用户给商品打分，但用户不给用户打分。二部图的邻接矩阵有一个块状结构:
-
其中 \(B\) 是两组节点之间的二部邻接矩阵。
-
多重图 (multigraph) 允许同一对节点之间有多条边或自环。知识图谱通常就是多重图：两个实体之间可以有多种关系 (比如"出生于"、"居住于"、"任职于")。
-
超图 (hypergraph) 把边推广到可以同时连接两个以上的节点。一条超边 (hyperedge) 连接一组节点，表示更高阶的关系。一篇由五人共同署名的论文，就是一条连接五个作者节点的超边。
-
完全图 (complete graph) \(K_n\) 每对节点之间都有边。它是全连接层在图上的对应物，也正是 Transformer 所作用的结构 (每个 token 都关注其他所有 token)。
度、路径与连通性¶
-
节点的度 (degree) 是与之相连的边数。在无向图里，节点 \(i\) 的度是 \(d_i = \sum_j A_{ij}\)。高度数的节点是"枢纽"，连接众多。
-
度矩阵 (degree matrix) \(D\) 是对角线上放着度数的对角阵：\(D_{ii} = d_i\)。这个矩阵会在图论和 GNN 的公式里反复出现。
-
两个节点之间的路径 (path) 是把它们连起来的一串边。\(i\) 到 \(j\) 之间的最短路径 (或称测地线) 是边数最少的路径 (在带权图中则是总权重最小的路径)。Dijkstra 算法能在 \(O((|V| + |E|) \log |V|)\) 时间内找到最短路径。
-
若一张图中任意两个节点之间都有路径相连，就称它是连通的 (connected)。否则它就有多个连通分量 (connected components)：彼此之间没有边的孤立子图。
-
图的直径 (diameter) 是所有节点对之间最短路径的最大值，它度量了图"摊得有多开"。社交网络以直径极小著称 ("六度分隔")。
-
环 (cycle) 是起点与终点相同的路径。没有环的图叫树 (tree)。树是最简单的连通图：\(n\) 个节点恰好 \(n-1\) 条边。
-
中心性 (centrality) 度量节点的重要程度。度中心性就是度数本身。介数中心性 (betweenness centrality) 数的是经过一个节点的最短路径条数。特征向量中心性 (eigenvector centrality) 让节点的重要性由邻居的重要性决定，由此导出特征向量方程 \(A\mathbf{x} = \lambda \mathbf{x}\) (第 2 章)。谷歌的 PageRank 就是特征向量中心性在有向图上的一个变体。
图拉普拉斯矩阵¶
- 图拉普拉斯矩阵 (graph Laplacian) 可能是图论里最重要的矩阵。它定义为:
- 其中 \(D\) 是度矩阵，\(A\) 是邻接矩阵。对于我们的三角形例子:
-
拉普拉斯矩阵有一些非凡的性质:
- 它总是对称且半正定 (回忆第 2 章：所有特征值 \(\geq 0\))。对任意向量 \(\mathbf{x}\):
- 这个二次型度量了图上信号 $\mathbf{x}$ 沿边变化的剧烈程度。若相邻节点取值接近，$\mathbf{x}^T L \mathbf{x}$ 就小；若差别很大，它就大。拉普拉斯矩阵度量的是图上信号的**平滑度 (smoothness)**。
- 最小的特征值总是 0，对应的特征向量是 $\mathbf{1} = [1, 1, \ldots, 1]^T$ (常值信号毫无变化)。零特征值的个数等于连通分量的个数。
- 第二小的特征值 $\lambda_2$ 叫**代数连通度 (algebraic connectivity)**，也叫菲德勒值 (Fiedler value)。它度量图的连通紧密程度：$\lambda_2 = 0$ 表示图不连通，$\lambda_2$ 越大表示图连得越紧。
- 归一化拉普拉斯 (normalised Laplacian) 按度数做了缩放:
- 这样归一化能让拉普拉斯的性质不依赖于节点度数的绝对量级。\(D^{-1/2} A D^{-1/2}\) 一项就是对称归一化邻接矩阵，它会直接出现在 GCN 的公式里 (第 3 节)。
谱图论¶
-
图拉普拉斯矩阵的特征值和特征向量定义了图的谱 (spectrum)，它们扮演着傅里叶变换在图上的对应物。
-
在经典信号处理里，傅里叶变换把信号分解成频率分量 (正弦与余弦)。在图上，拉普拉斯矩阵的特征向量担当了这些频率基的角色。小特征值的特征向量在图上变化缓慢 (低频、平滑)，大特征值的特征向量则变化剧烈 (高频、震荡)。
-
图上信号 \(\mathbf{x}\) 的图傅里叶变换 (Graph Fourier Transform, GFT) 为:
-
其中 \(U\) 是拉普拉斯特征向量构成的矩阵 (回忆第 2 章的特征分解：\(L = U \Lambda U^T\))。逆变换是 \(\mathbf{x} = U \hat{\mathbf{x}}\)。
-
图卷积 (graph convolution) 在谱域里就是频域里的逐点相乘，恰如空间域上的卷积对应于傅里叶域上的乘法 (第 8 章的卷积定理):
-
滤波器 \(\hat{g}_\theta\) 是特征值的可学习函数。这是谱域 GNN 的地基，我们会在第 3 节里把它化简成实用的图卷积网络 (Graph Convolutional Network, GCN)。
-
计算瓶颈在于对 \(L\) 做特征分解，对 \(n\) 节点的图代价是 \(O(n^3)\)。这对大图 (数百万节点) 不现实。多项式近似 (切比雪夫多项式) 完全绕开了特征分解，而这一近似直接催生了 GCN。
社区检测¶
-
许多真实世界的图都具备社区结构 (community structure)：内部连接稠密的节点簇，簇与簇之间连接稀疏。社交网络里有朋友圈，生物网络里有功能模块，引文网络里有研究领域。
-
谱聚类 (spectral clustering) 用拉普拉斯的特征向量来找社区。做法是：用 \(L\) 最小的 \(k\) 个非平凡特征向量把每个节点嵌入到一个向量，然后在这个嵌入空间里跑 k 均值 (第 6 章)。同一社区的节点会在谱嵌入里聚成一团。
-
之所以奏效，是因为菲德勒向量 (\(\lambda_2\) 的特征向量) 会天然地把图切成两组：取值为正的节点与取值为负的节点，切口穿过的正是连接最稀疏的地方。更高阶的特征向量会把它进一步细化成更多组。
-
模块度 (modularity) \(Q\) 度量一次社区划分的质量。它比较社区内部的边数与随机图里的期望边数:
- 其中 \(c_i\) 是节点 \(i\) 所属社区的标号，当两个节点在同一社区时 \(\delta\) 为 1。\(Q\) 的取值范围是 \(-0.5\) 到 \(1\)，越大表示社区结构越强。
真实世界的图¶
-
社交网络：节点是人，边是友谊或互动。Facebook 有几十亿节点、几千亿条边。这类图通常是稀疏的 (每个人有几百个朋友，不是几十亿)，展现出小世界性质 (平均路径长度很短)，度分布是重尾的 (少数枢纽拥有百万级连接)。
-
分子图：节点是原子，边是化学键。每个原子带特征 (元素类型、电荷、杂化方式)，每条键也带特征 (单键、双键、三键、芳香键)。分子图规模小 (几十到几百个节点) 但结构性极强。从图结构预测分子性质是 GNN 的一个主要应用。
-
知识图谱：节点是实体 (人、地、概念)，边是带类型的关系 ("出生于"、"是……的首都"、"是……的实例")。知识图谱驱动了搜索引擎、推荐系统与问答。它们通常是有向多重图，有几百万实体与几十亿关系。
-
引文网络：节点是论文，边是引用 (有向)。聚类可以揭示研究社区。节点特征包括标题、摘要、发表年份。
-
蛋白质相互作用网络：节点是蛋白质，边表示物理相互作用或功能关联。理解这类图有助于发现药物靶点与疾病机制。
-
路网与交通：节点是路口，边是带距离/时间权重的路段。这类图上的最短路径算法驱动了导航系统。自动驾驶里的运动预测 (第 11 章) 就把智能体之间的交互表示为图。
编程任务 (使用 CoLab 或 notebook)¶
-
用邻接矩阵搭一张小图，计算基本属性：每个节点的度、长度为 2 的路径数、以及图是否连通。
import jax.numpy as jnp # 一张简单的图: 5 个节点 # 边: 0-1, 0-2, 1-2, 2-3, 3-4 A = jnp.array([[0, 1, 1, 0, 0], [1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0]], dtype=float) # 度 degrees = A.sum(axis=1) print(f"Degrees: {degrees}") # 长度为 2 的路径数 A2 = A @ A print(f"Paths of length 2 (node 0 to 3): {int(A2[0, 3])}") # 是否连通? 检查 A^(n-1) 是否全部非零 An = jnp.linalg.matrix_power(A + jnp.eye(5), 4) # 用 (A+I)^4 判断可达性 connected = jnp.all(An > 0) print(f"Connected: {connected}") -
计算图拉普拉斯矩阵及其特征值。验证最小的特征值是 0，对应的特征向量是常值向量。
import jax.numpy as jnp A = jnp.array([[0, 1, 1, 0, 0], [1, 0, 1, 0, 0], [1, 1, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0]], dtype=float) D = jnp.diag(A.sum(axis=1)) L = D - A eigenvalues, eigenvectors = jnp.linalg.eigh(L) print(f"Eigenvalues: {eigenvalues}") print(f"Smallest eigenvector: {eigenvectors[:, 0]}") print(f"Fiedler value (algebraic connectivity): {eigenvalues[1]:.4f}") # 验证: x^T L x 度量平滑度 x = jnp.array([1.0, 1.0, 1.0, -1.0, -1.0]) # 两组 smoothness = x @ L @ x print(f"Smoothness of two-group signal: {smoothness:.2f}") -
在一张有两个社区的图上做谱聚类。用菲德勒向量做嵌入，再按符号分组。
import jax.numpy as jnp import matplotlib.pyplot as plt # 两个各含 5 个节点的社区, 之间弱连接 A = jnp.zeros((10, 10)) # 社区 1: 节点 0-4 (稠密) for i in range(5): for j in range(i+1, 5): A = A.at[i, j].set(1).at[j, i].set(1) # 社区 2: 节点 5-9 (稠密) for i in range(5, 10): for j in range(i+1, 10): A = A.at[i, j].set(1).at[j, i].set(1) # 一条桥接边 A = A.at[2, 7].set(1).at[7, 2].set(1) D = jnp.diag(A.sum(axis=1)) L = D - A eigenvalues, eigenvectors = jnp.linalg.eigh(L) # 菲德勒向量 (第二小的特征值对应的特征向量) fiedler = eigenvectors[:, 1] communities = (fiedler > 0).astype(int) print(f"Fiedler vector: {fiedler}") print(f"Clusters: {communities}") plt.bar(range(10), fiedler, color=["#3498db" if c == 0 else "#e74c3c" for c in communities]) plt.xlabel("Node"); plt.ylabel("Fiedler vector value") plt.title("Spectral Clustering via Fiedler Vector") plt.show()
📌 本节要点¶
- 图 \(G = (V, E)\)：用节点集合 \(V\) 与边集合 \(E\) 表示实体及其关系，是不规则数据的通用语言。
- 邻接矩阵 \(A\): \(n \times n\) 矩阵完整编码图的结构；\(A^k_{ij}\) 数出 \(i\) 到 \(j\) 长度为 \(k\) 的路径数。
- 图的类型：无向 / 有向 / 带权 / 二部 / 多重 / 超图 / 完全图，对应不同的实际系统。
- 度矩阵 \(D\)：对角阵，对角元是节点度数；与 \(A\) 一起构成图论公式的基本积木。
- 连通性与直径：连通分量数、最短路径与直径描述图的整体形态；小世界现象让社交网络直径极小。
- 图拉普拉斯 \(L = D - A\)：对称半正定，二次型 \(\mathbf{x}^T L \mathbf{x} = \sum_{(i,j)} (x_i - x_j)^2\) 度量信号平滑度。
- 谱与菲德勒值：零特征值个数等于连通分量数；第二小特征值 \(\lambda_2\) 度量代数连通度。
- 图傅里叶变换与谱卷积：拉普拉斯特征向量充当图上的频率基，谱域逐点乘等价于图卷积，是谱域 GNN 的起点。
- 社区检测：谱聚类用菲德勒向量把图切成密簇，模块度 \(Q\) 度量划分质量。
- 真实图：社交、分子、知识、引文、蛋白质、路网等系统天然是图，这也是 GNN 落地的主战场。