图论

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

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

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

节点、边和邻接

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

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

• 邻接矩阵 \(A\) 是图的矩阵表示。对于一个有 \(n\) 个节点的图，\(A\) 是一个 \(n \times n\) 矩阵，其中如果从节点 \(i\) 到节点 \(j\) 存在一条边，则 \(A_{ij} = 1\)，否则 \(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\) 的路径的数量。

• 每个节点可以带有一个特征向量 \(\mathbf{x}_i \in \mathbb{R}^d\)。对于一个社交网络，这可能是用户的个人信息。对于一个分子，它编码原子类型、电荷和其他属性。完整的节点特征集是一个矩阵 \(X \in \mathbb{R}^{n \times d}\)，其中每一行是一个节点的特征。

• 边也可以携带特征：分子中的键类型、空间图中的距离、知识图谱中的关系类型。边 \((i, j)\) 的边特征是一个向量 \(\mathbf{e}_{ij} \in \mathbb{R}^{d_e}\)。

图的类型

• 无向图 具有对称的边：如果 \(i\) 连接到 \(j\)，那么 \(j\) 也连接到 \(i\)。邻接矩阵是对称的：\(A = A^T\)（对称矩阵，第 2 章）。友谊和化学键是无向的。

• 有向图 的边具有方向：从 \(i\) 到 \(j\) 的边并不意味着从 \(j\) 到 \(i\) 的边。邻接矩阵是非对称的。Twitter 的关注关系、网页超链接和引文网络都是有向的。

• 加权图 为每条边分配一个数值权重。邻接矩阵的条目是实数值而不是二值的：\(A_{ij} = w_{ij}\)。道路网络中的距离、大脑连接中的相关强度以及社交网络中的互动频率都是加权图。

• 二分图 有两组不相交的节点，边只存在于两组之间（组内无边）。用户和产品构成一个二分图：用户评价产品，但用户之间不互相评价。二分图的邻接矩阵具有分块结构：

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

• 其中 \(B\) 是两组节点之间的二分邻接矩阵。

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

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

• 完全图 \(K_n\) 在每一对节点之间都有一条边。这是全连接层的图类比，也是 Transformer 所操作的结构（每个标记都关注每个其他标记）。

度、路径和连通性

• 一个节点的度 是与其相连的边的数量。在无向图中，节点 \(i\) 的度为 \(d_i = \sum_j A_{ij}\)。高度节点是拥有许多连接的“枢纽”。

• 度矩阵 \(D\) 是一个对角矩阵，对角线上是节点的度：\(D_{ii} = d_i\)。这个矩阵在图论和 GNN 公式中经常出现。

• 两个节点之间的路径 是连接它们的一条边序列。\(i\) 和 \(j\) 之间的最短路径 是边数最少的路径（在加权图中是总权重最小的路径）。Dijkstra 算法 可以在 \(O((|V| + |E|) \log |V|)\) 时间内找到最短路径。

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

• 图的直径 是任意一对节点之间最长最短路径的长度。它衡量图的“分散”程度。社交网络以其小的直径而闻名（“六度分隔”）。

• 环 是一条起点和终点相同的路径。没有环的图是树。树是最简单的连通图：\(n\) 个节点恰好有 \(n-1\) 条边。

• 中心性 衡量节点的重要性。度中心性 就是节点的度。介数中心性 计算通过一个节点的最短路径的数量。特征向量中心性 根据节点邻居的重要性来分配重要性，这导致了特征向量方程 \(A\mathbf{x} = \lambda \mathbf{x}\)（第 2 章）。Google 的 PageRank 是特征向量中心性在有向图上的一个变体。

图拉普拉斯矩阵

• 图拉普拉斯矩阵 可能是图论中最重要的矩阵。它的定义为：

\[L = D - A\]

• 其中 \(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}^T L \mathbf{x} = \sum_{(i,j) \in E} (x_i - x_j)^2\]

