Name: 深度图学习：原理、模型与前沿实践
Author: step-3.5-flash

图结构数据与表示学习基础

表示学习作为机器学习的核心范式之一，旨在将离散、符号化的数据对象映射为连续、低维的向量表示，使得在向量空间中的几何关系（如距离、角度）能够反映原始数据的内在语义或结构相似性。对于欧几里得数据（如图像、文本、时间序列），卷积、循环等操作因其平移不变性或时序连续性而天然适用， representations 往往通过端到端训练与任务目标紧密耦合。然而，图结构数据——无论是社交网络、分子化合物、交通网络还是知识图谱——本质上具有不规则性和可变拓扑，传统的深度学习架构无法直接应用。这催生了一个根本性问题：如何为图数据设计一种统一的表示学习框架，既能捕捉其结构特性，又能灵活融合节点特征，并适应从半监督分类到链接预测等多种下游任务？

本章将超越常见的图神经网络（GNN）入门介绍，从表示学习的统一视角重新审视这一问题。我们将首先深入剖析图的结构特性——同质性、异质性、小世界性与无标度性——并形式化地论证这些特性如何从根本上影响表示学习的设计空间。随后，我们将建立严格的数学符号体系，将图上的信号处理、滤波与聚合操作统一到图信号处理（Graph Signal Processing, GSP）的框架下，从而为理解后续各类GNN模型提供共同的理论基础。在此基础上，我们将系统回顾以DeepWalk、Node2Vec为代表的传统图嵌入方法，揭示其基于浅层模型和随机游走假设的固有局限，进而逻辑严密地引出神经网络方法的必然性：唯有通过可微的消息传递机制，才能实现结构-特征联合的端到端优化，并自适应地处理复杂图结构。本章内容不仅为全书奠定坚实的数学与概念基础，更旨在培养读者一种“从谱到空域、从统一到特化”的分析思维，以应对快速演进的图学习前沿。

---

图的结构特性及其对表示学习的影响

图并非一个单一、同质的数据结构，而是具有丰富拓扑特性的复杂系统。这些特性并非装饰性的细节，而是决定表示学习算法成败的核心因素。理解它们，是设计有效模型的第一步。

同质性假设及其双面性

同质性（Homophily）是许多现实图（如社交网络、引文网络、部分生物网络）的普遍现象：连接的节点倾向于具有相同的标签或相似的特征。定量上，同质性常通过边缘同质性（Edge Homophily）衡量：$h_{edge} = \frac{1}{|\mathcal{E}|} \sum_{(u,v) \in \mathcal{E}} \mathbb{I}(y_u = y_v)$，即连接节点标签一致的边所占比例。高同质性图（$h_{edge} > 0.7$）上，简单的邻域聚合（如取邻居特征的平均）往往能取得良好效果，因为“物以类聚”意味着邻居信息是节点自身属性的强预测信号。例如，在政治博客网络中，用户倾向于关注观点相近的博主，因此一个用户的嵌入可以通过其关注列表的嵌入平均来初步估计。

然而，过度依赖同质性假设是危险的。首先，许多重要图是异质的（Heterophilic），例如用户-商品二分图（用户与商品连接，但用户与用户、商品与商品之间可能无边）、欺诈检测图（欺诈者与正常用户相连，标签相反）或某些分子图（原子类型不同但化学键相连）。在这些图上，邻域聚合可能引入噪声，甚至导致“过平滑”（Over-smoothing）问题：经过多层聚合后，所有节点嵌入趋同，失去判别力。其次，即使整体同质性高，局部异质性也可能存在：一个社区内部高度同质，但社区之间通过少量“桥接”边连接。这些桥接边对信息传播和社区检测至关重要，但简单的聚合可能淹没其信号。因此，现代GNN设计必须考虑自适应聚合（如通过注意力机制为不同邻居分配不同权重）或分离同质与异质邻居（如使用跳连接或子图采样）。

小世界性与信息传播效率

