图卷积网络（GCN）详解

1. 引言

1.1 什么是图卷积网络

图卷积网络（Graph Convolutional Network, GCN）是由 Thomas Kipf 和 Max Welling 于 2017 年在论文《Semi-Supervised Classification with Graph Convolutional Networks》中提出的¹。GCN 是一种直接在图结构数据上运作的神经网络，能够有效地学习节点的低维嵌入表示。

与传统的卷积神经网络（CNN）处理规则网格数据（如图像）不同，图数据具有不规则、非欧几里得的结构。GCN 的核心思想是将卷积操作从传统网格推广到图结构，利用图的拓扑信息来聚合邻居节点的特征。

┌─────────────────────────────────────────────────────────────────────────┐
│                    GCN 在图数据上的卷积操作示意                            │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   传统CNN（图像）                    图卷积（GCN）                        │
│   ┌───┬───┬───┐                   ┌───┐                                 │
│   │ 1 │ 2 │ 3 │                   │ A │──┬──→┌───┐                      │
│   ├───┼───┼───┤                   └─┬─┘  │   │ B │                      │
│   │ 4 │ 5 │ 6 │    卷积核           │    └──→├───┤                      │
│   ├───┼───┼───┤   ┌───┬───┐       ┌─┴─┐      │ C │                      │
│   │ 7 │ 8 │ 9 │   │ w1│ w2│  →    │ A │──────└───┘                      │
│   └───┴───┴───┘   ├───┼───┤       └───┘                                 │
│    规则网格           │ w3│ w4│       不规则图结构                        │
│    固定邻域           └───┴───┘       动态邻域                            │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

1.2 GCN 的重要地位

GCN 在图神经网络发展史上具有里程碑式的意义：

里程碑	意义
首次提出	将谱域图卷积简化为空间域的逐层传播
计算效率	避免了昂贵的特征分解，$O(E)$ 复杂度
可扩展性	首次能够处理大规模真实世界图数据
半监督学习	有效利用无标签节点的图结构信息

---

2. 数学基础

2.1 图的基本定义

设无向图 $G=(V,E)$，其中：

• $V=\{1,2,\dots ,N\}$ 是节点集合，$N=|V|$ 为节点数
• $E\subseteq V\times V$ 是边集合，$M=|E|$ 为边数

邻接矩阵 $A\in {\mathbb{R}}^{N\times N}$：

