图论基础：从欧拉七桥到神经网络

1736年，圣彼得堡科学院收到了一封来自哥尼斯堡七桥问题的信件。 Leonard Euler 在解决这个能否一次走遍所有七座桥而不重复的问题时，创造了图论——一门只关注连接关系而忽略几何形状的数学。他抽象出“点”和“线”的概念，证明了这样的路径不存在。这个为游戏而生的理论，在三百多年后，意外地成为了理解复杂系统、构建人工智能的核心工具。今天，当我们谈论图神经网络（GNN）时，我们本质上是在用机器学习重新诠释欧拉的遗产：将万物抽象为图，在连接中挖掘智慧。本章将带你快速回顾图论的核心概念，聚焦于那些在算法设计中反复出现的表示方法、矩阵工具和结构思想，为后续章节中图卷积网络的谱方法与时域方法打下坚实的直觉基础。

图的基本术语：节点、边与图的家族

图（Graph）是描述一组对象（节点，Node/Vertex）以及它们之间关系（边，Edge）的数学结构。一个图 $G$ 定义为 $G = (V, E)$，其中 $V$ 是节点集合，$E$ 是边集合。边可以是有向的（Directed），即 $(u, v) \in E$ 表示从节点 $u$ 指向节点 $v$ 的关系；也可以是无向的（Undirected），即 $\{u, v\} \in E$ 表示双向关系。更进一步，边可以被赋予权重（Weight），形成加权图（Weighted Graph），权重可以表示距离、强度、频率等数值。没有权重的图称为无权图（Unweighted Graph）。

节点（Node）是图的基本单元，它可以代表任何实体：社交网络中的用户、分子结构中的原子、交通网络中的路口、知识图谱中的实体。边（Edge）则代表实体间的关系：关注、化学键、道路、属性关联。节点的度（Degree）是与其相连的边的数量。对于无向图，度就是连接数；对于有向图，我们区分出度（Out-degree，指向外的边）和入度（In-degree，指向内的边）。节点的度分布是图最基础的不变量之一，真实世界网络（如社交网络、互联网）往往表现出幂律分布（Power-law Degree Distribution），即少数节点拥有大量连接（“枢纽”或“影响者”），而大多数节点连接稀疏。

图的大小通常用节点数 $|V| = n$ 和边数 $|E| = m$ 描述。根据 $m$ 与 $n$ 的关系，图可分为：

• **稠密图（Dense Graph）**：$m$ 接近 $n^2$（完全图有 $m = n(n-1)/2$ 条无向边）。
• **稀疏图（Sparse Graph）**：$m$ 远小于 $n^2$，通常 $m = O(n)$ 或 $O(n \log n)$。绝大多数真实世界网络都是稀疏的——一个人不可能认识所有人，一个网页很少链接到所有其他网页。

图的家族还包括：

• **多重图（Multigraph）**：允许节点间存在多条边（如城市间有多条公路）。
• **带自环的图（Graph with Self-loops）**：边从节点指向自身，在建模中有时用于表示节点自身的状态保留。
• **二分图（Bipartite Graph）**：节点可划分为两个集合 $U$ 和 $W$，所有边都跨越集合，如用户-商品交互图。

理解这些基本术语是讨论表示与算法的前提。接下来，我们进入核心问题：如何将抽象的图存储到计算机内存中？不同的表示方法将直接影响后续图神经网络的计算效率与可行性。

图的表示：邻接矩阵与邻接表的博弈

将图存储为计算机可处理的数据结构，是图算法与图神经网络的第一步。最主流的两种表示是邻接矩阵（Adjacency Matrix）和邻接表（Adjacency List）。它们的优劣对比是图计算中永恒的话题，选择何种表示往往取决于图的密度和需要执行的操作类型。

邻接矩阵：稠密图的直白告白

邻接矩阵 $A$ 是一个 $n \times n$ 的二维数组，其中元素 $A_{ij}$ 表示节点 $i$ 到节点 $j$ 是否有边。对于无权图，$A_{ij} = 1$ 表示存在边，$0$ 表示不存在。对于加权图，$A_{ij}$ 存储边权值，若无边则通常为 $0$ 或 $\infty$。无向图的邻接矩阵是对称的（$A_{ij} = A_{ji}$），有向图则不一定。

```python

无权无向图示例：3个节点，边 (0,1), (0,2), (1,2)

A = [ [0, 1, 1], [1, 0, 1], [1, 1, 0] ] ```

