# 作业五：图神经网络（GNN）与节点分类

**发布日期**：2026 年 10 月 8 日

**截止日期**：2026 年 10 月 18 日 23:59（CST）

---

## 一、作业背景

在前四次作业中，我们沿着几何深度学习的主线，逐步探索了不同数据域上的神经网络架构：

| 作业 | 数据域 | 架构 | 核心对称性 |
|------|--------|------|-----------|
| 1-2 | 无结构（向量） | MLP | 无 |
| 3 | 规则网格（图像） | CNN | 平移等变 |
| 4 | 序列 | Transformer | 置换等变（+位置编码） |
| **5** | **图** | **GNN** | **置换等变** |

本次作业我们进入最后一个核心域——**图（Graph）**。现实世界中大量数据天然以图的形式存在：社交网络中的用户关系、分子中的原子键、论文之间的引用网络、交通路网等。这些数据的共同特点是：**节点没有固定的空间排列，邻居数量不固定，也没有自然的排序**——CNN 的固定卷积核和 Transformer 的位置编码都不再适用。

**图神经网络（GNN）** 通过 **消息传递（Message Passing）** 机制解决了这个问题：每个节点收集邻居的信息来更新自己的表示，且聚合方式对邻居的顺序不敏感（如求和、取均值）。这天然保证了**置换等变性**——无论你怎么重新编号节点，GNN 的输出会相应地重排，但数值不变。

本次作业以经典的 **Cora 引文网络**为实验场景，实现图卷积网络（GCN）完成**半监督节点分类**任务：

- **任务一**：使用 PyTorch Geometric（PyG）库搭建 GCN，体验标准 GNN 工作流
- **任务二**：从头实现 GCN 的核心传播公式，深入理解 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}HW$

> **Cora 数据集**：2,708 篇机器学习论文（节点），5,429 条引用关系（边），每篇论文用 1,433 维 bag-of-words 向量表示，共 7 个类别（Case_Based、Genetic_Algorithms、Neural_Networks、Probabilistic_Methods、Reinforcement_Learning、Rule_Learning、Theory）。标准分割：每类仅 20 个训练节点（共 140 个），500 个验证节点，1,000 个测试节点。

---

## 二、环境准备

### 安装依赖

```bash
pip install torch torchvision
pip install torch_geometric
pip install matplotlib scikit-learn
```