$$A_{ij}=\{\begin{array}{ll}1& \text{if }(i,j)\in E\\ 0& \text{otherwise}\end{array}$$

度矩阵 $D\in {\mathbb{R}}^{N\times N}$（对角矩阵）：

$$D_{ii}=\sum _{j=1}^N{A}_{ij}=d_i$$

其中 $d_i$ 是节点 $i$ 的度。

2.2 拉普拉斯矩阵

2.2.1 拉普拉斯矩阵的定义

图拉普拉斯矩阵（Graph Laplacian）是谱图理论的核心工具，定义为：

$$L=D-A$$

其中 $D$ 是度矩阵，$A$ 是邻接矩阵。

拉普拉斯矩阵的性质：

性质	描述
半正定性	$L$ 是半正定矩阵，所有特征值 ${\lambda }_i\ge 0$
行和为零	$L1=0$，其中 $1$ 是全 1 向量
二次型形式	${\mathbf{x}}^{\top }L\mathbf{x}=\frac{1}{2}{\sum }_{i,j}{A}_{ij}(x_i-x_j{)}^2$
稀疏性	与邻接矩阵具有相同的稀疏结构

2.2.2 对称归一化拉普拉斯

对称归一化拉普拉斯矩阵（Symmetric Normalized Laplacian）定义为：

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

记 $\tilde{A}=D^{-1/2}A{D}^{-1/2}$，这是 GCN 中的核心矩阵。

特征值性质：$L_{sym}$ 的特征值范围为 $[0,2]$，其中 ${\lambda }_1=0$ 对应全 1 向量。

2.2.3 随机游走归一化拉普拉斯

随机游走归一化拉普拉斯（Random Walk Normalized Laplacian）定义为：

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

该矩阵满足 $1^{\top }{L}_{rw}=0$，与随机游走的转移概率密切相关。

设转移概率矩阵 $P=D^{-1}A$，则：

$$L_{rw}=I-P$$

2.2.4 三种拉普拉斯矩阵的对比

类型	定义	特征值范围	应用场景
组合拉普拉斯 $L=D-A$	$L_{ij}=-1$ if $i\sim j$, $L_{ii}=d_i$	$[0,2d_{max}]$	理论分析
对称归一化 $L_{sym}=I-D^{-1/2}A{D}^{-1/2}$	$L_{sym}=D^{-1/2}L{D}^{-1/2}$	$[0,2]$	GCN, 谱分析
随机游走 $L_{rw}=I-D^{-1}A$	$L_{rw}=D^{-1}L$	$[0,1]$	PageRank, 随机游走

2.3 图傅里叶变换

2.3.1 动机：从欧几里得空间到图

在传统信号处理中，傅里叶变换将信号从时域转换到频域：

$$\hat{f}(\omega )=⟨f,e^{i\omega t}⟩=\int f(t)e^{-i\omega t}dt$$

其中 $e^{i\omega t}$ 是拉普拉斯算子 $-\frac{{\partial }^2}{\partial t^2}$ 的特征函数。

关键洞察：拉普拉斯算子的特征函数提供了”频率”基。将这一思想推广到图上，图拉普拉斯矩阵 $L$ 的特征向量即为图的”频率基”。

2.3.2 图傅里叶变换定义

设 $L=U\Lambda U^{\top }$ 是拉普拉斯矩阵 $L$ 的特征分解，其中：

• $U=[{\mathbf{u}}_1,{\mathbf{u}}_2,\dots ,{\mathbf{u}}_N]\in {\mathbb{R}}^{N\times N}$ 是特征向量矩阵
• $\Lambda =\text{diag}({\lambda }_1,{\lambda }_2,\dots ,{\lambda }_N)$ 是特征值对角矩阵

对于图上的信号 $\mathbf{x}\in {\mathbb{R}}^N$，图傅里叶变换（Graph Fourier Transform, GFT）定义为：

$$\hat{\mathbf{x}}=U^{\top }\mathbf{x}\Rightarrow {\hat{x}}_k=⟨\mathbf{x},{\mathbf{u}}_k⟩=\sum _{i=1}^N{u}_k(i)x_i$$

逆图傅里叶变换为：

$$\mathbf{x}=U\hat{\mathbf{x}}\Rightarrow x_i=\sum _{k=1}^N{\hat{x}}_k{u}_k(i)$$

2.3.3 频率解释

图拉普拉斯矩阵的特征值 ${\lambda }_k$ 具有”频率”的语义：

特征值	频率语义	特征向量特性
${\lambda }_1=0$	最低频率	全局常数（${\mathbf{u}}_1\propto 1$）
${\lambda }_k$ 增大	频率增加	振荡加剧，局部变化增多
${\lambda }_N\approx 2$	最高频率	符号变化频繁

┌─────────────────────────────────────────────────────────────────────────┐
│                    图拉普拉斯特征向量的频率语义                            │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  λ₁ = 0          λ₂, λ₃             λ₄, λ₅             λ_N ≈ 2         │
│  ┌─────────┐     ┌─────────┐        ┌─────────┐        ┌─────────┐     │
│  │ + + + + │     │ - - - - │        │ + - + - │        │ + - + - │     │
│  │ + + + + │     │ - + + - │        │ - + - + │        │ - + - + │     │
│  │ + + + + │     │ - - + - │        │ + - + - │        │ + - + - │     │
│  │ + + + + │     │ - + - + │        │ - + - + │        │ - + - + │     │
│  └─────────┘     └─────────┘        └─────────┘        └─────────┘     │
│   常数信号         低频信号            中频信号            高频信号        │
│  (全局平滑)       (局部变化)          (边缘振荡)         (噪声/细节)      │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

2.4 卷积定理在图上的推广

2.4.1 卷积定理

在传统欧几里得空间，卷积定理指出：时域卷积等价于频域乘积

$$(f\ast g)(t)=\int f(\tau )g(t-\tau )d\tau \iff \widehat{f\ast g}(\omega )=\hat{f}(\omega )\cdot \hat{g}(\omega )$$

2.4.2 图卷积定理

将卷积定理推广到图上，利用图傅里叶变换：

$$(f{\ast }_{G}g)(i)=\sum _{j\in V}f(j)g(i,j)$$

其中图卷积定义为：

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

这里 $\odot$ 表示逐元素乘积（Hadamard 积）。

等价形式：

$$\mathbf{x}{\ast }_G\mathbf{g}=U\text{diag}(\hat{\mathbf{g}})U^{\top }\mathbf{x}$$

2.4.3 谱域图卷积

设滤波器 ${\mathbf{g}}_{\theta }$ 在谱域的参数化为 ${\hat{g}}_{\theta }({\lambda }_k)={\theta }_k$，则谱域图卷积为：

$$\mathbf{y}=U\text{diag}(\mathbf{\theta })U^{\top }\mathbf{x}$$

其中 $\mathbf{\theta }=[{\theta }_1,{\theta }_2,\dots ,{\theta }_N{]}^{\top }$ 是可学习的滤波器参数。

物理意义：

• 每个特征值 ${\lambda }_k$ 对应一个”频率通道”
• 参数 ${\theta }_k$ 控制该频率通道的增益
• 通过调整 ${\theta }_k$，可实现低通、高通或带通滤波

2.5 谱域图卷积的计算问题

2.5.1 直接计算的复杂度

朴素的谱域卷积存在两个主要问题：

问题	复杂度	说明
特征分解	$O(N^3)$	需要计算 $L=U\Lambda U^{\top }$
矩阵乘法	$O(N^2)$ per layer	$U\text{diag}(\mathbf{\theta })U^{\top }$
非局部性	全图操作	无法利用图的稀疏性

对于大规模图（如社交网络、知识图谱），这种计算方式不可行。

2.5.2 Chebyshev 多项式近似

为解决计算效率问题，Defferrard 等人提出用 Chebyshev 多项式近似滤波器²：

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

其中：

• $T_k(x)=\cos (k\arccos (x))$ 是 Chebyshev 多项式
• $\tilde{\Lambda }=\frac{2}{{\lambda }_{\max }}\Lambda -I$ 是归一化的特征值矩阵
• $K$ 是多项式阶数，控制滤波器的局部性

空间解释：$K$ 阶 Chebyshev 多项式滤波器仅利用 $K$ 跳邻居的信息。

计算形式：

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

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

2.5.3 GCN：一阶近似

Kipf 和 Welling 进一步简化，取 $K=1$（一阶近似）并假设 ${\lambda }_{\max }\approx 2$：

$$g_{\theta }\ast \mathbf{x}\approx {\theta }_0\mathbf{x}+{\theta }_1(L-I)\mathbf{x}={\theta }_0\mathbf{x}-{\theta }_1{D}^{-1/2}A{D}^{-1/2}\mathbf{x}$$

令 $\theta ={\theta }_0=-{\theta }_1$（参数共享），并加入自环（self-loop）：

$$\tilde{A}=A+I,\tilde{D}=D+I$$

得到简化的卷积：

$$\mathbf{y}=\theta {\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}\mathbf{x}$$

---

3. GCN 层传播规则

3.1 单层传播公式

对于第 $l$ 层 GCN，给定输入节点特征 ${\mathbf{H}}^{(l)}\in {\mathbb{R}}^{N\times F_l}$，输出特征 ${\mathbf{H}}^{(l+1)}\in {\mathbb{R}}^{N\times F_{l+1}}$ 为：

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

其中：

• ${\mathbf{W}}^{(l)}\in {\mathbb{R}}^{F_l\times F_{l+1}}$ 是可学习的权重矩阵
• $\sigma (\cdot )$ 是激活函数（如 ReLU）
• $\tilde{A}=A+I$ 是加入自环的邻接矩阵
• ${\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$ 是对称归一化的邻接矩阵

矩阵维度变换：

$$\underset{N\times F_{l+1}}{\underbrace{{\mathbf{H}}^{(l+1)}}}=\sigma \left(\underset{N\times N}{\underbrace{{\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}}}\cdot \underset{N\times F_l}{\underbrace{{\mathbf{H}}^{(l)}}}\cdot \underset{F_l\times F_{l+1}}{\underbrace{{\mathbf{W}}^{(l)}}}\right)$$

3.2 逐节点视角

从单个节点 $i$ 的角度，传播规则可写为：

$${\mathbf{h}}_i^{(l+1)}=\sigma \left(\sum _{j\in \mathcal{N}(i)\cup \{i\}}\frac{1}{\sqrt{d_i{d}_j}}{\mathbf{h}}_j^{(l)}{\mathbf{W}}^{(l)}\right)$$

其中 $\mathcal{N}(i)$ 是节点 $i$ 的邻居集合。

信息聚合过程：

1. 邻居收集：收集节点 $i$ 及其所有邻居 $j\in \mathcal{N}(i)\cup \{i\}$ 的特征
2. 归一化加权：对每个邻居的特征乘以归一化系数 $\frac{1}{\sqrt{d_i{d}_j}}$
3. 线性变换：与权重矩阵 ${\mathbf{W}}^{(l)}$ 相乘
4. 非线性激活：应用激活函数 $\sigma (\cdot )$

┌─────────────────────────────────────────────────────────────────────────┐
│                      GCN 单层传播的逐节点计算                             │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│   节点 i 的邻居节点                                                      │
│                                                                         │
│              h_j⁽ˡ⁾                    h_k⁽ˡ⁾                          │
│               ┌─┐                          ┌─┐                          │
│          1/√(dᵢdⱼ)│                   1/√(dᵢdₖ)│                       │
│               ┌─┴─┴──────────────────────┴─┐                           │
│               │                            │                           │
│               │      ┌───────────────┐    │                           │
│   h_i⁽ˡ⁾ ───→│─────→│   聚合: Σ 1/√  │───→│───→ ReLU ──→ h_i⁽ˡ⁺¹⁾     │
│               │      │     dᵢdⱼ hⱼ⁽ˡ⁾  │    │         │              │
│               │      └───────────────┘    │         │              │
│               │                            │         ↓              │
│               └────────────────────────────┘       W⁽ˡ⁾               │
│                          │                                                  │
│                       h_l⁽ˡ⁾                                              │
│                          ┌─┐                                              │
│                     1/√(dᵢdₗ)│                                             │
│                          └─┘                                              │
│                                                                         │
│   其中 ℕ(i) ∪ {i} = {i, j, k, l}                                         │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

3.3 多层堆叠

多层 GCN 的堆叠方式为：

$${\mathbf{H}}^{(l+1)}=\sigma \left(\hat{A}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)}\right)$$

