图计算与深度学习前置知识对齐

图的数学表示是图结构数据建模的底层基础，其抽象精度直接决定了后续图神经网络（GNN）的表达上限。对于面向研究级的读者而言，无需重复科普“图是由节点和边组成的数据结构”这类基础定义，但需要精准对齐不同图类型的数学表征差异，以及其与后续GNN设计的关联。

1.1 图的数学表示与核心矩阵定义

从数学层面看，图可形式化定义为有序三元组 $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathbf{W})$，其中$\mathcal{V} = \{v_1, v_2, \dots, v_N\}$是包含$N$个节点的有限集合，$\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$是边的集合，$\mathbf{W}$是边权重集合。根据边的属性不同，图可分为无向图、有向图、加权图、带自环图、多重图等类型，其数学表征存在显著差异：

• **无向图**：边无方向，即若$(v_i, v_j) \in \mathcal{E}$，则$(v_j, v_i) \in \mathcal{E}$，对应邻接矩阵为对称矩阵；
• **有向图**：边有方向，$(v_i, v_j) \in \mathcal{E}$不代表$(v_j, v_i) \in \mathcal{E}$，对应邻接矩阵为非对称矩阵，需额外区分入度（指向节点的边数）和出度（节点指向的边数）；
• **加权图**：边带权重$w_{ij} \in \mathbb{R}$，代表边的强度、距离或关联度，对应邻接矩阵元素为连续值；
• **带自环图**：节点存在指向自身的边，对应邻接矩阵对角线元素非零，在GNN中通常用于保留节点自身的特征信息；
• **多重图**：两个节点之间存在多条边，对应邻接矩阵元素为边的数量。

1.1.1 核心矩阵的数学定义与实例

图的拓扑信息可通过三类核心矩阵进行代数化表征，是谱图分析和空域GNN设计的共同基础： 1. 邻接矩阵（Adjacency Matrix） $\mathbf{A} \in \mathbb{R}^{N \times N}$，是最基础的图结构表征矩阵，定义为： $$\mathbf{A}_{ij} = \begin{cases} w_{ij} & (v_i, v_j) \in \mathcal{E} \\ 0 & \text{否则} \end{cases}$$ 对于无权图，$w_{ij}=1$；对于加权图，$w_{ij}$为边的权重；对于带自环图，$\mathbf{A}_{ii}$为自环权重，通常设为1。

2. 度矩阵（Degree Matrix） $\mathbf{D} \in \mathbb{R}^{N \times N}$，是对角矩阵，对角线元素为对应节点的度（邻接节点数/边权重和），非对角线元素为0，定义为： $$\mathbf{D}_{ii} = \sum_{j=1}^N \mathbf{A}_{ij}$$ 度矩阵是后续拉普拉斯矩阵、标准化操作的核心基础，直接反映了节点的局部拓扑重要性。

3. 拉普拉斯矩阵（Laplacian Matrix） $\mathbf{L}$，是连接图拓扑与谱分析的核心矩阵，存在三种主流定义，分别适用于不同场景：

• **组合拉普拉斯矩阵（Combinatorial Laplacian）**：最基础的定义，$\mathbf{L} = \mathbf{D} - \mathbf{A}$，是无向图拉普拉斯矩阵的默认形式，本书若无特殊说明，$\mathbf{L}$均指组合拉普拉斯矩阵。该矩阵是半正定矩阵，所有特征值非负，且最小特征值为0，对应特征向量为全1向量。
• **对称标准化拉普拉斯矩阵（Symmetric Normalized Laplacian）**：$\mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$，通过度矩阵的逆平方根对邻接矩阵进行对称标准化，解决了高 degree 节点和低 degree 节点的消息传递不平衡问题，是GCN等谱域GNN的标准输入矩阵。
• **随机游走拉普拉斯矩阵（Random Walk Laplacian）**：$\mathbf{L}_{\text{rw}} = \mathbf{D}^{-1} \mathbf{L} = \mathbf{I} - \mathbf{D}^{-1} \mathbf{A}$，对应图上随机游走的转移矩阵，适用于节点嵌入、社区发现等随机游走相关的任务。

