首页 › 文章 › 图卷积网络深读
DEEP READING · 深读第 1 篇

图卷积网络深读:从谱滤波到 Kipf & Welling 的 GCN

Semi-Supervised Classification with Graph Convolutional Networks · ICLR 2017
2026-09-03 · 约 65 分钟 · 4 个交互实验 · 前置:线性代数(特征值、二次型)+ 基础机器学习(softmax、交叉熵)
导读 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)\) 上的聚合系数为

\[ \hat{A}_{ij} \;=\; \frac{\tilde{A}_{ij}}{\sqrt{\tilde{d}_i\,\tilde{d}_j}} \]
(1)

自环权重在端点为 \(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 2 3 4 5 x=3, d̃=2 x=2, d̃=3 x=1, d̃=3 x=2, d̃=3 x=5, d̃=2 0.408 0.333 0.333 0.408 自环 0.5 自环 0.333 自环 0.333 自环 0.333 自环 0.5 边与自环的权重均为 Â(i,j) = Ã(i,j) / √(d̃ᵢ·d̃ⱼ),行和不一定为 1 一轮聚合:h = (2.316, 2.225, 1.667, 3.041, 3.316)
图 1 五节点链上的一次邻域聚合。石青色圈表示端点,其度数较小、自环权重较高;灰色圈表示中间节点。线条粗细示意权重大小,数值均按式 (1) 计算。
交互实验 01 · 邻域聚合
一条消息,对结果贡献了多少?

选择接收节点,拖动任一节点的特征值。箭头指向本轮接收者,表格把每条消息拆成“输入 × 权重”。

默认参数下的图示;启用脚本后可调节3.00节点 12.00节点 21.00节点 32.00节点 45.00节点 5
进入当前接收节点的五项贡献
消息来源输入权重加权贡献
节点 13.00.4081.225
节点 22.00.3330.667
节点 31.00.3330.333
节点 42.00.0000.000
节点 55.00.0000.000
节点 2 的输出:2.225 · 权重之和:1.075
全图输出:(2.316, 2.225, 1.667, 3.041, 3.316)

对称归一化的行和不必等于 1。取消自环时,度数与全部边权会一并重算。

试一试:选择节点 2,只改变节点 5 的输入;这一层的输出不会变化。再选择节点 4,就能看到节点 5 的直接贡献。

图 2 把式 (1) 展开成可操作的消息计算。默认值复现正文的五节点链;对照模式分别使用行归一化与直接求和。本实验只计算传播矩阵与单通道信号的乘积,不包含学习权重或激活函数。

式 (1) 给出了聚合的计算方法。下面三节转向它的谱方法依据:先定义图上的频率和卷积,再说明多项式近似、一阶化简与重归一化分别保留和改变了什么。

3 谱方法基础:图上的频率与卷积

3.1 图频率与拉普拉斯二次型

图像卷积依赖规则网格上的平移结构。一般图没有统一的平移操作,而且节点重新编号不应改变模型表达的图结构。谱方法通过图拉普拉斯建立频域表示。先考虑非归一化拉普拉斯 \(L=D-A\),其二次型为:

\[ x^{\top} L\, x \;=\; \sum_{(u,v)\in E} \bigl( x_u - x_v \bigr)^{2} \]
(2)

展开即可验证:\(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\),则

\[ g_{\theta} \star x \;=\; U\, \operatorname{diag}(\theta)\, U^{\top} x \]
(3)
交互实验 02 · 图傅里叶变换
把信号拆成不同频率,再调节它们的增益

仍使用五节点链。先选一个频率模式或混合信号,再选择滤波器。两幅图的坐标尺度保持一致,虚线表示零值;石青表示正值,赭色表示负值。

滤波前:节点域的信号默认参数下的节点信号1.04节点 10.50节点 20.90节点 3-0.30节点 40.24节点 5
滤波后:节点域的信号默认参数下的节点信号0.69节点 10.74节点 20.55节点 30.15节点 40.09节点 5
频域操作:每个系数分别乘以增益
0.00
1.001.00
0.29
0.750.60
1.00
0.370.00
1.71
0.180.00
2.00
0.140.11
归一化拉普拉斯能量:1.467 → 0.128
滤波后信号:(0.690, 0.744, 0.554, 0.147, 0.093)

增加滤波强度时,高频增益下降得更快。混合信号中较快交替的分量因此先被压低。

试一试:切换到零频模式,再选互补高通。这个分量会完全消失;它的原始节点值虽有高低,按度数缩放后却不沿边变化。

图 3 式 (3) 的数值示意,采用未加自环的 \(P_5\) 的归一化拉普拉斯正交特征基。混合信号取 \(x=u_0+0.8u_1+0.8u_4\)。低通增益为 \(e^{-t\lambda}\),高通增益为 \(1-e^{-t\lambda}\),数值显示经舍入,显示的能量是 \(x^\top L_{\mathrm{sym}}x\)。两种响应用于演示谱滤波过程,并非原 GCN 的传播响应;节点纵向位置表示信号值。

式 (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\) 展开:

\[ g_{\theta'} \star x \;\approx\; \sum_{k=0}^{K} \theta'_k\, T_k(\tilde{L})\, x, \qquad \tilde{L} = \frac{2}{\lambda_{\max}}L - I \]
(4)

多项式滤波具有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 再推广这一结论。

交互实验 03 · 局部性
多走一跳,能看到哪些新节点?

把传播次数从 0 开始增加,观察信息可到达的范围。赭色是目标节点;同色节点与目标的最短距离相同,浅灰节点暂时在感受野之外。

默认参数下的图示;启用脚本后可调节1目标21 跳31 跳42 跳52 跳62 跳72 跳8未到达9未到达
可到达 7 个节点:1、2、3、4、5、6、7
恰在当前跳数的新节点:4、5、6、7

试一试:从节点 1 出发,先看 1 跳,再看 2 跳。节点 2 与 3 之间有边,但重复到达它们不会增加不同节点的数量。

图 4 最短路径展示 \(K\) 跳局部性。高亮范围是 \(K\) 阶多项式滤波可能依赖的输入集合,也是堆叠 \(K\) 层局部 GCN 时的结构感受野。它不表示每个节点都有非零的实际贡献:系数抵消、学习权重和非线性都可能改变贡献;一阶层与一般多项式滤波也不因此等价。

4.2 化简到一阶:四步代数,每步标明性质

GCN 先令 \(K=1\),再约束系数。以下将推导分为四步,以区分模型选择、谱尺度近似和恒等变形。

从式 (4) 到一阶滤波器的四步

① 截断(选择)。令 \(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_{\theta} \star x \;=\; \theta\,\bigl(I_N + D^{-1/2} A D^{-1/2}\bigr)\, x \]
(5)

此时,滤波器从逐频率独立增益变为受单个参数控制的直线响应。三种参数化方式的差别如下。

滤波器自由参数能表达的响应 \(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 次的结果。

0.1 1 10 100 1000 纵轴:向量范数(对数刻度) 0123 4567 8910 连乘次数 k(星形图,随机单位向量) 修正前(谱半径 2) 修正后(谱半径 1)
图 5 星形图上连续传播时的向量范数。未重归一化时,范数逐渐呈近似倍增趋势,10 次后从 1 增至约 442;重归一化后,范数经数次传播趋近于 0.48。纵轴为对数刻度,曲线表示纯传播,不含可学习权重与激活函数。

5.3 GCN 的逐层传播规则

将重归一化后的矩阵用于神经网络,每层执行特征变换、邻域聚合和非线性激活:

\[ H^{(l+1)} \;=\; \sigma\!\bigl(\, \hat{A}\, H^{(l)}\, W^{(l)} \,\bigr), \qquad \hat{A}=\tilde{D}^{-1/2}\tilde{A}\tilde{D}^{-1/2} \]
(6)
公式 (6) 的四个组成部分

\(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\),其前向模型为:

\[ Z = f(X, A) = \operatorname{softmax}\!\bigl(\, \hat{A}\; \operatorname{ReLU}\!\bigl(\hat{A} X W^{(0)}\bigr)\, W^{(1)} \,\bigr) \]
(7)
结构示意 · 两层 GCN
沿节点维聚合,沿特征维变换

每一行始终对应同一个节点。石青色小格示意特征通道;两层传播都使用同一张图,通道数则可以变化。

输入特征全部节点参与前向计算\(X:\ N\times C\)
第 1 层 · 隐表示聚合 → 线性变换 → ReLU\(H^{(1)}:\ N\times H\)
第 2 层 · 类别概率聚合 → 线性变换 → softmax\(Z:\ N\times F\)
传播矩阵决定“谁与谁混合”

左乘 \(\hat A\) 混合节点行;右乘 \(W^{(l)}\) 变换每行的特征通道。非线性施加在两次线性运算之后。

训练掩码决定“哪些行计入损失”

所有节点均产生预测,但训练交叉熵只读取训练标签对应的行。测试标签不进入训练损失。

同一层内,\(\hat A(HW)=(\hat AH)W\)。图中先聚合只是阅读顺序;实现可以根据维数先做特征变换,再聚合。
图 6 式 (7) 的前向数据流。小格仅表示矩阵的行与列,不编码真实数据或类别置信度;示意省略 dropout。训练标签决定监督位置,图结构则决定一个节点的输入能否影响这些位置。

训练交叉熵仅覆盖带标签节点:\(\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)\) 空间;训练还需要保存特征、隐层激活和参数,不能将邻接存储量当作全部内存开销。

下表列出三个引文网络共用的训练配置。实验中的层数选择应结合模型容量、正则化、验证策略与数据划分理解。

配置取值备注
隐层宽度16Cora、Citeseer、Pubmed 共用
Dropout0.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(训练耗时)
Cora2 708 / 5 429 / 72075.7%(Planetoid)81.5%(4 秒)
Citeseer3 327 / 4 732 / 62069.1%(ICA)70.3%(7 秒)
Pubmed19 717 / 44 338 / 32077.2%(Planetoid)79.0%(38 秒)
NELL65 755 / 266 144 / 210161.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 次随机权重初始化的平均分类准确率,单位为百分比。

传播模型CiteseerCoraPubmed对应章节
多层感知机(完全不用图)46.555.171.4第 1 节“只看特征”
切比雪夫 \(K=3\)69.879.574.4式 (4)
切比雪夫 \(K=2\)69.681.273.8式 (4)
一阶、两参数(论文式 6)68.380.077.5第 4.2 节第③步
单参数、未重归一化(式 5)69.379.277.4第 4.2 节第④步
只有一阶项(无自环)68.780.577.8第 2 节去自环对照
重归一化(式 6)70.381.579.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}^{\,k} x \;=\; \sum_i \lambda_i^{\,k}\, \langle x, u_i\rangle\, u_i \]
(8)