其中 $\hat{A}={\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$。

$K$ 层 GCN 的等效滤波器：

$${\mathbf{H}}^{(K)}=\sigma \left(\hat{A}\sigma \left(\hat{A}\cdots \sigma (\hat{A}\mathbf{X}{\mathbf{W}}^{(0)})\cdots {\mathbf{W}}^{(K-2)}\right){\mathbf{W}}^{(K-1)}\right)$$

根据谱理论，这等价于 $K$ 阶多项式滤波器：

$${\mathbf{H}}^{(K)}=\sum _{k=0}^K{\theta }_k{\hat{A}}^k\mathbf{XW}$$

3.4 前向传播算法

完整的 GCN 前向传播算法如下：

def gcn_layer(A, H, W, sigma=relu):
    """
    GCN 单层前向传播
    
    参数:
        A: 邻接矩阵 (N, N)，包含自环
        H: 节点特征 (N, F_in)
        W: 权重矩阵 (F_in, F_out)
        sigma: 激活函数
    
    返回:
        H_out: 输出特征 (N, F_out)
    """
    # Step 1: 计算度矩阵
    D = torch.diag(A.sum(dim=1))  # (N, N)
    
    # Step 2: 计算归一化系数 D^{-1/2}
    D_inv_sqrt = D.pow(-0.5)
    D_inv_sqrt[torch.isinf(D_inv_sqrt)] = 0  # 处理度为0的节点
    
    # Step 3: 计算归一化邻接矩阵
    A_norm = D_inv_sqrt @ A @ D_inv_sqrt  # (N, N)
    
    # Step 4: 消息传递 + 线性变换
    H_out = A_norm @ H @ W  # (N, F_out)
    
    # Step 5: 非线性激活
    if sigma is not None:
        H_out = sigma(H_out)
    
    return H_out

---

4. PyTorch Geometric 实现

4.1 PyTorch Geometric 简介

PyTorch Geometric（PyG）是基于 PyTorch 的图神经网络库，提供了丰富的图操作工具和预实现的 GNN 层。

4.2 GCNConv 实现解析

以下是 PyTorch Geometric 中 GCNConv 的核心实现：

import torch
import torch.nn.functional as F
from torch_geometric.nn import MessagePassing
from torch_geometric.utils import add_self_loops, degree
 
class GCNConv(MessagePassing):
    """
    图卷积层 (Graph Convolutional Layer)
    
    继承自 MessagePassing，实现了消息传递范式
    """
    
    def __init__(self, in_channels, out_channels, improved=False, bias=True):
        """
        参数:
            in_channels: 输入特征的维度
            out_channels: 输出特征的维度
            improved: 是否使用增强版（2*A + I 代替 A + I）
            bias: 是否添加偏置
        """
        super(GCNConv, self).__init__(aggr='add')  # 聚合方式：加和
        
        self.in_channels = in_channels
        self.out_channels = out_channels
        self.improved = improved
        
        # 线性变换权重
        self.weight = torch.nn.Parameter(torch.Tensor(in_channels, out_channels))
        
        # 偏置
        if bias:
            self.bias = torch.nn.Parameter(torch.Tensor(out_channels))
        else:
            self.register_parameter('bias', None)
        
        # 权重初始化
        self.reset_parameters()
    
    def reset_parameters(self):
        """Xavier 初始化"""
        torch.nn.init.xavier_uniform_(self.weight)
        if self.bias is not None:
            torch.nn.init.zeros_(self.bias)
    
    def forward(self, x, edge_index):
        """
        前向传播
        
        参数:
            x: 节点特征 (num_nodes, in_channels)
            edge_index: 边索引 (2, num_edges)
        
        返回:
            变换后的节点特征 (num_nodes, out_channels)
        """
        # Step 1: 添加自环
        # 将 (2, num_edges) 的边索引扩展，加入自环边
        edge_index, _ = add_self_loops(
            edge_index, 
            num_nodes=x.size(0),
            loop='self' if not self.improved else 'self_improved'
        )
        
        # Step 2: 线性变换
        x = torch.matmul(x, self.weight)
        
        # Step 3: 消息传递
        # propagate 函数会调用 message、aggregate、update
        out = self.propagate(edge_index, x=x)
        
        # Step 4: 添加偏置
        if self.bias is not None:
            out = out + self.bias
        
        return out
    
    def message(self, x_j, edge_index_i, num_nodes):
        """
        消息函数：计算从邻居节点 j 发送到目标节点 i 的消息
        
        参数:
            x_j: 邻居节点 j 的特征 (num_edges, out_channels)
            edge_index_i: 目标节点索引 (num_edges,)
            num_nodes: 总节点数
        
        返回:
            归一化后的消息
        """
        # 计算度 (out-degree)
        # degree 返回每个节点的出度
        row, col = edge_index_i  # 实际上这里 edge_index 是展开的
        
        # 计算归一化系数: 1 / sqrt(d_i * d_j)
        # deg 是一个 (num_nodes,) 的向量
        deg = degree(edge_index_i, num_nodes, dtype=x_j.dtype)
        
        # 避免除零
        deg_inv_sqrt = deg.pow(-0.5)
        deg_inv_sqrt[torch.isinf(deg_inv_sqrt)] = 0
        
        # 归一化系数
        norm = deg_inv_sqrt[edge_index_i] * deg_inv_sqrt  # 简化写法
        
        # 消息 = 归一化系数 × 邻居特征
        return norm.view(-1, 1) * x_j
    
    def message_and_aggregate(self, adj_t, x):
        """
        优化的消息传递：使用稀疏矩阵乘法
        
        当 adj_t 是稀疏矩阵时，比逐边计算更高效
        """
        # adj_t 是归一化后的邻接矩阵（稀疏格式）
        return torch.sparse.mm(adj_t, x)
    
    def update(self, aggr_out):
        """
        更新函数：对聚合后的消息应用激活函数
        
        参数:
            aggr_out: 聚合后的特征
        
        返回:
            更新后的节点表示
        """
        return aggr_out

4.3 完整 GCN 模型

以下是一个用于节点分类的完整 GCN 模型：

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GCNConv
from torch_geometric.datasets import Planetoid
 
class GCN(nn.Module):
    """
    图卷积网络模型
    
    用于半监督节点分类任务
    """
    
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.5):
        """
        参数:
            in_channels: 输入特征维度
            hidden_channels: 隐藏层维度
            out_channels: 输出类别数
            dropout: Dropout 比率
        """
        super(GCN, self).__init__()
        
        # 第一层：输入 -> 隐藏
        self.conv1 = GCNConv(in_channels, hidden_channels)
        
        # 第二层：隐藏 -> 输出
        self.conv2 = GCNConv(hidden_channels, out_channels)
        
        # Dropout
        self.dropout = dropout
    
    def forward(self, x, edge_index):
        """
        前向传播
        
        参数:
            x: 节点特征 (num_nodes, in_channels)
            edge_index: 边索引 (2, num_edges)
        
        返回:
            输出 logits (num_nodes, out_channels)
        """
        # 第一层：GCN + ReLU + Dropout
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        x = F.dropout(x, p=self.dropout, training=self.training)
        
        # 第二层：GCN
        x = self.conv2(x, edge_index)
        
        return x
    
    def encode(self, x, edge_index):
        """
        编码函数：返回节点嵌入（不含分类头）
        """
        x = self.conv1(x, edge_index)
        x = F.relu(x)
        return x
 
 
