1. 图结构数据的数学基础 | Mathematical Foundations of Graph-Structured Data

图结构数据（Graph-Structured Data）是现实世界中广泛存在的一类非欧几里得（Non-Euclidean）数据结构，从社交网络中的用户好友关系、分子生物学中的原子化学键连接，到知识图谱中的实体-关系-实体三元组，再到交通网络中的道路节点连通性，其核心特征是通过节点（Node）和边（Edge）的二元关系描述实体间的关联，而非传统深度学习所擅长的规则网格（如图像）或序列（如文本）结构。这种非结构化的拓扑特性使得传统卷积神经网络（CNN）基于平移不变性（Translation Invariance）的卷积操作、循环神经网络（RNN）基于顺序依赖的序列建模方法难以直接适配，因此构建图结构数据的统一数学表示框架、推导其上的信号处理与运算规则，是图神经网络（Graph Neural Network, GNN）与知识图谱表示学习（Knowledge Graph Representation Learning, KGRL）研究的核心数学基础。

1.1 图的数学表示

形式化地，一个图$G$可定义为三元组$G = (V, E, \mathcal{W})$，其中$V = \{v_1, v_2, ..., v_n\}$是包含$n$个节点的有限集合，$E \subseteq V \times V$是边的集合，$\mathcal{W}$是边权重的集合。根据边的方向性和权重特性，图可分为四类基础类型：无向图（Undirected Graph）中边无方向，即若$(v_i, v_j) \in E$则$(v_j, v_i) \in

$E$则$(v_j, v_i) \in E$，即边的关系具有对称性，典型场景为社交网络中的用户好友关系、分子结构中的原子共价键连接，此时邻接矩阵为对称矩阵；有向图（Directed Graph）中边具有方向性，仅当$(v_i, v_j) \in E$时存在从$v_i$到$v_j$的有向边，典型场景为社交媒体的用户关注关系、知识图谱中的实体-关系指向、交通网络的单行道拓扑，此时邻接矩阵为非对称矩阵；加权图（Weighted Graph）中每条边关联一个非负实数权重$w_{ij} \in \mathcal{W}$，用于量化节点间关联的强度，典型场景为交通网络中的道路通行时间/距离、知识图谱中关系的置信度、分子图中的原子间作用力大小，此时邻接矩阵的元素为对应边的权重$A_{ij}=w_{ij}$；二部图（Bipartite Graph）的节点集合可划分为两个互不相交的子集$V_1, V_2$，所有边均连接不同子集的节点，即$E \subseteq V_1 \times V_2$，典型场景为电商平台的用户-商品交互图、学术网络的作者-论文发表图、推荐系统中的用户-物品评分图。

除上述四类基础图类型外，实际应用中还存在两类常见特殊结构：自环（Self-loop）指起点和终点相同的边，即$(v_i, v_i) \in E$，在知识图谱中用于表示实体的自反关系（如“的人是”），在图神经网络中常用于实现节点的自连接，保留节点自身的特征信息；多重边（Multi-edge）指两个节点之间存在多条不同的边，典型场景为两个城市之间的多条航线、知识图谱中两个实体之间的多种关系类型。无自环和多重边的图被称为简单图（Simple Graph），是绝大多数基础GNN研究的默认假设，而包含上述特殊结构的图被称为复杂图（Complex Graph），是工业场景中的主流形态。

1.1.1 邻接矩阵（Adjacency Matrix）

邻接矩阵是图的最基础矩阵表示，用于编码节点间的连接关系。对于包含$n$个节点的图$G$，其邻接矩阵$A \in \mathbb{R}^{n \times n}$定义为： $$ A_{ij} = \begin{cases} w_{ij}, & (v_i, v_j) \in E \\ 0, & (v_i, v_j) \notin E \end{cases} \tag{1.1} $$ 其中$w_{ij}$为边$(v_i, v_j)$的权重，无向图中$A_{ij}=A_{ji}$，因此$A$为对称矩阵；有向图中$A_{ij}$仅表示从$v_i$到$v_j$的边权重，无对称性约束。邻接矩阵的幂次具有明确的路径语义：$A^k$的$(i,j)$元素表示从节点$v_i$到$v_j$的长度为$k$的路径数量（加权图中为路径的权重乘积和），这一性质是图神经网络消息传递（Message Passing）机制的数学基础——GNN的$k$层信息聚合恰好对应节点$k$步可达邻居的特征融合。

