Chebyshev谱图卷积网络：从数学原理到GNN实战

1次阅读

没有评论

共计 2738 个字符，预计需要花费 7 分钟才能阅读完成。

图神经网络（GNN）的核心挑战在于如何有效处理非欧式空间数据。传统卷积神经网络（CNN）在规则网格数据上表现出色，但在图结构数据上却难以直接应用。图卷积主要分为两种范式：空域方法和频域方法。

空域方法 ：直接在图上定义卷积操作，通过聚合邻居节点信息来更新当前节点表示。这种方法直观易懂，但难以捕捉全局图结构信息。
频域方法 ：将图信号转换到频域进行卷积操作，再利用逆变换回到空域。这种方法能够捕捉全局信息，但计算复杂度较高。

Chebyshev 谱图卷积网络属于频域方法，通过 Chebyshev 多项式逼近图拉普拉斯算子的特征函数，显著降低了计算复杂度。

图拉普拉斯矩阵 (L) 定义为 (L = D – A)，其中 (D) 是度矩阵，(A) 是邻接矩阵。归一化后的拉普拉斯矩阵为 (L = I – D^{-1/2} A D^{-1/2})。

通过对 (L) 进行谱分解，可以得到其特征值和特征向量：(L = U \Lambda U^T)，其中 (U) 是特征向量矩阵，(\Lambda) 是特征值对角矩阵。

Chebyshev 多项式 (T_k(x)) 是一组正交多项式，定义为：

[T_k(x) = 2x T_{k-1}(x) – T_{k-2}(x) ]

其中 (T_0(x) = 1)，(T_1(x) = x)。

利用 Chebyshev 多项式，可以逼近图拉普拉斯算子的特征函数，从而将频域卷积核表示为：

[g_\theta(\Lambda) \approx \sum_{k=0}^{K-1} \theta_k T_k(\tilde{\Lambda}) ]

其中 (\tilde{\Lambda} = 2 \Lambda / \lambda_{\text{max}} – I) 是将特征值缩放至 ([-1, 1]) 区间。

通过 Chebyshev 多项式逼近，卷积操作可以表示为：

[y = U g_\theta(\Lambda) U^T x = \sum_{k=0}^{K-1} \theta_k T_k(\tilde{L}) x ]

其中 (\tilde{L} = 2 L / \lambda_{\text{max}} – I)。这种参数化方式显著降低了计算复杂度，从 (O(n^2)) 降至 (O(K|E|))，其中 (|E|) 是边数。

import torch

def normalize_laplacian(adj):
    # 计算度矩阵
    degree = torch.sum(adj, dim=1)
    degree_sqrt = torch.diag(1.0 / torch.sqrt(degree))
    # 归一化拉普拉斯矩阵
    laplacian = torch.eye(adj.size(0)) - degree_sqrt @ adj @ degree_sqrt
    return laplacian

def chebyshev_polynomials(laplacian, K):
    # 缩放拉普拉斯矩阵
    lambda_max = torch.max(torch.linalg.eigvals(laplacian).real)
    scaled_laplacian = (2.0 / lambda_max) * laplacian - torch.eye(laplacian.size(0))

    # 初始化 Chebyshev 多项式基
    T_k = [torch.eye(laplacian.size(0)), scaled_laplacian]
    for k in range(2, K):
        T_k.append(2 * scaled_laplacian @ T_k[-1] - T_k[-2])
    return T_k

import torch.nn as nn

class ChebyshevConv(nn.Module):
    def __init__(self, in_features, out_features, K):
        super(ChebyshevConv, self).__init__()
        self.K = K
        self.weight = nn.Parameter(torch.Tensor(K, in_features, out_features))
        self.reset_parameters()

    def reset_parameters(self):
        nn.init.xavier_uniform_(self.weight)

    def forward(self, x, T_k):
        # x: (batch_size, num_nodes, in_features)
        # T_k: list of (num_nodes, num_nodes)
        output = torch.zeros_like(x) @ self.weight[0]
        for k in range(self.K):
            output += torch.einsum('nm,bmi->bni', T_k[k], x) @ self.weight[k]
        return output

我们分别在 Cora 和 PubMed 数据集上测试了不同 K 值（1 到 5）对节点分类准确率的影响。实验结果表明：