图神经网络论文阅读(二十) Towards Deeper Graph Neural Networks

本文三位作者均毕业于Texas A&M University。
在深度图神经网络领域方面，本文完成了多项重要工作：
研究者指出，在当前图卷积运算中，若表示变换与传播过程存在过度耦合现象，则会对算法性能产生显著影响。
通过分离这两种操作间的关联关系，在更大范围内的节点特征提取上取得突破性进展。
基于此研究框架的基础上，在信息提取机制上实现了进一步优化与创新。

Graph Convolution Operations

从以下角度简要介绍图神经网络中的运算符，并说明其主要分为传播（PROPAGATION）和变换（TRANSFORMATION）两大类。

传播过程涉及对邻域信息的聚合；而转换过程中更新中心节点的信息起关键作用。值得注意的是，在GCN架构中，节点的信息通常通过特定机制进行表示。

在每一轮传播转化的过程中，在同一个CNN-step中同时完成转化与传播的过程。这也正是本文提出的"entanglement"这一概念所揭示的现象对图神经网络的表现产生了重要影响。这一现象与我们之前研究的一些论文有着相似的认识[1]例如APPNP[CNNII][GIN]等方法都是通过将聚合与更新操作分离来实现改进[2]尽管它们提出的机理可能不同[3]但通过解耦这两步操作却显著提升了图神经网络的效果[4]

EMPIRICAL AND THEORETICAL ANALYSIS OF DEEP GNNS

本文中最具吸引力的章节是从理论与实践两个维度展开探讨的。深入分析了其为何能够实现过平滑。

Quantitative Metric for Smoothness

平滑程度表征了网络中各节点间相似性的指标。为此开发了一种基于欧氏距离的方法来评估网络结构的过度平滑程度：该方法通过计算各节点间的相似性来判断是否存在过度平滑。

其中D(x_i,x_j)表示节点之间的欧氏距离：

在此基础上，提出全局平滑度量，也就是每个节点平滑度的均值：

Why Deeper GNNs Fail

首先，使用t-SNE可视化的技术直观上查看网络平滑性的变化：

可以看到，在layer5的时候网络已经无法很好地区分节点信息了（从纺锤状变为曲线）。可以看出随着layer5开始[模型]的能力出现了显著下降。那么这个降低是否是由过平滑造成的呢？为此统计测试集的准确率与平滑度量的变化

随着深度的加深，节点间相似程度呈下降趋势；即节点间的相似程度逐步降低；而该网络性能在后续层次中持续降低；这表明该算法性能下降与图平滑度并无显著关联；本文对5-6层网络表现出的'过度平滑'现象提出了疑问；特别指出，在节点表示需经历大量迭代传播的情况下才会出现过度平滑问题；然而实际上对于像Cora这样的相对较为稀疏的图，在仅进行6次传播前就已展现出性能下降现象；这一现象可能由过度平滑之外的因素所导致

对上述公式的可视化：

可观察到经过layer50处理后继续维持良好的效果。\n\n平滑度量指标的变化如下：

更深层次的模型能够充分利用更大的范围而不受负面影响的影响。我们注意到，在Cora中75-hop范围内的情况会逐渐导致性能下降。

Theoretical Analysis of Very Deep Models

本文最为棘手的部分在于阐述两种典型传播机制的过度平滑现象。具体而言，在GraphSAGE中采用SUM（MEAN）聚合，在GCN中采用类似的聚合方法。其中\hat{A}=A+I。

接下来证明当传播的次数无限大，上述两种聚合\widehat{A}^k_⊕，\widehat{A}^k_⊙都收敛成固定的值，说明过平滑的效应。
先定义一个全是1的行向量e∈R^{1*n}，Ψ(x)=x/sum(x)，Φ(x)=x/||x||。
Theorem 3.1 。给定一个连通图G，lim_{k→∞}\widehat{A}^k_⊕=Π_⊕，其中Π_⊕是一个矩阵其每一行都是π_⊕并且π_⊕=Ψ(e\hat{D})。
Theorem 3.2 。给定一个连通图G，lim_{k→∞}\widehat{A}^k_⊙=Π_⊙，其中Π_⊙=Φ(\hat{D^{1/2}}e^T)(Φ(\hat{D^{1/2}}e^T))^T。
Lemma 3.3 。给定一个图G，λ是\widehat{A}^k_⊕的特征值，其左特征向量为v_l ∈ R^{1×n}右特征向量为v_r∈ R^{n×1}，当且仅当λ是\widehat{A}^k_⊙的特征值，其左特征向量为v_l\hat{D}^{-1/2}∈ R^{1×n}右特征向量为\hat{D}^{1/2}v_r∈ R^{n×1}。也就是说这俩不同的矩阵之间是存在联系的。
Lemma 3.4 。给定一个图G，\widehat{A}^k_⊕，\widehat{A}^k_⊙总是有一个特征值1的相关特征向量，并且其他的特征值满足|λ|<1（也就是最大特征向量为1）。并且这两个矩阵的1特征值的左右特征向量分别表示为e\hat{D}，e^T，e\hat{D}^{1/2}，\hat{D}^{1/2}e^T。

Proof 3.1. 由于\widehat{A}^k_⊕的非负性且行的和为1，因此可以看成是马尔可夫链的动态转移矩阵。这个马尔科夫链是不可约的和非周期的，因为图G是连通的，而连通中包含了自环。根据其性质，lim_{k→∞}\widehat{A}^k_⊕=Π_⊕，Π是一个所有行都等于π的向量，满足马尔科夫稳态分布：π=πP，∑_iπ_i=1，也就是任意以概率P进行的游走都不会改变其概率的分布。对于π=πP也就是1π=πP，是特征值1对应的左特征向量。根据Lemma3.4，可以表示为e\hat{D}；带入到⊕这里，就是π_⊕=Ψ(e\hat{D})。这个证明还是蛮好理解的，前提是有一些先验知识。
Proof 3.2. \widehat{A}^k_⊙是一个对角化的对称矩阵，\widehat{A}^k_⊙=QΛQ^T是成立的，Q是单位正交矩阵，Λ的对角矩阵是特征值。那么其k阶的传播为：

因为Q*Q^T抵消后只剩下中间的主要\Lambda^k项。这个过程可以通过将对角矩阵转换成特征向量与特征值相加的形式来实现。根据定理3.4可知，在这种情况下最大的\lambda=1而其他\lambda_i < 1随着k \rightarrow \infty, 所有\lambda_i^k \rightarrow 0, 因此最终仅剩下对应\lambda=1的那个主成分及其左右特征向量之间的乘积关系成立即为：\Pi_\odot = \Phi(\hat{D^{1/2}}e^\top)\Phi(\hat{D^{1/2}}e^\top)^\top.

至于定理3.3、3.4的具体推导过程感兴趣的读者可以参考原文, 真的是太难复述了, 真的是浪费时间去复述这些内容……

DEEP ADAPTIVE GRAPH NEURAL NETWORK

有了之前的基础，本文的网络模型十分简单易懂：

经过深度前馈神经网络模型完成特征映射过程以获取中间结果Z；随后基于对称归一化的拉普拉斯矩阵通过l次传播机制实现信息扩散以生成第l层级表示H_l；在此基础上引入残差连接将各传播层级的结果拼接汇总形成最终表示H；构建自适应特征选择向量S其类似于注意力机制的作用域能够自动识别不同层次的重要程度；通过整个网络结构的学习与优化过程完成分类任务

EXPERIMENTAL STUDIES

半监督分类的性能：