GCN谱方法理论基础

概述

图卷积网络（Graph Convolutional Network，GCN）的谱方法（Spectral Methods）是GCN的理论根基。它将传统信号处理中的傅里叶变换推广到图结构数据，通过对图拉普拉斯矩阵的特征分解定义”图上的频率”，并在此基础上构造卷积运算。¹

本文档深入推导谱GCN的完整数学框架，从图信号处理基础出发，逐步推导ChebNet、Kipf-Welling GCN、SGC等关键架构，并讨论谱方法的根本局限——为读者理解后续空间方法（GraphSAGE、GAT）和几何深度学习统一框架奠定理论基础。

---

1. 图信号处理基础

1.1 图的形式化定义

设无向加权图 $\mathcal{G}=(\mathcal{V},\mathcal{E},W)$，其中：

• $\mathcal{V}=\{v_1,v_2,\dots ,v_N\}$：节点集合，$|\mathcal{V}|=N$
• $\mathcal{E}$：边集合，$|\mathcal{E}|=E$
• $W\in {\mathbb{R}}^{N\times N}$：邻接矩阵（加权），$W_{ij}\ge 0$

常用符号：

• $A$：邻接矩阵
• $D$：度矩阵，对角元素 $D_{ii}={\sum }_j{A}_{ij}$
• $X\in {\mathbb{R}}^{N\times d}$：节点特征矩阵
• $\mathbf{x}\in {\mathbb{R}}^N$：节点上的标量信号

1.2 拉普拉斯矩阵

普通拉普拉斯（Combinatorial Laplacian）

$L=D-A$

性质：

• 对称半正定（Symmetric Positive Semi-Definite）
• 最小特征值为 $0$，对应常信号
• 特征值个数等于 $N$，构成正交完备基

归一化拉普拉斯（Symmetric Normalized Laplacian）

$L_{\text{sym}}=I-D^{-1/2}A{D}^{-1/2}$

或者另一种常用的随机游走归一化：

$L_{\text{rw}}=I-D^{-1}A$

$L_{\text{sym}}$ 的性质：

• $L_{\text{sym}}=U\Lambda U^T$，其中 $U$ 是正交矩阵（$U^{T}U=I$）
• $\Lambda =\text{diag}({\lambda }_0,{\lambda }_1,\dots ,{\lambda }_{N-1})$
• $0={\lambda }_0\le {\lambda }_1\le \dots \le {\lambda }_{N-1}\le 2$

拉普拉斯作为”图上的二阶差分”

对节点 $i$，拉普拉斯作用在信号 $\mathbf{x}$ 上：

$(L\mathbf{x}{)}_i={\sum }_{j\in \mathcal{N}(i)}{A}_{ij}(x_i-x_j)=D_{ii}{x}_i-{\sum }_{j\in \mathcal{N}(i)}{A}_{ij}{x}_j$

直观解释：节点 $i$ 的信号与其邻居信号差异的加权求和。

1.3 二次型与平滑度

拉普拉斯的二次型是图信号处理中的核心概念：

${\mathbf{x}}^{T}L\mathbf{x}=\frac{1}{2}{\sum }_{i,j}{A}_{ij}(x_i-x_j{)}^2$

几何意义：

• 当所有节点信号相同时（$x_i=x_j$），二次型为 $0$
• 二次型越大，相邻节点信号差异越大
• 因此 $L$ 的特征向量对应”信号变化的不同频率”

1.4 特征分解

设 $L_{\text{sym}}=U\Lambda U^T$，其中：

• $U=[{\mathbf{u}}_0,{\mathbf{u}}_1,\dots ,{\mathbf{u}}_{N-1}]$：特征向量矩阵，$U^{T}U=I$
• $\Lambda =\text{diag}({\lambda }_0,{\lambda }_1,\dots ,{\lambda }_{N-1})$：特征值

常信号的特征向量：${\mathbf{u}}_0=(1/\sqrt{N})1$，对应 ${\lambda }_0=0$。

---

2. 图傅里叶变换

2.1 传统傅里叶变换的回顾

传统连续信号 $f(t)$ 的傅里叶变换：

$\hat{f}(\xi )={\int }_{-\infty }^{\infty }f(t)e^{-2\pi i\xi t}dt$