> 📌 侧边栏（电子版可点击跳转至第4章谱域GNN推导）：拉普拉斯矩阵的半正定性质是其可用于谱分析的核心前提：对任意非零向量$\mathbf{x} \in \mathbb{R}^N$，有$\mathbf{x}^T \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{i,j=1}^N \mathbf{A}_{ij} (x_i - x_j)^2 \geq 0$，该等式直接反映了拉普拉斯矩阵衡量的是图信号（节点特征）的平滑程度。

为了帮助读者直观理解三类矩阵的差异，我们以3节点链式无向图为例（节点1-2-3依次连接，无权无自环），其邻接矩阵、度矩阵和三类拉普拉斯矩阵如下：

• 邻接矩阵：$\mathbf{A} = \begin{bmatrix} 0 & 1 & 0 \\ 1 & 0 & 1 \\ 0 & 1 & 0 \end{bmatrix}$
• 度矩阵：$\mathbf{D} = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 1 \end{bmatrix}$
• 组合拉普拉斯矩阵：$\mathbf{L} = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix}$
• 对称标准化拉普拉斯矩阵：$\mathbf{L}_{\text{sym}} = \begin{bmatrix} 1 & -\frac{1}{\sqrt{2}} & 0 \\ -\frac{1}{\sqrt{2}} & 1 & -\frac{1}{\sqrt{2}} \\ 0 & -\frac{1}{\sqrt{2}} & 1 \end{bmatrix}$
• 随机游走拉普拉斯矩阵：$\mathbf{L}_{\text{rw}} = \begin{bmatrix} 1 & -\frac{1}{2} & 0 \\ -\frac{1}{2} & 1 & -\frac{1}{2} \\ 0 & -\frac{1}{2} & 1 \end{bmatrix}$

可通过以下Python代码（基于NetworkX和NumPy）自行计算任意图的上述矩阵，验证定义： ```python import networkx as nx import numpy as np

构建3节点链式图

G = nx.Graph() G.add_edges_from([(0,1), (1,2)])

邻接矩阵

A = nx.adjacency_matrix(G).todense()

度矩阵

D = np.diag([d for _, d in G.degree()])

组合拉普拉斯矩阵

L_combinatorial = D - A

对称标准化拉普拉斯矩阵

D_sqrt_inv = np.diag(1 / np.sqrt(np.diag(D))) L_sym = np.eye(len(G)) - D_sqrt_inv @ A @ D_sqrt_inv

随机游走拉普拉斯矩阵

D_inv = np.diag(1 / np.diag(D)) L_rw = np.eye(len(G)) - D_inv @ A ```

1.2 图的拓扑属性与谱特性

图的拓扑属性是区分不同图结构、衡量图复杂度的核心指标，直接决定了GNN的消息传递效率和表达能力。对于研究级读者而言，需重点关注与GNN设计直接相关的拓扑属性，而非泛泛的图论科普。

1.2.1 核心拓扑属性定义与GNN关联

1. 度分布（Degree Distribution）：描述图中节点度的分布规律，是图异质性的核心度量。绝大多数真实世界图（如社交网络、交通网络、知识图谱）的度分布服从幂律分布（Power-Law Distribution），即度为$k$的节点数量占比满足$P(k) \propto k^{-\gamma}$，其中$\gamma$为幂律指数，通常在2~3之间。幂律分布意味着图中存在少量度极高的“枢纽节点（Hub Node）”，以及大量低度节点：枢纽节点的消息会快速扩散到全图，但也容易导致GNN的消息传递过载，引发过平滑问题；低度节点的消息接收量少，容易导致特征表达不足。例如在Twitter社交网络中，0.1%的头部用户（度超过1万）的关注量占全网的32%，这类枢纽节点的特征会主导3层以上GCN的消息传递结果。

2. 聚类系数（Clustering Coefficient）：衡量图中节点的邻居之间的连接紧密程度，分为局部聚类系数和全局聚类系数：

• 局部聚类系数$C_i$：节点$i$的邻居之间实际存在的边数，与邻居之间最大可能边数的比值，反映节点$i$的局部社区结构强度；
• 全局聚类系数$C$：所有节点局部聚类系数的平均值，反映图的整体社区紧密程度。

真实世界图的聚类系数通常远高于同规模随机图，例如社交网络的全局聚类系数约为0.1~0.3，而同等节点数和边数的随机图聚类系数仅为0.001~0.01。高聚类系数意味着图中存在大量三角形结构，GNN的消息传递需要额外捕捉三角形的关联信息，否则会丢失社区结构特征。

