图卷积神经网络#
学习目标与记号#
推导 GCN 的自环、度矩阵和对称归一化传播公式；
从逐节点与矩阵两个角度解释 GCN，并核对参数与中间张量维度；
实现一层 GCN，识别结构泄漏、零度节点、过度平滑和稀疏计算问题；
本节沿用统一记号：普通小写字母表示标量，粗体小写字母表示向量，粗体大写字母表示矩阵或高阶张量；层编号写作上标 \([l]\)，节点、样本或边编号写作下标；转置写作 \(\trans\)。除非另有说明，节点特征按行存放，邻接约定为 \(A_{ij}>0\) 表示节点 \(j\) 向节点 \(i\) 发送消息。正文与练习中的程序都应同时检查数值结果和数组维度。本节练习的参考答案见 图卷积神经网络（GCN）答案。
GCN 是 消息传递框架 中采用归一化邻居求和的特例；图和矩阵的方向约定见 图矩阵与特征记号。
图卷积神经网络（graph convolutional network，GCN） 1Kipf 与 Welling（2017），Semi-Supervised Classification with Graph Convolutional Networks。 用固定的度归一化规则聚合邻居，是图节点分类最常用的基线之一。下面采用 Kipf-Welling GCN 的常见写法，并把“图卷积”理解为由谱图卷积近似得到、又可直接解释为消息传递的传播层。
重归一化公式#
图 37 GCN 先加入自环，再用边两端的度数缩放邻接矩阵，最后传播线性变换后的节点特征#
根据 自环的定义，GCN 先为每个节点加入一条权重为 1 的自环，再根据新的邻接矩阵重新计算度：
定义对称归一化传播矩阵
第 \(l\) 层为
其中，\(\bH^{[l]}=[(\bh_1^{[l]})\trans;\ldots;(\bh_n^{[l]})\trans]\in\mathbb{R}^{n\times d^{[l]}}\)，\(\bW^{[l]}\in\mathbb{R}^{d^{[l]}\times d^{[l+1]}}\) 是共享参数。自环使每个节点保留自身特征；对称归一化将边 \(j\to i\) 的系数写为
因此高阶节点发送和接收的单条边贡献都会被缩小。对无向图，\(\bS\) 仍然对称；它一般不是行随机矩阵，所以每行元素和不必等于 1。
下面的动画以节点 \(v_3\) 信息的更新为例，从加入自环开始，依次展示度归一化、邻居特征传播和节点表示更新，帮助理解式中的矩阵运算如何对应到图上的局部信息传递。
为什么要构造对称归一化传播矩阵？
加入自环后的邻接矩阵 \(\tilde{\bA}\) 说明哪些节点之间可以传递信息，以及每条边具有多大的原始权重。如果直接计算 \(\tilde{\bA}\cdot\bH\)，度数较大的节点会汇总更多项，得到的数值通常也更大；连续堆叠多层后，这种由节点度数造成的尺度差异还可能不断累积。
度矩阵 \(\tilde{\bD}\) 记录每个节点的总连接权重，因此可以用来修正这种差异。在 \(\bS=\tilde{\bD}^{-1/2}\cdot\tilde{\bA}\cdot\tilde{\bD}^{-1/2}\) 中，边 \(j\to i\) 的权重除以 \(\sqrt{\tilde d_i\tilde d_j}\)，同时考虑发送节点和接收节点的度数。这样既保留了邻接矩阵给出的连接结构，又避免度数较大的节点仅仅因为邻居较多而产生过大的单边影响，使多层传播中的数值尺度更稳定。
这种归一化对边的两端采用相同形式，所以无向图的传播矩阵仍然对称，能够与后面的 归一化图拉普拉斯和谱视角 保持一致。需要注意，对称归一化并不是把每一行都变成和为 1；它的主要作用是根据边两端的度数调整传播强度。
逐节点解释#
矩阵式等价于
线性变换与结构传播在这一层中都是线性的，所以可以先计算 \(\bH^{[l]}\cdot\bW^{[l]}\) 再稀疏传播，也可以先传播再乘权重；结果在精确算术中相同，但临时张量宽度和计算成本可能不同。
谱视角的来由#
先把“谱”理解成图上的变化快慢。 在声音中，低频成分变化较慢，高频成分变化较快。图上的节点没有必然的左右次序，因此不能直接用“沿时间轴变化了多快”来定义频率。图信号处理改为观察 相连节点的取值是否相近：若大多数相连节点的取值接近，就称该信号在图上变化较慢；若相连节点的取值频繁发生较大变化，就称它变化较快。
什么是图信号？ 假设每个节点只有一个数值，把所有节点的取值组成 \(\bx=[x_1,\ldots,x_n]\trans\in\mathbb{R}^{n}\)，就得到一个图信号。例如，社交图中的 \(x_i\) 可以是用户 \(i\) 对某个问题的评分，传感器图中的 \(x_i\) 可以是传感器 \(i\) 测得的温度。如果每个节点有多个特征，则可以先把特征矩阵 \(\bX\) 的每一列看成一个图信号，再分别理解它们在图上的变化。
第一步：用图拉普拉斯矩阵衡量变化程度。 为了先看清核心思想，考虑边权非负的无向图，并定义未归一化的图拉普拉斯矩阵 \(\bL_{\mathrm{un}}=\bD-\bA\)。对任意图信号 \(\bx\)，有
该结果的证明放在本节 综合练习 中。等式右边把每条边两端的数值之差平方后加起来；相连节点的取值越接近，该量越小，表示信号越平滑；相连节点的取值相差越大，该量越大，表示信号在图上变化越快。因此，图拉普拉斯矩阵可以看成检查“相邻节点之间变化”的工具。
例 7.3 三节点路径上的慢变化与快变化
考虑路径 \(v_1-v_2-v_3\)，两条边的权重都为 1。对两个图信号
有
第一个信号在所有节点上取值相同，经过任意一条边都不发生变化。第二个信号每经过一条边都从 1 变为 \(-1\) 或从 \(-1\) 变为 1，因此它在这张图上变化得更快。这与一维信号中“缓慢变化对应低频，频繁变号对应高频”的直觉一致。
节点度数差异较大时，常改用本节所需的对称归一化图拉普拉斯矩阵
其中，假设所考虑的节点都有正的度数。它对应的变化程度为
该结果的证明同样放在本节 综合练习 中。与未归一化形式相比，这个式子在比较相连节点时还考虑了节点度数，从而减少“仅仅因为某个节点的邻居较多，数值就显得更大”的影响。
第二步：寻找一组“变化快慢不同”的基本图案。 对无向图，\(\bL\) 是实对称矩阵，可以分解为
其中，\(\bu_k\) 是第 \(k\) 个特征向量，\(\lambda_k\) 是对应的特征值，\(\bU=[\bu_1,\ldots,\bu_n]\)，\(\bLambda=\operatorname{diag}(\lambda_1,\ldots,\lambda_n)\)。这里不必先把“特征向量”理解得过于抽象：可以把每个 \(\bu_k\) 看成一种覆盖整张图的基本取值模式。
若 \(\bu_k\) 的模长为 1，即 \(\bu_k\trans\bu_k=1\)，则 \(\bu_k\trans\cdot\bL\cdot\bu_k=\lambda_k\)。因此，较小的 \(\lambda_k\) 对应在相连节点之间变化较慢的模式，可类比为低频模式；较大的 \(\lambda_k\) 对应变化较快的模式，可类比为高频模式。特征值集合 \(\{\lambda_1,\ldots,\lambda_n\}\) 称为图拉普拉斯矩阵的 谱，“谱视角”因此得名。
第三步：把图信号拆成这些基本模式。 由于特征向量构成一组标准正交基，任意图信号都可以在它们上展开：
基于这个结果，向量 \(\widehat{\bx}\) 的第 \(k\) 个分量说明基本模式 \(\bu_k\) 在原信号中占多大比重。这两个运算分别类似普通信号处理中的傅里叶变换和傅里叶逆变换，因此也称为 图傅里叶变换 及其逆变换。
第四步：分别调整慢变化和快变化成分。 谱滤波器为每个特征值 \(\lambda_k\) 指定一个系数 \(g_{\btheta}(\lambda_k)\)，并用该系数缩放相应的基本模式：
其中，\(\btheta\) 表示滤波器的参数，\(g_{\btheta}(\bLambda)=\operatorname{diag}(g_{\btheta}(\lambda_1),\ldots,g_{\btheta}(\lambda_n))\)。这个过程可以直观地理解为：先将原信号拆成变化快慢不同的成分，再分别放大或缩小这些成分，最后将它们重新组合成节点上的信号。若低频成分保留得较多、高频成分被削弱，就得到低通滤波，输出中相连节点的取值通常会更接近。
第五步：用多项式把全局计算改成局部传播。 上述谱滤波公式需要对整张图的拉普拉斯矩阵做特征分解，对大图来说计算和存储代价都很高，而且换一张图后特征向量也会改变。一种常用方法是用 \(K\) 阶多项式近似滤波器：
其中，\(K\) 是多项式的最高次数，\(\theta_r\) 是第 \(r\) 项的系数，它们决定不同传播次数的信息在输出中占多大比重。
这个式子只需要反复完成“拉普拉斯矩阵与节点特征相乘”，不需要显式计算 \(\bU\)。矩阵 \(\bL\) 只在自身节点和直接相连的节点之间可能有非零元素，因此乘一次最多引入一跳邻居的信息；乘 \(K\) 次最多引入 \(K\) 跳范围内的信息。这就是“低阶多项式可以把全局谱运算变成局部邻域运算”的具体含义。
第六步：从一阶局部滤波得到常见 GCN。 记 \(\bP=\bD^{-1/2}\cdot\bA\cdot\bD^{-1/2}\)，则 \(\bL=\bI-\bP\)。将一阶多项式中的同类项合并后，一个图信号的更新可以写成
其中，\(\alpha\) 和 \(\beta\) 是合并同类项后得到的两个标量系数。
第一项保留节点自身的信息，第二项汇总直接邻居的信息。Kipf-Welling GCN 进一步减少独立系数的数量，并通过“先加自环，再重新计算度数”把自身信息和邻居信息统一到传播矩阵。
对加入自环后的图，若记它的归一化图拉普拉斯矩阵为 \(\tilde{\bL}=\bI-\bS\)，则 \(\bS=\bI-\tilde{\bL}\) 本身就是 \(\tilde{\bL}\) 的一阶多项式。这说明，虽然 GCN 的实现不直接计算特征向量，它的传播运算仍然可以从谱滤波的角度理解。
在多特征情形下，再对各节点共享线性变换 \(\bW^{[l]}\) 并使用非线性函数 \(\sigma\)，便得到
这个谱视角告诉了我们什么？ 从节点聚合视角看，GCN 在将自身特征和邻居特征加权汇总；从谱视角看，这种局部汇总通常会减少相连节点之间的快速变化，使节点表示更平滑。两种说法描述的是同一个运算，只是观察角度不同。这也解释了为什么层数过多时，不同节点的表示可能越来越相似。
理解谱视角时需要注意什么？
实现常见 GCN 时，不需要在程序中计算拉普拉斯矩阵的特征向量；直接用稀疏传播矩阵 \(\bS\) 完成邻居信息汇总即可。谱分解在这里主要用于说明公式的来源与平滑倾向，而不是实现每一层时必须执行的步骤。
另外，常见 GCN 只是谱图卷积的一种简化形式，不是所有图卷积的唯一定义。“GCN 具有平滑倾向”也不表示每一层、每一个特征都必然变得更平滑：学习到的线性变换、非线性函数和图的具体结构都会影响最终结果。
训练、复杂度与深度问题#
在单图半监督节点分类中，网络对整张训练图前向传播，但损失只在训练节点掩码上计算：
验证集和测试集中的标签不能用于计算训练损失，也不能作为每次更新模型参数的依据。
设图中有 \(n\) 个节点和 \(m\) 条边，第 \(l\) 层的每个节点有 \(d^{[l]}\) 个特征，下一层的每个节点有 \(d^{[l+1]}\) 个特征。若先计算 \(\bZ=\bH\cdot\bW\)，就需要对 \(n\) 个节点分别进行一次特征变换，计算量约为 \(O(nd^{[l]}d^{[l+1]})\)；随后沿 \(m\) 条边汇总相邻节点的信息，计算量约为 \(O(md^{[l+1]})\)。
当网络层数很多时，节点反复汇总邻居的信息，不同节点的表示可能变得越来越相似，最终难以区分，这种现象称为 过度平滑。另一方面，一个节点能够接收到的远距离信息会随着层数增加而迅速增多，但所有信息都要压缩到一个维度固定的节点向量中，部分信息可能因此丢失，这种现象称为 过度挤压。两种现象都可能出现在较深的图神经网络中，但产生的原因不同。
NumPy 参考实现#
下面用两个 NumPy 函数完成一层 GCN 的前向计算。normalized_adjacency 根据邻接矩阵构造加入自环后的对称归一化传播矩阵 \(\bS\)；gcn_layer 再计算 \(\sigma(\bS\cdot\bH\cdot\bW)\)。若图有 \(n\) 个节点，features 的大小为 \(n\times d_{\mathrm{in}}\)，weight 的大小为 \(d_{\mathrm{in}}\times d_{\mathrm{out}}\)，则输出大小为 \(n\times d_{\mathrm{out}}\)。参数 activation 表示激活函数，默认不改变计算结果，也可以传入 ReLU 等函数。
import numpy as np
def normalized_adjacency(adjacency):
a = np.asarray(adjacency, dtype=float)
if a.ndim != 2 or a.shape[0] != a.shape[1]:
raise ValueError("adjacency 必须是方阵")
a_tilde = a + np.eye(a.shape[0])
degree = a_tilde.sum(axis=1)
if np.any(degree <= 0):
raise ValueError("加入自环后度必须为正")
inv_sqrt = degree ** -0.5
return inv_sqrt[:, None] * a_tilde * inv_sqrt[None, :]
def gcn_layer(adjacency, features, weight, activation=lambda x: x):
s = normalized_adjacency(adjacency)
features = np.asarray(features, dtype=float)
weight = np.asarray(weight, dtype=float)
if features.ndim != 2 or weight.ndim != 2:
raise ValueError("节点特征矩阵和权重矩阵必须是二维数组")
if features.shape[0] != s.shape[0] or features.shape[1] != weight.shape[0]:
raise ValueError("GCN 输入维度不匹配")
return activation(s @ features @ weight)
normalized_adjacency 首先给每个节点额外增加一条权重为 1 的自环，然后重新计算度数，并分别从行和列两个方向乘以度数的逆平方根，得到 \(\tilde{\bD}^{-1/2}\cdot\tilde{\bA}\cdot\tilde{\bD}^{-1/2}\)。因此，传入该函数的邻接矩阵通常不需要预先加入自环。在 gcn_layer 中，s @ features 在相邻节点之间传播并汇总信息，随后乘以 weight，把每个节点的特征从 \(d_{\mathrm{in}}\) 维转换为 \(d_{\mathrm{out}}\) 维，最后使用激活函数得到本层输出。整个过程中节点数保持不变。
这段代码只用于演示和检查一层 GCN 的前向计算，不包含偏置、参数训练或损失函数。它使用完整的邻接矩阵，因此更适合小图；处理大图时应采用稀疏矩阵或边索引实现。
Shiny 交互演示：GCN 对称归一化聚合
在交互页面中选择 GCN 后，可以核对加入自环后的度数、传播矩阵 \(\bS\)、逐邻居贡献和新的节点表示。页面也保留均值消息传递与 GAT，便于在图和节点特征完全相同的条件下比较三种聚合权重。
核心推导与实现核验#
核心关系
推导路径。 先给邻接矩阵加入单位阵以保留自身信息，再用新度矩阵对每条边按两端度数对称缩放，最后传播线性变换后的节点表示并施加非线性。
关键条件
归一化边权的逐项形式为 \(\tilde A_{ij}/\sqrt{\tilde d_i\tilde d_j}\)。无向图中 \(\tilde A_{ij}=\tilde A_{ji}\)，分母交换 \(i,j\) 不变，因此传播矩阵对称；但它的行和一般不等于 1。
数据规模
若图中有 \(n\) 个节点，第 \(l\) 层每个节点有 \(d^{[l]}\) 个特征，则节点表示 \(\bH^{[l]}\) 的大小为 \(n\times d^{[l]}\)。权重 \(\bW^{[l]}\) 的大小为 \(d^{[l]}\times d^{[l+1]}\)，图传播矩阵 \(\bS\) 为 \(n\times n\)，所以输出为 \(n\times d^{[l+1]}\)；训练掩码也应有 \(n\) 个标记。
常见误区
度必须从 \(\bA+\bI\) 重新计算；把对称归一化误写成只除接收节点度会得到不同模型；将验证/测试标签或测试边用于训练会造成泄漏。
动手检查
在小图上显式构造 \(\bS\)，检查无向图时 \(\bS\) 对称、对角元为 \(1/\tilde d_i\)；与逐节点加权和逐项比较，并用 自动微分框架 核对梯度。
数值稳定性与规模
加入自环后度应为正；度的逆平方根用浮点类型计算。大图使用稀疏 \(\bS\)，不显式构造稠密的 \(n\times n\) 矩阵；深层模型还应监控表示方差和梯度。
本节小结#
GCN 使用加自环后的对称度归一化邻接矩阵传播节点特征。
矩阵式与逐节点加权消息式完全等价，维度和边方向必须一致。
GCN 是图学习任务中常用的基础模型，也经常作为比较其他方法的参照。使用 GCN 时，应只沿图中实际存在的边进行计算，避免在构造图时使用预测阶段无法获得的信息，并注意层数过多可能使不同节点的表示越来越相似，因此不能简单地通过不断增加层数来获取更远处的信息。
综合练习#
程序题应固定随机种子、写出维度断言并报告运行环境。全部参考答案见 图卷积神经网络（GCN）答案。
两节点 GCN 计算。 对无向两节点单边图，令 \(\bA=\begin{bmatrix}0&1\\1&0\end{bmatrix}\)、标量节点特征 \(\bX=(2,4)\trans\)、标量权重 \(W=3\)，激活函数为恒等映射。计算 \(\tilde{\bA}\)、\(\tilde{\bD}\)、\(\bS\) 和一层输出。
三节点归一化计算。 对无向三节点链 \(1-2-3\)，加入自环后计算每个节点的新度数和 \(\bS\) 的全部非零元素。计算三行元素和，并用结果说明对称归一化矩阵一般不是行随机矩阵。
对称性与置换性质证明。 证明无向图的 \(\bS=\tilde{\bD}^{-1/2}\cdot\tilde{\bA}\cdot\tilde{\bD}^{-1/2}\) 对称；再证明同步置换邻接矩阵和节点特征时，一层 GCN 输出按同一置换变化。写清度矩阵在置换后的变化。
乘法次序与成本。 证明 \(\bS\cdot(\bH\cdot\bW)=(\bS\cdot\bH)\cdot\bW\)。若 \(n=10\,000\)、存储边数 \(m=100\,000\)、\(d_{\mathrm{in}}=256\)、\(d_{\mathrm{out}}=32\)，忽略常数并按一次稀疏传播约需 \(md\) 次标量乘法，估算两种次序的主要乘法数并判断哪一种更省。
图拉普拉斯二次型证明。 对边权非负的无向图，令 \(\bD=\operatorname{diag}(d_1,\ldots,d_n)\)、\(d_i=\sum_{j=1}^{n}A_{ij}\) 且 \(\bL_{\mathrm{un}}=\bD-\bA\)。证明
\[\bx\trans\cdot \bL_{\mathrm{un}}\cdot\bx =\frac{1}{2}\sum_{i=1}^{n}\sum_{j=1}^{n} A_{ij}(x_i-x_j)^2.\]推导中应明确说明度的定义和无向图的对称性 \(A_{ij}=A_{ji}\) 分别用在何处，并解释系数 \(1/2\) 为什么能消除无向边的重复计数。
归一化图拉普拉斯二次型证明。 对边权非负的无向图，假设所有节点的度数都为正，并令 \(\bL=\bI-\bD^{-1/2}\cdot\bA\cdot\bD^{-1/2}\)。证明对任意 \(\bx\in\mathbb{R}^{n}\)，有
\[\bx\trans\cdot\bL\cdot\bx =\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.\]可以令 \(\by=\bD^{-1/2}\cdot\bx\)，将本题转化为上一题的结论。说明为什么必须假设 \(d_i>0\)，并指出 \(y_i\) 与 \(x_i\) 的关系。
稀疏 GCN 实现。 基于
edge_index实现加自环、重新计算度和对称归一化的一层 GCN。程序不得构造稠密邻接矩阵，应支持批量节点特征和可选非线性，并返回归一化边权，检查重复自环、零度节点、端点范围和权重维度。手算、库函数与梯度核验。 按照 手算结果与可信实现对照 的原则，用第 1、2 题的小图逐项比较手算、稠密
NumPy、第 7 题稀疏实现和可信 GCN 库层。对齐自环和归一化约定后，比较前向输出以及对输入和权重的梯度；加入节点置换、单节点图、孤立节点和重复边测试，并给出误差容限。节点分类流程测试。 实现两层 GCN 节点分类器和训练、验证、测试掩码损失。测试三个掩码互斥，只有训练节点标签影响参数更新，改变验证或测试标签不会改变单次训练梯度；同步置换图、特征、标签和掩码后，各集合指标保持不变。
不使用图结构的模型与 GCN。 在同一节点分类数据上比较逻辑回归、MLP 与两层 GCN。各模型使用相同的训练集、验证集和测试集划分、随机种子、输入特征、近似参数量和训练更新次数，并使用同一个验证集和相同标准选择模型；报告准确率与 macro-F1、训练时间、固定节点批量预测时间、峰值内存、参数量和图传播运行次数。
稠密与稀疏 GCN。 在节点数和边密度逐步增大的图上比较稠密矩阵与稀疏边实现。固定图与特征、随机种子集合、数据类型、层宽、前向次数、预热及重复计时规则；报告输出误差、固定图批量预测时间、峰值内存、实际处理边数和图传播调用次数，并指出稠密实现无法运行的规模。
深度、宽度与学习率。 比较 GCN 深度 \(L\in\{1,2,4,8\}\)、若干隐藏宽度和学习率。固定数据划分、随机种子集合、最大训练更新次数、早停规则和评价代码；报告预测质量、训练时间、固定批量预测时间、峰值内存、参数量、图传播调用次数、节点表示方差和平均余弦相似度，区分容量、优化和过度平滑的影响。