反变换：

$$f(t) = \int_{-\infty}^{\infty} \hat{f}(\xi) e^{2\pi i \xi t} d\xi$

关键思想：$e^{2\pi i\xi t}$ 是拉普拉斯算子 $\Delta ={\partial }^2/\partial t^2$ 的特征函数：

$\Delta e^{2\pi i\xi t}=-4{\pi }^2{\xi }^2{e}^{2\pi i\xi t}$

2.2 类比：图上的”特征函数”

关键观察：图的拉普拉斯 $L$ 扮演了 $\Delta$ 的角色。它的特征向量 ${\mathbf{u}}_k$ 就是图上的”频率基”：

$L{\mathbf{u}}_k={\lambda }_k{\mathbf{u}}_k$

图频率：${\lambda }_k$ 越大，特征向量 ${\mathbf{u}}_k$ 在相邻节点上的振荡越剧烈。

2.3 图傅里叶变换（GFT）

定义图信号 $\mathbf{x}\in {\mathbb{R}}^N$ 的图傅里叶变换为：

$\hat{x}({\lambda }_k)=⟨\mathbf{x},{\mathbf{u}}_k⟩={\sum }_{n=1}^N{x}_n{u}_{k,n}={\mathbf{u}}_k^T\mathbf{x}$

矩阵形式：

$\hat{\mathbf{x}}=U^T\mathbf{x}$

其中 $\hat{\mathbf{x}}\in {\mathbb{R}}^N$ 是频域表示。

2.4 逆图傅里叶变换（IGFT）

$\mathbf{x}={\sum }_{k=0}^{N-1}\hat{x}({\lambda }_k){\mathbf{u}}_k$

矩阵形式：

$\mathbf{x}=U\hat{\mathbf{x}}$

由于 $U$ 正交，IGFT 是 GFT 的简单转置。

2.5 卷积定理的推广

传统卷积定理：时域卷积等价于频域乘积。

$(f\ast g)(t)={\mathcal{F}}^{-1}[\hat{f}(\xi )\cdot \hat{g}(\xi )]$

图上卷积定义：给定滤波器 $\mathbf{g}$，其 GFT 为 $\hat{\mathbf{g}}$，定义 $\mathbf{x}$ 与 $\mathbf{g}$ 的图卷积为：

$(\mathbf{x}\ast \mathbf{g}{)}_G=U\left((U^T\mathbf{x})\odot (U^T\mathbf{g})\right)=U\left(\hat{\mathbf{x}}\odot \hat{\mathbf{g}}\right)$

其中 $\odot$ 是 Hadamard（元素级）乘积。

---

3. 谱卷积神经网络

3.1 谱卷积算子

基于卷积定理，定义参数化的谱滤波器 ${\mathbf{g}}_{\theta }$：

${\mathbf{g}}_{\theta }\ast \mathbf{x}=U{\mathbf{g}}_{\theta }(\Lambda )U^T\mathbf{x}$

其中：

• ${\mathbf{g}}_{\theta }(\Lambda )=\text{diag}({\theta }_0,{\theta }_1,\dots ,{\theta }_{N-1})$：可学习参数对角矩阵
• 每个 ${\theta }_k$ 是对应”频率” ${\lambda }_k$ 的滤波器系数

3.2 第一代谱 GCN

直接实现：第一代谱 GCN（Bruna et al., ICLR 2014）直接使用上述公式：

$H^{(l+1)}=\sigma \left(U{\mathbf{g}}_{\theta }(\Lambda )U^T{H}^{(l)}{W}^{(l)}\right)$

问题：

1. 计算成本高：每次前向都需要 $O(N^2)$ 的特征分解，$O(N^2)$ 的矩阵乘法
2. 非局部化：滤波器在空域不是局部化的
3. 与图结构无关：滤波器依赖特定图的特征分解，无法迁移到新图

3.3 参数化策略的演进

为解决第一代 GCN 的问题，研究者提出多种参数化方案：

策略 1：多项式参数化（ChebNet）

${\mathbf{g}}_{\theta }(\Lambda )={\sum }_{k=0}^{K-1}{\theta }_k{\Lambda }^k$

多项式滤波器自然实现空域的 $K$ 跳局部化。

