图论基础 / Fundamentals of Graph Theory

在图论（Graph Theory）中，图（Graph）是描述事物之间关系的一种抽象数学模型。从社交网络中的 friendships 到分子结构中的化学键，从互联网的拓扑结构到交通路网，图结构无处不在。一个图 $G$ 由顶点集 $V$（Vertices，也称 Nodes）和边集 $E$（Edges，也称 Links）组成，记为 $G = (V, E)$。顶点代表研究对象，边代表研究对象之间的关系。例如，在社交网络中，顶点可以表示用户，边表示用户之间的好友关系。这种将复杂系统抽象为图的方式，为分析其结构和动态特性提供了强有力的数学工具。图神经网络（Graph Neural Networks, GNNs）正是建立在这一数学基础上，通过消息传递机制学习图中顶点和边的表示。因此，扎实的图论基础是理解 GNN 的关键前提。本章将系统介绍图论的核心概念、分类体系、矩阵表示方法以及基本属性，并通过中英双语对照，为后续章节的深入学习奠定坚实的数学基础。

图的基本定义与核心术语

图的数学定义

形式上，一个图 $G$ 被定义为有序对 $G = (V, E)$，其中 $V$ 是非空顶点集合，$E$ 是边集合，每条边是 $V$ 中两个顶点的无序对（对于无向图）或有序对（对于有向图）。顶点数 $|V|$ 通常记为 $n$，边数 $|E|$ 记为 $m$。当 $V$ 和 $E$ 都是有限集时，称 $G$ 为有限图（Finite Graph），这也是本书讨论的主要对象。

考虑一个简单的无向图示例：$V = \{1, 2, 3\}$，$E = \{\{1,2\}, \{2,3\}, \{1,3\}\}$。这表示三个顶点两两相连，形成一个三角形。若用有向图表示，边可能是有序对，如 $(1,2)$ 表示从顶点 1 指向顶点 2 的弧（Arc）。

顶点与边

顶点（Vertex/Node）是图的基本单元，代表实体（Entity）。边（Edge/Link）代表实体间的关系（Relationship）。在无向图（Undirected Graph）中，边 $\{u, v\}$ 没有方向，表示 $u$ 与 $v$ 的对称关系；在有向图（Directed Graph，也称 Di-graph）中，边 $(u, v)$ 表示从 $u$ 到 $v$ 的方向性关系，$u$ 称为起点（Source），$v$ 称为终点（Target）。

自环（Self-loop）：一条连接顶点与自身的边，即 $\{v, v\}$ 或 $(v, v)$。自环在某些应用中有意义，例如在社交网络中，用户关注自己可能表示某种自我引用。

多重边（Multi-edge）：两个顶点之间可以存在多条边。例如，在通信网络中，两个城市之间可能有多条光纤链路。允许自环和多重边的图称为伪图（Pseudograph）；不允许自环但允许多重边的图称为多图（Multigraph）；既不允许自环也不允许多重边的图称为简单图（Simple Graph）。除非特别说明，本书默认讨论简单图。

度（Degree）

顶点的度（Degree）是与其关联的边数，是衡量顶点局部重要性的基本指标。

• **无向图**：顶点 $v$ 的度记为 $\deg(v)$，等于与 $v$ 相连的边数。例如，在上面的三角形图中，每个顶点的度均为 3。
• **有向图**：分为**入度（In-degree）** $\deg^-(v)$，指向 $v$ 的边数；**出度（Out-degree）** $\deg^+(v)$，从 $v$ 发出的边数。显然，$\deg(v) = \deg^-(v) + \deg^+(v)$。

握手定理（Handshaking Lemma）：在任何图中，所有顶点的度之和等于边数的两倍，即 $\sum_{v \in V} \deg(v) = 2m$。这是因为每条边贡献两个度（无向图）或一个入度一个出度（有向图，总和仍为 $2m$）。该定理可推导出：任何图中，度数为奇数的顶点个数必为偶数。

```mermaid graph LR A[顶点 A] --- B[顶点 B] B --- C[顶点 C] A --- C style A fill:#e1f5fe style B fill:#f3e5f5 style C fill:#e8f5e8 ``` *图 1.1：一个无向简单图示例，顶点 A、B、C 的度均为 2。*