小世界性（Small-worldness）由高聚类系数和短平均路径长度共同定义。社交网络是典型的小世界网络：你的朋友的朋友很可能也是你的朋友（高聚类），而你与世界另一端的人可能仅通过六度分隔相连（短路径）。从表示学习角度看，小世界性意味着信息可以在少数跳内传播到全局。理论上，如果图直径$D$很小，那么一个$L$层GNN（每层聚合一跳邻居）在$L \geq D$时就能让每个节点感知到全图信息。这解释了为何在直径小的小世界图上，较深的GNN可能有效，而在直径大的树状或链状图上，深层GNN容易因感受野有限或过平滑而失效。

然而，小世界性也带来挑战：短路径可能导致过平滑加速。由于信息快速混合，深层GNN中不同节点的嵌入迅速收敛到相似向量。实践中，常通过残差连接（如Jumping Knowledge Networks）、分层池化或早期停止来缓解。此外，小世界网络的聚类结构暗示存在社区，而社区内节点可能具有相似功能。因此，表示学习应能捕捉这种局部模块性，例如通过图池化操作（如DiffPool）将节点聚类为超节点，形成层次化表示。

无标度性与度分布的影响

无标度性（Scale-freeness）指节点度分布服从幂律：少数“枢纽”节点拥有大量连接（高中心性），而大多数节点连接稀疏。互联网、引文网络、代谢网络常呈现此特性。这对表示学习有深远影响：

1. 枢纽节点的信息主导性：在聚合操作中，若简单平均或求和，高连 degree 枢纽节点的特征会多次、重复地贡献到其众多邻居的表示中，可能导致其嵌入主导整个图的表示，而稀疏节点被淹没。解决方案包括归一化（如GCN中使用对称归一化$\mathbf{\tilde{D}}^{-1/2} \mathbf{\tilde{A}} \mathbf{\tilde{D}}^{-1/2}$，其中$\mathbf{\tilde{A}} = \mathbf{A} + \mathbf{I}$）以平衡不同度节点的贡献，或使用注意力机制让节点学习为不同邻居分配权重，从而减轻枢纽效应。

2. 稀疏节点的表示困难：低连 degree 节点（如新加入社交网络的用户）的邻居信息极少，单层聚合后表示可能不可靠。多跳聚合虽能扩大感受野，但可能引入不相关噪声。因此，针对稀疏节点，可能需要特征增强（如结合节点属性预训练）或自适应采样（如GraphSAGE中根据节点度调整采样邻居数）。

3. 对异常检测的意义：无标度性下，枢纽节点往往是关键基础设施或影响力中心，其异常（如被攻击、成为欺诈中心）可能破坏整个网络。表示学习若能准确编码枢纽节点的角色，将极大助力异常检测任务。

结构特性对模型设计的综合启示

下表总结了主要结构特性、其影响及相应的设计考量：

值得注意的是，真实图往往同时具备多种特性。例如，一个学术合作网络可能是同质的（同一领域学者合作）、小世界的（合作链短）、且无标度的（少数学者合作广泛）。因此，理想的表示学习框架应具备灵活性，能通过模块化设计（如聚合函数、归一化方式、采样策略）适应不同特性组合。这正是神经网络方法相较于传统浅层嵌入的优势所在：其参数化形式允许在训练中自动调整以适应数据内在结构。

---

图上的信号、滤波与聚合：形式化定义

为了超越具体模型，我们需要一个统一的形式化框架。图信号处理（GSP）提供了这一基础，将图视为一个离散域，其上定义的函数称为图信号，而卷积等操作则通过图拉普拉斯矩阵的谱性质定义。

图信号与图傅里叶变换

设图$G = (\mathcal{V}, \mathcal{E})$有$N$个节点，节点集$\mathcal{V} = \{1, ..., N\}$。一个图信号是定义在节点上的实值函数，可视为$\mathbb{R}^N$中的一个向量$\mathbf{x} = [x_1, ..., x_N]^T$，其中$x_i$是节点$i$的信号值。在机器学习中，图信号可以是节点的特征（如用户画像）、标签（如类别）、或任意节点属性。当有$F$维特征时，信号矩阵为$\mathbf{X} \in \mathbb{R}^{N \times F}$，每一列是一个独立的图信号。