策略 2：切比雪夫展开（ChebNet）

${\mathbf{g}}_{\theta }(\Lambda )={\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{\Lambda })$

其中 $T_k$ 是 Chebyshev 多项式，$\tilde{\Lambda }$ 是重缩放的特征值。

策略 3：1阶截断（Kipf-Welling GCN）

${\mathbf{g}}_{\theta }(\Lambda )={\theta }_{0}I+{\theta }_1(\Lambda -I)$

进一步简化参数数量。

---

4. ChebNet：基于切比雪夫多项式的谱卷积

4.1 动机

第一代谱 GCN 的滤波器：

1. 计算复杂度高（需要完整特征分解）
2. 滤波器不是局部化的（在空域弥散）
3. 与图大小 $N$ 耦合

ChebNet 的目标：用 $K$ 阶多项式近似滤波器，使得：

• 仅依赖 $K$ 跳邻居（局部化）
• 不需要显式特征分解
• 与图大小 $N$ 解耦

4.2 切比雪夫多项式回顾

切比雪夫多项式 $T_k(x)$ 定义在 $[-1,1]$ 上：

递推关系：

$T_k(x)=2x{T}_{k-1}(x)-T_{k-2}(x)$

初始条件：

• $T_0(x)=1$
• $T_1(x)=x$

前几项：

• $T_0(x)=1$
• $T_1(x)=x$
• $T_2(x)=2x^2-1$
• $T_3(x)=4x^3-3x$
• $T_4(x)=8x^4-8x^2+1$

4.3 ChebNet 的完整推导

步骤 1：拉普拉斯重缩放

由于切比雪夫多项式定义在 $[-1,1]$，需要重缩放拉普拉斯：

$\tilde{L}=\frac{2}{{\lambda }_{\max }}L-I$

其中 ${\lambda }_{\max }$ 是 $L$ 的最大特征值。这样 $\tilde{L}$ 的特征值在 $[-1,1]$ 内。

注：原论文使用非归一化拉普拉斯 $L=D-A$，最大特征值 ${\lambda }_{\max }\le 2\max (D_{ii})$。

步骤 2：滤波器多项式展开

${\mathbf{g}}_{\theta }(\Lambda )={\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{\Lambda })$

其中：

• $T_k(\tilde{\Lambda })$：作用于对角矩阵 $\tilde{\Lambda }$，仍是对角矩阵
• ${\theta }_k$：可学习参数

关键性质：由于 $T_k(\tilde{\Lambda })$ 是 $\tilde{\Lambda }$ 的 $k$ 次多项式，$T_k(\tilde{L})$ 是 $\tilde{L}$ 的 $k$ 次多项式。

步骤 3：图卷积公式

${\mathbf{g}}_{\theta }\ast \mathbf{x}=U{\mathbf{g}}_{\theta }(\Lambda )U^T\mathbf{x}=U\left({\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{\Lambda })\right)U^T\mathbf{x}$

利用 $L=U\Lambda U^T$ 和 $\tilde{L}=U\tilde{\Lambda }{U}^T$：

$={\sum }_{k=0}^{K-1}{\theta }_{k}U{T}_k(\tilde{\Lambda })U^T\mathbf{x}={\sum }_{k=0}^{K-1}{\theta }_k{T}_k(\tilde{L})\mathbf{x}$

最终公式：

$\boxed{{\mathbf{g}}_{\theta }\ast \mathbf{x}=\sum _{k=0}^{K-1}{\theta }_k{T}_k(\tilde{L})\mathbf{x}}$

4.4 ChebNet 的优良性质

性质 1：局部化

$T_k(\tilde{L})$ 是 $\tilde{L}$ 的 $k$ 次多项式，作用在节点 $i$ 上仅依赖 $k$ 跳邻居：

$(T_k(\tilde{L})\mathbf{x}{)}_i=\text{func}(\{x_j:j\in {\mathcal{N}}_k(i)\})$

因此滤波器是严格 $K$ 跳局部化的。

性质 2：无特征分解

递推计算 $T_k(\tilde{L})\mathbf{x}$：

