图论

图论

图论（graph theory）提供了描述实体之间关系的数学语言。本文件涵盖节点、边、邻接矩阵、图的类型、度与连通性、图拉普拉斯、谱图理论，以及现实世界中的图应用。我们会在纯计算机科学的章节里更深入地讨论图。

• 到目前为止，这本书里的数据都活在规则结构上：\mathbb{R}^n 中的向量（第 1 章）、作为数字网格的矩阵（第 2 章）、作为像素网格的图像（第 8 章）、作为有序列表的序列（第 7 章）。但许多现实系统是不规则的：社交网络没有网格结构，分子没有从左到右的顺序，道路网络也无法整齐地铺成一行行一列列。

• 图（graph）是表示这些不规则、关系型结构的数学工具。一个图刻画实体（节点）以及它们之间的关系（边）。一旦数据被表示成图，我们就可以应用文件 01 里的几何深度学习原理来学习。

节点、边与邻接

• 一个图 G = (V, E) 由一个**节点（node，又称顶点 vertex）集合 V = \{v_1, v_2, \ldots, v_n\} 和一个连接节点对的边（edge）**集合 E \subseteq V \times V 组成。

• 节点代表实体：人、原子、城市、网页、神经元。边代表关系：朋友关系、化学键、道路、超链接、突触。

• 邻接矩阵（adjacency matrix） A 是图的矩阵表示。对于一个有 n 个节点的图，A 是一个 n \times n 的矩阵，其中 A_{ij} = 1 表示存在一条从节点 i 到节点 j 的边，否则 A_{ij} = 0。

• 例如，一个三角形图（3 个节点，全部相连）的邻接矩阵是：

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

• 对角线为零，因为节点不与自身相连（默认没有自环）。邻接矩阵是我们在第 2 章学过的布尔矩阵的直接应用：每个元素都是一个二元关系。

• 邻接矩阵完整地编码了图的结构。对 A 做矩阵运算能揭示图的性质：A^2_{ij} 数的是节点 i 与 j 之间长度为 2 的路径数目（回想第 2 章的矩阵乘法：每个元素是对中间节点求和的乘积之和）。更一般地，A^k_{ij} 数的是长度为 k 的路径数。

• 每个节点都可以带一个特征向量（feature vector） \mathbf{x}_i \in \mathbb{R}^d。对于社交网络，这可能是用户的资料信息；对于分子，它编码原子类型、电荷和其他属性。全部节点特征组成一个矩阵 X \in \mathbb{R}^{n \times d}，其中每一行是一个节点的特征。

• 边也可以带特征：分子中的化学键类型、空间图中的距离、知识图谱中的关系类型。边 (i, j) 的**边特征（edge feature）**是一个向量 \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 也有边。其邻接矩阵是非对称的。Twitter 的关注、网页超链接和引用网络都是有向的。

• **加权图（weighted graph）**给每条边赋予一个数值权重。邻接矩阵的元素是实数而不是二元的：A_{ij} = w_{ij}。道路网络中的距离、大脑连接中的相关强度、社交网络中的互动频率都是加权的。

• **二部图（bipartite graph）**有两个不相交的节点集合，边只存在于两个集合之间（集合内部没有边）。用户和商品构成一个二部图：用户给商品打分，但用户不会给用户打分。二部图的邻接矩阵具有块结构：

A = \begin{bmatrix} 0 & B \\ B^T & 0 \end{bmatrix}

• 其中 B 是两个节点集合之间的二部邻接矩阵。

• **多重图（multigraph）**允许同一对节点之间有多条边和/或存在自环。知识图谱通常是多重图：两个实体之间可以有多种关系（例如"出生于"、"居住在"、"工作于"）。

• **超图（hypergraph）把边推广为一次连接多于两个节点。一条超边（hyperedge）**连接一组节点，表示高阶关系。一篇由五个人合著的研究论文就是一条连接五个作者节点的超边。

• 完全图（complete graph） K_n 在每一对节点之间都有一条边。这是全连接层的图类比，也是 Transformer 所作用的结构（每个 token 都注意到所有其他 token）。

度、路径与连通性

• 一个节点的**度（degree）**是与它相连的边的数目。在无向图中，节点 i 的度是 d_i = \sum_j A_{ij}。高度数的节点是连接众多的"枢纽（hub）"。

• 度矩阵（degree matrix） D 是一个对角矩阵，对角线上放的是度：D_{ii} = d_i。这个矩阵在图论和 GNN 公式里无处不在。

• 两个节点之间的一条**路径（path）是连接它们的一串边。节点 i 和 j 之间的最短路径（shortest path，又称测地线 geodesic）**是边数最少的路径（在加权图中则是总权重最小的）。Dijkstra 算法能在 O((|V| + |E|) \log |V|) 时间内找到最短路径。

• 如果每一对节点之间都存在路径，则图是连通的（connected）。否则它有多个连通分量（connected component）：彼此之间没有边的孤立子图。

• 图的**直径（diameter）**是任意一对节点之间最长的最短路径。它衡量图有多"分散"。社交网络的直径以小著称（"六度分隔"）。

• 环（cycle）是起点和终点为同一节点的路径。没有环的图是一棵树（tree）。树是最简单的连通图：n 个节点恰好有 n-1 条边。

