Common GCN Layer

GCNConv (Graph Convolutional Network)

核心思想：利用度矩阵进行归一化，解决节点度数差异导致的数值爆炸。

数学本质：对称归一化。

x_{i}^{(k)} = \sum_{j \in N (i) \cup {i}} \frac{1}{\sqrt{{\hat{d}}_{i} {\hat{d}}_{j}}} W x_{j}^{(k - 1)}

Matrix Form
- $\hat{A}$ : 包含自环的邻接矩阵 $[N, N]$ 。
- $\hat{D}$ : 对应的度矩阵。
- ${\hat{D}}^{- 1 / 2} \hat{A} {\hat{D}}^{- 1 / 2}$ : 这是归一化后的邻接矩阵

X^{(k)} = {\hat{D}}^{- 1 / 2} \hat{A} {\hat{D}}^{- 1 / 2} X^{(k - 1)} W

PyG 特点：
- 会自动处理 add_self_loops。
- 计算归一化系数 $α_{i, j} = 1 / \sqrt{{\hat{d}}_{i} {\hat{d}}_{j}}$ 并缓存，提高效率。
适用场景：经典的半监督节点分类，对图结构比较固定的任务效果稳健。

python

class GCNConv(MessagePassing):
    def __init__(self, in_channels, out_channels):
        super().__init__(aggr='add')
        self.lin = Linear(in_channels, out_channels, bias=False)

    def forward(self, x, edge_index):
        # 1. 添加自环
        edge_index, _ = add_self_loops(edge_index, num_nodes=x.size(0))
        # 2. 线性变换 (通常先做线性变换，减少 message 阶段计算量)
        x = self.lin(x)
        # 3. 计算归一化系数 (度矩阵 D)
        row, col = edge_index
        deg = degree(col, x.size(0), dtype=x.dtype)
        deg_inv_sqrt = deg.pow(-0.5)
        norm = deg_inv_sqrt[row] * deg_inv_sqrt[col] # 即 1/sqrt(di*dj)

        return self.propagate(edge_index, x=x, norm=norm)

    def message(self, x_j, norm):
        # 邻居特征乘以归一化系数
        return norm.view(-1, 1) * x_j

PyG 不存储稠密矩阵，而是通过 COO (Coordinate) 格式实现稀疏存储。
edge_index [2, E]：
- 解包魔法：row, col = edge_index。row 是源节点（发送者），col 是目标节点（接收者）。
- 布局逻辑：采用 $[2, E]$ 而不是 $[E, 2]$ 是为了方便 Python 解包和 PyTorch 索引。
degree() 函数：
- 本质：通过 scatter_add 实现的高效并行计数。
- 公式对应：计算度矩阵 $\hat{D}$ 。通常输入 col 来计算入度，用于归一化。
高级索引 (Advanced Indexing)：
- norm = deg_inv_sqrt[row] * deg_inv_sqrt[col]。
- 意义：将“节点维度”的属性（ $N$ ）瞬间广播到“边维度”（ $E$ ），为每条边分配专属权重。

PyG 的核心逻辑是：你写单条边的逻辑，我做全图的并行。

参数名即“索引键” (Naming Convention)

PyG 通过 inspect 机制自动识别 message 函数的参数名：

x_j：自动执行 x[edge_index[0]]（取邻居特征）。
x_i：自动执行 x[edge_index[1]]（取中心特征）。
norm / edge_attr：若维度等于 $E$ ，则直接按边对齐透传。

维度变换：.view(-1, 1)

作用：将形状从 [E]（向量）转为 [E, 1]（列矩阵）。
目的：触发 广播机制 (Broadcasting)。
运算：执行 norm.view(-1, 1) * x_j 不是矩阵乘法，而是逐元素相乘。它让一个标量权重作用于特征向量的每一个维度。

SAGEConv (GraphSAGE)

