图论基础与谱图理论 | Graph Theory Fundamentals and Spectral Graph Theory

图论基础与谱图理论

Graph Theory Fundamentals and Spectral Graph Theory

图（Graph）作为一种离散数学结构，承载着描述实体之间关系的能力，其历史可追溯至欧拉（Leonhard Euler）在1736年对哥尼斯堡七桥问题的开创性研究。自那时起，图论便成为数学与计算机科学的核心支柱，渗透至网络分析、电路设计、交通规划、分子化学乃至人工智能等众多领域。在深度学习的演进历程中，传统的卷积神经网络（Convolutional Neural Networks, CNN）与循环神经网络（Recurrent Neural Networks, RNN）主要面向欧几里得空间（Euclidean Space）中的规则数据——如图像（图像可视为像素点阵）、文本（文本可视为词序列）——而现实世界的数据却往往呈现出非欧几里得的图结构特征。社交网络中的用户关系、知识图谱中的实体关联、分子图中的原子键合、通信网络中的拓扑连接，皆以图的形式呈现，这种结构的不规则性（irregularity）与复杂性催生了图神经网络（Graph Neural Networks, GNN）的兴起。

理解图神经网络的理论基础，必须首先掌握图论的核心概念与谱图理论（Spectral Graph Theory）的数学框架。谱图理论关注图的矩阵表示及其特征值/特征向量所揭示的结构性质，这一理论为图卷积网络（GNN在谱域的变体）提供了坚实的数学根基。本章将系统阐述图的定义与分类、图的表示方法、图的基本性质，并深入探讨谱图理论的核心内容，包括拉普拉斯矩阵（Laplacian Matrix）的谱分解、图上的傅里叶变换（Graph Fourier Transform）以及图信号处理（Graph Signal Processing）的基本概念。

1. 图的定义与分类 | Definition and Classification of Graphs

1.1 图的基本定义 | Basic Definition of Graphs

定义 1.1（图）：一个图（Graph）$G$ 是一个有序二元组$G = (V, E)$，其中$V$是一个非空有限集合，称为顶点集（Vertex Set）或节点集（Node Set），$V$中的元素称为顶点（Vertex）或节点（Node）；$E$是顶点集$V$的笛卡尔积$V \times V$的一个多重子集（Multi-subset），称为边集（Edge Set），$E$中的元素称为边（Edge）。若$E$中的元素是有序对$(u, v)$，则称该图为有向图（Directed Graph or Digraph）；若$E$中的元素是无序对$\{u, v\}$，则称该图为无向图（Undirected Graph）。

在无向图中，我们通常将边$\{u, v\}$简记为$uv$或$(u, v)$，并称$u$和$v$是这条边的端点（endpoints），或者说$u$与$v$相邻（adjacent）。若$(u, v) \in E$，则称顶点$u$和$v$是邻接的；每条边都关联两个顶点，称为该边的端点。在有向图中，边$(u, v)$从$u$指向$v$，$u$称为尾（tail），$v$称为头（head）。

定义 1.2（简单图）：若图$G = (V, E)$中不包含自环（self-loop，即$u = v$的边）且任意两个不同顶点之间至多只有一条边，则称$G$为简单图（Simple Graph）。反之，若允许自环或多重边存在，则称为多重图（Multigraph）。

定义 1.3（完全图）：若简单图$G$中任意两个不同的顶点之间都恰好有一条边，则称$G$为完全图（Complete Graph），记为$K_n$，其中$n = |V|$为顶点数。完全图$K_n$的边数为$\frac{n(n-1)}{2}$。

```mermaid graph LR A[图的基本定义] --> B[顶点集 V] A --> C[边集 E] B --> D[顶点/节点] C --> E[边/弧] D --> F[简单图] D --> G[多重图] F --> H[完全图 K_n] G --> I[允许自环和多重边] ```