${\bar{\mathbf{x}}}_0=\mathbf{x},{\bar{\mathbf{x}}}_1=\tilde{L}\mathbf{x},{\bar{\mathbf{x}}}_k=2\tilde{L}{\bar{\mathbf{x}}}_{k-1}-{\bar{\mathbf{x}}}_{k-2}$

计算复杂度：每次 $\tilde{L}\mathbf{x}$ 是稀疏矩阵-向量乘，复杂度 $O(E)$。递推需要 $K$ 步，总复杂度 $O(K\cdot E)$，与经典 CNN 同阶。

性质 3：参数数量可控

参数数量为 $K$（多项式阶数），与图大小 $N$ 无关。

4.5 ChebNet 的 PyTorch 实现

import torch
import torch.nn as nn
import torch.nn.functional as F
 
def chebyshev_polynomial(L_tilde, K):
    """
    计算切比雪夫多项式 T_0, T_1, ..., T_{K-1} 应用在 L_tilde 上的结果。
    返回列表，每个元素是 (K, N) 的矩阵或 (K, N, F) 的张量。
    """
    N = L_tilde.size(0)
    cheb_polynomials = [torch.eye(N, device=L_tilde.device), L_tilde]
    
    for k in range(2, K):
        cheb_polynomials.append(
            2 * L_tilde @ cheb_polynomials[-1] - cheb_polynomials[-2]
        )
    
    return cheb_polynomials  # 长度为 K
 
 
class ChebNetConv(nn.Module):
    """ChebNet 卷积层"""
    def __init__(self, in_channels, out_channels, K):
        super().__init__()
        self.K = K
        # K 个切比雪夫系数
        self.theta = nn.Parameter(torch.empty(K, in_channels, out_channels))
        self.bias = nn.Parameter(torch.zeros(out_channels))
        nn.init.xavier_uniform_(self.theta)
    
    def forward(self, x, L_tilde):
        """
        x: (N, in_channels) 节点特征
        L_tilde: (N, N) 重缩放的拉普拉斯
        """
        cheb_polys = chebyshev_polynomial(L_tilde, self.K)
        
        # 累加 theta_k * T_k(L_tilde) * x
        out = torch.zeros(x.size(0), self.theta.size(2), device=x.device)
        for k in range(self.K):
            # (N, N) @ (N, in_channels) -> (N, in_channels)
            Tx = cheb_polys[k] @ x
            # einsum: (in_channels, out_channels) 矩阵乘
            out += Tx @ self.theta[k]
        
        return out + self.bias
 
 
class ChebNet(nn.Module):
    """完整 ChebNet 用于节点分类"""
    def __init__(self, in_channels, hidden_channels, out_channels, K=3, num_layers=2):
        super().__init__()
        self.convs = nn.ModuleList()
        self.convs.append(ChebNetConv(in_channels, hidden_channels, K))
        for _ in range(num_layers - 2):
            self.convs.append(ChebNetConv(hidden_channels, hidden_channels, K))
        self.convs.append(ChebNetConv(hidden_channels, out_channels, K))
    
    def forward(self, x, L_tilde):
        for i, conv in enumerate(self.convs):
            x = conv(x, L_tilde)
            if i < len(self.convs) - 1:
                x = F.relu(x)
                x = F.dropout(x, p=0.5, training=self.training)
        return F.log_softmax(x, dim=1)

4.6 ChebNet 的局限

尽管 ChebNet 解决了第一代 GCN 的多个问题，仍存在以下局限：

1. $K$ 阶多项式的限制：对于复杂的图频率响应，多项式拟合可能不精确
2. 过深的 ChebNet 仍有过平滑问题：随层数增加，节点表示趋于相似
3. 每层独立学习：不同层无法共享底层结构

---

5. Kipf-Welling GCN：1阶切比雪夫近似

5.1 简化思路

Kipf & Welling 在 2017 年提出激进的简化：取 $K=2$（即 1 阶 Chebyshev 多项式展开）。

推导步骤

1. 1阶切比雪夫展开：

${\mathbf{g}}_{\theta }(\Lambda )\approx {\theta }_{0}I+{\theta }_1(\Lambda -I)$

即 $T_0(\tilde{\Lambda })=I$ 和 $T_1(\tilde{\Lambda })=\tilde{\Lambda }=\Lambda /{\lambda }_{\max }-I$。

2. 进一步简化：