优点： 1. 边存在性查询 O(1)：检查任意两点 $i,j$ 是否有边，只需访问 $A[i][j]$，常数时间。 2. 简单直观：矩阵形式便于数学运算，尤其是线性代数操作，这正是图信号处理与谱图理论的基础。 3. 适合稠密图：当 $m = \Theta(n^2)$ 时，矩阵没有空间浪费。

缺点： 1. 空间复杂度 $O(n^2)$：这是致命伤。对于一个拥有 100 万个节点的社交网络，即使每个用户平均只有 200 个好友（稀疏图），邻接矩阵需要 $10^{12}$ 个存储单元（假设每个单元 1 字节，约 1TB），而实际边数仅约 $10^8$ 条。巨大的空间开销在内存和计算中都不可接受。 2. 遍历所有边需 $O(n^2)$：即使图很稀疏，遍历矩阵仍需扫描所有 $n^2$ 个元素，效率低下。

邻接表：稀疏图的优雅之舞

邻接表为每个节点维护一个列表（或数组、哈希表），存储其所有邻居节点及对应边权。整个图的结构是一个由 $n$ 个列表组成的数组（或字典）。

```python

同上图的邻接表表示

adj_list = { 0: [1, 2], 1: [0, 2], 2: [0, 1] }

加权示例：0->1 权重 0.5

adj_list_weighted = { 0: [(1, 0.5), (2, 1.0)],

...

} ```

优点： 1. 空间复杂度 $O(n + m)$：仅需存储节点本身和每条边一次。对于 $n=10^6, m=10^8$ 的稀疏图，空间约为 $10^8$ 个指针/整数（几百MB），远优于矩阵的 TB 级。 2. 遍历所有边 O(m)：只需遍历每个节点的列表，总操作数与边数成正比，高效。 3. 灵活扩展：易于存储边权、边属性，也便于动态增删边。

缺点： 1. 边存在性查询 O(degree)：检查 $i,j$ 是否有边，需要遍历节点 $i$ 的邻居列表，最坏 $O(n)$，平均 $O(\text{avg degree})$。若频繁查询，可能需将列表转为哈希集合以达 $O(1)$ 平均，但增加空间与维护开销。 2. 矩阵运算不便：直接进行矩阵乘法等线性代数操作需额外转换，不如邻接矩阵直接。

博弈论：如何选择？

在实际图神经网络实现中，邻接表或其等价的稀疏矩阵表示（如 SciPy 的 `csr_matrix`）是绝对主流，因为真实世界图几乎都是稀疏的。例如，PyTorch Geometric (PyG) 和 Deep Graph Library (DGL) 内部均采用稀疏表示以支持大规模图。

然而，谱方法（Spectral Methods），如图卷积网络（GCN）的原始推导，天然依赖邻接矩阵 $A$ 和拉普拉斯矩阵 $L$。在实践中，我们通常： 1. 用邻接表存储原始图结构以节省空间。 2. 当需要进行谱操作（如特征分解、卷积）时，在计算图中将邻接表转换为稀疏矩阵格式（如 CSR/CSC），利用线性代数库（如 PyTorch、TensorFlow 的稀疏张量）高效计算。 3. 对于超大规模图，可能采用采样技术（如 GraphSAGE 的邻居采样）避免全图矩阵运算。

下表总结了核心对比：

| 特性 | 邻接矩阵 | 邻接表（稀疏矩阵） | |------|----------|-------------------| | 空间复杂度 | $O(n^2)$ | $O(n + m)$ | | 边查询时间 | $O(1)$ | $O(\text{deg})$（或 $O(1)$ 哈希） | | 遍历所有边时间 | $O(n^2)$ | $O(m)$ | | 矩阵运算便利性 | 极高 | 需稀疏矩阵库支持 | | 适用图类型 | 稠密图、小图 | 稀疏图、大图（现实世界） |

一个生动的比喻：邻接矩阵像一本全员通讯录，每个人都有一个完整页面记录与所有人的关系（哪怕大多数人无关）；邻接表则像每个人的手机通讯录，只存自己认识的人。当你要找“张三是否认识李四”，通讯录（矩阵）一翻即得；而要列出张三的所有朋友，手机通讯录（邻接表）显然更快更省内存。

图的遍历：DFS与BFS的探索舞步

图的遍历（Graph Traversal）是图算法的基石，如同在迷宫中寻找路径。两种基本策略是深度优先搜索（DFS）和广度优先搜索（BFS）。它们不仅是算法课上的经典，也为图神经网络中的邻域聚合提供了直观理解。

