图卷积神经网络（GCN）：参考答案#
说明#
以下答案与正文题目逐题对应。前六题给出主要推导与计算；第 7--9 题给出可以运行的程序和检查方法；第 10--12 题说明比较时需要保持哪些条件相同，以及实验结果能够说明什么、不能说明什么。
加入自环后
\[\begin{split}\tilde{\bA} =\begin{bmatrix}1&1\\1&1\end{bmatrix}, \qquad \tilde{\bD} =\begin{bmatrix}2&0\\0&2\end{bmatrix}, \qquad \boldsymbol{S} =\frac12\begin{bmatrix}1&1\\1&1\end{bmatrix}.\end{split}\]因而
\[\begin{split}\boldsymbol{H}^{[1]} =\boldsymbol{S}\cdot\bX W =\begin{bmatrix}3\\3\end{bmatrix}3 =\begin{bmatrix}9\\9\end{bmatrix},\end{split}\]这里 \(W\) 是标量，所以与向量相乘直接并置；若权重是矩阵，则写为矩阵乘法。
加自环后的度数是 \((2,3,2)\)。传播矩阵为
\[\begin{split}\boldsymbol{S} =\begin{bmatrix} \frac12&\frac1{\sqrt6}&0\\ \frac1{\sqrt6}&\frac13&\frac1{\sqrt6}\\ 0&\frac1{\sqrt6}&\frac12 \end{bmatrix}.\end{split}\]第一、三行和为 \(1/2+1/\sqrt6\approx0.9082\)，第二行和为 \(1/3+2/\sqrt6\approx1.1498\)。矩阵对称但行和不为 1；只有在特殊的度结构下，对称归一化才可能同时表现为行随机矩阵。
无向图有 \(\tilde{\bA}\trans=\tilde{\bA}\)，对角矩阵 \(\tilde{\bD}^{-1/2}\) 也等于自身转置，因此
\[\boldsymbol{S}\trans =\tilde{\bD}^{-1/2}\cdot \tilde{\bA}\trans\cdot \tilde{\bD}^{-1/2} =\boldsymbol{S}.\]对置换矩阵 \(\boldsymbol{P}\)，有 \(\tilde{\bA}'=\boldsymbol{P}\cdot\tilde{\bA}\cdot\boldsymbol{P}\trans\)、\(\tilde{\bD}'=\boldsymbol{P}\cdot\tilde{\bD}\cdot\boldsymbol{P}\trans\)，进而 \(\boldsymbol{S}'=\boldsymbol{P}\cdot\boldsymbol{S}\cdot\boldsymbol{P}\trans\)。于是
\[\sigma(\boldsymbol{S}'\cdot\boldsymbol{P}\cdot\boldsymbol{H}\cdot\bW) =\boldsymbol{P}\cdot\sigma(\boldsymbol{S}\cdot\boldsymbol{H}\cdot\bW),\]其中逐元素激活函数与行置换可交换。
矩阵乘法结合律直接给出两式相等。先变换特征的主要成本约为
\[nd_{\mathrm{in}}d_{\mathrm{out}}+md_{\mathrm{out}} =81.92\times10^6+3.2\times10^6 =85.12\times10^6.\]先传播输入特征的成本约为
\[md_{\mathrm{in}}+nd_{\mathrm{in}}d_{\mathrm{out}} =25.6\times10^6+81.92\times10^6 =107.52\times10^6.\]因为 \(d_{\mathrm{out}}<d_{\mathrm{in}}\)，本例先计算 \(\boldsymbol{H}\cdot\bW\) 更省。实际速度还受稀疏内核、缓存和后向传播影响，运算数不是墙钟时间的完整预测。
由 \(\boldsymbol{L}_{\mathrm{un}}=\bD-\bA\) 和对角矩阵 \(\bD\) 的定义，先展开二次型：
\[\begin{split}\begin{aligned} \boldsymbol{x}\trans\cdot \boldsymbol{L}_{\mathrm{un}}\cdot\boldsymbol{x} &=\boldsymbol{x}\trans\cdot (\bD-\bA)\cdot\boldsymbol{x}\\ &=\sum_{i=1}^{n}d_i x_i^2 -\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_i x_j\\ &=\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_i^2 -\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_i x_j, \end{aligned}\end{split}\]其中，最后一步使用了 \(d_i=\sum_{j=1}^{n}A_{ij}\)。无向图的邻接矩阵满足 \(A_{ij}=A_{ji}\)。交换两重求和中的下标 \(i,j\)，可得
\[\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_i^2 =\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_j^2.\]因此，可以用两个相等和式的平均替换第一个和式。将结果代回二次型的展开式，有
\[\begin{split}\begin{aligned} \boldsymbol{x}\trans\cdot \boldsymbol{L}_{\mathrm{un}}\cdot\boldsymbol{x} &=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij}(x_i^2+x_j^2) -\sum_{i=1}^{n}\sum_{j=1}^{n}A_{ij}x_i x_j\\ &=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij}(x_i^2-2x_i x_j+x_j^2)\\ &=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij}(x_i-x_j)^2. \end{aligned}\end{split}\]两重求和中，无向边 \(\{i,j\}\) 会分别以 \((i,j)\) 和 \((j,i)\) 出现一次，所以系数 \(1/2\) 用于消除这种重复计数。
因为每个 \(d_i>0\)，所以 \(\bD^{-1/2}\) 存在。令
\[\boldsymbol{y} =\bD^{-1/2}\cdot\boldsymbol{x}, \qquad y_i=\frac{x_i}{\sqrt{d_i}}.\]由 \(\boldsymbol{x}=\bD^{1/2}\cdot\boldsymbol{y}\) 以及对角矩阵的转置仍等于自身，有
\[\begin{split}\begin{aligned} \boldsymbol{x}\trans\cdot \boldsymbol{L}\cdot\boldsymbol{x} &=\boldsymbol{x}\trans\cdot \left( \bI-\bD^{-1/2}\cdot\bA\cdot\bD^{-1/2} \right)\cdot\boldsymbol{x}\\ &=\boldsymbol{y}\trans\cdot\bD\cdot\boldsymbol{y} -\boldsymbol{y}\trans\cdot\bA\cdot\boldsymbol{y}\\ &=\boldsymbol{y}\trans\cdot (\bD-\bA)\cdot\boldsymbol{y}\\ &=\boldsymbol{y}\trans\cdot \boldsymbol{L}_{\mathrm{un}}\cdot\boldsymbol{y}. \end{aligned}\end{split}\]再应用上一题的未归一化图拉普拉斯二次型恒等式，并代入 \(y_i=x_i/\sqrt{d_i}\)，可得
\[\begin{split}\begin{aligned} \boldsymbol{x}\trans\cdot \boldsymbol{L}\cdot\boldsymbol{x} &=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij}(y_i-y_j)^2\\ &=\frac{1}{2} \sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij} \left( \frac{x_i}{\sqrt{d_i}}- \frac{x_j}{\sqrt{d_j}} \right)^2. \end{aligned}\end{split}\]假设 \(d_i>0\) 的直接原因是，当 \(d_i=0\) 时 \(1/\sqrt{d_i}\) 没有定义。若存在零度节点，需要先明确对孤立节点的处理规则；GCN 的重归一化会先加入自环，使新度数为正。
可先用线性层得到 \(\boldsymbol{Z}=\boldsymbol{H}\cdot\bW\)，再沿边传播：
import torch def sparse_gcn(edge_index, x, weight, num_nodes=None, activation=None): n = x.shape[0] if num_nodes is None else int(num_nodes) if edge_index.ndim != 2 or edge_index.shape[0] != 2 or n != x.shape[0]: raise ValueError("边或节点维度错误") send, receive = edge_index.long() if torch.any((send < 0) | (send >= n) | (receive < 0) | (receive >= n)): raise IndexError("边端点越界") # 先移除已有自环，再统一加入一个自环，避免重复。 keep = send != receive nodes = torch.arange(n, device=x.device) send = torch.cat([send[keep], nodes]) receive = torch.cat([receive[keep], nodes]) degree = x.new_zeros(n) degree.index_add_(0, receive, x.new_ones(len(receive))) if torch.any(degree <= 0): raise ValueError("加入自环后度必须为正") norm = degree[receive].rsqrt() * degree[send].rsqrt() z = x @ weight out = x.new_zeros(n, z.shape[1]) out.index_add_(0, receive, norm[:, None] * z[send]) return (out if activation is None else activation(out)), norm
若输入是带权图，度和归一化都应使用明确的边权规则；负权图不能直接套用普通正度公式。
第 1、2 题先按照 手算结果与可信实现对照 的原则逐元素对照 \(\boldsymbol{S}\) 和输出，再将相同参数复制到第 7 题的稀疏实现和库层。库可能默认自行加自环、合并重复边或采用不同方向，必须先关闭或对齐这些选项。用
float64比较前向及输入、权重梯度，例如rtol=1e-7, atol=1e-9。置换测试验证等变性；单节点和孤立节点验证自环；重复边测试明确是累加还是合并。自动微分结果 一致只说明两份程序实现同一运算，不证明数据划分没有泄漏。两层分类器只在
train_mask上计算交叉熵；验证和测试函数使用eval模式且不更新参数。测试train_mask & valid_mask等均为空，每个掩码至少含一个节点。固定参数后分别改变验证、测试标签，重新计算一次训练梯度，结果必须完全相同。置换测试同时置换邻接、特征、标签和三个掩码，各集合预测指标应保持不变。若图划分还涉及测试边，应另行检查训练传播图是否允许看到这些边。一次性确定数据划分和预处理方法，三个模型使用相同的特征、随机种子、近似参数量和最大更新次数，并使用同一个验证集和相同标准选择模型。模型结构、超参数和训练方法确定后，测试集只使用一次。报告准确率、macro-F1、训练时间、固定节点批量预测时间、峰值内存、参数量和图传播运行次数。
逻辑回归与 MLP 检验不使用图结构时的可达到水平；GCN 只有在边提供有效信号时才应取得稳定增益。传导节点分类中一次全图前向与独立批量预测语义不同，计时必须说明预测范围和可见结构。
两种实现使用完全相同的自环、重复边、特征、权重、数据类型和设备；固定种子、预热、前向次数和重复计时方法。先报告最大输出误差，再记录固定图批量时间、峰值内存、实际边数和传播调用次数。稠密内存为 \(O(n^2)\)，稀疏结构内存约为 \(O(m)\)；但在小而密图上稠密矩阵内核可能更快。无法分配稠密矩阵的规模应记录为资源限制，而不是虚构时间。
固定划分、种子集合、最大更新次数、早停规则和评价代码；所有深度、宽度和学习率组合使用相同网格与验证选模流程。报告测试指标、训练时间、固定批量预测时间、峰值内存、参数量、传播调用次数、节点表示方差和平均余弦相似度。
深度和宽度会改变模型容量与计算量，学习率会改变训练过程。应列出各个深度、宽度和学习率组合的结果，或者分几次比较、每次只改变其中一项，不能同时改变三项后把结果解释为某一项的作用。如果更深的模型出现节点表示方差降低、相似度升高且性能下降，说明可能出现了过度平滑，但梯度、正则化和过度挤压也可能造成相似现象，因此还不能排除其他原因。