图卷积网络深读：三层公式读懂 Kipf & Welling 2017
1 它解决了什么问题
设想一个经典场景：引文网络里每个节点是一篇论文，边是引用关系；我们只有极少量节点带标签（比如七个类别各 20 篇），却要给全图所有节点分类。这叫图上的半监督学习（transductive 设定：测试节点在训练时就能看到，至少看到它们的连接方式）。
朴素做法有两种，各有致命伤：只看节点自身特征（词袋向量）训一个分类器——丢掉了"同被引用的论文大概率同类"这张关系网；把整张图手工塞进特征——图结构又高维又非欧。深度学习时代之前的主流（标签传播、Planetoid 一类）则难以同时吃下"特征"与"结构"。GCN 的答案：让神经网络每一层都沿着图的边聚合信息，特征与结构在同一个前向传播里融合。
谱图卷积的数学血统来自 Hammond 等（2011）的图小波与 Defferrard 等（2016）的 ChebNet（NeurIPS 2016，切比雪夫多项式过滤器）。Kipf & Welling 的贡献不是发明图卷积，而是把它砍到一阶、再砍掉一个归一化矩阵——牺牲一点谱理论的严谨，换来一行可写进黑板的传播规则。这个"砍"的动作本身成了后来者的公共起点。
2 记号与设定
无向图 \(G=(V, E)\)，\(N=|V|\) 个节点。邻接矩阵 \(A\in\{0,1\}^{N\times N}\)（无自环），度矩阵 \(D\) 为对角阵，\(D_{ii}=\sum_j A_{ij}\)。每个节点有特征向量，按行堆叠成 \(X\in\mathbb{R}^{N\times D}\)；标签只存在于一个小集合 \(\mathcal{Y}_L\subset V\)。目标：学会 \(f(X,A)\) 输出所有节点的类别。
3 第一层公式：谱图卷积的切比雪夫近似
图上没有平移，卷积怎么定义？谱方法绕道频域：图的"傅里叶变换"由拉普拉斯矩阵 \(L = D - A\)（归一化形式 \(L = I - D^{-1/2}AD^{-1/2}\)）的特征分解 \(L = U\Lambda U^{\top}\) 给出，特征向量充当基，特征值充当"频率"。于是信号 \(x\) 与过滤器 \(g_\theta\) 的图卷积定义为
问题立刻出现：算 \(U\) 是 \(O(N^3)\) 的买卖，且换一张图基就全变，学到的 \(\theta\) 无法迁移。ChebNet 的破局：把 \(g_\theta(\Lambda)\) 限制为拉普拉斯的 \(K\) 阶多项式，用切比雪夫多项式 \(T_k\) 展开，只需\(K+1\) 个系数：
① \(K\) 阶多项式过滤器意味着每个节点只从 \(K\) 跳邻域取信息——卷积从全局运算变成局部运算，\(U\) 被彻底绕开；② \(\tilde{L}\) 把特征值线性压缩到 \([-1,1]\)，这是切比雪夫多项式正交性的定义域；③ 计算上 \(T_k(\tilde{L})x\) 可用三项递推 \(T_k = 2\tilde{L}T_{k-1} - T_{k-2}\) 逐层做矩阵—向量乘，代价 \(O(|E|)\)，与边数线性。
4 第二层公式：一阶近似与重归一化
GCN 的关键一跳：令 \(K=1\)。切比雪夫展开只剩 \(T_0=1\) 与 \(T_1=\tilde{L}\) 两项；再令 \(\lambda_{\max}\approx 2\)（经验近似），两项系数取 \(\theta'_0=-\theta'_1\)，整理即得线性过滤器
每层只看直接邻居。但 \(I + D^{-1/2}AD^{-1/2}\) 的特征值范围是 \([0,2]\)，反复相乘会引发数值爆炸与梯度不稳。Kipf & Welling 的手术：重归一化技巧（renormalization trick）——给每个节点加自环后重新对称归一化，\(\tilde{A}=A+I_N\)，\(\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}\)，得到全文最重要的一行：
\(W^{(l)}\)：特征变换。每层先做一次普通线性映射，与 MLP 完全同构——GCN 并没有发明新的"层"，只是换了信息的输送管道。
\(\tilde{A} = A + I\)：加自环。聚合邻居时把自己也算进去。没有自环，一层的输出将完全不含自身原始特征，层间堆叠会迅速"忘我"。
\(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\)：对称归一化。左右各乘度数的平方根倒数，\((\hat{A})_{ij} = \tilde{A}_{ij}/\sqrt{\tilde{d}_i \tilde{d}_j}\)。行和近似为 1（但矩阵不严格行随机，保留了对称性——谱性质更好）。直观效果：高度数节点的巨大影响力被自动摊薄，每个节点输出的是邻居特征的加权平均而非求和。对比消息传递文献里 \(D^{-1}A\) 的"行归一化平均"，两者常可互换，GCN 选对称版的理由在数值稳定与谱解释。
\(\sigma\)：非线性。论文用 ReLU。没有它，多层线性过滤器叠起来仍是一层。
5 第三层公式：两层网络与训练目标
论文的完整模型就是两层，简洁到可以整体写出（记 \(\hat{A} = \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\)，输入用 \(H^{(0)}=X\)）：
训练目标只对带标签节点算交叉熵 \( \mathcal{L} = -\sum_{v\in\mathcal{Y}_L}\sum_c Y_{vc}\ln Z_{vc} \)，梯度却经由共享的 \(W\) 流过整张图——未标注节点的特征同样参与了前向，这就是 transductive 半监督的全部含义。复杂度 \(O(|\mathcal{E}| F F')\)：边数线性，可稀疏实现，官方给出的参考代码不足十行。
两跳感受野已经覆盖了引文网络里最相关的邻域；继续加深，感受野指数扩张，所有节点 embedding 趋同——论文自己报告 3 层以上开始掉分。这一现象后来被 Li 等（2018）以过度平滑（over-smoothing）正式命名：GCN 是对相邻节点做了低通滤波，层数越多滤波越狠。深层 GNN 的各种补救（残差、DropEdge、解耦传播）都是围绕这个病根展开的。
6 实验：记住这四个数字
| 数据集 | 节点 / 边 | 类别 | 每类标注 | GCN 准确率 | 此前最佳 |
|---|---|---|---|---|---|
| Cora | 2 708 / 5 429 | 7 | 20 | 81.5% | 75.7%（Planetoid） |
| Citeseer | 3 327 / 4 732 | 6 | 20 | 70.3% | 64.7% |
| Pubmed | 19 717 / 44 338 | 3 | 20 | 79.2% | 77.2% |
两个值得咀嚼的细节：① 对比实验里，用随机权重（不训练）的 GCN 提取 embedding 再接简单分类器，也已接近有监督基线——说明图结构先验本身携带了大量信息，学习主要发生在"怎么组合邻域"；② 边的随机删除实验显示性能对稀疏化相当鲁棒，直到删到只剩约一半才明显衰减。
7 局限：它没有解决什么
归纳能力缺失。GCN 是 transductive 的：训练时需要整张图（含测试节点），新节点进图意味着重新前向整图。GraphSAGE（Hamilton 等，2017）把聚合函数参数化，第一次做到对未见节点归纳推理。
注意力缺位。对称归一化对邻居一视同仁（只看度数）。GAT（Veličković 等，2018）用注意力机制学习每条边的权重，是公式 (4) 的自然升级。
规模天花板。全图单 batch 训练把显存绑死在 \(O(N)\)；GraphSAINT、Cluster-GCN 等子图采样方法为此而生。
谱解释的代价。一阶近似加重归一化后，模型严格说已不再对应精确的谱卷积——它更像"归一化邻接矩阵上的多层感知机"。这个务实的选择正是它流行的原因，也是谱纯度派批评的靶子。
8 与本站的衔接
本站《分子机器学习导论》第 3 章把 GCN 讲作消息传递框架（message passing）的一个实例：消息 = 邻居特征经 \(W\) 变换，聚合 = 度归一化平均，更新 = ReLU——分子图上原子聚合邻居、键携带约束的整套 GNN 流水线，正始于本文这行公式。若想继续深挖，建议按此顺序读：Defferrard 等 2016（ChebNet）补谱血统 → Veličković 等 2018（GAT）看注意力版本 → Gilmer 等 2017（MPNN）看统一框架，最后回到分子书第 3 章做习题。
- Kipf TN, Welling M. 2017. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR 2017). arXiv:1609.02907.
- Defferrard M, Bresson X, Vandergheynst P. 2016. Convolutional neural networks on graphs with fast localized spectral filtering. Advances in Neural Information Processing Systems 29: 3844–3852.
- Hammond DK, Vandergheynst P, Gribonval R. 2011. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis 30(2): 129–150.
- Li Q, Han Z, Wu XM. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of AAAI 2018: 3538–3545.
- Veličković P, Cucurull G, Casanova A, Romero A, Liò P, Bengio Y. 2018. Graph attention networks. International Conference on Learning Representations (ICLR 2018). arXiv:1710.10903.
- Hamilton W, Ying Z, Leskovec J. 2017. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems 30: 1024–1034.
- Gilmer J, Schoenholz SS, Riley PF, Veen O vd, Dahl GE. 2017. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning: 1263–1272.