假设 ${\lambda }_{\max }\approx 2$（对于归一化对称拉普拉斯 $L_{\text{sym}}$，确实成立），则：

${\mathbf{g}}_{\theta }(\Lambda )\approx {\theta }_{0}I+{\theta }_1(\Lambda /2-I)$

3. 减少参数：

为减少过拟合，强制 ${\theta }_0=-{\theta }_1=\theta$：

${\mathbf{g}}_{\theta }(\Lambda )\approx \theta (I+D^{-1/2}A{D}^{-1/2}-2I)/2=\theta (D^{-1/2}A{D}^{-1/2}-I)/...$

更准确地，设 ${\theta }^{\prime }=\theta /2$：

${\mathbf{g}}_{\theta }(\Lambda )\approx {\theta }_0^{\prime }(I+D^{-1/2}A{D}^{-1/2})$

5.2 重整化技巧

直接使用 $\hat{A}=D^{-1/2}A{D}^{-1/2}$ 会导致数值不稳定（特征值范围 $[-1,1]$）。Kipf & Welling 使用重整化技巧：

$\tilde{A}=A+I_N$

加上自环，然后：

${\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$

最终传播规则：

$\boxed{H^{(l+1)}=\sigma \left({\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}{H}^{(l)}{W}^{(l)}\right)}$

其中：

• $\tilde{A}=A+I_N$：加自环的邻接矩阵
• ${\tilde{D}}_{ii}={\sum }_j{\tilde{A}}_{ij}$：重整化的度
• $W^{(l)}\in {\mathbb{R}}^{d_l\times d_{l+1}}$：可学习参数矩阵
• $\sigma$：激活函数（如 ReLU）

5.3 逐元素解释

对于单个节点 $i$，第 $l$ 层的更新为：

$h_i^{(l+1)}=\sigma \left({\sum }_{j\in \tilde{\mathcal{N}}(i)}\frac{1}{\sqrt{{\tilde{D}}_{ii}{\tilde{D}}_{jj}}}{h}_j^{(l)}{W}^{(l)}\right)$

其中 $\tilde{\mathcal{N}}(i)$ 包括节点 $i$ 自己（因为加了自环）。

直观解释：

1. 每个节点聚合自己和邻居的特征
2. 用度数归一化，避免度大的节点主导
3. 通过 $W^{(l)}$ 做线性变换
4. 激活函数引入非线性

5.4 Kipf-Welling GCN 与多项式滤波器的关系

通过归纳，可以证明 $L$ 层 Kipf-Welling GCN 等价于一个特殊的 $L$ 阶多项式滤波器：

$Z=\text{softmax}\left({\hat{A}}^{L}XW\right)$

其中 $\hat{A}={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$，$W=W^{(1)}{W}^{(2)}\cdots W^{(L)}$。

关键洞察：Kipf-Welling GCN 是 ChebNet 的极端简化版本（$K=1$，${\theta }_0=-{\theta }_1$）。

5.5 Kipf-Welling GCN 的 PyTorch 实现

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
 
 
class KipfWellingGCN(nn.Module):
    """Kipf-Welling GCN（PyG版本）"""
    def __init__(self, in_channels, hidden_channels, out_channels, 
                 num_layers=2, dropout=0.5):
        super().__init__()
        self.convs = nn.ModuleList()
        self.convs.append(GCNConv(in_channels, hidden_channels))
        for _ in range(num_layers - 2):
            self.convs.append(GCNConv(hidden_channels, hidden_channels))
        self.convs.append(GCNConv(hidden_channels, out_channels))
        self.dropout = dropout
    
    def forward(self, x, edge_index, edge_weight=None):
        for i, conv in enumerate(self.convs):
            x = conv(x, edge_index, edge_weight)
            if i < len(self.convs) - 1:
                x = F.relu(x)
                x = F.dropout(x, p=self.dropout, training=self.training)
        return F.log_softmax(x, dim=1)
 
 
# 纯 PyTorch 实现（不依赖 PyG）
class GCNLayerManual(nn.Module):
    """手动实现 GCN 层以展示传播规则的细节"""
    def __init__(self, in_features, out_features):
        super().__init__()
        self.weight = nn.Parameter(torch.empty(in_features, out_features))
        self.bias = nn.Parameter(torch.zeros(out_features))
        nn.init.xavier_uniform_(self.weight)
    
    def forward(self, x, adj):
        """
        x: (N, in_features) 节点特征
        adj: (N, N) 邻接矩阵（含自环）
        """
        # 计算重整化度矩阵
        degree = adj.sum(dim=1)
        degree_inv_sqrt = torch.pow(degree, -0.5)
        degree_inv_sqrt[torch.isinf(degree_inv_sqrt)] = 0.0
        D = torch.diag(degree_inv_sqrt)
        
        # 重整化邻接矩阵
        adj_normalized = D @ adj @ D
        
        # 消息传递
        support = x @ self.weight
        output = adj_normalized @ support + self.bias
        return output

5.6 Kipf-Welling GCN 的局限性

局限 1：过平滑

随层数 $L$ 增加，${\hat{A}}^L$ 收敛到一个稳态，所有节点表示趋于相同。经验上 $L=2$ 或 $3$ 通常效果最好。

局限 2：表达能力受限

Kipf-Welling GCN 等价于特定的多项式滤波器。对于需要复杂频率响应的任务可能不够。

局限 3：无法处理有向图

公式依赖对称的 $\hat{A}$，对有向图需要特殊处理。

---

6. 简化图卷积网络（SGC）

6.1 核心洞察

Wu et al. (ICML 2019) 提出了一个关键观察：GCN 中的非线性变换和逐层权重矩阵可能是不必要的。²

论据：

1. Kipf-Welling GCN 已经等价于一个低通滤波器
2. 多层权重矩阵可以折叠为单个矩阵
3. 非线性可能不是必需

6.2 SGC 的推导

考虑 $L$ 层 Kipf-Welling GCN：

$Z=\text{softmax}\left(\hat{A}\cdots \hat{A}\hat{A}X{W}^{(1)}{W}^{(2)}\cdots W^{(L)}\right)$

移除所有非线性（$\sigma$），令 $W=W^{(1)}{W}^{(2)}\cdots W^{(L)}$：

$\boxed{Z=\text{softmax}\left({\hat{A}}^{L}XW\right)}$

这就是 SGC 的全部内容：$L$ 阶多项式滤波器 + 线性分类器。

6.3 SGC 的实现

import torch
import torch.nn as nn
import torch.nn.functional as F
 
 
def normalize_adj(adj):
    """对称归一化邻接矩阵"""
    adj = adj + torch.eye(adj.size(0), device=adj.device)  # 加自环
    degree = adj.sum(dim=1)
    degree_inv_sqrt = torch.pow(degree, -0.5)
    degree_inv_sqrt[torch.isinf(degree_inv_sqrt)] = 0.0
    D = torch.diag(degree_inv_sqrt)
    return D @ adj @ D
 
 
class SGC(nn.Module):
    """简化图卷积网络（SGC）"""
    def __init__(self, in_channels, out_channels, K=2):
        super().__init__()
        self.K = K
        # 单个线性分类器
        self.W = nn.Linear(in_channels, out_channels, bias=True)
        # 邻接矩阵会在第一次前向时缓存
        self.register_buffer('adj_normalized', None)
    
    def forward(self, x, adj):
        # 首次调用时归一化邻接矩阵
        if self.adj_normalized is None or self.adj_normalized.shape != adj.shape:
            self.adj_normalized = normalize_adj(adj)
        
        # K 次邻接矩阵乘法
        for _ in range(self.K):
            x = self.adj_normalized @ x
        
        # 线性分类
        return self.W(x)

6.4 SGC 的优势

1. 速度快：训练时无需迭代，直接计算特征表示
2. 参数少：仅一个 $W$ 矩阵
3. 可解释：${\hat{A}}^{K}X$ 是显式的 $K$ 跳邻居聚合
4. 理论保证：作为低通滤波器的解析形式

6.5 SGC 的局限

1. 表达能力有限：相当于 ChebNet 的最简化版本
2. 异配图表现差：低通滤波假设在异配图（heterophilic graphs）上不成立
3. 无特征变换能力：所有层共享 $W$，无法逐层学习

---

7. 谱方法的根本局限

7.1 局限 1：依赖图结构

谱方法的核心依赖图的拉普拉斯特征分解。当图结构变化时（如归纳学习新图），滤波器必须重新学习。

7.2 局限 2：非空域局部化

谱滤波器虽然在 ChebNet 中被多项式约束实现空域局部化，但其本质上仍是全局算子。

7.3 局限 3：方向性假设

谱方法假设图是无向的。对于有向图（如知识图谱），需要特殊处理（如有向拉普拉斯）。

7.4 局限 4：异配图不适用

低通滤波假设相连节点相似。但异配图（heterophilic graphs）中，相连节点可能不相似，低通滤波反而损害性能。

7.5 局限 5：动态图不适用

谱滤波器依赖固定的特征分解。对于动态图，需要昂贵的重新计算或近似方法。

---

8. 从谱方法到空间方法的桥梁

8.1 等价性视角

Kipf-Welling GCN 的传播规则可以从空间角度重新解释：

$h_i^{(l+1)}=\text{AGGREGATE}\left(\{h_j^{(l)}:j\in \tilde{\mathcal{N}}(i)\}\right)$

其中聚合函数为度归一化的加权和。这与空域方法（GraphSAGE、GAT）的消息传递框架是一致的。

8.2 谱方法的贡献

尽管空间方法在实际中更常用，谱方法的贡献不可磨灭：

1. 理论框架：将 GCN 嵌入图信号处理，提供严格的数学分析
2. 算法创新：ChebNet、Kipf-Welling GCN 的多项式滤波器
3. 理解基础：理解过平滑、感受野、频率响应等概念的基础

---

9. 完整实验：Cora 节点分类

9.1 数据准备

import torch
from torch_geometric.datasets import Planetoid
from torch_geometric.transforms import NormalizeFeatures
 
# 加载 Cora 数据集
dataset = Planetoid(root='/tmp/Cora', name='Cora', 
                     transform=NormalizeFeatures())
data = dataset[0]
 
print(f"节点数: {data.num_nodes}")
print(f"边数: {data.num_edges}")
print(f"特征维度: {data.num_node_features}")
print(f"类别数: {dataset.num_classes}")

9.2 训练 ChebNet

def train(model, data, optimizer, criterion):
    model.train()
    optimizer.zero_grad()
    out = model(data.x, data.adj)  # 需要预计算 adj
    loss = criterion(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss.item()
 
@torch.no_grad()
def test(model, data):
    model.eval()
    out = model(data.x, data.adj)
    pred = out.argmax(dim=1)
    
    accs = []
    for mask in [data.train_mask, data.val_mask, data.test_mask]:
        acc = (pred[mask] == data.y[mask]).float().mean()
        accs.append(acc.item())
    return accs

9.3 结果对比

模型	参数量	训练时间	测试准确率
ChebNet ($K=3$)	~92K	中等	81.2%
Kipf-Welling GCN	~23K	快	81.5%
SGC	~9K	极快	81.0%

观察：

• 在简单数据集上三者性能接近
• SGC 训练最快，但表达能力受限
• ChebNet 参数最多，可能在小数据上过拟合

---

10. 总结

10.1 谱方法的核心思想

1. 图傅里叶变换：用拉普拉斯特征向量定义”频率”
2. 卷积定理：图卷积等价于频域乘积
3. 多项式滤波器：用 $K$ 阶多项式逼近滤波器，保证局部化和计算效率

10.2 关键架构演进

第一代谱 GCN (Bruna 2014)
    ↓ 解决计算成本和非局部化问题
ChebNet (Defferrard 2016)
    ↓ 进一步简化参数
Kipf-Welling GCN (2017)
    ↓ 激进简化，移除非线性
SGC (Wu 2019)

10.3 谱方法的价值

• 为 GCN 提供严格的数学理论
• 揭示了”图卷积 = 多项式滤波器”的本质
• 启发了后续空间方法的设计
• 仍是理解 GCN 过平滑、感受野等问题的关键工具

---

参考

Footnotes

1. Shuman et al., “The Emerging Field of Signal Processing on Graphs”, IEEE Signal Processing Magazine, 2013 ↩

2. Wu et al., “Simplifying Graph Convolutional Networks”, ICML 2019. arXiv:1902.07153 ↩