def train_node_classification():
    """
    完整的训练流程示例（Cora 数据集）
    """
    # 加载数据集
    dataset = Planetoid(root='/tmp/Cora', name='Cora')
    data = dataset[0]
    
    # 初始化模型
    model = GCN(
        in_channels=dataset.num_node_features,
        hidden_channels=16,
        out_channels=dataset.num_classes,
        dropout=0.5
    )
    
    optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)
    criterion = nn.CrossEntropyLoss()
    
    # 训练循环
    model.train()
    for epoch in range(200):
        optimizer.zero_grad()
        
        # 前向传播
        out = model(data.x, data.edge_index)
        
        # 只使用有标签的节点计算损失
        loss = criterion(out[data.train_mask], data.y[data.train_mask])
        
        # 反向传播
        loss.backward()
        optimizer.step()
        
        if epoch % 20 == 0:
            # 评估
            model.eval()
            pred = model(data.x, data.edge_index).argmax(dim=1)
            correct = (pred[data.test_mask] == data.y[data.test_mask]).sum()
            acc = int(correct) / int(data.test_mask.sum())
            print(f'Epoch {epoch:03d}, Loss: {loss:.4f}, Test Acc: {acc:.4f}')
            model.train()
 
 
# 简化版本：手动实现 GCN 层
class SimpleGCNLayer(nn.Module):
    """
    不依赖 PyG 的简化 GCN 实现
    便于理解底层原理
    """
    
    def __init__(self, in_features, out_features):
        super(SimpleGCNLayer, self).__init__()
        self.linear = nn.Linear(in_features, out_features)
    
    def forward(self, x, adj):
        """
        参数:
            x: 节点特征 (N, in_features)
            adj: 归一化邻接矩阵 (N, N)
        
        返回:
            输出特征 (N, out_features)
        """
        # 消息传递：聚合邻居信息
        support = torch.mm(adj, x)  # (N, N) @ (N, F_in) -> (N, F_in)
        
        # 线性变换
        output = self.linear(support)  # (N, F_in) @ (F_in, F_out) -> (N, F_out)
        
        return output
 
 