核心思想：不再使用矩阵全局归一化，而是采用采样+聚合。它最大的创新是引入了中心节点与邻居信息的 拼接 (Concatenation)。

数学本质：

x_{t a r g e t} = Linear (concat (x_{s e l f}, {aggregate}_{j \in N (i)} (x_{j})))

PyG 特点：
- 聚合方式（aggr）非常灵活：mean, max, lstm。
- 通过 root_weight=True 独立处理节点自身信息。
适用场景：大规模动态图，支持归纳学习（即可以推理训练时没见过的节点）。

python

class SAGEConv(MessagePassing):
    def __init__(self, in_channels, out_channels):
        super().__init__(aggr='mean') # 默认均值聚合
        self.lin_l = Linear(in_channels, out_channels) # 邻居权重
        self.lin_r = Linear(in_channels, out_channels) # 自身权重

    def forward(self, x, edge_index):
        # 直接传播，无需手动加自环（因为后面有残差连接）
        out = self.propagate(edge_index, x=x)
        # 自身特征 + 聚合后的邻居特征
        out = self.lin_l(out) + self.lin_r(x) 
        return out

与 GCN 将节点自身看作“带自环的邻居”不同，GraphSAGE 认为 “我”和“我的邻居”是本质不同的。
GCN 逻辑： $x_{i}^{'} = Linear (mean (j \in N (i) \cup {i}))$ —— 混合后再变换。
SAGE 逻辑： $x_{i}^{'} = {Linear}_{s e l f} (x_{i}) + {Linear}_{n e i g h} (mean (j \in N (i)))$ —— 独立变换再融合。

线性层 (Linear) 的双重角色

在 SAGEConv 的实现中，通常看到两个独立的 Linear 层（lin_l 和 lin_r）：

数学等价性：公式里的 $Linear (concat (x_{s e l f}, x_{n e i g h}))$ 在数学上完全等同于 $W_{r} x_{s e l f} + W_{l} x_{n e i g h}$ 。
功能分工：
- self.lin_r (Root)：负责提取节点自身的特征，起到类似 Skip-Connection 的作用，确保自身信息不被邻居噪音淹没。
- self.lin_l (Neighbor)：负责对聚合后的邻居信息进行特征提取和降维。
聚合逻辑：先平均，再变换

这是 SAGE 性能优化的核心技巧：

步骤 1 (聚合)：计算所有邻居特征的算术平均值 $μ = \frac{1}{| N (i) |} \sum x_{j}$ 。此过程无可学习参数。
步骤 2 (变换)：将平均值 $μ$ 喂给 self.lin_l。
效率对比：
- 若先变换再聚合：每条边都要做一次矩阵乘法（计算量 $\propto E$ ）。
- 若先聚合再变换：每个节点只需做一次矩阵乘法（计算量 $\propto N$ ）。由于 $E ≫ N$ ，SAGE 的这种做法在海量数据下极快。

在 SAGEConv 的实现中，message 函数通常可以省略或只写 return x_j：

原因：SAGE 的消息传递逻辑极其纯粹——它不需要像 GCN 那样在每条边上计算复杂的归一化系数（norm）。
默认行为：如果你不写 message，PyG 基类会自动默认执行“原样传递”。
逻辑重心：SAGE 的核心逻辑不在 message（边）里，而是在 forward 最后的线性融合（节点）里。

Q: SAGE 需要像 GCN 那样手动添加自环 (Self-loop) 吗？
- A: 不需要。因为 self.lin_r(x) 已经显式地处理了节点自身特征。强行加自环反而会导致自身信息在聚合阶段被平均化，削弱了 SAGE 分离自我的优势。
Q: 为什么 SAGE 不用 $D^{\frac{- 1}{2}} A D^{\frac{- 1}{2}}$ 这种复杂的归一化？
- A: 为了灵活性。SAGE 采用简单的 mean 或 max 聚合，这使得它对新节点（推理时才出现的点）非常友好，这被称为归纳学习 (Inductive Learning)。

GATConv (Graph Attention Network)

核心思想：并非所有邻居都同等重要。通过注意力机制动态学习邻居的权重。

数学本质：
- 注意力系数 (Attention Coefficients) 对于边 $(j, i)$ ，其原始注意力分数 $e_{i, j}$ 取决于目标节点 $i$ 和源节点 $j$ 的特征变换后的拼接：
  - W：共享的线性变换矩阵。
  - ||：拼接 (Concatenation) 操作。
  - $a$ ：可学习的注意力向量（维度为 $2 \times out_channels$ ）。
  - $e_{i, j} = LeakyReLU ({\vec{a}}^{T} [W x_{i} ‖ W x_{j}])$
- 归一化 (Softmax) 为了使不同节点的邻居贡献可比，对节点 $i$ 的所有邻居进行 Softmax 归一化，得到最终权重 $α_{i, j}$ ：
  - $α_{i, j} = {softmax}_{j} (e_{i, j}) = \frac{\exp (e_{i, j})}{\sum_{k \in N (i) \cup {i}} \exp (e_{i, k})}$
- 多头注意力 (Multi-head Attention) 为了增强学习的稳定性，通常并行执行 $K$ 个独立的注意力机制，并进行拼接（最后层则取平均）：
  - $x_{i}^{'} = {concat}_{k = 1}^{K} (\sum_{j \in N (i) \cup {i}} α_{i, j}^{(k)} W^{(k)} x_{j})$
PyG 特点：
- 支持 Multi-head Attention（多头注意力），增加模型稳定性。
- GATv2Conv (PyG 特色补丁)：修复了标准 GAT 的“静态注意力”问题，使其更具表达力。
适用场景：邻居重要性差异大的图（如社交网络中的关键意见领袖）。

python

class GATConv(MessagePassing):
    def __init__(self, in_channels, out_channels, heads=1):
        super().__init__(aggr='add')
        self.heads = heads
        self.lin = Linear(in_channels, heads * out_channels)
        # 注意力向量 (可学习参数)
        self.att = Parameter(torch.Tensor(1, heads, 2 * out_channels))

    def forward(self, x, edge_index):
        x = self.lin(x).view(-1, self.heads, -1)
        return self.propagate(edge_index, x=x)

    def message(self, x_i, x_j, index, ptr, size_i):
        # 1. 将 x_i 和 x_j 拼接计算注意力分数
        x = torch.cat([x_i, x_j], dim=-1)
        alpha = (x * self.att).sum(dim=-1)
        alpha = F.leaky_relu(alpha, 0.2)
        # 2. 对属于同一个中心节点 i 的所有邻居进行 Softmax 归一化
        alpha = softmax(alpha, index, ptr, size_i)
        return x_j * alpha.view(-1, self.heads, 1)

多头特征的“折叠与拆解”

在进入注意力计算前，GAT 必须将平铺的特征矩阵重塑为多头结构。

代码：x = self.lin(x).view(-1, self.heads, -1)
逻辑：
1. self.lin(x)：将维度从 [N, in] 变为 [N, heads * out]。
2. .view(-1, heads, out)：将混合特征拆分为 [节点数, 头数, 每个头的特征数]。
本质：这是一种“空间拆解”，让每个注意力头在独立的特征子空间内并行工作。

注意力参数 self.att

定义：Parameter(torch.Tensor(1, heads, 2 * out_channels))
维度意义：
- 1：广播占位符，确保一组参数能作用于所有边 $E$ 。
- heads：为每个头准备独立的评分标准。
- 2 * out_channels：因为注意力是由中心点特征和邻居特征拼接（Concat）而成的，长度翻倍。

注意力分数计算

在 message 函数中，通过以下三步产出注意力权重 $α$ ：

特征合体：x = torch.cat([x_i, x_j], dim=-1)
- 维度变为 [E, heads, 2 * out_channels]。dim=-1 确保在最内层特征位进行横向拼接。
点积打分：alpha = (x * self.att).sum(dim=-1)
- 逐元素相乘 (*)：利用广播机制给特征加权。
- 求和 (sum)：将特征维压缩，得到原始分数 $e_{i, j}$ ，维度为 [E, heads]。
激活修剪：alpha = F.leaky_relu(alpha, 0.2)
- 维度不变，仅改变数值分布，为后续 Softmax 增大区分度。

局部归一化：softmax

代码：alpha = softmax(alpha, index, ptr, size_i)
核心难点：
- index (或 ptr)：充当“隔离墙”。它确保 Softmax 只在指向同一个中心节点的邻居之间进行。
- ptr 的本质：它是排序后的边索引指针，像“切割刀”一样瞬间定位内存块，实现极速并行归一化。
结果：alpha 变为在每个节点邻居范围内和为 1 的概率权重。

维度对齐的“终章”

最后一步加权：x_j * alpha.view(-1, self.heads, 1)

为什么加 1？
- x_j 维度是 [E, heads, out_channels]。
- alpha.view 变成 [E, heads, 1]。
- 触发广播机制，让同一个权重标量作用于邻居特征向量的每一个维度。

GINConv (Graph Isomorphism Network)

核心思想：理论上表达能力最强的 GNN（等价于 WL-Test）。

数学本质：

x_{i}^{'} = MLP ((1 + ϵ) \cdot x_{i} + \sum_{j \in N (i)} x_{j})

PyG 特点：
- 它要求传入一个完整的 nn.Sequential（MLP）作为参数。
- 通常不进行归一化，直接求和，以保留图的同构信息。
适用场景：图分类任务的必选 Baseline，辨别不同图结构的能力极强。

python

class GINConv(MessagePassing):
    def __init__(self, nn): # nn 是一个外部传入的 Sequential (MLP)
        super().__init__(aggr='add')
        self.nn = nn
        self.eps = Parameter(torch.Tensor([0])) # 可学习的权重因子

    def forward(self, x, edge_index):
        out = self.propagate(edge_index, x=x)
        # 核心：(1+eps)*自身 + 邻居聚合
        out = self.nn((1 + self.eps) * x + out)
        return out

    def message(self, x_j):
        return x_j

核心数学哲学：判别力最大化

GIN 的设计目标是让 GNN 的表达能力达到 WL 图同构测试 的理论上限。

公式： $x_{i}^{'} = MLP ((1 + ϵ) \cdot x_{i} + \sum_{j \in N (i)} x_{j})$
单射聚合 (Injective Aggregation)：GIN 坚持使用 Sum (求和) 而非 Mean 或 Max。
- 原因：Mean 只能分辨特征的比例，Max 只能分辨特征的存在，而只有 Sum 能分辨出“结构的数量差异”（例如区分 1 个邻居和 3 个相同特征的邻居）。

核心参数 $ϵ$ 详解

维度：通常为 标量 (1,) (Scalar)。
物理意义：它是“自我”与“集体”的平衡杠杆。
- 通过 $(1 + ϵ)$ ，模型可以确保节点自身的特征不被庞大的邻居信息淹没。
- 由于 $ϵ$ 是可学习的（nn.Parameter），模型会根据层数和任务自动调整“保持个性”还是“融入邻居”。
计算逻辑：利用 广播机制 (Broadcasting) 自动适配节点特征的维度（例如 64 维或 128 维）。

GATv2Conv

GATv2Conv相比于经典的 GAT，GATv2 解决了原版的一个核心缺陷：静态注意力问题 (Static Attention)。

在原版 GAT 中，所有邻居的注意力顺序对于任何中心节点都是固定的。GATv2 通过改变运算顺序，实现了真正的动态注意力。

数学本质：从“静态”到“动态”
- GAT： $e_{i, j} = {\vec{a}}^{T} LeakyReLU (W [x_{i} ‖ x_{j}])$
  - 问题：线性变换 $W$ 和拼接在激活函数内部。由于 $W$ 是全局共享的，导致注意力排名不随中心节点 $i$ 的变化而变化。
- GATv2： $e_{i, j} = {\vec{a}}^{T} LeakyReLU (W_{i} x_{i} + W_{j} x_{j})$
  - 改进：先进行各自的线性变换，再应用激活函数，最后才与向量 $\vec{a}$ 做内积。这使得模型能为每个节点对学习到完全独立的得分。
参数维度：两个线性层的分工在代码实现中，GATv2 通常定义两个独立的线性层（或一个大层拆分）：
- self.lin_l (Left)：对应目标节点 $i$ 的变换。
- self.lin_r (Right)：对应源节点 $j$ 的变换。
- self.att: 维度变为 [1, heads, out_channels]。
注意：这里不再是 2 * out_channels，因为激活函数后不再是拼接，而是元素级加法。

python

class GATv2Conv(MessagePassing):
    def __init__(self, in_channels: int, out_channels: int, heads: int = 1,
                 concat: bool = True, negative_slope: float = 0.2,
                 dropout: float = 0.0, bias: bool = True, **kwargs):
        # 初始化基类，聚合方式为 'add'
        super().__init__(aggr='add', node_dim=0, **kwargs)

        self.in_channels = in_channels
        self.out_channels = out_channels
        self.heads = heads
        self.concat = concat
        self.negative_slope = negative_slope
        self.dropout = dropout

        # GATv2 核心：左右两个独立的线性变换
        self.lin_l = Linear(in_channels, heads * out_channels, bias=bias)
        self.lin_r = Linear(in_channels, heads * out_channels, bias=bias)

        # 注意力向量 a，对应拼接后的维度，所以是 out_channels
        self.att = Parameter(torch.Tensor(1, heads, out_channels))

        if bias and concat:
            self.bias = Parameter(torch.Tensor(heads * out_channels))
        elif bias and not concat:
            self.bias = Parameter(torch.Tensor(out_channels))
        else:
            self.register_parameter('bias', None)

        self.reset_parameters()

    def reset_parameters(self):
        glorot(self.lin_l.weight)
        glorot(self.lin_r.weight)
        glorot(self.att)
        zeros(self.bias)

    def forward(self, x: Tensor, edge_index: Tensor):
        # 1. 线性变换并重塑维度 [N, heads, out_channels]
        x_l = self.lin_l(x).view(-1, self.heads, self.out_channels)
        x_r = self.lin_r(x).view(-1, self.heads, self.out_channels)

        # 2. 传播：传入左右两组特征
        # x=(x_l, x_r) 会自动注入 message 函数中的 x_i 和 x_j
        out = self.propagate(edge_index, x=(x_l, x_r))

        # 3. 后处理：多头拼接或取平均
        if self.concat:
            out = out.view(-1, self.heads * self.out_channels)
        else:
            out = out.mean(dim=1)

        if self.bias is not None:
            out = out + self.bias

        return out

    def message(self, x_i: Tensor, x_j: Tensor, index: Tensor, 
                ptr: Tensor, size_i: int) -> Tensor:
        # GATv2 的灵魂公式：e = a^T * leaky_relu(W_l*x_i + W_r*x_j)
        # 这里用加法代替拼接后的线性变换，数学本质一致且更高效
        x = x_i + x_j  
        x = F.leaky_relu(x, self.negative_slope)
        
        # 注意力得分计算 [E, heads]
        alpha = (x * self.att).sum(dim=-1)
        alpha = softmax(alpha, index, ptr, size_i)
        alpha = F.dropout(alpha, p=self.dropout, training=self.training)

        # 最终带权重的邻居消息
        return x_j * alpha.view(-1, self.heads, 1)

GAT (v1) 的缺陷：注意力权重 $α_{i, j}$ 的计算公式为 ${\vec{a}}^{T} LeakyReLU (W [x_{i} ‖ x_{j}])$ 。由于线性变换 $W$ 在激活函数内部，导致对于任意中心节点 $i$ ，其所有邻居 $j$ 的得分排名顺序是固定的（静态的）。
GATv2 的改进：公式演变为 ${\vec{a}}^{T} LeakyReLU (W_{l} x_{i} + W_{r} x_{j})$ 。
- 动态性：通过先进行各自的线性投影 ( $W_{l}, W_{r}$ )，再进行非线性激活，最后与向量 $\vec{a}$ 做内积。这使得模型能为每一个节点对学习到完全独立的、动态的评分逻辑。
关键超参数：negative_slope 的数学推导
作用：LeakyReLU 激活函数的负半轴斜率（通常设为 0.2）。
数学意义：
1. 打破线性：若无此项，注意力计算退化为简单的线性缩放。
2. 保留“讨厌”的能力：对比 ReLU（直接切断负值为 0，导致 $\exp (0) = 1$ ），LeakyReLU 允许负得分通过。
3. 计算推导：当原始得分 $e_{i, j}$ 为负时，通过 $0.2 \cdot e_{i, j}$ 依然能保持较小的 $\exp$ 值。这确保了在 Softmax 归一化后，不相关的邻居能获得趋近于 0 的权重，而不是被强行赋予一个基准权重。
A. 左右权重分工 (lin_l & lin_r)
- 在 forward 中，特征被分为 x_l (目标节点/中心点) 和 x_r (源节点/邻居)。
- 在 message 中，通过 x_i + x_j 实现交互。这在数学上等价于对拼接后的特征进行变换，但在实现上更高效。
B. 偏置项 (self.bias) 的自适应
- 偏置的形状必须根据多头注意力的合并方式（concat 参数）动态调整：
- Concat = True：输出维度是 heads * out_channels，偏置对应加长，每个头拥有独立的偏置。
- Concat = False (Mean)：输出维度缩减回 out_channels，所有头共用一套偏置。
C. 权重初始化 (reset_parameters)
- 必要性：torch.Tensor 分配的是随机内存垃圾。
- Glorot (Xavier) 初始化：专门用于 self.att 和线性层权重，确保初始状态下各层方差一致，防止注意力机制在第一轮迭代时因 Softmax 饱和而“死掉”（即权重全部分配给某一个邻居）。

MessagePassing 执行流程图

函数/操作	核心逻辑	维度变化
`forward`	拆分多头特征 $x_{l}$ , $x_{r}$	$[N, F] \to [N, H, O]$
`propagate`	启动消息传递，注入参数	-
`message`	$LeakyReLU (x_{i} + x_{j}) * att$	$[E, H, O] \to [E, H]$
`softmax`	根据 index/ptr 局部竞争	$[E, H]$ (Sum=1)
`aggregate`	$Sum$ 所有带权重的邻居消息	$[E, H, O] \to [N, H, O]$
`forward` 尾部	$Concat$ 或 $Mean + Bias$	$[N, H, O]$ 或 $[N, H * O]$ 或 $[N, O]$

Algorithm

Tutorial

assignment

Assignment

As-1

As-2

Lab-1

Lab-2

Lab-3

Lab-4

GAMES101

Assignment-1

Assignment-2

Assignment-3

Assignment-4

Lab

Lecture

Peoject

CSCN

Ploidy

PyG-Common GCN Layer

Common GCN Layer ​

GCNConv (Graph Convolutional Network) ​

SAGEConv (GraphSAGE) ​

GATConv (Graph Attention Network) ​

GINConv (Graph Isomorphism Network) ​

GATv2Conv ​

Common GCN Layer

GCNConv (Graph Convolutional Network)

SAGEConv (GraphSAGE)

GATConv (Graph Attention Network)

GINConv (Graph Isomorphism Network)

GATv2Conv