路径（Path）、回路（Circuit）与连通性（Connectivity）

路径：顶点序列 $v_0, v_1, \dots, v_k$，其中每对相邻顶点 $(v_{i-1}, v_i)$ 都是一条边。路径长度（Length）是边数 $k$。若起点和终点相同（$v_0 = v_k$），则称为回路（Circuit）或环（Cycle）。若路径中顶点互异（除起点终点可能相同外），称为简单路径（Simple Path）；若回路中除起点终点外顶点互异，称为简单回路（Simple Cycle）。

最短路径（Shortest Path）：两点间长度最小的路径，其长度称为距离（Distance）。最短路径问题是图论和 GNN 中的核心计算问题之一。

连通性：

• **无向图**：若任意两个顶点间都存在路径，则图是**连通图（Connected Graph）**。否则，图分解为多个**连通分量（Connected Component）**，每个分量是极大的连通子图。例如，若图有两个不相连的部分，则有两个连通分量。
• **有向图**：若忽略方向后图连通，则称为**弱连通（Weakly Connected）**；若任意两个顶点间都存在双向路径（即 $u$ 可达 $v$ 且 $v$ 可达 $u$），则称为**强连通（Strongly Connected）**。强连通分量（Strongly Connected Component, SCC）是极大的强连通子图。

连通性反映了图的结构完整性。在社交网络中，连通分量对应孤立社群；在互联网中，强连通分量可能表示相互可达的服务器集群。

子图（Subgraph）与诱导子图（Induced Subgraph）

子图：若图 $G' = (V', E')$ 满足 $V' \subseteq V$ 且 $E' \subseteq E$，且 $E'$ 中每条边的端点均在 $V'$ 中，则 $G'$ 是 $G$ 的子图。

诱导子图：给定顶点子集 $V' \subseteq V$，由 $V'$ 及 $G$ 中所有端点均在 $V'$ 中的边构成的子图，记为 $G[V']$。诱导子图保留了 $V'$ 之间的所有原始关系，是 GNN 中常见的采样目标。

特殊图结构

• **完全图（Complete Graph）** $K_n$：任意两个不同顶点间均有边，即 $m = \binom{n}{2}$。每个顶点度为 $n-1$。
• **正则图（Regular Graph）**：所有顶点度相同的图。$k$-正则图每个顶点度为 $k$。
• **二分图（Bipartite Graph）**：顶点集可划分为两个不相交子集 $U$ 和 $W$，使得每条边都连接 $U$ 和 $W$ 中的顶点。二分图可表示为矩阵，常用于推荐系统。
• **树（Tree）**：连通且无简单回路的无向图。树有 $n-1$ 条边，是连通的极小图。**有根树**指定一个根顶点，具有层次结构。
• **环图（Cycle Graph）** $C_n$：$n$ 个顶点排列成环，每个顶点度为 2。

```mermaid graph TD subgraph 完全图 K4 A[1] --- B[2] A --- C[3] A --- D[4] B --- C B --- D C --- D end style A fill:#ffebee style B fill:#f3e5f5 style C fill:#e1f5fe style D fill:#e8f5e8 ``` *图 1.2：完全图 $K_4$，每对顶点间均有边。*

图的分类体系

图的分类基于不同的结构特征，理解这些类型对于选择合适的 GNN 模型至关重要。

无向图与有向图

这是最基本的分类。无向图表示对称关系，如朋友关系（若 A 是 B 的朋友，则 B 也是 A 的朋友）；有向图表示非对称关系，如关注关系（A 关注 B 不蕴含 B 关注 A）。在 GNN 中，消息传递机制在无向图中通常是对称的，而在有向图中需要考虑方向性，例如使用入度或出度进行归一化。

加权图与无权图

无权图（Unweighted Graph）：所有边权重为 1 或视为存在与否。这是最简形式。

加权图（Weighted Graph）：每条边 $e$ 有一个权重 $w(e) \in \mathbb{R}$，表示关系的强度或成本。例如，在交通网络中，边权重可以是距离或通行时间；在分子图中，边权重可以是键级（单键、双键等）。加权图可视为无权图的扩展，邻接矩阵元素为权重而非 0/1。

同构图与异构图