图的核心结构信息编码在拉普拉斯矩阵中。最常用的组合拉普拉斯矩阵定义为： $$ \mathbf{L} = \mathbf{D} - \mathbf{A} $$ 其中$\mathbf{A} \in \{0,1\}^{N \times N}$是邻接矩阵（无向图对称），$\mathbf{D} \in \mathbb{R}^{N \times N}$是度矩阵，对角元素$d_{ii} = \sum_j A_{ij}$。$\mathbf{L}$是对称半正定的，因此可进行特征分解： $$ \mathbf{L} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T $$ 其中$\mathbf{U} = [\mathbf{u}_1, ..., \mathbf{u}_N] \in \mathbb{R}^{N \times N}$是特征向量矩阵（正交，$\mathbf{U}^T \mathbf{U} = \mathbf{I}$），$\mathbf{\Lambda} = \text{diag}(\lambda_1, ..., \lambda_N)$是特征值对角矩阵，满足$0 = \lambda_1 \leq \lambda_2 \leq ... \leq \lambda_N \leq 2$（对于归一化拉普拉斯）。特征向量$\mathbf{u}_k$构成了图上的傅里叶基，对应频率递增的谐波：$\mathbf{u}_1$是常数向量（零频率），高频特征向量对应快速振荡的模式。

图傅里叶变换（Graph Fourier Transform, GFT）将图信号从节点域（空间域）变换到谱域（频率域）： $$ \hat{\mathbf{x}} = \mathbf{U}^T \mathbf{x} $$ $\hat{\mathbf{x}}_k = \mathbf{u}_k^T \mathbf{x}$是信号在频率$\lambda_k$上的分量。逆变换为$\mathbf{x} = \mathbf{U} \hat{\mathbf{x}}$。GFT的物理意义：它揭示了信号在图的全局结构模式（由特征向量定义）上的投影。例如，在一个社区结构明显的图上，低频特征向量可能在社区内部同号、社区之间反号，因此一个平滑的信号（相邻节点值相近）其GFT系数集中在低频。

图滤波与图卷积

在传统信号处理中，滤波是在频域乘以一个传递函数$g(\lambda)$，然后逆变换回空间域。类比到图上，图滤波器$g_\theta(\mathbf{L})$是一个关于$\mathbf{L}$的函数（通常参数化为$\theta$），图卷积定义为： $$ \mathbf{x} * g_\theta = \mathbf{U} g_\theta(\mathbf{\Lambda}) \mathbf{U}^T \mathbf{x} $$ 其中$g_\theta(\mathbf{\Lambda}) = \text{diag}(g_\theta(\lambda_1), ..., g_\theta(\lambda_N))$。这一定义保证了平移不变性的图类比：在规则网格（如图像）上，卷积是平移等变的；在图上，由于节点无序，图卷积被定义为与图的拉普拉斯特征结构交换的线性算子，即满足$\mathbf{U} g(\mathbf{\Lambda}) \mathbf{U}^T \mathbf{A} = \mathbf{A} \mathbf{U} g(\mathbf{\Lambda}) \mathbf{U}^T$（在特定条件下）。

然而，直接计算GFT和逆变换复杂度为$O(N^2)$，不适用于大图。实践中，滤波器被参数化为$\mathbf{L}$的多项式，从而避免显式对角化： $$ g_\theta(\mathbf{L}) = \sum_{k=0}^{K} \theta_k \mathbf{L}^k $$ 其中$\theta_k$是可学习参数，$K$是滤波器支撑大小（多项式阶数）。代入卷积定义： $$ \mathbf{x} * g_\theta = \sum_{k=0}^{K} \theta_k \mathbf{L}^k \mathbf{x} $$ 注意$\mathbf{L}^k \mathbf{x}$可递归计算，且$\mathbf{L}^k_{ij}$非零当且仅当节点$i$和$j$之间距离不超过$k$（在未加权图上）。因此，多项式滤波器本质上是K跳邻域的线性组合，每个$\mathbf{L}^k \mathbf{x}$可以视为在$k$跳邻域上的某种聚合。这直接连接了谱域卷积与空域聚合。

空域聚合操作：消息传递框架