- 这个二次型衡量了图上信号 $\mathbf{x}$ 沿着边的变化程度。如果相邻节点具有相似的值，则 $\mathbf{x}^T L \mathbf{x}$ 很小。如果它们差异很大，则值很大。拉普拉斯矩阵衡量了图上信号的**平滑度**。

- 最小的特征值总是 0，对应的特征向量是 $\mathbf{1} = [1, 1, \ldots, 1]^T$（常数信号的变化为零）。零特征值的数量等于连通分量的数量。

- 第二小的特征值 $\lambda_2$ 是**代数连通度**（Fiedler 值）。它衡量图的连通程度：$\lambda_2 = 0$ 表示图不连通，较大的 $\lambda_2$ 表示图紧密连接。

• 归一化拉普拉斯矩阵 用度进行缩放：

\[\hat{L} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}\]

• 这种归一化确保了拉普拉斯矩阵的性质不依赖于节点度的绝对尺度。项 \(D^{-1/2} A D^{-1/2}\) 是对称归一化邻接矩阵，它直接出现在 GCN 的公式中（文件 3）。

谱图理论

• 图拉普拉斯矩阵的特征值和特征向量定义了图的谱，它们充当了图傅里叶变换的类比。

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

• 图上信号 \(\mathbf{x}\) 的图傅里叶变换 为：

\[\hat{\mathbf{x}} = U^T \mathbf{x}\]

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

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

\[g_\theta \star \mathbf{x} = U \left( (U^T g_\theta) \odot (U^T \mathbf{x}) \right) = U \, \text{diag}(\hat{g}_\theta) \, U^T \mathbf{x}\]

• 滤波器 \(\hat{g}_\theta\) 是特征值的一个可学习函数。这是谱 GNN 的基础，我们将在文件 3 中将其简化为实用的 GCN。

• 计算瓶颈是 \(L\) 的特征分解，对于有 \(n\) 个节点的图，其复杂度为 \(O(n^3)\)。这对于大型图（数百万个节点）来说是不切实际的。多项式近似（Chebyshev 多项式）完全避免了特征分解，而这种近似直接导出了 GCN。

社区检测

• 许多现实世界的图具有社区结构：内部连接密集、社区之间连接稀疏的节点簇。社交网络有朋友群，生物网络有功能模块，引文网络有研究领域。

• 谱聚类 使用拉普拉斯特征向量来发现社区。其思想：使用 \(L\) 的 \(k\) 个最小的非平凡特征向量来嵌入每个节点，然后在这个嵌入空间中应用 k-means（第 6 章）。同一社区中的节点在谱嵌入中彼此靠近。

• 这是有效的，因为 Fiedler 向量（\(\lambda_2\) 的特征向量）自然地将图分成两组：正值节点和负值节点，切割通过最稀疏的连接。更高的特征向量进一步将其细分为更多的组。

• 模块度 \(Q\) 衡量社区划分的质量。它比较了社区内部边的数量与随机图中的期望数量：

\[Q = \frac{1}{2|E|} \sum_{ij} \left( A_{ij} - \frac{d_i d_j}{2|E|} \right) \delta(c_i, c_j)\]

• 其中 \(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}")
   
   # 长度为 2 的路径
   A2 = A @ A
   print(f"从节点 0 到 3 的长度为 2 的路径数量: {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}")
   

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}")
   print(f"最小特征向量: {eigenvectors[:, 0]}")
   print(f"Fiedler 值 (代数连通度): {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:.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 向量 (第 2 小的特征值)
   fiedler = eigenvectors[:, 1]
   communities = (fiedler > 0).astype(int)
   
   print(f"Fiedler 向量: {fiedler}")
   print(f"聚类: {communities}")
   
   plt.bar(range(10), fiedler, color=["#3498db" if c == 0 else "#e74c3c" for c in communities])
   plt.xlabel("节点"); plt.ylabel("Fiedler 向量值")
   plt.title("基于 Fiedler 向量的谱聚类")
   plt.show()