深度优先搜索（DFS）：一条路走到黑

DFS 从一个起始节点出发，沿着一条路径尽可能深地探索，直到遇到死胡同（无未访问邻居）再回溯到上一个分支点，继续探索其他分支。其核心是栈（Stack）结构（递归调用天然实现栈）。

伪代码： ``` DFS(u): visited[u] = True for each neighbor v of u: if not visited[v]: DFS(v) ```

特点与应用：

• **空间**：递归栈深度最坏 $O(n)$（链状图）。
• **路径发现**：常用于检测环、拓扑排序（有向无环图）、寻找强连通分量（Tarjan 算法）。
• **直觉**：像探险家手持一根长绳，深入洞穴，绳子尽头即回溯。

在神经网络语境下，DFS 的递归展开与某些递归图网络（如 Recursive Neural Networks）的思想相通，但 GNN 通常采用更局部的邻域聚合。

广度优先搜索（BFS）：涟漪扩散

BFS 从起始节点开始，先访问所有距离为 1 的邻居，再访问所有距离为 2 的邻居，依此类推，像水波纹一样逐层扩散。其核心是队列（Queue）结构。

伪代码： ``` BFS(start): queue = [start] visited[start] = True while queue not empty: u = queue.dequeue() for each neighbor v of u: if not visited[v]: visited[v] = True queue.enqueue(v) ```

特点与应用：

• **空间**：队列最坏存储 $O(n)$ 节点（星型图）。
• **最短路径**：在无权图中，BFS 第一次到达目标节点时即找到最短路径（边数最少）。
• **层次遍历**：自然给出节点到起点的距离（层数）。
• **直觉**：像石头投入水中，涟漪一圈圈扩大。

与 GNN 的联系：图卷积网络（GCN）的邻域聚合本质上是固定阶数（如 1-hop 或 2-hop）的 BFS 式聚合。例如，GCN 的一阶聚合：$h_v^{(l+1)} = \sigma(\sum_{u \in \mathcal{N}(v)} W^{(l)} h_u^{(l)})$，其中 $\mathcal{N}(v)$ 是 $v$ 的一跳邻居集合，这正对应 BFS 的第一层。高阶 GCN 或 GraphSAGE 则通过多层堆叠实现多跳聚合，类似 BFS 的多层扩散。

遍历的变种与实现细节

• **迭代 vs 递归**：DFS 递归实现简洁但可能栈溢出（大图），可用显式栈迭代实现。BFS 天然队列迭代。
• **有向图遍历**：需注意方向。DFS/BFS 在有向图中可能无法到达所有节点（如单向流）。
• **时间标记**：DFS 中记录节点第一次访问和最后一次回溯的时间戳，可用于判断祖先关系、寻找割边等。

在实际图神经网络库中，遍历通常被封装为高效的稀疏矩阵乘法（如 $A \cdot H$，其中 $A$ 是邻接矩阵，$H$ 是节点特征矩阵），这隐式地完成了所有节点的一跳邻居聚合，等价于并行化的 BFS 第一层。但理解 DFS/BFS 的递归与层次思想，对于设计更深层、更复杂的消息传递机制至关重要。

连通性：图的“一体性”度量

连通性（Connectivity）描述图中节点之间的可达程度，是图结构最根本的属性之一。不同图类型（无向/有向）有不同定义。

无向图的连通分量

在无向图中，若任意两点 $u, v$ 间存在路径（忽略方向），则称图是连通（Connected）的。若图不连通，则其 maximal connected subgraphs 称为连通分量（Connected Components）。每个分量内部连通，分量之间无连接。

检测算法：只需对每个未访问节点运行一次 DFS 或 BFS，所有访问到的节点构成一个分量。总时间 $O(n + m)$。

例子：社交网络可能由多个互不关注的社区组成；互联网理论上连通，但局部故障可能导致分区。

有向图的连通性

有向图中，路径必须遵循边方向，连通性更精细：

• **强连通（Strongly Connected）**：任意两点 $u, v$ 互相可达（$u \to v$ 且 $v \to u$）。最大强连通子图称为**强连通分量（SCC）**。
• **弱连通（Weakly Connected）**：若忽略所有边方向后，图是无向连通的。
• **单向连通（Unilaterally Connected）**：任意两点至少单向可达（$u \to v$ 或 $v \to u$）。

SCC 检测：经典算法是 Kosaraju 或 Tarjan，均基于两次 DFS，时间 $O(n + m)$。Tarjan 算法一次 DFS 利用栈和 low-link 值找出所有 SCC。