def build_normalized_adj(A):
    """
    构建归一化邻接矩阵
    
    A: 邻接矩阵 (N, N)
    返回: 对称归一化邻接矩阵
    """
    # 添加自环
    A = A + torch.eye(A.size(0))
    
    # 度矩阵
    D = A.sum(dim=1)
    
    # 归一化系数 D^{-1/2}
    D_inv_sqrt = torch.diag(D.pow(-0.5))
    D_inv_sqrt[torch.isinf(D_inv_sqrt)] = 0
    
    # 对称归一化
    A_norm = D_inv_sqrt @ A @ D_inv_sqrt
    
    return A_norm

4.4 批处理训练

对于大规模图数据，PyG 支持高效的批处理：

from torch_geometric.loader import DataLoader
from torch_geometric.datasets import TUDataset
 
def batch_training_example():
    """
    批处理训练示例（使用图级数据集）
    """
    # 加载图级数据集（如 ENZYMES）
    dataset = TUDataset(root='/tmp/ENZYMES', name='ENZYMES')
    
    # 创建数据加载器
    loader = DataLoader(dataset, batch_size=32, shuffle=True)
    
    # 定义带批处理的 GCN
    class GraphLevelGCN(nn.Module):
        def __init__(self, in_channels, hidden_channels, out_channels):
            super().__init__()
            self.conv1 = GCNConv(in_channels, hidden_channels)
            self.conv2 = GCNConv(hidden_channels, hidden_channels)
            self.lin = nn.Linear(hidden_channels, out_channels)
        
        def forward(self, x, edge_index, batch):
            # x: 所有节点的拼接
            # edge_index: 所有边的拼接
            # batch: 标识每个节点属于哪个图
            
            # 两层 GCN
            x = self.conv1(x, edge_index)
            x = F.relu(x)
            x = self.conv2(x, edge_index)
            x = F.relu(x)
            
            # 图级池化（所有节点求均值）
            x = global_mean_pool(x, batch)
            
            # 分类头
            return self.lin(x)
    
    model = GraphLevelGCN(
        in_channels=dataset.num_node_features,
        hidden_channels=64,
        out_channels=dataset.num_classes
    )
    
    optimizer = torch.optim.Adam(model.parameters(), lr=0.001)
    
    model.train()
    for batch in loader:
        optimizer.zero_grad()
        
        out = model(batch.x, batch.edge_index, batch.batch)
        loss = F.cross_entropy(out, batch.y)
        
        loss.backward()
        optimizer.step()