以本章开头的四节点环图$G$为例（节点编号0、1、2、3，边为(0,1)、(1,2)、(2,3)、(3,0)，无权重），其邻接矩阵为： $$ A = \begin{bmatrix} 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 1 \\ 1 & 0 & 1 & 0 \end{bmatrix} $$ 计算$A^2$可得： $$ A^2 = \begin{bmatrix} 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \\ 2 & 0 & 2 & 0 \\ 0 & 2 & 0 & 2 \end{bmatrix} $$ 其中$A^2_{02}=2$，对应节点0到节点2的长度为2的路径有两条：0→1→2和0→3→2，与直观理解完全一致。邻接矩阵的谱半径（最大特征值）是图的重要拓扑属性，在社交网络中对应影响力的最大传播范围，在知识图谱中对应关系的最大传播深度。

1.1.2 度矩阵（Degree Matrix）

度矩阵是描述节点连接数量的对角矩阵，其定义与邻接矩阵直接相关。对于无向图，节点$v_i$的度（Degree）$d_i$为其邻接节点的数量（加权图中为邻接边权重之和），即$d_i = \sum_{j=1}^n A_{ij}$；对于有向图，需区分出度（Out-degree）$d_i^{out} = \sum_{j=1}^n A_{ij}$（从$v_i$出发的边数量）和入度（In-degree）$d_i^{in} = \sum_{j=1}^n A_{ji}$（指向$v_i$的边数量）。

度矩阵$D \in \mathbb{R}^{n \times n}$为对角矩阵，对角线元素为对应节点的度： $$ D_{ij} = \begin{cases} d_i, & i=j \\ 0, & i \neq j \end{cases} \tag{1.2} $$ 对于有向图，可分别定义出度矩阵$D_{out}$和入度矩阵$D_{in}$，对角线元素为对应节点的出度和入度。度矩阵与邻接矩阵的迹（Trace）满足重要关系：无向图中$\text{tr}(A) = 0$（对角线元素为0），$\text{tr}(D) = \sum_{i=1}^n d_i = 2|E|$，其中$|E|$为边的总数，因为每条边会被两个节点的度各计算一次；有向图中$\text{tr}(D_{out}) = \text{tr}(D_{in}) = |E|$，因为每条边仅被一个出度和一个入度各计算一次。

以四节点环图为例，每个节点的度均为2，因此度矩阵为： $$ D = \begin{bmatrix} 2 & 0 & 0 & 0 \\ 0 & 2 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 2 \end{bmatrix} $$ 对于异质图（如知识图谱），度矩阵的分布往往呈现高度长尾性：热门实体（如“美国”“人工智能”）的度可达数千甚至数万，而冷门实体的度仅为1或2，这种度不均匀性是图神经网络训练中需要重点解决的问题，也是归一化矩阵设计的核心动机。

1.1.3 拉普拉斯矩阵（Laplacian Matrix）及其变体

拉普拉斯矩阵是图论中最核心的矩阵之一，由邻接矩阵和度矩阵推导而来，其基础定义（无向图）为： $$ L = D - A \tag{1.3} $$ 拉普拉斯矩阵的变体主要分为三类，分别适用于不同的图类型和应用场景： 1. 对称拉普拉斯矩阵（Symmetric Laplacian）：无向图的基础形式，即上述的$L=D-A$，为实对称半正定矩阵，具有正交的特征向量基，是谱图理论的核心研究对象。 2. 归一化对称拉普拉斯矩阵（Normalized Symmetric Laplacian）：为解决度不均匀问题提出，定义为$L_{sym} = D^{-1/2} L D^{-1/2} = I - D^{-1/2} A D^{-1/2}$，其中$I$为单位矩阵，$D^{-1/2}$为度矩阵的负二分之一次方（即对角线元素为$d_i^{-1/2}$，若$d_i=0$则对应元素为0）。归一化后，每个节点的贡献被调整到同一尺度，避免了高 degree 节点的主导效应。 3. 随机游走拉普拉斯矩阵（Random-walk Laplacian）：定义为$L_{rw} = D^{-1} L = I - D^{-1} A$，其物理意义为随机游走的转移矩阵的补矩阵，在PageRank、图随机游走等任务中应用广泛。