同构图（Homogeneous Graph）：所有顶点属于同一类型，所有边属于同一类型。大多数经典图论和早期 GNN 研究基于同构图，如社交网络（用户-用户）或分子图（原子-键）。

异构图（Heterogeneous Graph）：包含多种类型的顶点和边。例如，学术网络中，顶点类型包括论文（Paper）、作者（Author）、会议（Venue）；边类型包括“撰写”（WrittenBy）、“发表于”（PublishedIn）。异构图更贴近现实，但需要专门设计的 GNN 模型（如 HGT、RGCN）来处理类型信息。

动态图与时序图

静态图（Static Graph）：顶点、边及其属性不随时间变化。大多数教材和图数据集是静态的。

动态图（Dynamic Graph）：顶点或边随时间添加、删除或属性变化。例如，社交网络中的好友关系随时间演变。动态图可分为离散时间动态图（快照序列）和连续时间动态图（事件序列）。处理动态图需要时序建模能力，如使用循环神经网络或时间注意力。

其他重要分类

• **稀疏图 vs 稠密图**：若边数 $m \ll n^2$，为稀疏图；若 $m$ 接近 $n^2$，为稠密图。真实世界图（如社交网络、互联网）通常是稀疏的（$m = O(n)$ 或 $O(n \log n)$），这影响了 GNN 的计算效率。
• **平面图（Planar Graph）**：可在平面上画出且边不相交的图。分子图通常是平面图。
• **树与森林**：无回路的连通图是树；不连通的森林是树的集合。

图的矩阵表示方法

矩阵表示将图转化为代数形式，便于进行线性代数运算，是 GNN 实现的核心。本节介绍三种基本矩阵：邻接矩阵、度矩阵和拉普拉斯矩阵。

邻接矩阵（Adjacency Matrix）

对于 $n$ 个顶点的图，邻接矩阵 $A \in \{0,1\}^{n \times n}$（无权图）或 $A \in \mathbb{R}^{n \times n}$（加权图）定义为：

$$ A_{ij} = \begin{cases} w(i,j) & \text{若边 } (i,j) \in E \\ 0 & \text{否则} \end{cases} $$

其中 $w(i,j)$ 是边权重（无权图为 1）。对于无向图，$A$ 是对称矩阵（$A = A^\top$）；对于有向图，$A$ 一般不对称。

示例：考虑有向图 $V=\{1,2,3\}$，$E=\{(1,2),(2,3),(1,3)\}$，则

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

邻接矩阵的 $i$ 行和（无向图）或行和（有向图出度）等于顶点 $i$ 的度（或出度）。邻接矩阵的幂 $A^k$ 的 $(i,j)$ 元素表示从 $i$ 到 $j$ 长度为 $k$ 的路径数目。

在 GNN 中，邻接矩阵常作为消息传递的权重矩阵，定义邻居聚合的范围。实际应用中，邻接矩阵可能非常庞大（$n$ 很大），因此常采用稀疏矩阵存储格式（如 CSR、CSC）。

度矩阵（Degree Matrix）

度矩阵 $D \in \mathbb{R}^{n \times n}$ 是对角矩阵，对角元素为各顶点的度：

$$ D_{ii} = \deg(v_i) = \sum_{j=1}^n A_{ij} \quad (\text{无向图或出度}) $$

对于有向图，可分别定义入度矩阵 $D^{\text{in}}$ 和出度矩阵 $D^{\text{out}}$，其中 $(D^{\text{in}})_{ii} = \sum_j A_{ji}$，$(D^{\text{out}})_{ii} = \sum_j A_{ij}$。

示例：对上例有向图，出度矩阵为

$$ D^{\text{out}} = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 0 \end{pmatrix} $$

度矩阵在归一化邻接矩阵时起关键作用，例如在 Graph Convolutional Networks (GCN) 中，归一化邻接矩阵为 $\tilde{A} = D^{-1/2} A D^{-1/2}$。

拉普拉斯矩阵（Laplacian Matrix）

拉普拉斯矩阵 $L$ 定义为度矩阵与邻接矩阵之差：

$$ L = D - A $$

对于无向图，$L$ 是对称半正定矩阵，具有重要谱性质。其元素为：