---

5. 与空间方法的比较

5.1 空间图卷积方法概述

空间方法直接在图的拓扑结构上定义卷积操作，通过聚合邻居节点的信息来更新节点表示。与谱方法相比，空间方法更直观且更容易实现。

方法	年份	聚合方式	核心创新
GraphSAGE	2017	Mean/LSTM/Pool	归纳式学习，采样邻居
GAT	2018	注意力加权	引入自注意力机制
GIN	2019	Max-pooling	理论上证明了表达能力

5.2 GraphSAGE

5.2.1 核心思想

GraphSAGE（SAmple and AGgrEgatE）由 Hamilton 等人提出³，解决了转导学习（transductive learning）的局限性，能够泛化到未见节点。

class GraphSAGEConv(MessagePassing):
    """
    GraphSAGE 卷积层
    """
    
    def __init__(self, in_channels, out_channels, aggr='mean'):
        super().__init__(aggr=aggr)
        self.in_channels = in_channels
        self.out_channels = out_channels
        
        # 自身变换
        self.lin_self = nn.Linear(in_channels, out_channels)
        
        # 邻居变换
        self.lin_neighbor = nn.Linear(in_channels, out_channels)
    
    def forward(self, x, edge_index):
        # 自身特征变换
        h_self = self.lin_self(x)
        
        # 消息传递获取邻居聚合
        h_neighbor = self.propagate(edge_index, x=x)
        
        # 拼接并激活
        out = F.relu(h_self + h_neighbor)
        
        return out
    
    def message(self, x_j):
        # 邻居特征变换
        return self.lin_neighbor(x_j)

5.2.2 聚合器设计

GraphSAGE 提出了多种聚合器：