> **PyTorch Geometric 安装说明**：`torch_geometric` 需要与你的 PyTorch 和 CUDA 版本匹配。如果 `pip install torch_geometric` 报错，请参考 [官方安装指南](https://pytorch-geometric.readthedocs.io/en/latest/install/installation.html) 选择对应版本。
>
> **纯 CPU 用户**：本次作业的计算量极小（Cora 仅 2,708 个节点），纯 CPU 运行所有任务仅需数秒，无需 GPU。

### 数据集

Cora 数据集由 PyG 自动下载和管理，首次运行时会下载到 `./data/Cora/` 目录（约 5MB）。

---

## 三、作业内容

### 任务一：使用 PyG 实现 GCN 节点分类（`gcn_cora.py`）

编写 Python 脚本，使用 PyTorch Geometric 库完成 Cora 数据集上的 GCN 节点分类。

#### 具体步骤

1. **加载 Cora 数据集**：使用 `torch_geometric.datasets.Planetoid` 加载 Cora，打印数据集的基本信息（节点数、边数、特征维度、类别数、各 mask 的大小）。

2. **搭建 GCN 模型**：使用 `torch_geometric.nn.GCNConv` 搭建一个 2 层 GCN：

   ```
   Input(1433) → GCNConv(1433, 64) → ReLU → Dropout(0.5) → GCNConv(64, 7)
   ```

3. **训练模型**：使用 Adam 优化器 + CrossEntropyLoss，训练 200 个 epoch。注意：
   - 损失函数只在 `train_mask` 对应的节点上计算
   - 但前向传播涉及整张图的所有节点（消息传递需要邻居信息）

4. **评估与可视化**：
   - 记录每个 epoch 的训练 loss、训练/验证/测试准确率
   - 绘制 loss 和 accuracy 曲线，保存为 `gcn_curves.png`
   - 打印最终测试集准确率

5. **节点嵌入可视化**：使用 t-SNE 将训练好的 GCN 第一层输出（64 维隐藏表示）降维到 2D，按类别着色绘制散点图，保存为 `gcn_tsne.png`。观察同类节点是否在嵌入空间中聚集。

#### 参考超参数

| 参数 | 建议值 | 说明 |
|------|--------|------|
| `hidden_dim` | 64 | GCN 隐藏层维度 |
| `learning_rate` | 0.01 | 学习率 |
| `weight_decay` | 5e-4 | L2 正则化 |
| `dropout` | 0.5 | Dropout 概率 |
| `epochs` | 200 | 训练轮数 |

#### 代码框架（供参考）

```python
import torch
import torch.nn.functional as F
from torch_geometric.datasets import Planetoid
from torch_geometric.nn import GCNConv
import matplotlib.pyplot as plt

torch.manual_seed(42)

# ======================== 加载数据集 ========================

dataset = Planetoid(root='./data', name='Cora')
data = dataset[0]

print(f"节点数: {data.num_nodes}")
print(f"边数: {data.num_edges}")
print(f"特征维度: {data.num_node_features}")
print(f"类别数: {dataset.num_classes}")
print(f"训练/验证/测试节点数: {data.train_mask.sum()}/{data.val_mask.sum()}/{data.test_mask.sum()}")

# ======================== 定义 GCN 模型 ========================

class GCN(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.5):
        super().__init__()
        # TODO: 定义两层 GCNConv
        # Hint: self.conv1 = GCNConv(in_channels, hidden_channels)
        ...
        self.dropout = dropout

    def forward(self, x, edge_index):
        # TODO: 前向传播
        # Layer 1: conv1 → ReLU → Dropout
        # Layer 2: conv2 (无激活，输出 logits)
        ...

# ======================== 训练循环 ========================

device = torch.device('cuda' if torch.cuda.is_available() else 'cpu')
model = GCN(dataset.num_node_features, 64, dataset.num_classes).to(device)
data = data.to(device)
optimizer = torch.optim.Adam(model.parameters(), lr=0.01, weight_decay=5e-4)

def train():
    model.train()
    optimizer.zero_grad()
    out = model(data.x, data.edge_index)
    # TODO: 只在 train_mask 节点上计算 loss
    loss = F.cross_entropy(out[data.train_mask], data.y[data.train_mask])
    loss.backward()
    optimizer.step()
    return loss.item()

@torch.no_grad()
def evaluate():
    model.eval()
    out = model(data.x, data.edge_index)
    pred = out.argmax(dim=1)
    accs = {}
    for split, mask in [('train', data.train_mask), ('val', data.val_mask), ('test', data.test_mask)]:
        accs[split] = (pred[mask] == data.y[mask]).float().mean().item()
    return accs

# TODO: 训练 200 个 epoch，记录 loss 和 accuracy
# TODO: 绘制曲线并保存

# ======================== t-SNE 可视化 ========================

# TODO: 提取 GCN 第一层的隐藏表示，用 sklearn.manifold.TSNE 降维并绘图
# Hint: 在 forward 中额外返回中间层输出，或用 hook 提取
```

---

### 任务二：从头实现 GCN（`gcn_from_scratch.py`）

**不使用** `GCNConv`，直接用 PyTorch 的矩阵运算实现 GCN 的核心传播公式：

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

其中 $\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 是对称归一化的邻接矩阵（含自环）。

#### 具体步骤

1. **构建归一化邻接矩阵 $\hat{A}$**：
   - 从 `edge_index` 构建稀疏邻接矩阵 $A$
   - 加入自环：$\tilde{A} = A + I$
   - 计算度矩阵：$\tilde{D}_{ii} = \sum_j \tilde{A}_{ij}$
   - 对称归一化：$\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$

2. **实现 GCN 层**：用 `nn.Linear`（或 `nn.Parameter`）做线性变换 $HW$，用 $\hat{A}$ 做邻域聚合。

3. **搭建模型并训练**：与任务一相同的超参数，训练 200 个 epoch。

4. **对比验证**：打印最终测试准确率，确认与任务一的 PyG 实现结果接近。

#### 代码框架（供参考）

```python
import torch
import torch.nn as nn
import torch.nn.functional as F
from torch_geometric.datasets import Planetoid

torch.manual_seed(42)

# ======================== 加载数据集 ========================

dataset = Planetoid(root='./data', name='Cora')
data = dataset[0]

# ======================== 构建归一化邻接矩阵 ========================

def build_norm_adj(edge_index, num_nodes):
    """
    从 edge_index 构建 A_hat = D_tilde^{-1/2} @ A_tilde @ D_tilde^{-1/2}
    """
    # TODO: 构建稀疏邻接矩阵 A（使用 torch.sparse_coo_tensor）
    # TODO: 加自环 A_tilde = A + I
    # TODO: 计算度 D_tilde
    # TODO: 计算 D_tilde^{-1/2}
    # TODO: 返回 D_tilde^{-1/2} @ A_tilde @ D_tilde^{-1/2}
    # Hint: 可以用稠密矩阵实现（Cora 只有 2708 个节点，稠密矩阵仅 ~28MB）
    ...

A_hat = build_norm_adj(data.edge_index, data.num_nodes)

# ======================== 从头实现 GCN ========================

class GCNFromScratch(nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, dropout=0.5):
        super().__init__()
        # TODO: 定义两个线性层（不含 bias，因为 GCN 原论文不使用 bias）
        # Hint: self.W1 = nn.Linear(in_channels, hidden_channels, bias=False)
        ...
        self.dropout = dropout

    def forward(self, x, A_hat):
        # TODO: Layer 1: A_hat @ x @ W1 → ReLU → Dropout
        # TODO: Layer 2: A_hat @ h @ W2
        # Hint: torch.mm(A_hat, x) 或 A_hat @ x 做矩阵乘法
        ...

# ======================== 训练与评估 ========================

# TODO: 与任务一相同的训练循环，但使用 A_hat 而非 edge_index
```

---

### 任务三（可选）：实现 GAT 并与 GCN 对比

使用 PyG 的 `GATConv` 实现一个 GAT（Graph Attention Network）模型，与 GCN 在 Cora 上对比。

**参考结构**：

```python
from torch_geometric.nn import GATConv

class GAT(torch.nn.Module):
    def __init__(self, in_channels, hidden_channels, out_channels, heads=8, dropout=0.6):
        super().__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 = self.conv1(x, edge_index).relu()
        x = F.dropout(x, p=self.dropout, training=self.training)
        x = self.conv2(x, edge_index)
        return x
```

对比 GCN 和 GAT 的测试准确率、训练时间、参数量，并分析 GAT 注意力机制带来的优劣。

---

## 四、具体要求

| 项目 | 要求 |
|------|------|
| 编程语言 | Python 3.8+ |
| 框架 | PyTorch + PyTorch Geometric |
| 任务一模型 | 2 层 GCN（使用 `GCNConv`） |
| 任务二模型 | 2 层 GCN（从头实现，不使用 `GCNConv`） |
| 测试准确率 | 两个任务均 ≥ **78%**（Cora 标准分割下 GCN 的典型结果为 ~81%） |
| 可视化 | 训练曲线 `gcn_curves.png` + t-SNE 图 `gcn_tsne.png` |
| GPU 支持 | 代码自动检测 CUDA，兼容纯 CPU 运行 |
| 代码规范 | 结构清晰，关键步骤有注释 |

---

## 五、运行方式

```bash
# 任务一：使用 PyG 的 GCN
python gcn_cora.py

# 任务二：从头实现 GCN
python gcn_from_scratch.py
```

> **提示**：Cora 数据集极小（2,708 节点，1,433 维特征），两个任务在 CPU 上训练 200 个 epoch 均仅需 **数秒**。首次运行时 PyG 会自动下载数据集到 `./data/Cora/` 目录（约 5MB），后续运行直接从本地加载。

---

## 六、检查方法

1. **训练流程**：两个脚本均能正常运行至完成，控制台打印每 epoch（或每 10 个 epoch）的 loss 和准确率。
2. **准确率达标**：两个任务的测试集准确率均 ≥ 78%。
3. **一致性验证**：任务二（从头实现）的测试准确率与任务一（PyG 实现）接近（差距应在 ±3% 以内）。
4. **曲线图**：`gcn_curves.png` 显示 loss 下降、accuracy 上升的合理趋势。
5. **t-SNE 图**：`gcn_tsne.png` 中同类节点应形成明显聚类。

---

## 七、思考问题（可选）

### Q1 | GCN 传播公式的逐步拆解

GCN 的层级传播规则为：

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

(a) 如果不加自环（即用 $A$ 而非 $\tilde{A} = A + I$），节点在消息传递中会丢失什么信息？写出此时节点 $i$ 的更新公式，并说明为什么这对单独的孤立节点（度为 0）是致命的。

(b) 如果不做对称归一化（即用 $\tilde{A}$ 而非 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$），对于一个度为 1000 的节点和一个度为 2 的节点，它们聚合后的特征向量的范数大致相差多少倍？这会带来什么数值问题？

(c) 对比两种归一化方式：

| 归一化 | 公式 | 含义 |
|--------|------|------|
| 行归一化 | $D^{-1}A$ | ？ |
| 对称归一化 | $D^{-1/2}AD^{-1/2}$ | ？ |

为什么 GCN 选择对称归一化而非行归一化？（提示：考虑邻接矩阵的谱性质——对称矩阵的特征值是实数，这对谱图论的分析有什么好处？）

> **Hint**：行归一化 $D^{-1}A$ 相当于对每个节点取邻居特征的**算术平均**（随机游走归一化），它是非对称的；对称归一化 $D^{-1/2}AD^{-1/2}$ 相当于每条边的贡献按两端度的几何平均归一化，保持了矩阵的对称性。对称矩阵可以正交对角化 $L_{\text{sym}} = U\Lambda U^T$，这是谱图卷积的理论基础。

---

### Q2 | GNN 的置换等变性

GNN 的核心性质是**置换等变性**：如果重新编号所有节点（用置换矩阵 $P$ 作用），GNN 的输出也会做相同的重排。

(a) 设 GCN 的传播为 $f(X, A) = \sigma(\hat{A}XW)$。证明：

$$f(PX, PAP^T) = P \cdot f(X, A)$$

其中 $P$ 是任意置换矩阵（$PP^T = I$）。

(b) 回顾作业四 Q2：Transformer 的 Self-Attention **也是**置换等变的（$\text{Attention}(\Pi X) = \Pi \cdot \text{Attention}(X)$）。GNN 和 Transformer 都具有置换等变性，但它们的"聚合范围"不同——GNN 在稀疏图上聚合，Transformer 在完全图上聚合。这在实践中意味着什么？填写下表：

| | GCN | Transformer（无位置编码） |
|---|-----|--------------------------|
| 邻域 | ？ | ？ |
| 聚合复杂度 | ？ | ？ |
| 是否利用图结构 | ？ | ？ |
| 适合的图规模 | ？ | ？ |

(c) CNN 是平移等变的。我们知道"CNN 是 GNN 在规则网格上的特例"。请具体说明：将一张 $H \times W$ 的图像看作图时，节点是什么？边是什么？CNN 比一般 GNN 多利用了什么信息，使得它可以为每个邻居位置分配不同的权重？

> **Hint**：对于 (a)，关键是证明 $\hat{A}' = P\hat{A}P^T$，即归一化邻接矩阵在置换下也相应变换。对于 (c)，CNN 的卷积核为每个**相对位置** $(\Delta i, \Delta j)$ 分配了独立的权重——这依赖于网格的**空间坐标**，而一般图上的邻居没有固定的空间坐标。

---

### Q3 | 消息传递框架：统一所有 GNN

几乎所有 GNN 都可以写成消息传递的形式：

$$\mathbf{h}_i^{(l+1)} = \text{UPDATE}\left(\mathbf{h}_i^{(l)},\ \text{AGG}\left(\left\{\text{MSG}(\mathbf{h}_i^{(l)}, \mathbf{h}_j^{(l)}, \mathbf{e}_{ij}) : j \in \mathcal{N}(i)\right\}\right)\right)$$

(a) 将 GCN 写成消息传递形式。具体地，GCN 的 $\text{MSG}$、$\text{AGG}$、$\text{UPDATE}$ 分别是什么？

(b) 将 GAT 写成消息传递形式。GAT 与 GCN 的消息传递有什么不同？

(c) 如果我们允许 $\text{AGG}$ 为 `sum` / `mean` / `max` 三种，它们各自在什么场景下更合适？

| AGG | 等价操作 | 优势 | 劣势 |
|-----|---------|------|------|
| `sum` | ？ | ？ | ？ |
| `mean` | ？ | ？ | ？ |
| `max` | ？ | ？ | ？ |

> **Hint**：`sum` 聚合能区分"3 个邻居各贡献 1"和"1 个邻居贡献 1"（因为 $3 \neq 1$），但 `mean` 不能（$1/3 + 1/3 + 1/3 = 1/1$）。这与 GNN 的**表达力**有关——见 Q7。

---

### Q4 | 半监督学习：为什么 140 个标签就够？

Cora 的标准设定中，每类仅 20 个标注节点（共 140 个），但 GCN 能达到 ~81% 的测试准确率。

(a) 如果完全不使用图结构，只用 MLP（`1433 → 64 → 7`）在 140 个训练节点上训练，你预期准确率大约是多少？为什么？

(b) GCN 在前向传播中使用了**所有节点**的特征和**整张图**的边，但 loss 只在 140 个训练节点上计算。标签信息是如何"传播"到未标注节点的？请从消息传递的角度解释这个过程。

(c) **同质性假设（Homophily）**：Cora 数据集的同质性比率约为 0.81（即 81% 的边连接同类节点）。如果一个图的同质性为 0（完全异质），GCN 还能工作吗？为什么？

> **Hint**：对于 (a)，140 个训练样本 + 1433 维特征 → 严重的维度灾难。对于 (b)，考虑 2 层 GCN：第一层，未标注节点的表示融入了邻居（可能包含训练节点）的信息；第二层，进一步融入 2-hop 邻居的信息。loss 对训练节点的梯度会回传到它们邻居的表示，从而间接更新未标注节点的嵌入。对于 (c)，GCN 本质上是在做邻域平滑——让相连节点的表示趋于相似。如果相连节点的标签完全不同，平滑反而会模糊类别边界。

---

### Q5 | 过平滑问题：GNN 为什么不能太深？

作业三中我们知道，更深的 CNN = 更大的感受野 = 更好的性能（在一定范围内）。但 GNN 不同——超过 2-3 层后，性能通常开始下降。

(a) 一个 $L$ 层的 GCN 中，每个节点聚合了多少跳（hop）邻居的信息？对于 Cora（平均度约 4，直径约 19），$L = 10$ 时每个节点的接收场大约覆盖多少节点？

(b) 当所有节点都融入了全图的信息后，它们的表示会变得怎样？这个现象叫什么？为什么它对节点分类是灾难性的？

(c) 过平滑的数学本质：反复应用归一化邻接矩阵 $\hat{A}$ 相当于对图信号做低通滤波。设 $\hat{A}$ 的特征值为 $\lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_N$，则 $\hat{A}^L$ 的特征值为 $\lambda_i^L$。当 $L \to \infty$ 时，只有 $\lambda_1 = 1$ 对应的分量存活，其余全部衰减为 0。此时 $\hat{A}^L X$ 会收敛到什么？（提示：$\lambda_1 = 1$ 的特征向量与度有何关系？）

> **Hint**：对于 (c)，对称归一化拉普拉斯 $\hat{A} = I - L_{\text{sym}}$ 的最大特征值 $\lambda_1 = 1$，对应的特征向量正比于 $\tilde{D}^{1/2} \mathbf{1}$。当 $L \to \infty$ 时，所有节点的表示收敛到同一方向——图的"直流分量"。这就是**过平滑（Over-Smoothing）**：所有节点的嵌入趋于相同，不再可分。

---

### Q6 | GCN 与谱图卷积

GCN 有一个优美的理论动机来自**谱图论**。

(a) 图拉普拉斯矩阵定义为 $L = D - A$（或归一化形式 $L_{\text{sym}} = I - D^{-1/2}AD^{-1/2}$）。对于一个图信号 $\mathbf{x} \in \mathbb{R}^N$，拉普拉斯的二次型 $\mathbf{x}^T L \mathbf{x}$ 等于什么？写出展开式并解释其物理含义。

(b) 图上的"傅里叶变换"定义为 $\hat{\mathbf{x}} = U^T \mathbf{x}$，其中 $L = U\Lambda U^T$ 是特征分解。图上的"卷积"在谱域定义为 $g_\theta \star \mathbf{x} = U\, g_\theta(\Lambda)\, U^T \mathbf{x}$。

GCN 对 $g_\theta(\lambda)$ 做了什么近似，从而得到了空间域的简洁公式 $\hat{A}X$？这个近似对应了什么阶的多项式滤波器？

(c) 为什么说 GCN 是一个**低通滤波器**？这对节点分类任务意味着什么？在什么类型的图上这个低通假设会失效？

> **Hint**：对于 (a)，$\mathbf{x}^T L \mathbf{x} = \sum_{(i,j) \in E} (x_i - x_j)^2$，度量的是信号在图上的"平滑度"——值越小，相连节点的信号越接近。对于 (b)，GCN 用一阶切比雪夫近似：$g_\theta(\lambda) \approx \theta_0 + \theta_1 \lambda$，经过简化和重参数化后得到了 $\hat{A}$ 的形式。一阶多项式意味着 GCN 是最简单的局部滤波器——每层只看 1-hop 邻居。

---

### Q7 | 几何深度学习大统一：补全课程主线

回顾作业三 Q7 和作业四 Q10，现在你已经学完了四种核心架构。请完成最终版的统一对比表：

| 机制 | 连接方式 | 权重共享 | 对称群 | 邻域 | 适用数据 |
|------|---------|---------|--------|------|---------|
| **MLP** | ？ | ？ | ？ | ？ | ？ |
| **CNN** | ？ | ？ | ？ | ？ | ？ |
| **GNN (GCN)** | ？ | ？ | ？ | ？ | ？ |
| **GNN (GAT)** | ？ | ？ | ？ | ？ | ？ |
| **Transformer** | ？ | ？ | ？ | ？ | ？ |

并回答：

(a) 从 MLP → CNN → GNN → Transformer，对称性假设依次如何变化？假设越强意味着什么？假设越弱意味着什么？

(b) **一句话总结几何深度学习的核心主张。**

> **Hint**：几何深度学习的核心论点：不同的神经网络架构不是孤立发明的——它们是同一个统一框架（"域 + 对称性 → 等变架构"）在不同几何域上的具体实例。

---

## 八、提交要求

将以下文件打包为 `学号_姓名_HW5.zip`：

- `gcn_cora.py` — 任务一：使用 PyG 的 GCN 脚本
- `gcn_from_scratch.py` — 任务二：从头实现 GCN 的脚本
- `gcn_curves.png` — 训练曲线图
- `gcn_tsne.png` — 节点嵌入 t-SNE 可视化图
- 终端输出截图（包含最终测试准确率）
- （可选）GAT 对比实验结果

通过课程 QQ 群的作业系统上传。

---

## 九、参考依赖

```
torch
torch_geometric
matplotlib
scikit-learn
```