$$ L_{ij} = \begin{cases} \deg(v_i) & \text{若 } i=j \\ -1 & \text{若 } i \neq j \text{ 且 } (i,j) \in E \\ 0 & \text{否则} \end{cases} $$

示例：对无向三角形图（每个顶点度 2），

$$ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 0 & 1 \\ 1 & 1 & 0 \end{pmatrix},\quad D = \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix},\quad L = \begin{pmatrix} 2 & -1 & -1 \\ -1 & 2 & -1 \\ -1 & -1 & 2 \end{pmatrix} $$

拉普拉斯矩阵的特征值非负，且最小特征值为 0，对应特征向量为全 1 向量。特征值分布反映图的连通性：若图有 $k$ 个连通分量，则 $L$ 有 $k$ 个零特征值。这些性质被用于谱聚类（Spectral Clustering）和图信号处理。

归一化拉普拉斯矩阵

为避免度差异的影响，常使用归一化版本：

• **对称归一化拉普拉斯矩阵**：$L_{\text{sym}} = I - D^{-1/2} A D^{-1/2} = D^{-1/2} L D^{-1/2}$
• **随机游走归一化拉普拉斯矩阵**：$L_{\text{rw}} = I - D^{-1} A$

$L_{\text{sym}}$ 对称，适合谱分析；$L_{\text{rw}}$ 与随机游走转移矩阵相关。在 GCN 中，$\tilde{A} = D^{-1/2} A D^{-1/2} = I - L_{\text{sym}}$ 直接用于卷积。

关联矩阵（Incidence Matrix，可选）

关联矩阵 $B \in \{0,1\}^{n \times m}$ 描述顶点与边的关联关系。对于无向图，每列（对应一条边）在边的两个端点位置为 1。对于有向图，通常起点为 -1，终点为 1。关联矩阵满足 $L = B B^\top$（无向图），建立了图与线性代数的深刻联系。

矩阵表示在 GNN 中的意义

在 GNN 中，邻接矩阵 $A$ 定义了消息传递的邻居集合。例如，在 GraphSAGE 中，顶点 $v$ 的新表示通过聚合其邻居 $N(v)$ 的表示得到，数学上可写为 $h_v^{(l+1)} = \text{AGGREGATE}^{(l)}(\{h_u^{(l)}, \forall u \in N(v)\})$，其中 $N(v)$ 由 $A$ 确定。度矩阵 $D$ 用于归一化，防止度大的顶点主导聚合结果。拉普拉斯矩阵的谱分解可视为图上的傅里叶变换，为图卷积提供理论基础（尽管 GCN 简化了谱方法）。

图的基本拓扑属性

除了前述连通性，图还有许多刻画全局或局部结构的属性。

传递闭包（Transitive Closure）

对于有向图，传递闭包是包含原图所有可达关系的最小图：若存在从 $u$ 到 $v$ 的路径，则传递闭包中存在边 $(u,v)$。传递闭包可通过计算 $A$ 的布尔幂（$A^* = I \lor A \lor A^2 \lor \dots$）得到，或使用 Warshall 算法。在知识图谱中，传递闭包用于推理隐含关系。

团（Clique）与独立集（Independent Set）

• **团**：顶点子集 $C \subseteq V$，使得 $C$ 中任意两个顶点均有边相连。即 $G[C]$ 是完全子图。最大团（Maximal Clique）是不能被更大团包含的团；最大团（Maximum Clique）是顶点数最多的团。寻找最大团是 NP-hard 问题。
• **独立集**：顶点子集 $I \subseteq V$，使得 $I$ 中任意两个顶点均无边相连。即 $G[I]$ 无边。最大独立集问题也是 NP-hard。

团和独立集互为补集：$I$ 是 $G$ 的独立集当且仅当 $I$ 是补图 $\bar{G}$ 的团。

图直径与平均路径长度

• **直径（Diameter）**：图中所有顶点对之间距离的最大值。直径小表示图“小世界”，如社交网络的六度分隔。
• **平均路径长度（Average Path Length）**：所有顶点对距离的平均值。衡量图的全局可达性。

聚类系数（Clustering Coefficient）

聚类系数衡量顶点邻居之间的紧密程度，反映图的聚集倾向。

• **局部聚类系数**：对于顶点