谱GNN与图小波方法

1. 背景与动机

1.1 谱域图卷积的局限

传统的谱域图卷积基于图拉普拉斯矩阵 $L=D-A$ 的特征分解：

$$g_{\theta }\ast x=U\text{diag}(\theta )U^{\top }x$$

其中 $U$ 是 $L$ 的特征向量矩阵。这种方法存在以下问题：

问题	描述
特征分解代价高	$O(N^3)$ 复杂度，难以扩展到大图
频率混叠	拉普拉斯特征值不具有明确的频率语义
平移不变性缺失	图结构不规则导致频谱解释困难

1.2 图小波的引入

图小波（Graph Wavelet）通过小波基函数提供局部化的频域表示：

$${\psi }_{s,i}(j)=(U\Sigma (s{)}^{1/2}{U}^{\top }{)}_{ij}$$

其中 $\Sigma (s)=\text{diag}({\lambda }_1^s,{\lambda }_2^s,\dots ,{\lambda }_n^s)$ 是尺度矩阵。

核心优势：

• 空间局部性：小波基在图上具有局部支撑
• 多尺度分析：不同尺度 $s$ 对应不同频率
• 稀疏表示：自然产生稀疏系数

---

2. 图小波理论基础

2.1 图小波框架

定义图小波框架 $\{{\psi }_{s,i}\}$ 满足框架条件：

$$A\Vert x{\Vert }^2\le \sum _{s,i}|⟨x,{\psi }_{s,i}⟩{|}^2\le B\Vert x{\Vert }^2$$

其中 $A,B$ 是框架界。

Chebyshev多项式近似允许在不必计算完整特征分解的情况下计算小波系数：

$$T_k(\tilde{L})=2\tilde{L}{T}_{k-1}(\tilde{L})-T_{k-2}(\tilde{L})$$

其中 $\tilde{L}=2L/{\lambda }_{\max }-I$ 是归一化拉普拉斯。

2.2 小波卷积操作

图小波卷积定义为：

$$y=\sum _k{\theta }_k\ast {\psi }_k(x)=\sum _k{\theta }_k\cdot W_{k}x{W}_k^{\top }$$

其中 $W_k$ 是第 $k$ 层小波滤波器。

---

3. 谱GNN架构

3.1 Specformer：特征值注意力

Specformer（ICLR 2025）引入特征值注意力机制，实现可学习的谱滤波器：

class SpecformerLayer(nn.Module):
    def __init__(self, num_nodes, hidden_dim, num_heads):
        super().__init__()
        self.eigenvalue_proj = nn.Linear(num_nodes, hidden_dim)
        self.attention = nn.MultiheadAttention(hidden_dim, num_heads)
        
    def forward(self, x, eigvecs, eigvals):
        # eigvecs: (N, N), eigvals: (N,)
        W = eigvecs @ torch.diag(self.eigenvalue_proj(eigvals)) @ eigvecs.T
        return self.attention(x, x, x, attn_mask=W)

核心创新：

• 特征值作为注意力查询
• 学习频率响应函数
• 保持排列不变性

3.2 S²GNN：空谱协同

S²GNN 结合空间消息传递和谱滤波：

$$h_i^{(l+1)}=\text{SPATIAL}(h_i^{(l)},\{h_j^{(l)}\})+\text{SPECTRAL}(h_i^{(l)},L)$$

架构设计：

• 双分支结构：空间分支 + 谱分支
• 动态权重融合
• 兼顾局部和全局信息

3.3 L²-GNN：双线性参数化

L²-GNN（2025）提出双线性参数化实现快速谱滤波：

$$W=\sum _{k=0}^{K-1}{\alpha }_k{L}^k$$

通过两次线性参数化实现高效计算：

1. 参数层：学习系数 ${\alpha }_k$
2. 卷积层：$O(K\cdot |E|)$ 的稀疏矩阵乘法

---

4. 通用图谱小波框架

4.1 框架数学形式

设图 $G=(V,E)$，定义小波基函数：

$${\psi }_{s,i}(j)=[U\Sigma (s{)}^{1/2}{U}^{\top }{]}_{ij}$$

其中：

• $U$：拉普拉斯特征向量
• $\Sigma (s)$：尺度矩阵
• $s\in \{s_1,s_2,\dots ,s_S\}$：多尺度参数

4.2 卷积层设计

class WaveletConvLayer(nn.Module):
    def __init__(self, in_channels, out_channels, scales, K):
        super().__init__()
        self.scales = scales
        self.K = K  # Chebyshev多项式阶数
        self.filter_weights = nn.Parameter(
            torch.randn(len(scales), K, in_channels, out_channels)
        )
        
    def forward(self, x, L, L_max):
        # L: 归一化拉普拉斯, L_max: 最大特征值
        outputs = []
        for s in self.scales:
            # 计算尺度矩阵 T(s)
            T_s = self.compute_chebyshev(L, L_max, s)
            # 应用滤波器
            out = x @ self.filter_weights[s] @ T_s.T
            outputs.append(out)
        return torch.stack(outputs).sum(dim=0)
    
    def compute_chebyshev(self, L, L_max, s):
        # 计算 exp(-s * L) 的Chebyshev近似
        L_norm = 2 * L / L_max - torch.eye(L.size(0))
        T = [torch.eye(L.size(0)), L_norm]
        for k in range(2, self.K):
            T.append(2 * L_norm @ T[-1] - T[-2])
        return torch.stack(T[:self.K]).mean(dim=0) * torch.exp(-s * L_max)

---

5. 与标准GNN的对比

特性	标准GCN	GraphTransformer	谱小波GNN
消息传递	一阶邻居	全图注意力	多尺度邻域
感受野	局部K-hop	全局	可控多尺度
计算复杂度	$O(	E	)$
可解释性	低	中	高（频率响应）
理论保证	WL-test	表达能力上界	谱逼近误差

---

6. 应用与实验

6.1 节点分类基准

在Cora、CiteSeer、PubMed上的结果：

模型	Cora	CiteSeer	PubMed
GCN	81.5%	70.3%	79.0%
GAT	83.0%	72.5%	79.0%
Specformer	85.2%	74.1%	80.8%
L²-GNN	84.8%	73.6%	80.3%

6.2 图分类任务

在PROTEINS、IMDB-BINARY上的表现：

模型	PROTEINS	IMDB-B
DGCNN	76.0%	70.0%
SortPool	77.0%	74.4%
S²GNN	78.5%	76.2%

---

7. 参考文献