该论文由中国人民大学、复旦大学、阿里巴巴合作完成，第一作者为中国人民大学研究生陈明，通讯作者为中国人民大学教授魏哲巍。
1. 摘要
Graph Convolutional Network via Initial residual and Identity mapping(GCNII)，它是普通GCN模型的扩展，应用了两种简单而有效的技术：初始残差（Initial residual）和恒等映射（Identity mapping）
2. 简介
主要说了以下几点：
-
GNN
-
传统GCN的局限：浅层
-
现有的一些解决方案：
- 使用密集跳跃连接组合每一层的输出，以保持节点表示的位置
- 从输入图中随机删除一些边
另外有一些将深度传播与浅层神经网络结合：
- SGC试图通过在单个神经网络层中应用图卷积矩阵的 k 次幂来捕获图中的高阶信息
- PPNP和APPNP用自定义的PageRank矩阵代替图卷积矩阵的幂来解决过平滑问题
- GDC进一步扩展了APPNP，将自定义PageRank推广到任意图扩散过程
但是，这些方法只是将每一层的相邻特征进行线性组合，而失去了深度非线性架构强大的表达能力，仍然是浅模型。
-
本文的主要工作：
-
在每一层，初始残差从输入层构建一个跳跃连接，而恒等映射在权值矩阵中添加一个单位矩阵。
-
对多层GCN和GCNII模型进行了理论分析。已知叠加 K 层的GCN本质上模拟了一个具有预定系数的 K 阶多项式滤波器。之前的研究指出，该滤波器模拟了一个懒惰的随机游走（lazy random walk），最终收敛到平稳向量，从而导致过平滑。
-
证明了 K K K 层 G C N I I GCNII GCNII模型可以表示任意系数的 K 阶多项式谱滤波器。这个特性对于设计深度神经网络是必不可少的。
-
推导了平稳向量的封闭形式，并分析了普通GCN的收敛速度。分析表明，在多层GCN模型中，度比较大的节点更有可能出现过度平滑的现象。
-
3. 相关研究
符号设定
U Λ U T \mathbf{U} \Lambda \mathbf{U}^{T} UΛUT：拉普拉斯矩阵的特征分解， Λ \Lambda Λ是 L L L特征值的对角矩阵， U \mathbf{U} U时酉矩阵
Vanilla GCN
GCN可以用拉普拉斯的K阶多项式近似表示：
U
g
θ
(
Λ
)
U
T
x
≈
U
(
∑
l
=
0
K
θ
l
Λ
l
)
U
⊤
x
=
(
∑
l
=
0
K
θ
l
L
l
)
x
(1)
\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T} \mathbf{x} \approx \mathbf{U}\left(\sum_{l=0}^{K} \theta_{l} \boldsymbol{\Lambda}^{l}\right) \mathbf{U}^{\top} \mathbf{x}=\left(\sum_{l=0}^{K} \theta_{l} \mathbf{L}^{l}\right) \mathbf{x} \tag{1}
Ugθ(Λ)UTx≈U(l=0∑KθlΛl)U⊤x=(l=0∑KθlLl)x(1)
其中，
θ
∈
R
K
+
1
\theta \in \mathbf{R}^{K+1}
θ∈RK+1代表多项式系数的向量。
Vanilla GCN设置 K = 1 , θ 0 = 2 θ , θ 1 = − θ K=1,\theta_0=2\theta,\theta_1=-\theta K=1,θ0=2θ,θ1=−θ，从而定义了卷积操作： g θ ∗ x = θ ( I + D − 1 / 2 A D − 1 / 2 ) x g_{\theta}*x=\theta(I+D^{-1/2}AD^{-1/2})x gθ∗x=θ(I+D−1/2AD−1/2)x（未归一化的形式）
SGC论文中表明，K 层的GCN对应于图
G
~
\widetilde{G}
G
的频谱域上一个固定的 K 阶多项式滤波器( polynomial filte)。
(
D
~
−
1
/
2
A
~
D
~
−
1
/
2
)
K
x
=
(
I
n
−
L
~
)
K
x
\left(\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}\right)^{K} \mathbf{x}=\left(\mathbf{I}_{n}-\tilde{\mathbf{L}}\right)^{K} \mathbf{x}
(D~−1/2A~D~−1/2)Kx=(In−L~)Kx
表明在每个节点上添加自身环，
L
~
\widetilde{L}
L
有效地缩小基础图的频谱
4. GCNII
已知 K 层GCN在图
G
~
\widetilde{G}
G
的谱域上模拟了一个系数
θ
\theta
θ固定的 K 阶多项式滤波器$ (\sumK_{l=0}\theta_l\widetilde{L}l)x
。
而
固
定
的
系
数
。而固定的系数
。而固定的系数\theta$限制了多层GCN模型的表达能力，从而导致过度平滑。为了扩展深层，需要使GCN能够表达一个具有任意系数的 K 阶多项式滤波器。
H
(
l
+
1
)
=
σ
(
P
~
H
(
l
)
W
(
l
)
)
\mathbf{H}^{(l+1)}=\sigma\left(\tilde{\mathbf{P}} \mathbf{H}^{(l)} \mathbf{W}^{(l)}\right)
H(l+1)=σ(P~H(l)W(l))
将
G
C
N
I
I
GCNII
GCNII的第
L
L
L层定义为：
H
(
l
+
1
)
=
σ
(
(
(
1
−
α
l
)
P
~
H
(
l
)
+
α
l
H
(
0
)
)
(
(
1
−
β
l
)
I
n
+
β
l
W
(
l
)
)
)
\mathbf{H}^{(l+1)}=\sigma\left(\left(\left(1-\alpha_{l}\right) \tilde{\mathbf{P}} \mathbf{H}^{(l)}+\alpha_{l} \mathbf{H}^{(0)}\right)\left(\left(1-\beta_{l}\right) \mathbf{I}_{n}+\beta_{l} \mathbf{W}^{(l)}\right)\right)
H(l+1)=σ(((1−αl)P~H(l)+αlH(0))((1−βl)In+βlW(l)))
其中
α
l
\alpha_l
αl 和
β
l
\beta_l
βl 是后续需要讨论的两个超参数。
对于原始GCN（公式1）的改进：
-
将带有初始残差的平滑表示 P ~ H ( l ) \mathbf{\widetilde{P}H^{(l)}} P H(l)与第一层 $H^{(0)} $结合
-
在第 l l l个权重矩阵 $W^{(l)} $上添加了一个恒等映射 I n \mathbf{I_n} In
Initial residual connection
GCN+ResNet的缺点：
为了模拟ResNet中的残差结构，GCN中提出可以将结合平滑表示 P ~ H ( l ) \widetilde{P}H^{(l)} P H(l) 与 $H^{(l)} $结合。但是只是部分程度上减轻了过平滑的问题，随着层数加深模型准确率依然会下降。
所以，与其使用剩余连接来融合来自前一层的信息，不如构建一个与初始表示 H ( 0 ) H^{(0)} H(0) 的连接。初始残差连接确保了即使我们堆叠了许多层，每个节点的最终表示也都至少保留了来自输入层的部分 α l \alpha_l αl 输入。
可以简单地设置 α l = 0.1 \alpha_l=0.1 αl=0.1 或 $\alpha_l=0.$2，这样每个节点的最终表示至少包含输入特征的一部分。
采用类似APPNP的方法，对个性化PageRank，实现初始残差连接。但是，APPNP还表明，对特征矩阵执行多个非线性操作将导致过度拟合，从而导致性能下降。所以，APPNP在不同层之间施加线性组合，因此仍然是一个浅模型。这表明了单独的初始残留的想法不足以延伸GCN到深入模特。（后续深入思考）
Identity mapping
第 L L L 层中，在权重矩阵 W ( l ) W^{(l)} W(l) 中添加了一个单位矩阵 I n \mathbf{I_n} In，原因如下：
-
跟ResNet类似，恒等映射保证了深度模型至少与浅层模型准确率相同。
-
《Predict then propagate: Graph neural networks meet personalized pagerank》表明，在半监督任务中，特征矩阵的不同维数之间频繁的相互作用会降低模型的性能。直接将 P ~ H ( l ) \widetilde{P}H^{(l)} P H(l) 映射到输出中会减小类似的交互。
-
《Identity matters in deep learning》将ResNet写成 H ( l + 1 ) = H ( l ) ( W ( l ) + I n ) H^{(l+1)}=H^{(l)}(W^{(l)}+I_n) H(l+1)=H(l)(W(l)+In)，则满足以下性质：
（1）最优权重矩阵 W ( l ) W^{(l)} W(l) 具有较小的范数（允许我们对 W ( l ) W^{(l)} W(l) 进行强正则化以避免过拟合）
（2） 唯一的临界点是全局最小值（在训练数据有限的半监督任务中是可取的）
设置$ \beta_l$ 的原则是：确保权重矩阵的衰减随着堆叠的层数增加而自适应地增加。作者设 β l = l o g ( λ l + 1 ) ≈ λ l \beta_l=log(\frac{\lambda}{l}+1)\approx\frac{\lambda}{l} βl=log(lλ+1)≈lλ ， λ \lambda λ 为超参数。
Connection to iterative shrinkage-thresholding
iterative shrinkage-thresholding：迭代收缩阈值
(后续整理)
5. Spectral Analys 谱域分析
多层GCN分析
添加Residual connection的GCN：
H
(
ℓ
+
1
)
=
σ
(
(
P
~
H
(
ℓ
)
+
H
(
ℓ
)
)
W
(
ℓ
)
)
\mathbf{H}^{(\ell+1)}=\sigma\left(\left(\tilde{\mathbf{P}} \mathbf{H}^{(\ell)}+\mathbf{H}^{(\ell)}\right) \mathbf{W}^{(\ell)}\right)
H(ℓ+1)=σ((P~H(ℓ)+H(ℓ))W(ℓ))
去掉非线性的激活函数之后，表示为：
h
(
K
)
=
(
I
n
+
D
~
−
1
/
2
A
~
D
~
−
1
/
2
2
)
K
⋅
x
\mathbf{h}^{(K)}=\left(\frac{\mathbf{I}_{n}+\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}}{2}\right)^{K} \cdot \mathbf{x}
h(K)=(2In+D~−1/2A~D~−1/2)K⋅x
因此，此类GCN仅能表达固定系数的K阶多项式滤波器。注意固定系数的K阶多项式滤波器并不一定会导致过平滑，然而GCN所对应的K阶多项式系数实际上是在模拟 lazy random walk，该类随机游走会收敛到一个与初始状态（即节点特征）无关的稳态分布。
思考
- 从谱域的角度入手，围绕ResNet做工作
- 借鉴了很多APPNP的思路
- 有点像综述文章，记录了很多前人的工作
- 很多工作本质上都是在加大浅层的权重，感觉这种操作很生硬，也不具有普遍性，能有更合适的求权重的方法吗？