Chebyshev多项式与图滤波器

1. 引言

在谱图神经网络的实践中，直接计算拉普拉斯矩阵的特征分解代价高昂（$O(n^3)$），且滤波器难以迁移到不同图上。Chebyshev多项式近似提供了一种高效、局域化的解决方案，使得谱域卷积可以在不显式计算特征分解的情况下完成。¹

---

2. Chebyshev多项式基础

2.1 定义

Chebyshev多项式有第一类和第二类两种定义：

第一类Chebyshev多项式 $T_k(x)$：
$T_k(x)=\cos (k\arccos x),x\in [-1,1]$

递推关系：
$T_0(x)=1,T_1(x)=x$
$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$

第二类Chebyshev多项式 $U_k(x)$：
$U_k(\cos \theta )=\frac{\sin ((k+1)\theta )}{\sin \theta }$

递推关系：
$U_0(x)=1,U_1(x)=2x$
$U_k(x)=2x{U}_{k-1}(x)-U_{k-2}(x)$

2.2 重要性质

性质2.1（正交性）：
${\int }_{-1}^1{T}_m(x)T_n(x)\frac{dx}{\sqrt{1-x^2}}=\{\begin{array}{ll}\pi & m=n=0\\ \frac{\pi }{2}& m=n\ne 0\\ 0& m\ne n\end{array}$

性质2.2（极性）：
$|T_k(x)|\le 1,\forall x\in [-1,1]$

且在 $[-1,1]$ 外，$|T_k(x)|$ 以 $2k-1$ 次多项式增长。

性质2.3（最佳一致逼近）：
在所有 $k-1$ 次多项式中，$c_k{T}_{k-1}(x/c)$ 是最佳逼近 $1/x$ 的多项式（在 $[-1,-1/c]\cup [1/c,1]$ 上）。

2.3 归一化Chebyshev多项式

为适应拉普拉斯特征值范围 $[0,{\lambda }_{\max }]$，定义归一化多项式：

${\tilde{T}}_k(x)=T_k\left(\frac{2x}{{\lambda }_{\max }}-1\right)$

注意：${\tilde{T}}_k(0)=(-1{)}^k$，这会导致边界处的Runge现象。

---

3. 多项式近似的理论基础

3.1 函数逼近论

设目标滤波器函数 $g(\lambda )$ 定义在 $[0,{\lambda }_{\max }]$ 上。我们希望用 $K$ 阶多项式 ${\tilde{g}}_K(\lambda )$ 逼近 $g(\lambda )$。

一致逼近误差：
$\Vert g-{\tilde{g}}_K{\Vert }_{\infty }\le C\cdot {\rho }^{-K}$

其中 $\rho >1$ 与函数的解析性有关——函数越光滑，$\rho$ 越大，收敛越快。

3.2 谱收敛性

对于解析滤波器（如指数滤波器 $e^{-\lambda \tau }$），Chebyshev近似具有指数级收敛速度：

$\Vert g(\lambda )-{\tilde{g}}_K(\lambda ){\Vert }_{\infty }\le M\cdot {\left(\frac{1}{\rho }\right)}^K$

其中 $M$ 是函数在包含 $[0,{\lambda }_{\max }]$ 的椭圆域上的最大值。

3.3 Runge现象

当目标函数在 $[-1,1]$ 区间有极点时，等距节点的多项式插值会出现Runge现象——在区间边界出现剧烈震荡。

问题：Chebyshev近似的边界行为可能导致：

1. 滤波器系数 ${\theta }_k$ 绝对值过大（非法系数）
2. 训练时过拟合
3. 泛化性能下降

---

4. ChebNet：理论与实现

4.1 核心思想

ChebNet¹ 的核心思想是：用截断的Chebyshev多项式级数近似谱域滤波器。

设 $L$ 的特征值范围为 $[0,{\lambda }_{\max }]$，滤波器 $g_{\theta }$ 在谱域定义为：

$g_{\theta }(\lambda )={\sum }_{k=0}^{K-1}{\theta }_k{\lambda }^k\approx {\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{\lambda })$

其中 $\tilde{\lambda }=\frac{2\lambda }{{\lambda }_{\max }}-1\in [-1,1]$。

4.2 递归计算

Chebyshev多项式的递归特性使得计算可以高效进行：

T_0(x) = 1
T_1(x) = x
T_k(x) = 2x T_{k-1}(x) - T_{k-2}(x)

在图上，这对应于：

def chebyshev_polynomials(L, K, lambda_max):
    """
    计算归一化拉普拉斯上的Chebyshev多项式基
    
    参数:
        L: 归一化拉普拉斯矩阵 (n x n)
        K: 多项式阶数
        lambda_max: 最大特征值
    返回:
        T_k: K个(n x n)的张量，每层一个多项式基
    """
    # 归一化
    L_norm = 2 * L / lambda_max - torch.eye(L.size(0))
    
    T = [torch.eye(L.size(0)), L_norm]  # T_0, T_1
    
    for k in range(2, K):
        T_k = 2 * L_norm @ T[-1] - T[-2]
        T.append(T_k)
    
    return torch.stack(T)  # (K, n, n)

4.3 ChebNet卷积层

class ChebConv(nn.Module):
    def __init__(self, in_channels, out_channels, K, lambda_max):
        super().__init__()
        self.K = K
        self.lambda_max = lambda_max
        self.weight = nn.Parameter(torch.randn(K, in_channels, out_channels))
        self.bias = nn.Parameter(torch.zeros(out_channels))
        
    def forward(self, x, L):
        """
        x: (batch, n, in_channels)
        L: (n, n)
        """
        # 计算Chebyshev基
        T = chebyshev_polynomials(L, self.K, self.lambda_max)  # (K, n, n)
        
        # 多项式卷积：x * T_k -> (batch, n, in_channels) @ (n, n) -> (batch, n, n)
        # 对于每个k：H_k = T_k @ x @ W_k
        outputs = []
        for k in range(self.K):
            H_k = torch.einsum('bni,ij->bnj', x, T[k])  # (batch, n, in_channels)
            H_k = torch.einsum('bni,io->bno', H_k, self.weight[k])  # (batch, n, out_channels)
            outputs.append(H_k)
        
        # 求和
        out = torch.stack(outputs).sum(dim=0)
        return out + self.bias

4.4 K-局部化特性

ChebNet的一个关键性质是 $K$-局部化：滤波器 $g_{\theta }(L)$ 的输出仅依赖于 $K$ 跳内的节点。

定理：设 $T_k(L)$ 表示图上 $k$ 阶Chebyshev多项式，则：

$\text{supp}(T_k(L)\cdot {\delta }_i)\subseteq \{j:d(i,j)\le k\}$

即 $T_k(L)$ 将节点 $i$ 的信号仅传播到距离不超过 $k$ 的节点。

推论：$K$ 阶ChebNet层的感受野恰好是 $K$ 跳邻域。

---

5. ChebNetII：改进与扩展

5.1 问题分析

ChebNet的原始设计存在以下问题：

问题	描述	影响
非法系数	学习到的 ${\theta }_k$ 可能导致 $g_{\theta }(0)\ne {\theta }_0$	滤波器在 $\lambda =0$ 处行为异常
Runge现象	高阶多项式在边界振荡	训练不稳定
基准比较	在实际数据集上性能不如GCN	理论优势未能转化为实践优势

5.2 ChebNetII核心改进

文献²提出了ChebNetII，通过以下改进解决上述问题：

改进1：Chebyshev插值而非近似

将滤波器表示为 $K$ 个插值节点的线性组合：

$g_{\theta }(\lambda )={\sum }_{i=1}^K{\theta }_i{\ell }_i(\lambda )$

其中 ${\ell }_i(\lambda )$ 是基于Chebyshev节点 ${\lambda }_i^{\text{Cheb}}$ 的Lagrange基函数：

${\ell }_i(\lambda )={\prod }_{j\ne i}\frac{\lambda -{\lambda }_j^{\text{Cheb}}}{{\lambda }_i^{\text{Cheb}}-{\lambda }_j^{\text{Cheb}}}$

改进2：消除Runge现象

Chebyshev节点分布在 $[0,{\lambda }_{\max }]$ 上：

${\lambda }_i^{\text{Cheb}}=\frac{{\lambda }_{\max }}{2}\left(1+\cos \left(\frac{(2i-1)\pi }{2K}\right)\right),i=1,\dots ,K$

这种非均匀采样策略有效抑制了边界振荡。

改进3：正则化约束

添加额外的约束确保滤波器在 $\lambda =0$ 处有合理的值：

$g_{\theta }(0)={\sum }_{i=1}^K{\theta }_i{\ell }_i(0)=\alpha$

通过拉格朗日乘子或投影实现。

5.3 ChebNetII实现

class ChebNetII(nn.Module):
    def __init__(self, in_channels, out_channels, K, lambda_max):
        super().__init__()
        self.K = K
        self.lambda_max = lambda_max
        
        # Chebyshev节点
        self.nodes = self._chebyshev_nodes(lambda_max)
        
        # Lagrange基函数的系数（预计算）
        self.L_coeffs = self._precompute_lagrange_coeffs()
        
        # 可学习权重
        self.weight = nn.Parameter(torch.randn(K, in_channels, out_channels))
        self.bias = nn.Parameter(torch.zeros(out_channels))
        
    def _chebyshev_nodes(self, lambda_max):
        """生成Chebyshev节点"""
        i = torch.arange(1, self.K + 1)
        nodes = lambda_max / 2 * (1 + torch.cos((2 * i - 1) * torch.pi / (2 * self.K)))
        return nodes
    
    def _lagrange_basis(self, lambda_val, k):
        """
        计算第k个Lagrange基函数在lambda_val处的值
        
        L_k(lambda) = prod_{j!=k} (lambda - lambda_j) / (lambda_k - lambda_j)
        """
        result = torch.ones_like(lambda_val)
        for j in range(self.K):
            if j != k:
                result *= (lambda_val - self.nodes[j]) / (self.nodes[k] - self.nodes[j])
        return result
    
    def forward(self, x, L):
        batch_size, n, _ = x.shape
        
        # 评估谱域的Lagrange基
        # 特征值lambda_i对应谱域位置
        # 对于每个节点，使用幂迭代近似
        
        # 简化的实现：使用多项式基
        T = self._chebyshev_polynomials_sparse(L)
        
        # 卷积
        out = torch.zeros(batch_size, n, self.out_channels)
        for k in range(self.K):
            H_k = x @ T[k] @ self.weight[k]
            out += H_k
        
        return out + self.bias

5.4 与其他多项式基的比较

文献²系统比较了不同多项式基的性能：

多项式基	ChebNet	ChebNetII	GPR-GNN	BernNet
理论基础	最佳一致逼近	Chebyshev插值	PageRank谱	Bernstein多项式
数值稳定性	中等	高	高	高
表达能力	受限	完全	完全	完全
实际性能	较弱	最优	优	优

关键发现：虽然经典逼近理论认为Chebyshev基是最优的，但在图神经网络的有限多项式阶数下，插值方法（ChebNetII）反而表现更好。

---

6. 其他多项式基

6.1 Monomial基

Monomial基 $1,\lambda ,{\lambda }^2,\dots$ 最为简单，但存在两个问题：

1. 条件数爆炸：高阶Monomial的条件数随 $K$ 指数增长
2. 数值不稳定：直接求逆 $V^{-1}$ 困难

6.2 Bernstein基

Bernstein多项式定义为：

$B_k^K(x)=\left(\genfrac{}{}{0ex}{}{K}{k}\right)x^k(1-x{)}^{K-k},k=0,\dots ,K$

优势：

• 总是正的：$B_k^K(x)\ge 0$
• 归一化：${\sum }_k{B}_k^K(x)=1$
• 数值稳定

BernNet³ 基于Bernstein基设计谱滤波器：

$g_{\theta }(\lambda )={\sum }_{k=0}^K{\theta }_k{B}_k^K(\lambda /{\lambda }_{\max })$

6.3 Jacobi基

更一般地，Jacobi多项式 $P_k^{(\alpha ,\beta )}$ 提供了自由度 $(\alpha ,\beta )$ 调节基函数的性质：

• $\alpha =\beta =0$：Legendre多项式
• $\alpha =\beta =-1/2$：Chebyshev第一类
• $\alpha =\beta =1/2$：Chebyshev第二类

---

7. 自适应谱滤波器

7.1 可学习的谱响应

最近的工作允许网络直接从数据中学习谱滤波器，无需预设多项式形式。

GPR-GNN⁴ 使用参数化的PageRank谱：

$g_{\theta }(\lambda )={\sum }_{k=0}^K{\theta }_k(1-\lambda /{\lambda }_{\max }{)}^k$

7.2 频率注意力

Specformer⁵ 引入注意力机制学习频率响应：

class SpectralAttention(nn.Module):
    def __init__(self, num_freqs, hidden_dim):
        super().__init__()
        self.freq_proj = nn.Linear(num_freqs, hidden_dim)
        self.attention = nn.MultiheadAttention(hidden_dim, num_heads=4)
        
    def forward(self, eigvals, x):
        # eigvals: (n,) 特征值
        # x: (n, d) 节点特征
        
        # 特征值投影作为注意力查询
        freq_query = self.freq_proj(eigvals)  # (n, hidden_dim)
        
        # 谱域注意力
        out, _ = self.attention(freq_query.unsqueeze(0), x.unsqueeze(0), x.unsqueeze(0))
        return out.squeeze(0)

---

8. 大规模图上的应用

8.1 随机SVD加速

对于大规模图，可以利用随机SVD近似特征分解：

from scipy.sparse.linalg import svds
 
def lanczos_filter(L, k, p=10):
    """
    使用Lanczos方法近似计算k阶Chebyshev多项式
    
    参数:
        L: 稀疏拉普拉斯矩阵
        k: 多项式阶数
        p: 额外迭代次数（提高精度）
    """
    # 随机投影
    m = min(k + p, L.shape[0] - 1)
    Q, _ = scipy.linalg.qr(np.random.randn(L.shape[0], m))
    
    # Lanczos迭代
    T = q.T @ L @ q  # tridiagonal T
    eigenvalues, eigenvectors = np.linalg.eigh(T)
    
    return eigenvalues[:k], eigenvectors[:, :k]

8.2 分块对角化

对于异构图或分块图，可以分别处理各连通分量，然后合并结果。

---

9. 小结

方法	多项式基	收敛速度	数值稳定性	表达能力
ChebNet	Chebyshev	指数	中等	受限（非法系数）
ChebNetII	Chebyshev插值	指数	高	完全
GPR-GNN	PageRank	代数	高	完全
BernNet	Bernstein	代数	高	完全

Chebyshev多项式为谱图卷积提供了理论基础，但实际应用中需要注意数值稳定性和表达能力的问题。ChebNetII等改进方法通过插值和正则化策略有效解决了这些问题。

---

参考文献

Footnotes

1. Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). “Convolutional Neural Networks on Graphs with Chebyshev Approximation.” NeurIPS 2016. ↩ ↩²

2. He, M., Wei, Z., Wen, J., & Shang, C. (2022). “Convolutional Neural Networks on Graphs with Chebyshev Approximation, Revisited.” NeurIPS 2022. arXiv:2202.03580 ↩ ↩²

3. Biagetti, G., et al. (2021). “BernNet: Learning Arbitrary Graph Spectral Filters via Bernstein Approximation.” NeurIPS 2021. ↩

4. Chien, E., et al. (2020). “Adaptive Universal Generalized PageRank Graph Neural Network.” ICLR 2021. ↩

5. Liu, N., et al. (2025). “Specformer: Spectral Graph Neural Networks with Attention.” ICLR 2025. ↩