摘要
谱图卷积GCN在深层结构中表现愈发拉胯，本文探究其“假死”（suspended animation）现象
当模型足够深时，模型将不再响应训练数据，不可学习。
本文中还引入了图残差网络。
图数据中的广泛连接将导致现有的简单残差无法工作。
1.引文
GNN因为节点之间的广泛连接使得它们的学习过程不再独立，而是强相关。
GRESNET 中创建的广泛连接的 high-ways不仅仅是将光谱图卷积层堆叠在一起，而是允许将节点的元特征或中间表示输入到模型的每一层。
2.相关
图神经网络
LOOPYNET 将节点的元特征接受到模型的每一层中，可以有效地对抗假死问题。
异构图神经网络利用一层注意力来捕捉邻居和网络异质性的影响，这在现实世界的复杂网络上不能很好地工作。
GEM Liu et al. (2018)
DIFNN专门为图结构化数据引入了一种扩散神经网络，由于所有层的神经门和残差输入的参与，该网络不会出现过平滑问题。
Zhang et al. (2018)
残差网络
Srivastava et al. (2015);
He et al. (2015);
Bae et al. (2016);
Han et al. (2016);
Gomez et al. (2017);
Tai et al. (2017);
Yu et al. (2017);
Ahn et al. (2018);
Li et al. (2018a);
Behrmann et al. (2019)
为基于梯度训练的深层网络引入残差
resnet简化了highway网络，删去了融合门
3.GCN的假死问题
层数加深，频域GCN的准确率恶化严重
3.1 重温香草图卷积
GCN基本的符号定义和公式
3.2 假死
第一步可以看做一步马尔科夫链（MC或者说是随机游走）
第二步可以看做全连接（FC）
考虑到调整向量维度的权值在节点间共享，则给定两个具有相同表示的节点，全连接层也将生成相同的表示。因此FC过程对MC的收敛贡献不大
于是，假设FC的映射为恒等映射，摘出MC形成多步MC
这时要使T能收敛，高度依赖于输入的图数据结构，即邻接矩阵A^
不可约非周期网络（？）
不可约：任两个节点是accessible（全连接图？）
非周期：不是二部图
如果一个无权、不可约、有限、非周期的图的邻接矩阵不对称，初始自任意分布的向量x，MC会有唯一一个固定的分布向量π
如果邻接矩阵对称，那π服从均匀分布
由此扩展到多层MC，which will reduce the learned nodes’ representations to the stationary representation matrix（这将把学习到的节点的表示减少到固定表示矩阵）
如果 GCN中存在足够多的嵌套MC，那么节点表示将从列标准化特征矩阵X减少到固定表示π。如果图还无向，那么固定表示
以上解释了假死的起因（？）
4.假死限制
4.1 基于输入结构
定义τ层后X收敛于π
将假死限制记作ζ
其中λ2是A^第二大的特征值，λn是最小特征值（所有特征值小于1）
如果输入图G是d-正则，那么可简化为
由此可见，输入图结构决定了GCN的最深层数
λ2衡量了G到无连接图的距离，λn衡量了到二部图的距离
当λ2 = 1或者λn = −1，则ζ → ∞，且模型不会假死
4.2 其他影响因素
网络度分布
如果G有向无权，则MC收敛出π，此时任两点学习表示的差距为
大多数图的节点度分布遵循幂律，即大多数节点的度相当小。因此大多节点的度相同或相似，差距几近消失
元特征编码
差距表示为
对于现行的GCN等源码中的独热编码，其中矩阵X也很稀疏。
也是稀疏向量，这使得最终结果值相当小
训练集大小
其实节点具有相同的表示和相同的标签不会降低模型的学习性能。如果它们属于不同的类，这对训练和测试都很有挑战
梯度消失/爆炸
上述元素并不全都涉及假死，但对GCN的实践应用都影响不少。
5.图残差网络
传统CNN的残差学习基于数据独立性假设，而图数据广泛连接
5.1 图残差学习
H(x) = F(x) + R(x)
本文将F(x)叫做H(x)的近似映射，将R(x)叫做图残差项
5.2 GRESNET架构
朴素（naive）残差和元（raw）残差
5.3 图残差学习效果分析
目标是学得函数H : X → Y
假设函数 H 可微、可逆且满足以下条件：
- ||(H’(x) − H’(y))z|| ≤ α · ||x − y|| · ||z||
- ||H−1(x) − H−1(y)|| ≤ β · ||x − y||
- Det(H’(x)) > 0
α和β是常数
其中
c = c1 · max{α · β · (1 + β), β · (2 + α) + α}， c1 > 0.
上式表明在中间连续几层中损失函数的范数变动不大，也就是说本模型维持了输入的有效表达并克服了假死
7.总结
本文研究现有GNN，尤其是谱图卷积的假死问题，理论上梳理，提出解决该问题的图残差模型，对比实验证实效果