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 传播公式 $H^{(l+1)} = \sigma(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}H^{(l)}W^{(l)})$, 并解释 $\tilde{A} = A + I$、$\tilde{D}^{-1/2}(\cdot)\tilde{D}^{-1/2}$、$W^{(l)}$ 各自的作用。

谱域推导: 完整图卷积为何不可行($O(n^2)$ 特征分解、稠密 $U$), 一阶切比雪夫近似 $g_\theta \approx \theta_0 I + \theta_1 \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 如何一步步化简到 GCN 公式?

为什么用对称归一化 $\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}$ 而不是随机游走归一化 $\tilde{D}^{-1}\tilde{A}$? 两者在数值稳定性与聚合语义(加权平均 vs 归一化求和)上的区别。

过平滑(oversmoothing)的机制: 为什么层数加深后节点表示趋同(反复低通滤波、谱主特征向量主导)? 有哪些缓解手段?

直推式(transductive)与归纳式(inductive)学习: 经典 GCN 为什么是直推式? 训练时未见的新节点/新图如何泛化?