GCN 谱域

GCN(Graph Convolutional Network, Kipf & Welling 2017)的层传播公式为 $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$, 其中 $\tilde{A} = A + I$ 加自环, $\tilde{D}$ 为其度矩阵, $W^{(l)}$ 为可学习权重, $\sigma$ 为激活函数——本质是“度归一化的邻居特征加权平均 + 线性变换”。谱域动机: 图卷积 $x * g_\theta = U g_\theta(\Lambda) U^T x$ 需要 $O(n^2)$ 的特征分解, 用切比雪夫多项式 $T_k$ 近似 $g_\theta(\Lambda) \approx \sum_{k=0}^{K} \theta_k T_k(\hat{\Lambda})$; 取一阶截断($K = 1$)并令两参数共享($\theta_0 = -\theta_1 = \theta$)、重归一化($\tilde{A} = A + I$)后即得上述公式——每个节点聚合一跳邻居, 叠加 $L$ 层感受野扩到 $L$ 跳。代价是过平滑(oversmoothing): 多层后节点表示收敛到图谱的主特征向量、趋于一致(高频信息被反复低通滤波抹平), 因此经典 GCN 一般只堆 2–3 层; 缓解手段包括残差连接、JK-Net(跳接取池化)、PairNorm、层间规范化。

半监督节点分类(Cora/Citeseer/PubMed 基准)、引文网络与社交网络的表示学习; 面试必考题: 默写传播公式、谱域一阶切比雪夫推导、归一化方式选择、过平滑机制。

朴素图卷积依赖 $U g_\theta(\Lambda) U^T$ 需特征分解(稠密 $U$ 矩阵, $O(n^2)$ 且不可迁移), 无法规模化。一阶切比雪夫截断把滤波器化简为 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 的单次稀疏矩阵乘法($O(|E|)$), 训练只需像普通 DNN 一样学 $W$; 对称归一化同时稳定数值并让模型可泛化到未见节点(归纳式扩展), 奠定了后续 GAT/GraphSAGE/GIN 的“消息传递”范式。

检验攻克程度：针对「GCN 谱域」专属刷题排雷

做单选排雷题、推导选项机制，答错自动收录进专属错题本。