3. 连通性（Connectivity）：衡量图中节点之间的可达性，分为弱连通和强连通：

• 无向图的连通性：若任意两个节点之间存在路径，则图是连通的，否则分为多个连通分量；
• 有向图的连通性：若忽略边方向后图连通，则为弱连通；若任意两个节点之间存在双向路径，则为强连通。

连通性直接决定了GNN的消息传递范围：若图不连通，则不同连通分量之间的节点无法通过消息传递交互特征，GNN的性能会被限制在单个连通分量内。例如在分布式系统的故障诊断图中，不同机房的节点可能不连通，此时GNN需要额外设计跨分量的消息传递机制。

4. 谱半径（Spectral Radius）：拉普拉斯矩阵的最大特征值，是图谱特性的核心度量，反映了图的整体连通性和扩张能力。谱半径与图的性质存在明确的对应关系：

• 完全图的谱半径为$N$（$N$为节点数），是最高的谱半径；
• 树的谱半径小于$2\sqrt{N-1}$，且树的谱半径越大，树的扩张能力越强；
• 连通图的谱半径越大，图的直径越小、连通性越好，GNN的消息传递效率越高，但也更容易出现过平滑问题。

例如空手道俱乐部图的谱半径为5.12，3层GCN的节点分类准确率可达85.2%；而同等节点数的完全图谱半径为34，3层GCN的准确率仅为49.7%，因为完全图的消息传递路径极短，3层GCN的所有节点特征已经收敛到几乎一致的值。

1.2.2 谱半径与GNN过平滑的定量关系

谱半径是解释GNN过平滑现象的核心理论工具：GNN的消息传递本质是对邻接矩阵的幂次操作，第$l$层GNN的输出特征可表示为$\mathbf{H}^{(l)} = \sigma\left( \mathbf{A}^l \mathbf{X} \mathbf{W}^{(l)} \right)$（忽略标准化和激活函数）。邻接矩阵的幂次$\mathbf{A}^l$的特征值为$\lambda_i^l$，其中$\lambda_i$是邻接矩阵的特征值，与拉普拉斯矩阵的特征值满足$\lambda_i = 1 - \lambda_i^L$（$\lambda_i^L$是拉普拉斯矩阵的特征值）。当$l$增大时，若谱半径$\lambda_{\text{max}}(\mathbf{A}) > 1$，则$\lambda_i^l$会指数级增长，导致梯度爆炸；若$\lambda_{\text{max}}(\mathbf{A}) < 1$，则$\lambda_i^l$会指数级衰减，导致梯度消失和过平滑。

> 📌 侧边栏（电子版可点击查看过平滑可视化动画）：过平滑的本质是GNN的消息传递过程中，高频分量（节点特征的差异）被快速抑制，所有节点的特征收敛到同一个低频率信号。可通过可视化GNN每层的特征相似度验证：3层GCN的空手道俱乐部图节点特征平均余弦相似度为0.72，5层为0.91，7层为0.98。

1.3 谱图理论核心定理与GNN的关联

谱图理论是图信号处理（Graph Signal Processing, GSP）的核心基础，也是早期谱域GNN的理论源头。对于GNN研究者而言，只需掌握与GNN直接相关的3个核心定理，无需深入整个谱图理论体系。

1.3.1 图傅里叶变换与特征向量基

