图卷积网络深读:从谱滤波到 Kipf & Welling 的 GCN
1 它解决了什么问题
引文网络是本文的主要应用场景:每个节点代表一篇论文,边表示引用关系,任务是预测论文类别。训练标签只覆盖少量节点,例如七个类别各 20 篇,其余节点仍具有特征和连接信息。这属于图上的半监督学习。原论文采用 transductive(直推式)设定:测试节点在训练阶段已经位于图中,模型使用它们的特征和连接,但不使用测试标签。与之相对,inductive(归纳式)评估要求模型处理训练时未见的节点或图。
只根据节点自身的词袋向量训练分类器,会忽略引用关系中可能有用的信息。已有方法通过标签传播、图正则化或图嵌入利用这些关系,其中 Planetoid 也联合考虑特征、结构和标签。GCN 的设计特点是让神经网络的每一层沿图的边聚合特征,在同一个前向模型中学习节点表示,再用带标签节点的分类损失训练共享参数。
五节点链可以说明邻域信息的作用。令节点特征为 \(x=(3,2,1,2,5)\),节点 2 和节点 4 的自身特征同为 2。按第 2 节的权重聚合一次后,两者分别输出约 2.23 和 3.04;在本例中,差异来自邻居特征。GCN 因而能够区分某些自身特征相同、邻域不同的节点。接下来需要说明聚合权重的定义,以及它对传播量级的影响。
GCN 的谱方法依据包括 Hammond 等(2011)的图小波和 Defferrard 等(2016)的 ChebNet,即切比雪夫多项式滤波器。直接的谱卷积需要乘特征向量矩阵,单次乘法通常为 \(O(N^2)\);ChebNet 则用稀疏多项式运算,将固定阶数下的代价降至与边数线性。Kipf 的作者博客也从空域规则 \(\sigma(AHW)\) 出发解释 GCN,并引入自环与对称归一化。第 4、5 节将分别说明一阶化简和重归一化的数学含义。
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 C}\),其中 \(C\) 为输入特征维数;训练标签仅来自集合 \(\mathcal{Y}_L\subset V\)。加自环后记 \(\tilde{A}=A+I_N\),并重新计算 \(\tilde{D}_{ii}=\sum_j \tilde{A}_{ij}\),即将自环计入度数。传播矩阵定义为 \(\hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\)。
取五节点链 \(1\!-\!2\!-\!3\!-\!4\!-\!5\),令 \(x=(3,2,1,2,5)\)。此处暂不考虑权重矩阵 \(W\) 和激活函数 \(\sigma\),只计算邻域聚合。加自环后,节点度数由 \((1,2,2,2,1)\) 变为 \(\tilde{d}=(2,3,3,3,2)\),边 \((i,j)\) 上的聚合系数为
自环权重在端点为 \(1/\sqrt{2\cdot2}=1/2\),在中间节点为 \(1/\sqrt{3\cdot3}=1/3\)。连接端点的边权重为 \(1/\sqrt{2\cdot3}=1/\sqrt6\approx0.408\),中间两条边的权重为 \(1/3\)。将这些权重用于各节点,得到下表;计算使用精确权重,表中小数为舍入值。
| 节点 \(v\) | 自身 × 权重 | 邻居 × 权重 | 输出 \(h_v=\sum_u \hat{A}_{vu}\,x_u\) |
|---|---|---|---|
| 1 | \(3\times\tfrac12=1.500\) | \(2\times 0.408=0.816\) | 2.316 |
| 2 | \(2\times\tfrac13=0.667\) | \(3\times 0.408+1\times\tfrac13=1.558\) | 2.225 |
| 3 | \(1\times\tfrac13=0.333\) | \(2\times\tfrac13+2\times\tfrac13=1.333\) | 1.667 |
| 4 | \(2\times\tfrac13=0.667\) | \(1\times\tfrac13+5\times 0.408=2.375\) | 3.041 |
| 5 | \(5\times\tfrac12=2.500\) | \(2\times 0.408=0.816\) | 3.316 |
以上完成了 GCN 一层中的聚合步骤,完整层还包括特征变换和非线性。这个例子说明三个性质。
邻域信息会改变节点表示。节点 2 与节点 4 的自身特征同为 2,聚合结果却分别为 2.225 和 3.041。节点 4 邻接特征为 5 的节点 5,因此收到更大的加权贡献。两者在一次度归一化的邻域聚合后得到不同表示。
对称归一化通常不构成严格平均。本例中 \(\hat{A}\) 的行和为 \(0.908,\ 1.075,\ 1.000,\ 1.075,\ 0.908\),并非都等于 1。端点的邻居度数更大,因此行和小于 1;次端点包含一个度数更小的邻居,行和大于 1;中心点及其邻居度数相同,行和恰为 1。一般图的行和也不保证接近 1。若使用 \(\tilde{D}^{-1}\tilde{A}\),每行之和严格为 1,可以解释为加权平均,但矩阵通常不对称。两者通过相似变换关联,具有相同特征值;GCN 采用的对称形式便于在欧氏内积下进行谱分析。
自环与归一化分别影响信息来源和传播量级。直接求和 \(\tilde{A}x\) 得到 \((5,6,5,8,7)\),其中节点 4 的输出为 8,对称归一化后约为 3.04。求和会随邻居数量和特征大小增加,因而更容易受度数差异影响。若去掉自环再对称归一化,端点 1 的输出为 \(\tfrac{1}{\sqrt{2}}\times 2=1.414\),自身特征 3 在这一层的直接贡献为零。这说明原 GCN 为何同时采用两项设计;其他架构也可以通过单独的自身变换或残差连接保留节点信息。
选择接收节点,拖动任一节点的特征值。箭头指向本轮接收者,表格把每条消息拆成“输入 × 权重”。
| 消息来源 | 输入 | 权重 | 加权贡献 |
|---|---|---|---|
| 节点 1 | 3.0 | 0.408 | 1.225 |
| 节点 2 | 2.0 | 0.333 | 0.667 |
| 节点 3 | 1.0 | 0.333 | 0.333 |
| 节点 4 | 2.0 | 0.000 | 0.000 |
| 节点 5 | 5.0 | 0.000 | 0.000 |
全图输出:
对称归一化的行和不必等于 1。取消自环时,度数与全部边权会一并重算。
试一试:选择节点 2,只改变节点 5 的输入;这一层的输出不会变化。再选择节点 4,就能看到节点 5 的直接贡献。
式 (1) 给出了聚合的计算方法。下面三节转向它的谱方法依据:先定义图上的频率和卷积,再说明多项式近似、一阶化简与重归一化分别保留和改变了什么。
3 谱方法基础:图上的频率与卷积
3.1 图频率与拉普拉斯二次型
图像卷积依赖规则网格上的平移结构。一般图没有统一的平移操作,而且节点重新编号不应改变模型表达的图结构。谱方法通过图拉普拉斯建立频域表示。先考虑非归一化拉普拉斯 \(L=D-A\),其二次型为:
展开即可验证:\(x^\top Dx=\sum_u d_u x_u^2\),\(x^\top Ax=\sum_{(u,v)\in E}2x_ux_v\),相减后每条无向边恰好贡献一个差的平方。这个量称为 Dirichlet 能量,度量信号沿边的变化。若 \(Lu_i=\lambda_i u_i\),则 \(\lambda_i=u_i^\top Lu_i/\|u_i\|^2\),因此特征值衡量单位范数特征向量的变化能量。零特征值对应各连通分量上的常信号,其重数等于连通分量数;特征值越大,对应模式沿边的变化越剧烈。这是将特征值解释为图频率的依据。路径内部节点满足 \((Lx)_t=2x_t-x_{t-1}-x_{t+1}\),即通常二阶差分的相反数;例如 \(x_t=t^2\) 时该值为 \(-2\)。
GCN 的谱推导采用归一化拉普拉斯 \(L_{\text{sym}}=I-D^{-1/2}AD^{-1/2}\)。在度数为正时,它的能量为 \(x^\top L_{\text{sym}}x=\sum_{(u,v)\in E}(x_u/\sqrt{d_u}-x_v/\sqrt{d_v})^2\),因此平滑性针对的是按度数缩放后的信号。零特征方向相应变为 \(D^{1/2}\mathbf{1}\)。涉及未加自环的逆度矩阵时,以下推导先假定节点度数为正;第 6 节再说明孤立节点的处理。
3.2 拉普拉斯特征向量与傅里叶基
经典傅里叶基 \(e^{i\omega t}\) 是平移算子的特征函数,平移只改变其相位。图上可将邻接算子视为一种沿边传播的操作。记 \(S=D^{-1/2}AD^{-1/2}\),则 \(L_{\text{sym}}=I-S\),所以两者共享特征向量,对应特征值满足 \(\lambda_L=1-\lambda_S\)。谱分解 \(L=U\Lambda U^\top\) 由此提供一组按图频率组织的正交基。环图 \(C_N\) 给出了与经典情形的直接联系:其拉普拉斯是循环矩阵,可由离散傅里叶变换(DFT)基对角化。选择这组特征基时,环图上的图傅里叶变换就是 DFT;重特征值空间内也可以选择其他正交基。本文的谱公式采用实正交基,故写作转置 \(U^\top\);使用复数 DFT 基时应改为共轭转置。
3.3 从频域乘法定义谱图卷积
经典卷积在频域中对应逐点乘法。谱图卷积沿用这一思路:先计算图傅里叶系数 \(U^\top x\),逐分量乘以滤波器响应,再变换回节点域。从本节起,\(L\) 表示归一化拉普拉斯。若为每个特征方向设置一个可学习增益,取 \(g_\theta(\Lambda)=\operatorname{diag}(\theta)\)、\(\theta\in\mathbb{R}^N\),则
仍使用五节点链。先选一个频率模式或混合信号,再选择滤波器。两幅图的坐标尺度保持一致,虚线表示零值;石青表示正值,赭色表示负值。
滤波后信号:
增加滤波强度时,高频增益下降得更快。混合信号中较快交替的分量因此先被压低。
试一试:切换到零频模式,再选互补高通。这个分量会完全消失;它的原始节点值虽有高低,按度数缩放后却不沿边变化。
式 (3) 是在选定特征基下定义的谱滤波器;Shuman 等(2013)的综述系统讨论了这一框架。将它直接作为可学习层,有以下限制。
计算依赖稠密特征基。乘一次 \(U\) 通常需要 \(O(N^2)\) 运算,预先求出特征分解也可能成为大图上的主要开销。
参数与特征方向绑定。\(\theta_i\) 控制第 \(i\) 个特征方向的增益。换图或改变边后,特征基也会改变,原参数缺少直接对应到新图的规则;图规模不同时,参数维数还可能不同。
参数量随节点数增长。Cora 有 2 708 个节点,式 (3) 的单个标量滤波器就有 2 708 个自由参数。在每类仅有 20 个训练标签的条件下,需要限制模型容量,以降低过拟合风险。
一种解决方法是将响应限制为 \(\Lambda\) 的低阶多项式。它用少量共享系数描述频率响应,并可改写为 \(L\) 的多项式,从而避免显式计算 \(U\)。
4 从多项式谱滤波到一阶模型
4.1 K 阶多项式与局部计算
ChebNet(Defferrard 等 2016)把 \(g_\theta(\Lambda)\) 限制为拉普拉斯的 \(K\) 阶多项式,用切比雪夫多项式 \(T_k\) 展开:
多项式滤波具有K 跳局部性:\((L^k)_{uv}\neq0\) 要求 \(u\) 到 \(v\) 存在不超过 \(k\) 步的路径。证明可用归纳法:\(k=0\) 对应单位阵;在 \(L^k=L\cdot L^{k-1}\) 中,非零项要求先停留在原节点或沿边走一步,再到达一个至多 \(k-1\) 步可达的节点。因此,\(K\) 阶滤波器的输出只依赖 \(K\) 跳邻域。计算采用稀疏矩阵—向量乘,代价为 \(O(K(|E|+N))\);固定 \(K\) 且无孤立节点时,可简写为 \(O(|E|)\)。此外,\(K+1\) 个多项式系数不再绑定特定特征向量,可以在采用同一算子定义的图上使用,但迁移后的预测效果仍需检验。
切比雪夫基兼顾区间逼近与递推计算。它满足 \(T_k(\cos\phi)=\cos(k\phi)\)。令 \(t=\cos\phi\),则 \(|d\phi|=|dt|/\sqrt{1-t^2}\),余弦函数的正交性由此对应于权函数 \(1/\sqrt{1-t^2}\) 下的多项式正交性。将谱区间 \([0,\lambda_{\max}]\) 映射到 \([-1,1]\),便得到 \(\tilde{L}=2L/\lambda_{\max}-I\)。相较于高阶单项式基,这种表示具有有用的数值性质,也是 Hammond 等图小波框架采用的近似方法。实际计算令 \(q_0=x\)、\(q_1=\tilde{L}x\),按 \(q_{k+1}=2\tilde{L}q_k-q_{k-1}\) 递推即可,无需形成矩阵幂。
谱缩放通常使用最大特征值的估计,或使用归一化拉普拉斯的上界 2。它影响基函数的数值范围和系数表示。若各阶系数均可自由学习,改变正的缩放常数并不改变固定阶数的多项式空间;第 4.2 节先说明一阶情形,练习 4 再推广这一结论。
把传播次数从 0 开始增加,观察信息可到达的范围。赭色是目标节点;同色节点与目标的最短距离相同,浅灰节点暂时在感受野之外。
恰在当前跳数的新节点:
试一试:从节点 1 出发,先看 1 跳,再看 2 跳。节点 2 与 3 之间有边,但重复到达它们不会增加不同节点的数量。
4.2 化简到一阶:四步代数,每步标明性质
GCN 先令 \(K=1\),再约束系数。以下将推导分为四步,以区分模型选择、谱尺度近似和恒等变形。
① 截断(选择)。令 \(K=1\),只保留 \(T_0\) 与 \(T_1\),于是 \(\theta'\in\mathbb{R}^2\)。原论文的动机是通过堆叠一阶层扩大感受野,同时限制局部滤波器的自由度,并降低每层计算量。这些动机是否带来更好的预测效果,需要由实验判断。
② 代入 \(\lambda_{\max}\approx2\)(谱尺度近似)。归一化拉普拉斯的谱位于 \([0,2]\),采用尺度 2 后,\(\tilde{L}=L-I=-D^{-1/2}AD^{-1/2}\)。在两个系数均自由时,这不缩小可表示的一阶滤波族:对任意正数 \(\hat{\lambda}\),\(\theta'_0I+\theta'_1(2L/\hat{\lambda}-I)=(\theta'_0-\theta'_1)I+(2\theta'_1/\hat{\lambda})L\),仍可表示所有 \(aI+bL\)。这是关于函数族的结论,不保证固定参数下的输出或训练过程不变。对更高阶且系数均自由的多项式,同样可以通过换基吸收尺度变化;数值条件和正则化效果仍可能不同。
③ 消去 \(L\)(恒等)。记 \(S=D^{-1/2}AD^{-1/2}\),代入 \(L=I-S\) 得 \(\theta'_0x+\theta'_1\tilde{L}x=\theta'_0x-\theta'_1Sx\),这就是论文式 6。若将负号吸收到第二个参数中,也可写为 \(x\theta_0+Sx\theta_1\),仍有两个自由参数。
④ 约束系数(选择)。令 \(\theta'_0=\theta,\ \theta'_1=-\theta\),将自身项和邻域项合并为单参数形式 \(\theta(I+S)x\):
此时,滤波器从逐频率独立增益变为受单个参数控制的直线响应。三种参数化方式的差别如下。
| 滤波器 | 自由参数 | 能表达的响应 \(g(\lambda)\) | 与图规模的耦合 |
|---|---|---|---|
| 逐方向谱滤波(式 3) | \(N\) 个 | 各特征方向的独立增益 | 参数与具体图的特征基绑定 |
| ChebNet \(K\) 阶(式 4) | \(K+1\) 个 | 次数不超过 \(K\) 的多项式;陡峭响应通常需要更高阶数 | 参数量与节点数无关,作用于 \(K\) 跳邻域 |
| GCN 一阶(式 5) | \(1\) 个 | 直线 \(\theta(2-\lambda)\),幅值随频率下降 | 采用固定谱尺度 2 |
式 (5) 的响应幅值为 \(|\theta|(2-\lambda)\),在 \([0,2]\) 上单调不增,并在 \(\lambda=2\) 处为零,因此具有低通特征。这个结论对应重归一化前的 \(I+S\)。第 5 节改变传播矩阵后,一般图的新算子未必与原拉普拉斯共享特征向量,不能直接沿用这条频率响应曲线。第 8.1 节将分别讨论纯传播的极限和正则图的精确表达式。
5 谱半径的修正:重归一化
5.1 式 (5) 连续传播的放大效应
式 (5) 的传播矩阵 \(I+D^{-1/2}AD^{-1/2}\) 在连续作用时可能放大信号。记 \(S=D^{-1/2}AD^{-1/2}\),可分三步分析。
第一步:\(S\) 的谱位于 \([-1,1]\)。对任意向量 \(z\),将不等式 \(2|ab|\le a^2+b^2\) 用于 \(a=z_u/\sqrt{d_u}\)、\(b=z_v/\sqrt{d_v}\)。在 \(z^\top Sz=\sum_{(u,v)\in E}2z_uz_v/\sqrt{d_ud_v}\) 中,每条边贡献的绝对值不超过 \(z_u^2/d_u+z_v^2/d_v\)。每个节点出现在 \(d_u\) 条边中,求和后得到 \(|z^\top Sz|\le\|z\|^2\)。对称矩阵的 Rayleigh 商极值分别等于最小、最大特征值,因此 \(|\lambda(S)|\le1\)。练习 2 给出含自环时的完整证明。
第二步:1 是 \(S\) 的特征值。直接计算 \(S D^{1/2}\mathbf{1}=D^{-1/2}A\mathbf{1}=D^{-1/2}d=D^{1/2}\mathbf{1}\),可知 \(D^{1/2}\mathbf{1}\) 是不动方向。因此 \(I+S\) 的最大特征值为 2。
第三步:对应分量随连乘指数增长。在纯传播 \((I+S)^\ell x\) 中,\(D^{1/2}\mathbf{1}\) 方向的分量被乘以 \(2^\ell\):10 次约放大 \(10^3\) 倍,20 次约放大 \(10^6\) 倍。只要初始信号在该方向有非零投影,这一增长就会出现。原论文据此指出深层模型可能发生数值不稳定及梯度爆炸或消失。实际网络还包含权重矩阵与激活函数,因此这个论证说明传播算子本身的风险,并不意味着每个训练过程都会发生爆炸。
5.2 加自环后重新归一化
Kipf & Welling 将原传播矩阵替换为 \(I_N+D^{-1/2}AD^{-1/2}\ \longrightarrow\ \tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\),其中 \(\tilde{A}=A+I_N\),\(\tilde{D}\) 是 \(\tilde{A}\) 的度矩阵。这个替换是一项模型设计,并非恒等变形。它有两项可直接证明的谱性质。
谱半径降为 1。前述放缩也适用于非负对称矩阵 \(\tilde{A}\),因此 \(\hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 满足 \(|\lambda|\le1\)。同时,\(\tilde{D}^{1/2}\mathbf{1}\) 是特征值 1 的方向。相较于 \(I+S\),谱半径从 2 降至 1;又因 \(\hat{A}\) 对称,其连乘不会增大向量的欧氏范数。这排除了纯传播自身的指数放大,但不保证含任意权重矩阵的整个网络稳定。
自环排除特征值 \(-1\)。无自环时,含边的二部连通分量可使归一化邻接矩阵具有特征值 \(-1\)。给每个节点加上正权自环后,各连通分量的随机游走均非周期,\(-1\) 不再出现。因此 \(\hat{A}\) 的谱位于 \((-1,1]\)。
以下是本文构造的三个小图的谱计算结果,小数近似值保留至小数点后三位。
| 图 | \(I+D^{-1/2}AD^{-1/2}\) 的谱 | \(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 的谱 |
|---|---|---|
| 星形(中心+4 叶) | \(\{2,\ 1,\ 1,\ 1,\ 0\}\) | \(\{1,\ 0.5,\ 0.5,\ 0.5,\ -0.3\}\) |
| 路径 \(P_5\) | \(\{2,\ 1.707,\ 1,\ 0.293,\ 0\}\) | \(\{1,\ 0.833,\ 0.427,\ 0,\ -0.260\}\) |
| 五环 \(C_5\)(非二部) | \(\{2,\ 1.309,\ 1.309,\ 0.191,\ 0.191\}\) | \(\{1,\ 0.539,\ 0.539,\ -0.206,\ -0.206\}\) |
三个图的谱半径均从 2 降为 1,但各特征值并非等比例缩放。例如星形图中,三个特征值 1 变为 0.5,特征值 0 则变为 \(-0.3\)。重归一化改变了整个谱分布。图 5 用同一个单位范数初始向量 \(x_0\),比较两种传播矩阵连续作用 10 次的结果。
5.3 GCN 的逐层传播规则
将重归一化后的矩阵用于神经网络,每层执行特征变换、邻域聚合和非线性激活:
\(W^{(l)}\):特征变换。它是各节点共享的线性映射,作用于特征维;\(\hat{A}\) 则作用于节点维,混合相邻节点的信息。由矩阵乘法结合律,\(\hat{A}(HW)=(\hat{A}H)W\)。因此实现可按维数选择乘法顺序:输出特征维数较小时,先算 x @ W 通常可减少后续聚合的计算量。
\(\tilde{A}=A+I\):自环。自环使节点自身特征直接参与每层聚合,并消除无自环二部图的周期性。谱半径从 2 降至 1,则是加自环后重新计算度矩阵并归一化的整体结果,不能归因于单独的 \(+I\)。
\(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\):对称归一化。每个节点接收自身及邻居特征的加权和,权重为两端度数乘积的平方根之倒数。矩阵保持对称,谱位于 \((-1,1]\),但行和不保证为 1。行归一化矩阵 \(\tilde{D}^{-1}\tilde{A}\) 与它有相同特征值,也可以分析收敛;两者的不动向量和自然使用的内积不同。
\(\sigma\):非线性。论文隐层采用 ReLU。若去掉层间非线性,连续 \(k\) 层可合并为 \(\hat{A}^{\,k}X(W^{(0)}\cdots W^{(k-1)})\):图传播仍覆盖 \(k\) 跳邻域,但可学习部分合并为一次线性变换。第 8 节的 SGC 正是从这一观察出发。
6 两层网络、训练与实现细节
论文主要实验采用两层 GCN,记输入 \(H^{(0)}=X\),其前向模型为:
每一行始终对应同一个节点。石青色小格示意特征通道;两层传播都使用同一张图,通道数则可以变化。
左乘 \(\hat A\) 混合节点行;右乘 \(W^{(l)}\) 变换每行的特征通道。非线性施加在两次线性运算之后。
所有节点均产生预测,但训练交叉熵只读取训练标签对应的行。测试标签不进入训练损失。
训练交叉熵仅覆盖带标签节点:\(\mathcal{L}=-\sum_{v\in\mathcal{Y}_L}\sum_cY_{vc}\ln Z_{vc}\)。Cora 的训练标签约占节点总数的 \(5\%\),但 \(W^{(0)},W^{(1)}\) 在全图共享,未标注节点的特征也用于前向计算。对两层网络,某个带标签节点的损失直接依赖其至多两跳邻域中的输入特征;并非每个未标注节点都必然影响训练损失。在原论文的直推式协议下,使用测试节点的特征与边是任务设定的一部分,测试标签则不参与训练。
令 \(C\) 为输入维数、\(H\) 为隐层宽度、\(F\) 为类别数。论文 §3.2 将两层前向的复杂度写为 \(O(|\mathcal{E}|CHF)\),强调固定特征维数时对边数的线性依赖。若每层先做特征变换,再用稀疏邻接矩阵聚合,更细的计数为 \(O(NCH+NHF+(|E|+N)(H+F))\)。稀疏邻接本身占用 \(O(|E|+N)\) 空间;训练还需要保存特征、隐层激活和参数,不能将邻接存储量当作全部内存开销。
下表列出三个引文网络共用的训练配置。实验中的层数选择应结合模型容量、正则化、验证策略与数据划分理解。
| 配置 | 取值 | 备注 |
|---|---|---|
| 隐层宽度 | 16 | Cora、Citeseer、Pubmed 共用 |
| Dropout | 0.5 | 作用于输入特征与隐层激活;邻接矩阵保持不变 |
| L2 正则 | \(5\times10^{-4}\) | 只作用于第一个 GCN 层的权重 |
| 优化 | Adam,学习率 0.01 | 全批梯度下降;权重 Glorot 初始化 |
| 数据划分 | Cora:140 训练 / 500 验证 / 1000 测试 | 每类 20 个训练标签;Planetoid 标准划分 |
| 早停 | 窗口 10 | 论文描述为连续 10 个 epoch 验证损失不降;训练上限为 200 个 epoch |
| 超参出处 | 在 Cora 上调定 | 同一组用于 Citeseer 与 Pubmed;NELL 使用另一组配置 |
加自环后重新计算度数。用原始 \(D\) 归一化 \(\tilde{A}=A+I\) 会得到不同的传播矩阵,前述谱界也不再直接适用。
使用与论文一致的对称归一化。\(\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 与行归一化 \(\tilde{D}^{-1}\tilde{A}\) 的权重不同,复现实验时应明确采用哪一种。
预先计算稀疏边权。将 \(1/\sqrt{\tilde{d}_i\tilde{d}_j}\) 乘入每条边的权重,再执行稀疏矩阵乘法。固定图下,这一步可以在训练前完成。
输入特征按行归一化。这是论文 §5.2 及官方实现采用的预处理。复现时应保持一致;原论文没有单独报告去掉这一步的准确率消融。
先加自环可避免零度数。无自环的逆度矩阵需要单独约定度数为零时的处理方式。加入单位自环后,\(\tilde{d}_i\ge1\),孤立节点也能正常归一化,其自身特征得到保留。
区分论文描述与代码中的早停判据。官方训练代码在超过窗口后,将当前验证损失与此前 10 次损失的均值比较,前者较大时停止。这与“连续 10 次没有改进”的常见实现并不相同;复现时应记录实际采用的判据。
7 实验与消融:比较传播模型
下表列出原论文最终版 v4 的分类准确率和达到收敛的训练耗时。GCN 准确率为 100 次随机权重初始化的平均值;耗时来自论文的硬件与实现环境。Pubmed 的主结果为 79.0%;79.2% 出现在后面的 Cora 单参数变体消融中。
| 数据集 | 节点 / 边 / 类别 | 每类标签 | 表中最佳基线 | GCN(训练耗时) |
|---|---|---|---|---|
| Cora | 2 708 / 5 429 / 7 | 20 | 75.7%(Planetoid) | 81.5%(4 秒) |
| Citeseer | 3 327 / 4 732 / 6 | 20 | 69.1%(ICA) | 70.3%(7 秒) |
| Pubmed | 19 717 / 44 338 / 3 | 20 | 77.2%(Planetoid) | 79.0%(38 秒) |
| NELL | 65 755 / 266 144 / 210 | 1 | 61.9%(Planetoid) | 66.0%(48 秒) |
这些结果需要结合划分和基线阅读。Citeseer 上最佳基线为 ICA 的 69.1%,GCN 高出 1.2 个百分点。改用 10 个同规模随机划分后,Cora、Citeseer、Pubmed 的结果分别为 80.1±0.5、67.9±0.5、78.9±0.7,论文中的“±”表示标准误,说明成绩会受划分影响。NELL 经预处理得到二部图,共有 210 个类别,每类仅使用 1 个训练标签;在固定划分上,GCN 比 Planetoid 高 4.1 个百分点,耗时为 48 秒,对方为 185 秒。
论文还比较了不同传播模型。以下结果均为 100 次随机权重初始化的平均分类准确率,单位为百分比。
| 传播模型 | Citeseer | Cora | Pubmed | 对应章节 |
|---|---|---|---|---|
| 多层感知机(完全不用图) | 46.5 | 55.1 | 71.4 | 第 1 节“只看特征” |
| 切比雪夫 \(K=3\) | 69.8 | 79.5 | 74.4 | 式 (4) |
| 切比雪夫 \(K=2\) | 69.6 | 81.2 | 73.8 | 式 (4) |
| 一阶、两参数(论文式 6) | 68.3 | 80.0 | 77.5 | 第 4.2 节第③步 |
| 单参数、未重归一化(式 5) | 69.3 | 79.2 | 77.4 | 第 4.2 节第④步 |
| 只有一阶项(无自环) | 68.7 | 80.5 | 77.8 | 第 2 节去自环对照 |
| 重归一化(式 6) | 70.3 | 81.5 | 79.0 | 第 5 节 |
在这些实验设置下,可以得到以下三项观察。
图传播带来明显改善。MLP 与重归一化 GCN 的差距为 7.6–26.4 个百分点,其中 Pubmed 为 71.4→79.0,Cora 为 55.1→81.5。这支持利用图结构的价值,但差距依赖当前数据、划分和训练配置,不能解释为图结构在任意任务上的固定收益。
较高多项式阶数没有在此带来更好结果。Cora 上,Chebyshev \(K=2\) 为 81.2%,单参数一阶为 79.2%,重归一化后为 81.5%;Pubmed 上,两参数一阶为 77.5%,高于 \(K=3\) 的 74.4%。这说明较简单的传播模型在这些配置下具有竞争力,不能据此断言更大感受野普遍有害,或一阶模型是所有可能设计中的最优解。
重归一化变体在三列中均取得最高平均准确率。Cora 上,无自环、单参数未重归一化、重归一化三者分别为 80.5%、79.2%、81.5%;Citeseer 上前两者则为 68.7% 和 69.3%,排序不同。因此不能把自环、归一化的收益简单相加,也不能仅凭准确率将改善全部归因于数值稳定性。
论文附录 B 比较了最多 10 层的模型,采用 5 折交叉验证并包含残差变体;实验中 2–3 层表现较好,超过 7 层时无残差模型训练更困难,逐层结果见附录曲线。附录 A 还展示了空手道俱乐部网络上的三层随机权重 GCN:输入 \(X=I\),输出直接取二维,不经训练即可反映部分社区结构,作者将其与 DeepWalk 嵌入作了定性比较。这是 34 节点图上的可视化观察,不能据此推断随机权重模型在引文分类任务上接近有监督基线。
8 深层的代价与模型的边界
8.1 纯传播的过度平滑极限
重归一化控制了纯传播的范数,但反复聚合也会削弱部分节点差异。设 \(u_i\) 为 \(\hat{A}\) 的正交归一特征向量,将连续传播展开为:
若图连通,加入正权自环后,\(\hat{A}\) 是不可约且非周期的非负矩阵。由 Perron–Frobenius 理论,除简单特征值 \(\lambda_1=1\) 外,其余特征值均满足 \(|\lambda_i|<1\)。因此 \(k\to\infty\) 时,\(\hat{A}^{\,k}x\to c\,\tilde{D}^{1/2}\mathbf{1}\)。极限仍可因节点度数不同而取不同值,但初始信号在其他特征方向上的信息已经消失。若图不连通,这一结论分别作用于各连通分量;将多个分子图组成块对角矩阵时,也应按分量分析。
收敛速度由非主特征值的最大绝对值 \(\rho=\max_{i\ge2}|\lambda_i|\) 控制。路径 \(P_5\) 上 \(\rho=0.833\),因此相对于极限的误差范数在 10 次传播后至多约为初值的 \(0.833^{10}\approx0.16\);各特征分量按各自的 \(\lambda_i^{10}\) 衰减,并非都恰好缩小到这一比例。图 5 中趋于稳定的范数与这种收敛相容,但仅观察范数不足以证明表示已平滑。增加层数会扩大感受野,也会增加传播次数,实际效果需要结合信号和任务评估。
上述极限严格适用于纯传播 \(\hat{A}^{\,k}\)。Li 等(2018)从拉普拉斯平滑解释 GCN;Oono & Suzuki(2020)则在权重矩阵奇异值满足与图谱有关的条件下,证明若干 GNN 的输出趋近于由连通分量和度数决定的子空间。这些结论带有明确的模型与权重条件,不能推广为任意深层 GNN 都必然失去表达力。
在度数为 \(d>0\) 的正则图上,可写出精确响应:\(\hat{A}=I-\tfrac{d}{d+1}L_{\text{sym}}\),频率 \(\mu\) 处的 \(k\) 次传播增益为 \(\bigl(1-\tfrac{d}{d+1}\mu\bigr)^k\)。对每个非零频率,其绝对值随传播次数趋于零。不过,这个绝对值未必随 \(\mu\) 单调下降,因为一次传播的响应可能在高频处为负。应区分随深度衰减与随频率单调低通这两个命题。
左、右两团各是一个四节点环,中间可保留或移除桥边。每个节点都有自环(图中省略);圆内显示按含自环的度数缩放后的表示,便于观察平滑。正负颜色的尺度在传播前后固定。
图连通且每个节点都有自环。传播越深,按度数缩放后的表示趋向同一个值;原始表示的极限仍可因度数不同而不同。
查看未缩放的节点表示与极限值
当前表示:
理论极限:
试一试:传播 60 次后移除桥边。此时会按新的图重新计算,两个连通分量仍可保持不同的平稳信号。
8.2 模型边界与后续方法
直推式实验与归纳能力应分开讨论。原论文在固定图上训练和评估,但式 (6) 的共享权重不依赖节点编号。因此在特征定义一致时,传播规则可以应用于未见节点或新图,其泛化能力仍需独立评估。GraphSAGE(Hamilton 等 2017)进一步结合邻域采样与聚合函数,系统研究了归纳式学习,也比较了基于 GCN 的聚合变体。新节点加入后需要更新相关邻域和归一化系数,并不在数学上强制重算整张图的所有表示。
原始聚合权重不随特征自适应。在本文的二值邻接设定下,\(\hat{A}_{vu}\) 由连接关系和度数决定。GAT(Veličković 等 2018)通过注意力依据节点特征学习邻居权重。若要将边特征直接用于消息,例如分子图中的键型,可采用 MPNN(Gilmer 等 2017)的形式 \(m_{vu}=M(h_v,h_u,e_{vu})\)。原 GCN 可以接受标量加权邻接,但这不同于使用一般的向量边特征。原论文也说明,可将某些边关系转为附加节点,NELL 即采用了这种预处理。
全批训练受内存限制。每次训练需要保存图结构、节点特征和中间激活,内存随节点数、边数及特征维数增长。论文 §7.2 将小批训练列为后续方向,并指出精确计算需要考虑多层感受野。GraphSAINT、Cluster-GCN 等后续方法通过采样或划分子图降低训练开销。
部分任务可以进一步简化模型。SGC(Wu 等 2019)去掉层间非线性,并将逐层权重合并为一个矩阵,得到 \(K\) 次 \(\hat{A}\) 预传播后接逻辑回归。作者将其分析为固定图滤波与线性分类器的组合;在 Cora 的谱分析中,加自环后的 \(\tilde{L}_{\text{sym}}=I-\hat{A}\) 最大特征值从 2 降至约 1.5,这一数值依赖具体图。SGC 在 Cora、Citeseer、Pubmed 上的准确率分别为 81.0±0.0、71.9±0.1、78.9±0.0。其补充材料报告相应训练耗时为 0.13、0.14、0.29 秒,对应 GCN 为 0.49、0.59、8.31 秒;这些数据来自该文的同一基准环境,SGC 耗时包含预传播。它们支持在这些任务上采用较简单的模型,但不能证明非线性或可学习传播在其他任务中没有价值。
扩大传播范围时可以保留初始预测。APPNP(Gasteiger 等 2019)将预测与传播分开:神经网络先计算节点分类得分,再以带回传概率 \(\alpha\) 的个性化 PageRank 近似进行传播。每次迭代重新引入初始预测,使结果不只由纯传播的平稳方向决定。残差连接、DropEdge 等也从不同角度改善深层传播,适用效果仍取决于模型和数据。
实现式 (6) 时,还应区分框架的默认行为。PyTorch Geometric 的 GCNConv默认在归一化时加入自环;DGL 的 GraphConv(norm="both")提供对称归一化,但通常需要先给输入图添加自环。偏置与激活函数也应按所要复现的模型显式设置,不能仅凭层的名称认定实现完全相同。
9 与本站的衔接
本站《分子机器学习导论》第 3 章将 GCN 作为消息传递框架的一个实例:邻居特征经 \(W\) 变换后,按度归一化权重求和,再由 ReLU 更新节点表示。引文网络与分子图可以使用相同的传播形式,但边的含义、特征类型和预测目标不同。阅读该章时,可结合本文检查三点:第一,图级任务需要读出(readout),即将原子表示通过求和、平均池化等方式形成分子表示;第二,分子图的度分布与键特征需要按具体表示分析,归一化的实际收益不能直接照搬引文网络;第三,所需层数应根据任务相关结构的范围和实验结果选择,本文的两层配置不构成分子任务的通用结论。
延伸阅读可按问题选择:Defferrard 等 2016(ChebNet)讨论局部谱滤波,Wu 等 2019(SGC)检验进一步线性化的效果,Veličković 等 2018(GAT)引入注意力权重,Gilmer 等 2017(MPNN)给出包含边特征的消息传递框架。GCN 与 Weisfeiler–Lehman 测试的关系在原论文附录中也有讨论;严格的表达力比较还需要区分具体聚合函数及其假设。
练习
练习 1 行和、自环与聚合量级
对第 2 节的五节点链:(a) 验证 \(\hat{A}\) 的行和为 \(0.908,\ 1.075,\ 1.000,\ 1.075,\ 0.908\);(b) 取 \(x=(1,2,3,2,1)\),计算 \(\hat{A}x\),并与 \(\tilde{A}x\) 及去自环的对称归一化结果比较,说明归一化如何影响数值量级,自环如何影响自身特征的直接贡献。
解答/提示(a) 端点行:\(\tfrac12+1/\sqrt6\approx0.908\);次端行:\(1/\sqrt6+\tfrac13+\tfrac13\approx1.075\);中心行为三个 \(\tfrac13\),和为 1。(b) \(\hat{A}x\approx(1.316,\,2.075,\,2.333,\,2.075,\,1.316)\),这是加权和,不能因量级与 \(x\) 相近就称为严格平均。\(\tilde{A}x=(3,6,7,6,3)\),其数值包含邻居数与特征大小的共同影响。去自环的对称归一化给出 \((1.414,\,2.207,\,2.000,\,2.207,\,1.414)\):端点 1 的输出 \(2/\sqrt2\approx1.414\) 完全来自邻居,自身特征 1 在该层的直接贡献为零。
练习 2 对称归一化矩阵的谱界
设 \(\tilde{A}\) 为非负对称矩阵,且所有行和均为正,\(\tilde{D}\) 为其度矩阵。证明 \(\hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2}\) 的所有特征值位于 \([-1,1]\),且 \(1\) 是它的特征值。
解答/提示对任意向量 \(z\),令 \(w=\tilde{D}^{-1/2}z\)。由非负性、对称性及 \(2|w_iw_j|\le w_i^2+w_j^2\),得 \(|z^\top\hat{A}z|\le\sum_{i,j}\tilde{A}_{ij}|w_iw_j|\le\sum_{i,j}\tfrac{\tilde{A}_{ij}}2(w_i^2+w_j^2)=\tfrac12\sum_i(w_i^2\sum_j\tilde{A}_{ij}+w_i^2\sum_j\tilde{A}_{ji})=\sum_i\tilde{d}_iw_i^2=\|z\|^2\)。因此 Rayleigh 商位于 \([-1,1]\),从而 \(|\lambda|\le1\)。最后,\(\hat{A}\tilde{D}^{1/2}\mathbf{1}=\tilde{D}^{-1/2}\tilde{A}\mathbf{1}=\tilde{D}^{-1/2}\tilde{d}=\tilde{D}^{1/2}\mathbf{1}\),且该向量非零,所以 1 是特征值。
练习 3 两跳邻域的树近似
Cora 的平均度约为 \(2\times5429/2708\approx4.0\)。将局部邻域近似为度数均为 4、没有重复到达节点的树,估计两层 GCN 的感受野包含多少节点。说明三角形和度数差异如何影响估计,并讨论邻域大小是否足以确定最优层数。
解答/提示在给定近似下,感受野包括自身、4 个一跳邻居和 \(4\times3\) 个两跳邻居,共约 17 个节点。固定同样的局部度数时,三角形与其他重复路径会使不同路径到达同一个节点,因此减少实际覆盖的不同节点数。真实图的度数并不都等于平均度,高度数邻居也可能使感受野超过这一估计。邻域大小只衡量可用信息的范围;类别分布、特征质量和传播导致的信息混合共同影响性能,不能由 17 这个数推出两层最优或三层冗余。
练习 4 谱尺度与多项式滤波族
设 \(\hat{\lambda}>0\)。证明 \(K=1\) 的切比雪夫滤波族 \(\{\theta'_0I+\theta'_1(2L/\hat{\lambda}-I):\ \theta'\in\mathbb{R}^2\}\) 与 \(\{aI+bL:\ a,b\in\mathbb{R}\}\) 是同一个集合。再证明,当 \(K\ge2\) 且所有 \(K+1\) 个系数均可自由选择时,更换正的谱尺度也不改变次数至多为 \(K\) 的滤波族,并说明这一结论不保证哪些性质。
解答/提示一阶时,\(\theta'_0I+\theta'_1(2L/\hat{\lambda}-I)=(\theta'_0-\theta'_1)I+(2\theta'_1/\hat{\lambda})L\)。取 \(a=\theta'_0-\theta'_1\)、\(b=2\theta'_1/\hat{\lambda}\),可反解 \(\theta'_1=b\hat{\lambda}/2\)、\(\theta'_0=a+b\hat{\lambda}/2\),因此两族相同。一般 \(K\) 下,\(T_k(2t/\hat{\lambda}-1)\) 是首项系数非零的 \(k\) 次多项式,\(k=0,\ldots,K\) 的这些多项式与 \(1,t,\ldots,t^K\) 之间的换基矩阵为对角元非零的三角矩阵,所以张成同一空间。代入矩阵 \(L\) 后,所得滤波算子集合仍相同。\(T_2(t)=2t^2-1\) 引入二次项,但模型也有相应的独立系数,不能据此否定换基结论。改变尺度可能改变固定系数时的输出、数值条件、系数正则化及优化路径;若再约束或捆绑系数,也必须重新分析函数族。
参考文献
- 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.
- Shuman DI, Narang SK, Frossard P, Ortega A, Vandergheynst P. 2013. The emerging field of signal processing on graphs. IEEE Signal Processing Magazine 30(3): 83–98.
- Yang Z, Cohen WW, Salakhutdinov R. 2016. Revisiting semi-supervised learning with graph embeddings. Proceedings of the 33rd International Conference on Machine Learning: 40–48. arXiv:1605.05273.
- Li Q, Han Z, Wu XM. 2018. Deeper insights into graph convolutional networks for semi-supervised learning. Proceedings of AAAI 2018: 3538–3545. arXiv:1801.07606.
- 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 WL, Ying R, Leskovec J. 2017. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems 30: 1024–1034.
- Gilmer J, Schoenholz SS, Riley PF, Vinyals O, Dahl GE. 2017. Neural message passing for quantum chemistry. Proceedings of the 34th International Conference on Machine Learning: 1263–1272.
- Wu F, Souza A, Zhang T, Fifty C, Yu T, Weinberger KQ. 2019. Simplifying graph convolutional networks. Proceedings of the 36th International Conference on Machine Learning: 6861–6871. arXiv:1902.07153.
- Gasteiger J, Bojchevski A, Günnemann S. 2019. Predict then propagate: graph neural networks meet personalized PageRank. International Conference on Learning Representations (ICLR 2019). arXiv:1810.05997.
- Oono K, Suzuki T. 2020. Graph neural networks exponentially lose expressive power for node classification. International Conference on Learning Representations (ICLR 2020). arXiv:1905.10947.