• **中心性（centrality）**衡量一个节点的重要性。**度中心性（degree centrality）**就是度本身。**介数中心性（betweenness centrality）**统计有多少条最短路径经过某个节点。**特征向量中心性（eigenvector centrality）**根据一个节点邻居的重要性来给它打分，由此导出特征向量方程 A\mathbf{x} = \lambda \mathbf{x}（第 2 章）。Google 的 PageRank 就是有向图上特征向量中心性的一个变种。

图拉普拉斯

• **图拉普拉斯（graph Laplacian）**也许是图论中最重要的矩阵。它定义为：

• 其中 D 是度矩阵，A 是邻接矩阵。对我们的三角形例子：

L = \begin{bmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{bmatrix} - \begin{bmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{bmatrix} = \begin{bmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{bmatrix}

• 拉普拉斯有一些非凡的性质：

  • 它总是对称的且半正定的（回想第 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 值）**。它衡量图的连通程度：$\lambda_2 = 0$ 意味着图不连通，$\lambda_2$ 大意味着图紧密相连。
​

• **归一化拉普拉斯（normalised Laplacian）**用度来做缩放：

• 这种归一化保证拉普拉斯的性质不依赖于节点度的绝对尺度。项 D^{-1/2} A D^{-1/2} 是对称归一化邻接矩阵（symmetrically normalised adjacency），它会直接出现在文件 03 的 GCN 公式里。

谱图理论

• 图拉普拉斯的特征值和特征向量定义了图的谱（spectrum），它们扮演着图的傅里叶变换的角色。

• 在经典信号处理中，傅里叶变换把信号分解为频率分量（正弦和余弦）。在图上，拉普拉斯的特征向量扮演这些频率基的角色。低特征值对应的特征向量在图上变化缓慢（低频、平滑），而高特征值对应的特征向量变化迅速（高频、振荡）。

• 图上信号 \mathbf{x} 的**图傅里叶变换（Graph Fourier Transform，GFT）**为：

• 其中 U 是拉普拉斯特征向量组成的矩阵（回想第 2 章的特征分解：L = U \Lambda U^T）。逆变换为 \mathbf{x} = U \hat{\mathbf{x}}。

• 谱域图卷积是频域上的逐点乘法，正如空间域的卷积对应傅里叶域上的乘法（第 8 章的卷积定理）：

• 滤波器 \hat{g}_\theta 是关于特征值的可学习函数。这是谱 GNN 的基础，我们会在文件 03 中把它简化为实用的 GCN。

• 计算瓶颈在于 L 的特征分解，对一个有 n 个节点的图需要 O(n^3)。这对大图（上百万节点）来说不现实。多项式近似（Chebyshev 多项式）能完全避免特征分解，而这种近似直接导出了 GCN。

社区检测

• 许多现实世界的图具有社区结构（community structure）：密集相连的节点簇，簇与簇之间的连接稀疏。社交网络有朋友圈，生物网络有功能模块，引用网络有研究领域。

• **谱聚类（spectral clustering）**用拉普拉斯特征向量来找社区。思路是：用 L 的 k 个最小的非平凡特征向量给每个节点做嵌入，然后在这个嵌入空间里应用 k-means（第 6 章）。同一社区的节点在谱嵌入里会靠得很近。

• 之所以奏效，是因为 Fiedler 向量（\lambda_2 的特征向量）自然地把图分成两组：取值为正的节点和取值为负的节点，切开的正是最稀疏的连接。更高阶的特征向量把它细化成更多组。

• 模块度（modularity） Q 衡量一个社区划分的质量。它把社区内部的边数与一个随机图中期望的边数做比较：

• 其中 c_i 是节点 i 所属的社区，\delta 在两个节点同属一个社区时取 1。Q 的取值范围是 -0.5 到 1，值越大表示社区结构越强。

现实世界中的图

• 社交网络：节点是人，边是朋友关系或互动。Facebook 有数十亿节点和数千亿条边。这类图通常是稀疏的（每个人只有几百个朋友，而不是几十亿），呈现小世界性质（平均路径长度短），并且度分布是重尾的（少数枢纽有上百万连接）。

• 分子图：节点是原子，边是化学键。每个原子有特征（元素类型、电荷、杂化方式），每条边也有特征（单键、双键、三键、芳香键）。分子图很小（几十到几百个节点），但结构高度规律。从图结构预测分子性质是 GNN 的一个主要应用。

• 知识图谱：节点是实体（人、地点、概念），边是带类型的关系（"出生于"、"……的首都"、"……的实例"）。知识图谱支撑着搜索引擎、推荐系统和问答系统。它们通常是有向多重图，拥有数百万实体和数十亿关系。

• 引用网络：节点是论文，边是引用（有向）。聚类能揭示研究共同体。节点特征包括标题、摘要和发表年份。

• 蛋白质相互作用网络：节点是蛋白质，边表示物理相互作用或功能关联。理解这类图有助于识别药物靶点和疾病机制。

• 道路网络与交通：节点是路口，边是带有距离/时间权重的路段。这类图上的最短路径算法支撑着导航系统。自动驾驶的运动预测（第 11 章）把智能体之间的相互作用表示成图。

编程练习（使用 CoLab 或 notebook）

1. 用邻接矩阵构建一个小图，并计算基本性质：每个节点的度、长度为 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}")
​

2. 计算图拉普拉斯及其特征值。验证最小特征值为 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}")
​

3. 对一个有两个社区的图做谱聚类。用 Fiedler 向量给节点做嵌入，并按正负号把它们分开。

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 向量（第二小特征值对应的向量）
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()
​