若图连通,加入正权自环后,\(\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\) 单调下降,因为一次传播的响应可能在高频处为负。应区分随深度衰减与随频率单调低通这两个命题。

交互实验 04 · 传播深度
两团不同的信号,会在反复聚合后变成什么?

左、右两团各是一个四节点环,中间可保留或移除桥边。每个节点都有自环(图中省略);圆内显示按含自环的度数缩放后的表示,便于观察平滑。正负颜色的尺度在传播前后固定。

初始信号默认参数下的图示;启用脚本后可调节1.73节点 11.73节点 21.50节点 31.73节点 4-0.50节点 5-0.58节点 6-0.58节点 7-0.58节点 8
传播 0 次默认参数下的图示;启用脚本后可调节1.73节点 11.73节点 21.50节点 31.73节点 4-0.50节点 5-0.58节点 6-0.58节点 7-0.58节点 8
距理论极限的误差还剩:100.0%
图连通且每个节点都有自环。传播越深,按度数缩放后的表示趋向同一个值;原始表示的极限仍可因度数不同而不同。
查看未缩放的节点表示与极限值

当前表示:(3.000, 3.000, 3.000, 3.000, -1.000, -1.000, -1.000, -1.000)

理论极限:(0.959, 0.959, 1.107, 0.959, 1.107, 0.959, 0.959, 0.959)