例子：网页链接图：大部分网页可相互链接？不，通常是弱连通但非强连通。Twitter 关注图：大 V 被很多人关注但可能不关注回去，形成单向可达。

连通性的意义

• **图神经网络**：若图不连通，消息传递被限制在各分量内，跨分量节点永远无法交换信息。这要求 GNN 设计时要么假设图连通，要么显式处理多个分量（如分别处理或添加虚拟边）。
• **鲁棒性**：连通性衡量网络抗攻击能力。移除关键节点（如枢纽）可能分裂图，降低连通度。
• **谱性质**：图的拉普拉斯矩阵零特征值的重数等于连通分量数（后续详述）。

图的不变量：从度序列到拉普拉斯谱

图不变量（Graph Invariants）是在图同构（节点重命名后结构相同）下保持不变的量。它们刻画了图的“指纹”，用于图比较、分类和算法设计。我们聚焦于两个层次：组合不变量（如度序列）和代数不变量（如拉普拉斯谱）。

度序列与图形序列

度序列（Degree Sequence）是图中所有节点度的非递增排列。例如，完全图 $K_n$ 的度序列为 $(n-1, n-1, ..., n-1)$。给定一个非递增正整数序列 $d_1 \ge d_2 \ge ... \ge d_n$，是否存在一个简单图（无自环、无重边） realization？这由 Erdős–Gallai 定理 判定：序列可图形化当且仅当 $\sum d_i$ 为偶数，且对任意 $k=1..n$，$\sum_{i=1}^k d_i \le k(k-1) + \sum_{i=k+1}^n \min(d_i, k)$。

意义：度序列是图最粗略的统计描述。许多真实网络具有高度异质的度分布（幂律），而随机图（如 Erdős–Rényi 模型）度分布近似泊松。GNN 的聚合操作会改变度分布，理解这一变化有助于分析过平滑（Over-smoothing）现象。

拉普拉斯矩阵：图的“拉格朗日”

拉普拉斯矩阵（Laplacian Matrix）是图论与谱图理论的核心工具，定义为 $L = D - A$，其中 $D$ 是度矩阵（对角阵，$D_{ii} = \deg(i)$），$A$ 是邻接矩阵。对于加权图，$D_{ii} = \sum_j A_{ij}$。

基本性质： 1. 对称半正定：对无权无向图，$L$ 对称且所有特征值非负。证明

拉普拉斯矩阵的深度解析：从组合优化到谱聚类

拉普拉斯矩阵 $L = D - A$ 不仅是图论中的优雅构造，更是连接离散图结构与连续线性代数的桥梁。它的性质深刻反映了图的全局与局部特征，其谱分解（特征值与特征向量）构成了图信号处理与图神经网络的数学基石。

拉普拉斯二次型：图平滑度的量化

拉普拉斯矩阵最直观的性质由其二次型揭示：对于任意实值图信号 $\mathbf{x} \in \mathbb{R}^n$（将标量值赋给每个节点，如用户活跃度、原子电荷），有 $$ \mathbf{x}^T L \mathbf{x} = \frac{1}{2} \sum_{i,j} A_{ij} (x_i - x_j)^2. $$ 证明简述：展开左边得 $\sum_i d_i x_i^2 - \sum_{i,j} A_{ij} x_i x_j$。由于 $A$ 对称，$\sum_{i,j} A_{ij} x_i x_j = \sum_{i,j} A_{ij} x_j x_i$，故 $$ 2\mathbf{x}^T L \mathbf{x} = \sum_i d_i x_i^2 + \sum_j d_j x_j^2 - 2\sum_{i,j} A_{ij} x_i x_j = \sum_{i,j} A_{ij} (x_i^2 + x_j^2 - 2x_i x_j) = \sum_{i,j} A_{ij} (x_i - x_j)^2. $$ 直观解释：二次型衡量了信号 $\mathbf{x}$ 在相邻节点间的不平滑程度。若所有相邻节点值相等（完全平滑），则 $x_i - x_j = 0$，二次型为零。反之，若相邻节点值差异大，二次型增大。因此，$L$ 本质上是图上的离散拉普拉斯算子，类似于连续域中的二阶导数，用于检测信号的“振荡”。

例子：考虑一个3节点路径图 $1-2-3$，信号 $\mathbf{x} = [1, 2, 3]^T$。邻接矩阵 $A$ 有边 $(1,2),(2,3)$，度矩阵