从空域视角，图神经网络的核心是消息传递（Message Passing）或邻域聚合（Neighborhood Aggregation）。给定节点特征$\mathbf{h}_i^{(l)} \in \mathbb{R}^{F^{(l)}}$（第$l$层），聚合函数$\text{AGGREGATE}$收集邻居信息，更新函数$\text{COMBINE}$融合自身与邻居信息： $$ \mathbf{h}_i^{(l+1)} = \text{COMBINE}^{(l)} \left( \mathbf{h}_i^{(l)}, \text{AGGREGATE}^{(l)}(\{ \mathbf{h}_j^{(l)} : j \in \mathcal{N}(i) \}) \right) $$ 其中$\mathcal{N}(i)$是节点$i$的邻居集（通常包括$i$自身）。通过堆叠$L$层，节点$i$的最终表示$\mathbf{z}_i$融合了其$L$跳邻域内的结构信息和特征。

关键问题在于如何设计$\text{AGGREGATE}$和$\text{COMBINE}$。常见选择包括：

**均值**：$\text{AGGREGATE} = \text{mean}(\cdot)$，对应GCN的对称归一化邻接矩阵$\mathbf{\tilde{D}}^{-1/2} \mathbf{\tilde{A}} \mathbf{\tilde{D}}^{-1/2}$，其中$\mathbf{\tilde{A}} = \mathbf{A} + \mathbf{I}$，$\mathbf{\tilde{D}}$为对应度矩阵。可证明，当$\text{COMBINE}$为$\sigma(\cdot \mathbf{W})$时，GCN层等价于一阶多项式滤波器$g_\theta(\mathbf{L}) = \theta_0 \mathbf{I} + \theta_1 \mathbf{L}_{sym}$（忽略非线性）。
**求和**：$\text{AGGREGATE} = \text{sum}(\cdot)$，对应未归一化邻接矩阵$\mathbf{A}$，但未考虑度差异。
**最大池化**：$\text{AGGREGATE} = \text{max}(\cdot)$，对每个特征维取邻居最大值，能捕捉局部显著模式但可能丢失统计信息。
**注意力**：$\text{AGGREGATE}$为加权和，权重$\alpha_{ij} = \text{Attention}(\mathbf{h}_i, \mathbf{h}_j)$由节点对特征动态计算，如GAT。

谱域与空域的等价性：多项式滤波器$g_\theta(\mathbf{L}) = \sum_{k=0}^{K} \theta_k \mathbf{L}^k$作用于信号$\mathbf{X}$等价于一个$K$层GNN，其中每层聚合$k$跳邻居，且参数共享（每层用相同$\theta_k$）。但实际GNN（如GraphSAGE）允许每层不同参数，且$\text{AGGREGATE}$不限于线性组合（如最大池化、注意力），因此空域框架更灵活。谱域框架的优势在于理论分析清晰（如滤波器频率响应、平滑性），空域框架则更易扩展和工程实现。

---

传统图嵌入方法回顾与局限

在GNN兴起之前，图表示学习主要通过浅层嵌入（Shallow Embedding）实现：为每个节点学习一个独立的低维向量$\mathbf{z}_i \in \mathbb{R}^d$，目标函数直接基于图结构（有时结合特征）优化，不涉及多层非线性变换。这些方法在2010年代中期占据主流，为图表示学习奠定了基础，但存在根本性局限。

DeepWalk：基于随机游走的Skip-gram

DeepWalk将图视为一个“文档”，通过截断随机游走生成节点序列，然后应用词嵌入模型Skip-gram来学习节点嵌入。具体地： 1. 对每个节点启动多次随机游走，每次走$t$步，产生长度为$t$的节点序列。 2. 将每个序列视为句子，使用Skip-gram（或负采样）最大化中心节点预测上下文窗口内节点的概率。 3. 优化后，节点$i$的嵌入$\mathbf{z}_i$使其在向量空间中接近其在随机游走中频繁共现的节点。

思想核心：随机游走捕获了图的二阶邻近度（Two-step Proximity）——两个节点在随机游走中共同出现的概率反映了它们在图中的连接强度。通过调整游走长度和窗口大小，可以控制捕获的局部结构范围。

局限：

**仅利用结构，忽略特征**：