试一试:传播 60 次后移除桥边。此时会按新的图重新计算,两个连通分量仍可保持不同的平稳信号。

图 7 式 (8) 的纯传播实验:\(h^{(k)}=\hat A^k x\),圆内展示 \(h_i^{(k)}/\sqrt{\tilde d_i}\)。误差是 \(\|h^{(k)}-h^{(\infty)}\|_2\) 相对于初始误差的百分比;初始信号已在极限时记为 0%。切换图或初始信号时从新的输入重新计算。本实验没有学习权重、非线性或训练过程,因此不用于判断任意深层 GNN 的性能。

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\) 引入二次项,但模型也有相应的独立系数,不能据此否定换基结论。改变尺度可能改变固定系数时的输出、数值条件、系数正则化及优化路径;若再约束或捆绑系数,也必须重新分析函数族。

参考文献

  1. Kipf TN, Welling M. 2017. Semi-supervised classification with graph convolutional networks. International Conference on Learning Representations (ICLR 2017). arXiv:1609.02907.
  2. 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.
  3. Hammond DK, Vandergheynst P, Gribonval R. 2011. Wavelets on graphs via spectral graph theory. Applied and Computational Harmonic Analysis 30(2): 129–150.
  4. 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.
  5. 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.
  6. 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.
  7. 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.
  8. Hamilton WL, Ying R, Leskovec J. 2017. Inductive representation learning on large graphs. Advances in Neural Information Processing Systems 30: 1024–1034.
  9. 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.
  10. 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.
  11. 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.
  12. 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.