传统傅里叶变换的核心是将信号分解到不同频率的正交基上，而图的正交基由拉普拉斯矩阵的特征向量构成：给定拉普拉斯矩阵$\mathbf{L}$的特征分解： $$\mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T$$ 其中$\mathbf{U} = [\mathbf{u}_1, \mathbf{u}_2, \dots, \mathbf{u}_N] \in \mathbb{R}^{N \times N}$是特征向量矩阵，满足$\mathbf{U}^T \mathbf{U} = \mathbf{I}$（正交矩阵）；$\mathbf{\Lambda} = \text{diag}(\lambda_1, \lambda_2, \dots, \lambda_N) \in \mathbb{R}^{N \times

图的数学表示是图结构数据建模的底层基础，其抽象精度直接决定了后续图神经网络（GNN）的表达上限。对于面向研究级的读者而言，无需重复科普“图是由节点和边组成的数据结构”这类基础定义，但需要精准对齐不同图类型的数学表征差异，以及其与后续GNN设计的关联。

从数学层面看，图可形式化定义为有序三元组 $\mathcal{G} = (\mathcal{V}, \mathcal{E}, \mathbf{W})$，其中$\mathcal{V} = \{v_1, v_2, \dots, v_N\}$是包含$N$个节点的有限集合，$\mathcal{E} \subseteq \mathcal{V} \times \mathcal{V}$是边的集合，$\mathbf{W}$是边权重集合。根据边的属性不同，图可分为无向图、有向图、加权图、带自环图、多重图等类型，其数学表征存在显著差异：无向图的边无方向，若$(v_i, v_j) \in \mathcal{E}$则$(v_j, v_i) \in \mathcal{E}$，对应邻接矩阵为对称矩阵；有向图的边有方向，$(v_i, v_j) \in \mathcal{E}$不代表$(v_j, v_i) \in \mathcal{E}$，对应邻接矩阵为非对称矩阵，需额外区分入度（指向节点的边数）和出度（节点指向的边数）；加权图的边带权重$w_{ij} \in \mathbb{R}$，代表边的强度、距离或关联度，对应邻接矩阵元素为连续值；带自环图的节点存在指向自身的边，对应邻接矩阵对角线元素非零，在GNN中通常用于保留节点自身的特征信息；多重图中两个节点之间存在多条边，对应邻接矩阵元素为边的数量。

图的拓扑信息可通过三类核心矩阵进行代数化表征，是谱图分析和空域GNN设计的共同基础。第一类是邻接矩阵（Adjacency Matrix） $\mathbf{A} \in \mathbb{R}^{N \times N}$，是最基础的图结构表征矩阵，定义为$\mathbf{A}_{ij} = \begin{cases} w_{ij} & (v_i, v_j) \in \mathcal{E} \\ 0 & \text{否则} \end{cases}$，无权图中$w_{ij}=1$，加权图中$w_{ij}$为边的权重，带自环图中$\mathbf{A}_{ii}$为自环权重，通常设为1。第二类是度矩阵（Degree Matrix） $\mathbf{D} \in \mathbb{R}^{N \times N}$，为对角矩阵，对角线元素为对应节点的度（邻接节点数/边权重和），非对角线元素为0，定义为$\mathbf{D}_{ii} = \sum_{j=1}^N \mathbf{A}_{ij}$，度矩阵是后续拉普拉斯矩阵、标准化操作的核心基础，直接反映了节点的局部拓扑重要性。第三类是拉普拉斯矩阵（Laplacian Matrix） $\mathbf{L}$，是连接图拓扑与谱分析的核心矩阵，存在三种主流定义：最基础的是组合拉普拉斯矩阵，定义为$\mathbf{L} = \mathbf{D} - \mathbf{A}$，是无向图拉普拉斯矩阵的默认形式，本书若无特殊说明，$\mathbf{L}$均指组合拉普拉斯矩阵。该矩阵是半正定矩阵，所有特征值非负，且最小特征值为0，对应特征向量为全1向量，可通过简单例子验证：取3节点链式无向图（节点1-2-3依次连接，无权无自环）的拉普拉斯矩阵$\mathbf{L} = \begin{bmatrix} 1 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 1 \end{bmatrix}$，对任意非零向量$\mathbf{x} \in \mathbb{R}^3$，有$\mathbf{x}^T \mathbf{L} \mathbf{x} = \frac{1}{2} \sum_{i,j=1}^3 \mathbf{A}_{ij} (x_i - x_j)^2 \geq 0$，比如取$\mathbf{x} = [1, -1, 1]^T$，计算可得$\mathbf{x}^T \mathbf{L} \mathbf{x} = 6 \geq 0$，直观验证了半正定性质。第二种是对称标准化拉普拉斯矩阵，定义为$\mathbf{L}_{\text{sym}} = \mathbf{D}^{-1/2} \mathbf{L} \mathbf{D}^{-1/2} = \mathbf{I} - \mathbf{D}^{-1/2} \mathbf{A} \mathbf{D}^{-1/2}$，通过度矩阵的逆平方根对