定义 1.4（子图）：设$G = (V, E)$和$G' = (V', E')$是两个图，若$V' \subseteq V$且$E' \subseteq E$，则称$G'$为$G$的子图（Subgraph），记为$G' \subseteq G$。进一步，若$V' = V$且$E' \subset E$，则称$G'$为$G$的生成子图（Spanning Subgraph）或支撑子图；若$G'$仅包含$V'$中顶点之间的所有边，则称$G'$为由$V'$诱导的导出子图（Induced Subgraph），记为$G[V']$。

1.2 图的分类 | Classification of Graphs

根据不同的标准，图可分为多种类型，每种类型在建模与算法设计上各有特点。

1.2.1 有向图与无向图 | Directed and Undirected Graphs

无向图是最直觉的图模型，边不具有方向性，仅表示两端点之间存在某种关系。在社交网络建模中，“朋友关系”即是无向的——若用户$A$是用户$B$的朋友，则$B$也是$A$的朋友。在蛋白质交互网络、化合物分子结构、道路交通网络等场景中，无向图皆是自然的选择。

有向图的边具有明确的方向，从源头指向目标。在微博的关注关系中，用户$A$关注用户$B$并不意味着$B$也关注$A$，这种非对称关系需用有向边$(A, B)$表示。其他典型应用包括网页链接网络（万维网中网页之间的超链接具有方向性）、资金流向网络、工作流程调度、神经网络拓扑等。有向图中，入度（In-degree）与出度（Out-degree）的概念尤为关键：对于顶点$v$，其入度$d_{in}(v)$为指向$v$的边的数量，出度$d_{out}(v)$为从$v$发出的边的数量。

```mermaid graph TD subgraph 无向图示例 UD1((A)) --- UD2((B)) UD2 --- UD3((C)) UD1 --- UD3 end

subgraph 有向图示例 DIR1((A)) --> DIR2((B)) DIR2 --> DIR3((C)) DIR3 --> DIR1 end ```

1.2.2 加权图 | Weighted Graphs

定义 1.5（加权图）：加权图（Weighted Graph）$G = (V, E, w)$由顶点集$V$、边集$E$以及权重函数$w: E \rightarrow \mathbb{R}$组成，其中$w(e)$表示边$e$的权重。在实际应用中，权重可代表距离、成本、容量、强度、相似度等有意义的量值。

加权图广泛用于建模实际问题：道路网络中，边的权重可以是路段长度或通行时间；通信网络中，权重可表示带宽或延迟；推荐系统中，边的权重可表示用户对物品的偏好程度。在图神经网络的框架下，加权图往往对应于信号强度或关系重要性的差异，对消息传递（Message Passing）机制具有重要影响。

1.2.3 多重图 | Multigraphs

多重图允许一对顶点之间存在多条边，这在某些建模场景中不可或缺。航空网络模型中，同一城市对之间可能有多个航班运营，应以多重边表示；铁路系统中，同一区段可能承载多趟列车；电路图中，节点间可能存在多个并联元件。多重图可分为无向多重图与有向多重图，其矩阵表示需采用计数矩阵而非简单的0-1矩阵。

1.2.4 连通图与非连通图 | Connected and Disconnected Graphs

定义 1.6（连通性）：对于无向图$G = (V, E)$，若任意两个不同顶点$u, v \in V$之间都存在一条路径（Path），则称$G$为连通图（Connected Graph）。若$G$不是连通图，则其最大连通子图称为连通分量（Connected Component），简称分量。

路径是顶点序列$v_0, v_1, \ldots, v_k$，其中相邻顶点间有边相连，路径长度为边数$k$。若图中存在环（Cycle，即起点与终点相同的路径），则该图包含周期性结构。图的连通分量分析是图挖掘的基础任务，对于理解网络结构具有重要意义——例如，社交网络中往往存在多个互不关联的社群。

1.2.5 二分图 | Bipartite Graphs

定义 1.7（二分图）：若图$G = (V, E)$的顶点集$V$可以划分为两个不相交的子集$X$和$Y$（即$V = X \cup Y$且$X \cap Y = \emptyset$），使得每条边的两个端点分别属于$X$和$Y$，即$E \subseteq X \times Y$，则称$G$为二分图（Bipartite Graph），记为$G = (X, Y, E)$。

二分图天然地建模“关系”的两端，例如用户-商品交互网络（$X$为用户集，$Y$为商品集）、演员-电影网络、作者-论文网络等。特殊地，若二分图中$X$中每个顶点都与$Y$中每个顶点相连，则称为完全二分图（Complete Bipartite Graph），记为$K_{m, n}$，其中$|X| = m$，$|Y| = n$。

```mermaid graph TD subgraph 二分图结构 X1((X₁)) --> Y1((Y₁)) X1 --> Y2((Y₂)) X2((X₂)) --> Y1 X2 --> Y3((Y₃)) X3((X₃)) --> Y2 end ```

1.2.6 其他重要图类 | Other Important Graph Classes

除上述类型外，图论中还有诸多具有特殊结构的图类：树（Tree）是无环的连通无向图，恰好有$n-1$条边；有根树（Rooted Tree）指定了树中某个顶点作为根；平面图（Planar Graph）可在平面上绘制且边不相交；正则图（Regular Graph）中每个顶点具有相同的度；环图（Cyclic Graph）由一个环组成；星图（Star Graph）由一个中心顶点和若干叶顶点组成，中心与所有叶顶点相连但叶顶点之间不相连。这些特殊图类在算法设计与理论分析中具有重要价值。

2. 图的表示方法 | Graph Representations

图的结构需要通过特定的数据表示形式才能被算法处理。在计算与深度学习语境下，主要有三种矩阵表示方法：邻接矩阵、拉普拉斯矩阵与度矩阵。这些矩阵表示不仅是存储图结构的方式，更是谱图理论分析的出发点。

2.1 邻接矩阵 | Adjacency Matrix

定义 2.1（邻接矩阵）：设图$G = (V, E)$有$n = |V|$个顶点，将顶点集合标记为$V = \{v_1, v_2, \ldots, v_n\}$。图$G$的邻接矩阵（Adjacency Matrix）$\mathbf{A} \in \mathbb{R}^{n \times n}$定义为：

$$ \mathbf{A}_{ij} = \begin{cases} 1 & \text{若 } (v_i, v_j) \in E \text{ 或 } \{v_i, v_j\} \in E \\ 0 & \text{若 } (v_i, v_j) \notin E \text{ 且 } \{v_i, v_j\} \notin E \end{cases} $$

对于无向图，邻接矩阵是对称的，即$\mathbf{A} = \mathbf{A}^\top$；对于有向图，邻接矩阵一般不对称。对于加权图，$\mathbf{A}_{ij} = w(v_i, v_j)$，即直接存储边的权重，此时$\mathbf{A}_{ij} = 0$可表示无边或权重为零。

邻接矩阵提供了图的完整表示，任意两点间的可达性与路径信息可通过矩阵运算提取。邻接矩阵的$k$次幂$(\mathbf{A}^k)_{ij}$给出了顶点$v_i$与$v_j$之间长度为$k$的路径数目，这一性质在图分析中具有重要意义。

例 2.1：考虑一个包含4个顶点的简单无向图，顶点编号为$1, 2, 3, 4$，边集为$E = \{\{1,2\}, \{1,3\}, \{2,3\}, \{2,4\}, \{3,4\}\}$。其邻接矩阵为：

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

该矩阵为对称矩阵，主对角线元素为零（无自环），非对角线元素为1表示对应顶点间有边连接。

例 2.2（加权图邻接矩阵）：同一图结构，但边$\{1,2\}$权重为3，边$\{2,4\}$权重为5，其余边权重为1。则加权邻接矩阵为：

$$ \mathbf{A}_w = \begin{pmatrix} 0 & 3 & 1 & 0 \\ 3 & 0 & 1 & 5 \\ 1 & 1 & 0 & 1 \\ 0 & 5 & 1 & 0 \end{pmatrix} $$

邻接矩阵表示的优点在于直观、完整，便于通过矩阵运算进行图分析；其缺点在于对于稀疏图（大多数实际网络的边数远少于$n^2$），邻接矩阵将浪费大量存储空间（$O(n^2)$），且对于大规模图（如百万级顶点的社交网络），完整的矩阵存储与运算在计算上不可行。因此，实际系统常采用稀疏矩阵存储格式（如压缩稀疏行CSR、压缩稀疏列CSC等）以节省空间与计算资源。

2.2 度矩阵与度序列 | Degree Matrix and Degree Sequence

定义 2.2（度）：对于无向图$G = (V, E)$，顶点$v \in V$的度（Degree）记为$d(v)$或$\deg(v)$，定义为与$v$关联的边的数目。若图中有自环$(v, v)$，则在无向图中自环通常计为2度贡献（因为它关联两个端点，均为$v$）。在有向图中，顶点$v$的出度$d_{out}(v)$为从$v$发出的有向边数目，入度$d_{in}(v)$为指向$v$的有向边数目。

定义 2.3（度矩阵）：图$G = (V, E)$的度矩阵（Degree Matrix）$\mathbf{D} \in \mathbb{R}^{n \times n}$是一个对角矩阵，其对角元素为对应顶点的度：

$$ \mathbf{D}_{ii} = d(v_i), \quad \mathbf{D}_{ij} = 0 \text{ for } i \neq j $$

度矩阵与邻接矩阵结合，可定义多种图 Laplacian 矩阵，是谱图理论的核心工具。

定义 2.4（正则图与度序列）：若图中所有顶点度相同，即存在常数$k$使得$d(v) = k$对所有$v \in V$成立，则称该图为$k$-正则图（$k$-Regular Graph）。完全图$K_n$是$(n-1)$-正则图。图的度序列（Degree Sequence）是各顶点度值按某种顺序排列的序列$(d(v_1), d(v_2), \ldots, d(v_n))$，它刻画了图的度分布（Degree Distribution）。

度分布在网络分析中具有核心地位。研究表明，现实世界的网络（如互联网、社交网络、蛋白质网络）往往呈现度分布不均匀的特性，遵循所谓的幂律分布（Power-law Distribution）$P(d) \propto d^{-\gamma}$，这类网络被称为无标度网络（Scale-free Networks）。无标度网络中，绝大多数顶点度很小（扮演“普通人”角色），少数顶点度极大（扮演“网红”或“枢纽节点”角色），这种异质性对图神经网络的消息传递机制具有深刻影响——高度顶点将接收和传递更多信息，其特征更新往往更为主导。

2.3 拉普拉斯矩阵 | Laplacian Matrix

拉普拉斯矩阵（Laplacian Matrix），或称图拉普拉斯算子（Graph Laplacian Operator），是谱图理论的基石，连接了图的代数性质与几何结构。在图神经网络的谱域方法中，拉普拉斯矩阵的谱（即特征值与特征向量）扮演着核心角色。

定义 2.5（无向图拉普拉斯矩阵）：对于无向加权图$G = (V, E, w)$，其拉普拉斯矩阵（通常意义的）定义为$\mathbf{L} = \mathbf{D} - \mathbf{A}$，即度矩阵减去邻接矩阵。对于无权重图（每条边权重为1），该定义依然适用。

展开来看，拉普拉斯矩阵的元素定义为：

$$ \mathbf{L}_{ij} = \begin{cases} d(v_i) & \text{若 } i = j \\ -1 & \text{若 } i \neq j \text{ 且 } (v_i, v_j) \in E \\ 0 & \text{若 } i \neq j \text{ 且 } (v_i, v_j) \notin E \end{cases} $$

对于加权图，拉普拉斯矩阵定义为$\mathbf{L}_{ij} = \mathbf{D}_{ii} - \mathbf{A}_{ij}$，即：

$$ \mathbf{L}_{ij} = \begin{cases} \sum_{k} w(v_i, v_k) & \text{若 } i = j \\ -w(v_i, v_j) & \text{若 } i \neq j \text{ 且 } (v_i, v_j) \in E \\ 0 & \text{其他} \end{cases} $$

定义 2.6（对称归一化拉普拉斯矩阵）：在实际应用中，更常用的是对称归一化拉普拉斯矩阵（Symmetric Normalized Laplacian）：

$$ \mathbf{L}_{sym} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2} $$

对称归一化拉普拉斯矩阵的元素形式为：

$$ \math