图小波变换深度专题

1. 从Fourier到Wavelet

1.1 Fourier变换的局限

标准图Fourier变换基于拉普拉斯特征基：

$\overset{x}{^} (λ_{i}) = ⟨ x, u_{i} ⟩$

问题：

全局基：每个特征向量 $u_{i}$ 的支撑是整个图
缺乏局部性：无法高效表示局部信号变化
解释困难：特征值顺序不一定对应直观频率

1.2 小波变换的优势

小波基通过尺度函数提供局部化的频域表示：

特性	Fourier	Wavelet
基函数	全局正弦波	局部小波
频率分辨率	固定	多尺度
空间定位	无	高
计算复杂度	$O (n^{2})$	$O(k

2. 图小波框架

2.1 谱域小波定义

对于图 $G$ 和尺度参数 $s$ ，定义小波基函数：

$ψ_{s, i} (j) = [U Σ (s)^{1/2} U^{⊤}]_{ij}$

其中：

$U$ ：拉普拉斯特征向量矩阵
$Σ (s) = diag (λ_{1}^{s}, λ_{2}^{s}, \dots, λ_{n}^{s})$ ：尺度矩阵

简化形式（扩散小波）：

$ψ_{s, i} = (I - s L)^{i} e_{i}$

其中 $e_{i}$ 是节点 $i$ 的单位向量。

2.2 框架条件

小波基 ${ψ_{s, i}}$ 需满足框架条件：

$A ∥ x ∥^{2} \leq \sum_{s, i} ∣ ⟨ x, ψ_{s, i} ⟩ ∣^{2} \leq B ∥ x ∥^{2}$

其中 $A, B$ 是框架界（Frame Bounds）。

紧框架：当 $A = B = 1$ 时，小波基构成紧框架，信号可完美重建。

2.3 小波系数的计算

import torch
import scipy.sparse as sp
 
def compute_wavelet_coefficients(L, node_i, scales, k=20):
    """
    计算节点i在不同尺度下的小波系数
    
    参数:
        L: 归一化拉普拉斯矩阵
        node_i: 源节点索引
        scales: 尺度列表 [s1, s2, ..., sS]
        k: Chebyshev多项式阶数
    """
    n = L.shape[0]
    lambda_max = sp.linalg.eigsh(L, k=1, return_eigenvectors=False)[0]
    
    # 预计算Chebyshev基
    T = compute_chebyshev_basis(L, k, lambda_max)
    
    coeffs = []
    for s in scales:
        # 小波系数 = T_k(s) @ e_i
        e_i = torch.zeros(n)
        e_i[node_i] = 1.0
        
        # 通过Chebyshev近似计算 (I - sL)^i @ e_i
        wavelet_coef = e_i
        for power in range(1, int(1/s) + 1):
            wavelet_coef = (1 - s) * wavelet_coef - s * (L @ wavelet_coef)
        
        coeffs.append(wavelet_coef)
    
    return torch.stack(coeffs, dim=0)  # (S, n)

3. 图小波变换理论

3.1 小波框架的构建

扩散型小波通过迭代应用扩散算子构建：

$T_{s} = (I - s L)^{k}$

框架分解：任意信号 $x$ 可分解为：

$x = \sum_{s, i} ⟨ x, ψ_{s, i} ⟩ \tilde{ψ}_{s, i}$

其中 $\tilde{ψ}_{s, i}$ 是对偶框架元。

3.2 多尺度分析

尺度函数： $ϕ = ψ_{s_{0}, i}$ 对应最粗糙的尺度

细节系数： $ψ_{s, i}$ 对应不同尺度 $s > s_{0}$ 的细节

class MultiScaleAnalysis:
    def __init__(self, scales=[0.1, 0.5, 1.0, 5.0]):
        self.scales = scales  # 从细到粗
        
    def forward(self, x, L):
        """
        多尺度分解
        
        返回:
            approx: 近似系数（最粗尺度）
            details: 各尺度的细节系数
        """
        details = []
        
        for s in self.scales:
            # 计算小波变换
            wavelet_coeff = compute_wavelet(x, s, L)
            details.append(wavelet_coeff)
        
        # 最小尺度作为近似
        approx = details[0]
        
        return approx, details
    
    def inverse(self, approx, details, L):
        """
        多尺度重构
        """
        # 从最粗尺度开始重建
        x = approx
        
        for detail, s in zip(reversed(details), reversed(self.scales)):
            # 应用逆小波变换
            x = x + apply_inverse_wavelet(detail, s, L)
        
        return x

3.3 局部化特性

小波基的核心优势是空间局部化：

定义（局部化度量）：

$∥ ψ_{s, i} ∥_{2}^{2} = [U Σ (s) U^{⊤}]_{ii}$

衰减性质：对于连通图上的小波，有：

$∥ ψ_{s, i} ∥_{2}^{2} \approx e^{- s \cdot d (i, j)}$

即小波能量集中在距离 $i$ 约 $1/ s$ 的区域内。

4. 图小波神经网络

4.1 GWNN架构

Graph Wavelet Neural Network（GWNN）¹ 是首个利用图小波的GNN架构：

class GWNN(nn.Module):
    """
    Graph Wavelet Neural Network
    
    核心思想：用小波基替代Fourier基进行图卷积
    """
    def __init__(self, in_channels, out_channels, scales, k=20):
        super().__init__()
        self.scales = scales
        self.k = k
        
        # 小波基（预计算）
        self.psi = {}  # {scale: wavelet_basis}
        self.psi_inv = {}
        
        # 可学习的滤波器权重
        self.filter_weights = nn.Parameter(
            torch.randn(len(scales), k, in_channels, out_channels)
        )
        
    def set_wavelet_basis(self, L):
        """
        设置拉普拉斯矩阵并预计算小波基
        """
        n = L.shape[0]
        lambda_max = torch.linalg.eigvalsh(L).max()
        
        for s in self.scales:
            # 计算小波基 psi_s = (I - sL)^k
            I = torch.eye(n)
            L_s = I - s * L
            
            # Chebyshev近似
            psi_s = self._chebyshev_approximate(L_s, self.k, lambda_max)
            
            self.psi[s] = psi_s
            self.psi_inv[s] = psi_s.T  # 对于紧框架，对偶基是转置
        
    def forward(self, x, L):
        """
        x: (batch, n, in_channels)
        """
        if not self.psi:
            self.set_wavelet_basis(L)
        
        outputs = []
        for s in self.scales:
            # 小波域变换
            x_wavelet = self.psi[s] @ x  # (batch, n, in_channels)
            
            # 逐通道卷积
            x_filtered = torch.einsum(
                'bni,kic->bnkc',
                x_wavelet,
                self.filter_weights[self.scales.index(s)]
            ).sum(dim=2)  # (batch, n, out_channels)
            
            # 逆变换回空域
            x_spatial = self.psi_inv[s] @ x_filtered
            outputs.append(x_spatial)
        
        return torch.stack(outputs).sum(dim=0)

4.2 GWNN的优势

特性	GCN	GWNN
基函数	拉普拉斯特征向量	图小波基
局部化	全局	局部
计算效率	$O(	E
可解释性	低	高（频率-空间对应）
特征学习	隐式	可学习的谱滤波器

4.3 WaveGC架构

WaveGC²（ICML 2025）通过Chebyshev阶分解实现通用图小波卷积：

核心创新：

矩阵值滤波器：而非标量到标量的频率响应
奇偶分解：分别学习偶对称和奇对称部分
小波容许性：满足 $\sum_{s} ψ_{s} = 1$ （信号守恒）

class WaveGC(nn.Module):
    """
    WaveGC: 通用图小波卷积
    
    论文: "A General Graph Spectral Wavelet Convolution 
          via Chebyshev Order Decomposition" (ICML 2025)
    """
    def __init__(self, in_channels, out_channels, scales, K=10):
        super().__init__()
        self.scales = scales
        self.K = K
        
        # 奇偶分解的权重
        self.theta_even = nn.Parameter(torch.randn(K // 2 + 1, in_channels, out_channels))
        self.theta_odd = nn.Parameter(torch.randn(K // 2, in_channels, out_channels))
        
        # 多尺度融合权重
        self.scale_weights = nn.Parameter(torch.ones(len(scales)))
        
    def chebyshev_order_decompose(self, L_norm, K):
        """
        Chebyshev阶分解：
        将矩阵函数分解为奇偶部分
        """
        # 偶阶项
        T_even = [torch.eye(L_norm.size(0))]
        for k in range(2, K, 2):
            T_even.append(self._chebyshev_recursive(L_norm, k))
        
        # 奇阶项
        T_odd = []
        for k in range(1, K, 2):
            T_odd.append(self._chebyshev_recursive(L_norm, k))
        
        return T_even, T_odd
    
    def forward(self, x, L):
        """
        x: (batch, n, in_channels)
        """
        # 归一化拉普拉斯
        lambda_max = torch.linalg.eigvalsh(L).max()
        L_norm = 2 * L / lambda_max - torch.eye(L.size(0))
        
        # Chebyshev分解
        T_even, T_odd = self.chebyshev_order_decompose(L_norm, self.K)
        
        outputs = []
        for s in self.scales:
            # 计算尺度矩阵
            S = self._scale_matrix(s, lambda_max)
            
            # 偶阶小波（低频）
            wavelet_even = sum(
                S @ theta for S, theta in zip(T_even, self.theta_even)
            )
            
            # 奇阶小波（高频）
            wavelet_odd = sum(
                S @ theta for S, theta in zip(T_odd, self.theta_odd)
            )
            
            # 合并奇偶部分
            wavelet = wavelet_even + wavelet_odd
            
            # 应用小波滤波器
            out = x @ wavelet
            outputs.append(out)
        
        # 多尺度融合
        fused = torch.stack(outputs) * self.scale_weights.softmax(dim=0).view(-1, 1, 1, 1)
        return fused.sum(dim=0)

5. 短程与长程信号分离

5.1 小波的多分辨率特性

不同尺度 $s$ 对应不同的”频率”范围：

尺度 $s$	感受野	信号类型
小（如0.1）	局部	高频、细节
中等（如1.0）	中等	中频
大（如10.0）	全局	低频、轮廓

5.2 自适应小波学习

SEA-GWNN³ 通过学习自适应的小波基：

class AdaptiveWaveletGWNN(nn.Module):
    """
    SEA-GWNN: 自适应图小波神经网络
    
    论文: "Simple and Effective Adaptive Graph Wavelet Neural Network" (AAAI 2024)
    """
    def __init__(self, in_channels, out_channels, num_scales=4):
        super().__init__()
        self.num_scales = num_scales
        
        # 学习的基函数
        self.psi_learnable = nn.Parameter(
            torch.randn(num_scales, n, n)
        )
        
        # 投影矩阵
        self.projection = nn.Linear(in_channels, out_channels)
        
    def forward(self, x, L):
        # 归一化学习的小波基
        psi = self.psi_learnable
        psi = psi / (psi.sum(dim=-1, keepdim=True) + 1e-8)
        
        outputs = []
        for s in range(self.num_scales):
            # 应用学习的基
            x_transformed = psi[s] @ x
            out = self.projection(x_transformed)
            outputs.append(out)
        
        return sum(outputs) / self.num_scales

5.3 频率解耦

WaveGC实现了高频与低频成分的解耦：

$g_{θ} (λ) = 偶阶 g_{low} (λ) + 奇阶 g_{high} (λ)$

这使得网络可以独立学习不同频率成分的特征。

6. 与Fourier变换的对比

6.1 理论基础对比

特性	Fourier基	Wavelet基
频率局部化	✅ 完美	✅ 完美
空间局部化	❌ 无	✅ 优秀
基函数形式	$cos (k θ), sin (k θ)$	$(I - s L)^{k} e_{i}$
稀疏性	稠密	稀疏
可解释性	低	高

6.2 计算复杂度对比

操作	Fourier	Wavelet
变换 $O (n)$ 信号	$O (n^{2})$	$O (k ∥ E ∥)$
滤波	$O (n^{2})$	$O (k ∥ E ∥)$
逆变换	$O (n^{2})$	$O (k ∥ E ∥)$
总体	$O (n^{2})$	$O (k ∥ E ∥)$

对于稀疏图 $∣ E ∣ ≪ n^{2}$ ，小波变换的计算优势明显。

6.3 信号表示对比

def compare_representations(x, L, k=10):
    """
    对比Fourier和小波对同一信号的不同表示
    """
    # Fourier变换
    eigenvalues, eigenvectors = torch.linalg.eigh(L)
    x_fourier = eigenvectors.T @ x
    
    # 小波变换
    scales = [0.1, 0.5, 1.0, 5.0]
    x_wavelet = compute_wavelet_transform(x, L, scales, k)
    
    return {
        'fourier': x_fourier,  # 全局基表示
        'wavelet': x_wavelet   # 局部基表示
    }

7. 小波在时空图建模中的应用

7.1 Graph WaveNet架构

Graph WaveNet⁴ 将图小波与时序建模结合：

class GraphWaveNetLayer(nn.Module):
    """
    Graph WaveNet: 时空图神经网络
    
    结合图小波和TCN/GRU进行时空建模
    """
    def __init__(self, spatial_dim, temporal_dim, num_scales):
        super().__init__()
        
        # 空间：图小波卷积
        self.spatial_conv = WaveletConv(spatial_dim, spatial_dim, num_scales)
        
        # 时间：因果卷积
        self.temporal_conv = CausalConv1d(temporal_dim, temporal_dim, 3)
        
        # 门控机制
        self.gate = nn.Sequential(
            nn.Conv1d(temporal_dim, temporal_dim, 1),
            nn.Sigmoid()
        )
        
    def forward(self, x_spatial, x_temporal):
        """
        x_spatial: (batch, n, d_s)
        x_temporal: (batch, T, d_t)
        """
        # 空间卷积
        h = self.spatial_conv(x_spatial)
        
        # 时间门控
        h_t = h.transpose(1, 2)  # (batch, d, T)
        h_t = self.temporal_conv(h_t)
        gate = self.gate(h_t)
        
        return (h_t * gate).transpose(1, 2)

7.2 时序小波分解

Fast Temporal Wavelet GNN⁵ 对时间维度也进行小波分解：

$y_{t, s} = WAVELET_SCALE_{s} (GRU (x_{t}))$

8. 实践指南

8.1 小波基的选择

def select_wavelet_basis(graph, task_type):
    """
    根据任务类型选择小波基
    """
    # 计算图的谱性质
    L = compute_laplacian(graph)
    lambda_max = max_eigenvalue(L)
    
    if task_type == 'local_feature':
        # 局部特征：选择小尺度
        scales = [0.01, 0.05, 0.1, 0.5]
    elif task_type == 'global_pattern':
        # 全局模式：选择大尺度
        scales = [0.5, 1.0, 5.0, 10.0]
    else:
        # 混合任务：多尺度
        scales = [0.01, 0.1, 1.0, 10.0]
    
    return scales

8.2 超参数设置

参数	建议值	说明
尺度数量	3-6	太多增加计算量
Chebyshev阶数	10-30	更高阶更精确但更慢
小尺度	0.01-0.1	局部细节
大尺度	1.0-10.0	全局结构

8.3 实现注意事项

# 注意事项
class WaveletGNNBestPractices:
    """
    小波GNN最佳实践
    """
    def __init__(self):
        # 1. 预计算小波基（离线）
        self.psi = precompute_wavelet_basis(L)
        
        # 2. 批量处理时复用基
        # 不要在每次前向传播时重新计算
        
        # 3. 数值稳定性
        # 对于大尺度s，确保(I - sL)的特征值在[-1, 1]内
        
        # 4. 稀疏化
        # 小波基通常是稀疏的，利用稀疏矩阵加速

9. 小结

图小波变换为谱图神经网络提供了强大的工具：

优势	描述
局部化	小波基在空间上局部
多尺度	可分析不同频率成分
计算效率	$O (k ∥ E ∥)$ 而非 $O (n^{2})$
可解释性	频率-空间对应清晰
解耦能力	奇偶分解可分离高低频

最新进展（WaveGC）通过Chebyshev阶分解实现了：

通用的小波卷积框架
矩阵值滤波器的学习
短程与长程信息的解耦

参考文献

Xu, B., Shen, H., Cao, Q., Qiu, Y., & Cheng, X. (2019). “Graph Wavelet Neural Network.” ICLR 2019. arXiv:1904.07785 ↩
Liu, N., et al. (2025). “A General Graph Spectral Wavelet Convolution via Chebyshev Order Decomposition.” ICML 2025. arXiv:2405.13806 ↩
SEA-GWNN Authors. (2024). “SEA-GWNN: Simple and Effective Adaptive Graph Wavelet Neural Network.” AAAI 2024. ↩
Wu, Z., et al. (2019). “Graph WaveNet for Deep Spatial-Temporal Graph Modeling.” IJCAI 2019. arXiv:1906.00121 ↩
FTW-GNN Authors. (2023). “Fast Temporal Wavelet Graph Neural Networks.” arXiv:2302.08643. ↩

Metaphor

探索

图小波变换深度专题

图小波变换深度专题

1. 从Fourier到Wavelet

1.1 Fourier变换的局限

1.2 小波变换的优势

2. 图小波框架

2.1 谱域小波定义

2.2 框架条件

2.3 小波系数的计算

3. 图小波变换理论

3.1 小波框架的构建

3.2 多尺度分析

3.3 局部化特性

4. 图小波神经网络

4.1 GWNN架构

4.2 GWNN的优势

4.3 WaveGC架构

5. 短程与长程信号分离

5.1 小波的多分辨率特性

5.2 自适应小波学习

5.3 频率解耦

6. 与Fourier变换的对比

6.1 理论基础对比

6.2 计算复杂度对比

6.3 信号表示对比

7. 小波在时空图建模中的应用

7.1 Graph WaveNet架构

7.2 时序小波分解

8. 实践指南

8.1 小波基的选择

8.2 超参数设置

8.3 实现注意事项

9. 小结

参考文献

关系图谱

目录

Metaphor

探索

图小波变换深度专题

图小波变换深度专题

1. 从Fourier到Wavelet

1.1 Fourier变换的局限

1.2 小波变换的优势

2. 图小波框架

2.1 谱域小波定义

2.2 框架条件

2.3 小波系数的计算

3. 图小波变换理论

3.1 小波框架的构建

3.2 多尺度分析

3.3 局部化特性

4. 图小波神经网络

4.1 GWNN架构

4.2 GWNN的优势

4.3 WaveGC架构

5. 短程与长程信号分离

5.1 小波的多分辨率特性

5.2 自适应小波学习

5.3 频率解耦

6. 与Fourier变换的对比

6.1 理论基础对比

6.2 计算复杂度对比

6.3 信号表示对比

7. 小波在时空图建模中的应用

7.1 Graph WaveNet架构

7.2 时序小波分解

8. 实践指南

8.1 小波基的选择

8.2 超参数设置

8.3 实现注意事项

9. 小结

参考文献

Footnotes

关系图谱

目录