聚合器	公式	特点
Mean	$\frac{1}{	\mathcal{N}(i)
LSTM	$\text{LSTM}([h_j:j\in \mathcal{N}(i)])$	考虑邻居顺序
Pooling	$\max (\{\text{MLP}(h_j):j\in \mathcal{N}(i)\})$	捕捉集合特征

5.3 图注意力网络（GAT）

5.3.1 注意力机制

GAT（Graph Attention Network）由 Veličković 等人提出⁴，引入注意力机制来自适应地学习邻居节点的权重。

注意力系数：

$${\alpha }_{ij}=\frac{\exp \left(\text{LeakyReLU}\left({\mathbf{a}}^{\top }[\mathbf{W}{\mathbf{h}}_i\Vert \mathbf{W}{\mathbf{h}}_j]\right)\right)}{{\sum }_{k\in \mathcal{N}(i)\cup \{i\}}\exp \left(\text{LeakyReLU}\left({\mathbf{a}}^{\top }[\mathbf{W}{\mathbf{h}}_i\Vert \mathbf{W}{\mathbf{h}}_k]\right)\right)}$$

其中 $\mathbf{a}\in {\mathbb{R}}^{2F^{\prime }}$ 是注意力向量，$\Vert$ 表示拼接。

特征更新：

$${\mathbf{h}}_i^{\prime }=\sigma \left(\sum _{j\in \mathcal{N}(i)\cup \{i\}}{\alpha }_{ij}\mathbf{W}{\mathbf{h}}_j\right)$$

5.3.2 多头注意力

GAT 使用多头注意力来稳定学习过程：

$${\mathbf{h}}_i^{\prime (m)}=\sigma \left(\sum _{j\in \mathcal{N}(i)}{\alpha }_{ij}^{(m)}{\mathbf{W}}^{(m)}{\mathbf{h}}_j\right)$$

最终输出（$M$ 个注意力头）：

$${\mathbf{h}}_i^{\prime }={\Vert }_{m=1}^M{\mathbf{h}}_i^{\prime (m)}\text{或}{\mathbf{h}}_i^{\prime }=\sigma \left(\frac{1}{M}\sum _{m=1}^M{\mathbf{h}}_i^{\prime (m)}\right)$$

5.3.3 GAT 与 GCN 的对比

特性	GCN	GAT
邻居权重	固定（基于度）	自适应学习
计算复杂度	$O(E\cdot F)$	$O(E\cdot F)$（额外注意力计算）
注意力头数	不适用	$K$ 个并行头
表达能力	受限于固定权重	更强，可区分不同邻居
可解释性	较差	注意力权重可解释

import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.nn import GATConv
 
class GAT(nn.Module):
    """
    图注意力网络
    """
    
    def __init__(self, in_channels, hidden_channels, out_channels, heads=8, dropout=0.6):
        super(GAT, self).__init__()
        
        # 第一层：多头注意力
        self.conv1 = GATConv(
            in_channels, 
            hidden_channels, 
            heads=heads, 
            dropout=dropout
        )
        
        # 第二层：多头注意力
        self.conv2 = GATConv(
            hidden_channels * heads,  # 拼接后的维度
            out_channels,
            heads=1,  # 输出层通常用单个头
            concat=False,  # 不拼接，取平均
            dropout=dropout
        )
        
        self.dropout = dropout
    
    def forward(self, x, edge_index):
        x = F.dropout(x, p=self.dropout, training=self.training)
        x = F.elu(self.conv1(x, edge_index))
        x = F.dropout(x, p=self.dropout, training=self.training)
        x = self.conv2(x, edge_index)
        return F.log_softmax(x, dim=1)

5.4 三种方法的综合对比

维度	GCN	GraphSAGE	GAT
类型	谱方法简化	空间方法	空间方法
邻居聚合	归一化加权求和	Mean/LSTM/Pool	注意力加权求和
权重来源	度矩阵固定	可学习但无区分	注意力机制自适应
归纳学习	部分支持	完全支持	完全支持
时间复杂度	$O(E\cdot F)$	$O(E\cdot F)$	$O(E\cdot F)$
空间复杂度	$O(E)$	$O(K\cdot E)$	$O(E)$
适用场景	固定图、节点分类	大规模图、动态图	异构图、关系重要性

---

6. 局限性与发展挑战

6.1 主要局限性

6.1.1 过平滑问题

随着 GCN 层数增加，节点表示趋于收敛到相同的向量，导致可区分性丧失。

详见：过平滑与过压缩问题

数学分析：归一化邻接矩阵 $\hat{A}$ 的幂次行为

$$\underset{K\to \infty }{\lim }{\hat{A}}^K=1{\mathbf{\pi }}^{\top }$$

其中 $\mathbf{\pi }$ 是稳态分布。当 $K$ 足够大时，所有节点的表示趋向于相同。

6.1.2 感受野受限

GCN 的单层感受野仅限于 1 跳邻居。多层 GCN 虽可扩大感受野，但加深网络会加剧过平滑。

与 Transformer 的对比：

方法	远程依赖建模
GCN	需要 $O(K)$ 层才能覆盖 $K$ 跳邻居
Transformer	自注意力 $O(1)$ 层直接建模全局依赖

6.1.3 异构图支持不足

GCN 基于同质图假设（邻居与节点同分布），难以直接处理：

• 异构图（不同类型节点/边）
• 多关系图（知识图谱）
• 带属性的边

6.2 训练挑战

6.2.1 全图批训练

GCN 需要整图信息进行前向传播，无法像图像 CNN 那样进行随机 mini-batch 训练。

解决方案：

• GraphSAGE 的邻居采样
• Cluster-GCN 的图划分
• Mini-batch 技术

6.2.2 内存消耗

全图计算导致 $O(E)$ 内存复杂度，大规模图难以处理：

# 内存分析
# 假设 N=100万, E=1000万, F=256
 
memory_needed = (N * N) * 4  # 邻接矩阵: 4TB (!)
memory_needed = (E * F) * 4  # 稀疏存储: ~10GB

6.3 发展改进方向

改进方向	代表工作	核心贡献
更深网络	DropEdge, DenseGCN	缓解过平滑
注意力增强	GAT, GaAN	自适应邻居权重
图采样	GraphSAGE, FastGCN	支持大规模训练
图 Transformer	Graphormer, GTR	全局建模能力

---

7. 应用场景

7.1 节点分类

经典数据集：Cora, Citeseer, Pubmed（引用网络）

Cora 数据集统计：
- 节点数：2,708
- 边数：5,429
- 特征维度：1,433
- 类别数：7
- 任务：论文主题分类

7.2 图分类

应用：分子属性预测、蛋白质功能预测

# 分子属性预测示例
class MoleculeGCN(nn.Module):
    def __init__(self, num_features, hidden_dim, num_classes):
        super().__init__()
        self.conv1 = GCNConv(num_features, hidden_dim)
        self.conv2 = GCNConv(hidden_dim, hidden_dim)
        self.classifier = nn.Linear(hidden_dim, num_classes)
    
    def forward(self, x, edge_index, batch):
        # 图卷积
        x = F.relu(self.conv1(x, edge_index))
        x = F.relu(self.conv2(x, edge_index))
        
        # 图级池化
        x = global_mean_pool(x, batch)
        
        # 分类
        return self.classifier(x)

7.3 链接预测

应用：推荐系统、知识图谱补全

7.4 其他应用

领域	应用	说明
计算机视觉	场景图生成、点云分类	图结构建模物体关系
自然语言处理	知识图谱问答、文本分类	利用语义图增强表示
推荐系统	电商推荐、社交推荐	用户-物品交互图
交通预测	路网流量预测	时空图神经网络
生物医药	药物发现、蛋白质结构	分子图分析

---

8. 总结

8.1 GCN 的核心贡献

贡献	描述
简化谱卷积	将 $O(N^3)$ 特征分解简化为 $O(E)$ 空间操作
逐层传播	提出 ${\mathbf{H}}^{(l+1)}=\sigma (\hat{A}{\mathbf{H}}^{(l)}{\mathbf{W}}^{(l)})$
半监督学习	有效利用无标签节点的图结构信息
可扩展性	首次实现大规模图数据的神经网络处理

8.2 演进路线

┌─────────────────────────────────────────────────────────────────────────┐
│                         GCN 发展演进路线                                   │
├─────────────────────────────────────────────────────────────────────────┤
│                                                                         │
│  [谱域起源]                                                              │
│    └─→ 谱卷积 ($U diag(\theta) U^\top$) ── $O(N^3)$                     │
│    └─→ Chebyshev 近似 ── $O(K|E|)$                                      │
│                                                                         │
│  [GCN 突破]                                                              │
│    └─→ 一阶 Chebyshev ── $\hat{A} \mathbf{H} \mathbf{W}$                │
│    └─→ $O(|E|)$ 复杂度，支持大规模图                                     │
│                                                                         │
│  [空间方法兴起]                                                           │
│    └─→ GraphSAGE ── 归纳学习、邻居采样                                   │
│    └─→ GAT ── 注意力机制                                                │
│    └─→ GIN ── 理论表达能力保证                                           │
│                                                                         │
│  [当前前沿]                                                              │
│    └─→ 图 Transformer ── 全局建模                                        │
│    └─→ 200+ 层的深度 GCN ── 残差连接、归一化                              │
│    └─→ 图神经网络 + 大语言模型 ── 知识图谱问答                             │
│                                                                         │
└─────────────────────────────────────────────────────────────────────────┘

8.3 进一步学习

主题	资源
谱图理论	谱GNN与图小波方法
GNN 深度限制	GNN深度限制：过平滑与过压缩
时序图神经网络	时序图神经网络综述
知识图谱	知识图谱补全的GNN方法

---

参考资料

Footnotes

1. Kipf, T. N., & Welling, M. (2017). Semi-Supervised Classification with Graph Convolutional Networks. ICLR. https://arxiv.org/abs/1609.02907 ↩

2. Defferrard, M., Bresson, X., & Vandergheynst, P. (2016). Convolutional Neural Networks on Graphs with Fast Localized Spectral Filtering. NeurIPS. ↩

3. Hamilton, W., Ying, Z., & Leskovec, J. (2017). Inductive Representation Learning on Large Graphs. NeurIPS. ↩

4. Veličković, P., Cucurull, G., Casanova, A., Romero, A., Lio, P., & Bengio, Y. (2018). Graph Attention Networks. ICLR. ↩