对于有向图，拉普拉斯矩阵通常定义为$L = D_{out} - A$，为非对称矩阵，其谱分析需要用到左特征向量和右特征向量，是知识图谱、有向社交网络等场景的研究基础。

拉普拉斯矩阵具有一系列核心性质，是后续所有图信号处理和GNN理论的基石： 1. 半正定性：对于任意向量$x \in \mathbb{R}^n$，二次型$x^T L x \geq 0$，即所有特征值非负。可通过如下推导证明： $$ \begin{align*} x^T L x &= x^T (D - A) x \\ &= \sum_{i=1}^n d_i x_i^2 - \sum_{i,j=1}^n A_{ij} x_i x_j \\ &= \frac{1}{2} \sum_{i,j=1}^n A_{ij} (x_i - x_j)^2 \tag{1.4} \end{align*} $$ 公式(1.4)的物理意义为：$x^T L x$衡量了图信号$x$的总变差（Total Variation），即所有相邻节点信号差异的平方和。若信号在相邻节点上完全平滑（$x_i=x_j$对所有边$(i,j)$成立），则总变差为0；若信号在相邻节点上震荡剧烈，则总变差很大。这一性质是图信号平滑、图半监督学习、图正则化等技术的核心理论基础。 2. 零特征值与全1特征向量：拉普拉斯矩阵的最小特征值为0，对应的特征向量为全1向量$\mathbf{1} = [1,1,...,1]^T$，可通过直接代入验证：$L \mathbf{1} = (D - A) \mathbf{1} = D\mathbf{1} - A\mathbf{1} = \mathbf{d} - \mathbf{d} = 0$，其中$\mathbf{d}$为度向量。零特征值的重数等于图的连通分量数量，若图连通则零特征值的重数为1。 3. 代数连通度（Algebraic Connectivity）：拉普拉斯矩阵的最小非零特征值$\lambda_2$被称为代数连通度，是衡量图连通性的核心指标：$\lambda_2$越大，图越难被分割为两个独立的连通分量，图的整体连通性越强。例如，四节点环图的$\lambda_2=1$，而四节点链式图（0-1-2-3）的$\lambda_2 \approx 0.38$，说明环图的连通性显著优于链式图。

以四节点环图为例，其拉普拉斯矩阵为： $$ L = \begin{bmatrix} 2 & -1 & 0 & -1 \\ -1 & 2 & -1 & 0 \\ 0 & -1 & 2 & -1 \\ -1 & 0 & -1 & 2 \end{bmatrix} $$ 其特征值分解为$L = U \Lambda U^T$，其中特征值矩阵$\Lambda = \text{diag}(0,1,1,4)$，特征向量矩阵为： $$ U = \begin{bmatrix} \frac{1}{2} & \frac{1}{\sqrt{2}} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & \frac{1}{\sqrt{2}} & -\frac{1}{2} \\ \frac{1}{2} & -\frac{1}{\sqrt{2}} & 0 & \frac{1}{2} \\ \frac{1}{2} & 0 & -\frac{1}{\sqrt{2}} & -\frac{1}{2} \end{bmatrix} $$ 可以看到，对应特征值0的特征向量为全1向量，对应特征值1的两个特征向量为低频分量，相邻节点的分量差异较小，对应特征值4的特征向量为高频分量，相邻节点的分量差异最大，直观体现了特征值与频率的对应关系。

```mermaid graph LR A[任意向量x∈ℝⁿ] --> B[计算二次型xᵀLx] B --> C[代入L=D-A展开] C --> D[重写为½ΣA_ij(x_i - x_j)²] D --> E[结论：L半正定，xᵀLx≥0] E --> F[物理意义：图信号总变差] ```

1.2 图信号处理基础

图信号处理（Graph Signal Processing, GSP）是传统数字信号处理（DSP）在图结构上的推广，其核心目标是将传统信号处理的理论和工具扩展到非欧几里得的图结构上，为图神经网络的谱域设计提供理论支撑。

1.2.1 图信号的定义与特性

图信号（Graph Signal）是定义在图节点上的标量或向量值函数，可形式化表示为$x: V \rightarrow \mathbb