《Simple and Deep Graph Convolutional Networks》--论文阅读笔记

《Simple and Deep Graph Convolutional Networks》

简单和深度图卷积网络目录

《浅层而深度的图卷积网络：Simple and Deep Graph Convolutional Networks》

摘要

1. 引言（1.Introducción）

2. 先决知识（2.Preliminares）

3. GCNII模型（3.GCNII modelo）

4. 谱分析（4.Análisis espectral）

• 5. 其他相关领域研究综述

• 6. 实验分析与结果展示

• • 6.1. 半监督节点分类算法

• 6.2. 全监督节点分类算法

• 6.3 Inductive Learning: 这种学习方法基于归纳推理模式。

  • 6.4 Over-Smoothing Analysis for GCN: 在图卷积网络（GCN）中进行过度平滑化分析有助于理解其局限性。
  • 6.5 Ablation Study: 消融研究分析通过移除关键组件来评估模型性能的影响。
    总结：

主要作者包括魏哲巍等五位学者，在第ICML会议上发表了题为《...》的论文报告。报告内容详实丰富，在限定的篇幅内涵盖了多项创新性研究，并详细阐述了其理论基础及实验验证过程。论文共占用了11页内容，并附有相关参考链接可查询进一步信息

Abstract

图卷积网络(GCNS)是一种先进的图结构数据处理技术。

注：

**- vanilla GCN（原版GCN） ：Kipf and Welling introduced graph convolutional networks (GCNs) for semi-supervised learning tasks in their influential paper "Semi-supervised classification with graph convolutional networks" published in ICLR 2017. vanila GCN的详细解读可参考vanila GCN 论文解读

本研究探讨了深层次图卷积网络的设计与分析问题，并提出了一种改进型GCN（即GCNII）模型。该模型通过引入初始残差映射与单位映射等简单有效的技术手段，在原有基础模型的基础上实现了性能的显著提升。具体而言，在vanilla GCN模型的基础上进行了扩展后能够有效缓解过平滑现象的问题，并且随着网络深度的增加其性能表现得更加优异。值得注意的是即使在基础的GCN架构中加入残差连接也只能部分缓解这一挑战性问题因此表明浅层GCN在性能上优于深层设计的GCNs

1. Introduction

该网络通过将卷积操作扩展到图结构数据而实现了对图数据的学习能力提升。为了理解图数据的本质，“图形卷积”操作将相同的线性变换应用于节点及其所有邻居，并结合非线性激活函数实现了信息的传播。近年来研究者开发了多种变体，并成功应用于社会网络分析、交通流量预测以及生物医学领域的研究等关键领域。

尽管取得巨大成功, 但目前多数现代GCN架构均显简略或基础特性。虽然取得了巨大的成功, 但目前多数现代GCN架构均显简略或基础特性。这种简略结构限制了其从高阶邻居节点获取丰富信息的能力。然而, 增加更多层或引入非线性单元往往会降低这些模型的表现效果, 这种现象被称作over-smoothing现象, 即随着网络深度增加, 模型节点表示会趋向于收敛至相似值, 导致难以区分不同节点特征。RESNET通过残差连接在计算机视觉领域取得了显著成果, 并且这一解决方案对于训练非常深的神经网络是有效的。不幸的是, 在训练深度GCN时, 现有的2层架构仍无法与更深的结构相比。

最近若干项研究致力于缓解超平滑问题。其中JKNet(Xu等人, 2018年)引入了密集跳过连接机制来整合各层特征，并增强了节点表示的空间聚集特性。随后,DropEdge(Rong等人, 2020)提出了一种随机丢弃输入图中部分边的新策略以缓解过度光滑现象的影响。实验结果表明随着网络架构逐渐加深两种方法在一定程度上延缓了性能退化趋势。然而，在半监督学习任务中目前取得的最佳成果仍主要依赖于浅层模型的设计并因此对深化网络结构带来的潜在优势持保留态度。

除了SGC之外,还有其他方法将深度传播与浅层神经网络结合。Wu等人于2019年提出的SGC尝试通过在单个神经网络层中应用图形卷积矩阵的K次方来捕获图形中的高阶信息。Klicpera等人于2019a提出的PPNP和APPNP通过将个性化PageRank矩阵替代图的卷积矩阵的幂来解决过平滑问题。Klicpera等人于2019b提出的GDC则通过将个性化PageRank算法（由Page等人于1999提出）推广到任意图扩散过程来进一步扩展APPNP模型。然而这些方法仅在线性组合相邻特征时,在每一层中缺乏捕捉深层非线性结构的能力,这意味着它们仍属于浅层模型

综上所述，在构建能够有效防止过度平滑的GCN模型并深入探索其网络架构以实现最先进的结果时仍面临诸多未解之谜。这一难题促使在设计新型图神经网络时需要权衡网络深度是资源还是负担尚不明确。本文通过证明Vanilla GCN(Kipf&Well, 2017)可通过两个简单有效的修改扩展至深度架构从而肯定性地回答了这一开放性问题。特别地我们提出了一种基于初始残差与单位映射的图卷积网络(GCNII)，这是一种解决过平滑问题的深层GCN模型。在每一层初始残差从输入层建立跳过连接而单位映射则将单位矩阵叠加至权重矩阵中实证研究表明这两种简洁而巧妙的技术不仅能够有效防止过度平滑而且随着GCNII深度的增加其性能持续提升特别是在多种半监督与全监督任务中取得了新的最佳成果

此外，在研究GCN与GCNII模型时，默认对两者的理论特性进行了深入探讨。已知（Wu等人, 2019）通过叠加了k层叠加方式, 香草型GCN近似于具有预设系数的K阶多项式滤波器（）。研究表明, 这类滤波器本质上模拟的是惰性随机游走过程,最终趋于稳定状态向量,从而导致过度平滑现象的发生。（Wang等人, 2019）则指出, GCNII型模型能够实现不同系数下的K阶多项式谱滤波器表示能力。这一特性对于构建深度神经网络体系至关重要。我们还推导出了一般性的闭合表达式,并对香草型GCN的动力学特性进行了深入分析。实验结果表明,在多层GCN架构中，默认节点度数较高的节点更容易出现过度平滑现象

注解：
面对过平滑问题前人的研究：

在2018年中提出的JKNet架构通过密集跳过连接将各层输出进行整合，并旨在保留节点表示的空间特性

2.2020年研究者们建议通过从输入图中随机去除一部分边来缓解过平滑现象的影响。研究表明，在网络深度逐渐加深的情况下，这两种方法能够有效降低性能损失的程度

在半监督学习问题中，当前最好的成果仍然是基于浅层架构实现的。然而，在提升网络深度所带来的好处仍然值得怀疑

另一方面的研究 ，将深度传播和浅层神经网络相结合解决过平滑问题：

1.2019年 Wu等人提出的SGC旨在通过单一神经网络层中的图形卷积矩阵的K次方来提取高阶信息；
2.2019a年Klicpera等人提出的PPNP与APPNP则通过替代个性化PageRank矩阵来代替图的卷积矩阵幂，并缓解了过度平滑的问题。
3.2019b年Klicpera等人提出的GDC则通过将个性化PageRank扩展至任意图扩散过程，并实现了对APPNP的有效延伸。

现有的方法在各层中通过线性组合相邻特征来构建表征空间，在这种情况下未能充分捕捉深层非线性结构的强大表达能力。这表明尽管这些方法试图模仿人脑的学习机制，在深度特性上仍被限制为较浅的层次模型

鉴于此问题依然存在，在GCN模型的设计过程中，我们需要探索一种能够有效抑制过平滑现象的方法，并借助深度架构来实现最优性能的目标。然而这一关键挑战仍待进一步突破。

**设计新图神经网络挑战：**由于现有理论基础尚不完善，在应用网络深度时既可能充当资源支持者也可能成为瓶颈问题。
在此研究中，我们对经典的GCN与改进型GCNII模型展开了系统性探讨。不仅深入研究了其均衡状态下的闭合形式表达式，并全面剖析了原始GCN算法在不同场景下的收敛特性。

2. Preliminaries

符号。给定一个包含n个顶点和m条边的简单连通无向图G=(V,E)。我们称自环图为tilde{G}=(V, tilde{E})为在G中每个顶点添加一个自环边所形成的图，并使用集合{1, ..., n}来表示G及其自环图tilde{G}的所有顶点编号；对于顶点j∈V，则dj和dj+1分别表示其在G和tilde{G}中的度值。
令A为该图的邻接矩阵，并D为其度对角线矩阵。
则称L = I_n - D^{-1/2} A D^{-1/2}为此图的归一化拉普拉斯矩阵。
基于L的特征值分解UΛU^T（其中Λ为由L特征值构成的对角矩阵），我们有正则化信号x经过滤波器gγ（Λ）= diag(γ)后的图形卷积操作定义为：
y = gγ(L)x = U diag(gamma(U^T x))，
其中gamma ∈ R^{n×n}代表频域滤波系数向量。

Vanilla GCN. 推荐采用基于拉普拉斯矩阵的高阶多项式来近似图上的卷积操作:\mathbf{U} g_{\theta}(\Lambda) \mathbf{U}^{T}\bm{x}\approx\bm{U}\left(\sum_{l=0}^{K}\theta_l\bm{\Lambda}}^l\right)\bm{U}}^{\top}\bm{x}=\\left(\sum_{l=0}}^{K}\theta_l\\bm{L}}^l\\right)\bm{x} 其中θ∈ℝ^K+¹表示多项式的系数向量。

其中\theta \in \mathbf{R}^{K+1} 对应于多项式系数的向量。vanilla GCN设置K=1, \theta_{0}=2 \theta and \theta_{1}=-\theta 来获得卷积运算\mathbf{g}_{\theta} * \mathbf{x}=\theta\left(\mathbf{I}+\mathbf{D}^{-1 / 2} \mathbf{A} \mathbf{D}^{-1 / 2}\right) \mathbf{x} . 。最后，通过重整化技巧，用归一化版本\tilde{\mathbf{P}}=\tilde{\mathbf{D}}^{-1 / 2} \tilde{\mathbf{A}} \tilde{\mathbf{D}}^{-1 / 2}=\left(\mathbf{D}+\mathbf{I}_{n}\right)^{-1 / 2}\left(\mathbf{A}+\mathbf{I}_{n}\right)\left(\mathbf{D}+\mathbf{I}_{n}\right)^{-1 / 2}替换矩阵\mathbf{I}+\mathbf{D}^{-1 / 2} \mathbf{A} \mathbf{D}^{-1 / 2} 得到图的卷积层:
\mathbf{H}^{(\ell+1)}=\sigma\left(\tilde{\mathbf{P}} \mathbf{H}^{(\ell)} \mathbf{W}^{(\ell)}\right)其中σ:表示RELU操作。

SGCN：表明在图谱域上的\bar G中, \tilde L=I_n-\tilde D^{-1/2}\tilde A\tilde D^{-1/2}表示带自环边的图~\widetilde G的归一化拉普拉斯矩阵.进而,通过对信号x应用K层GCN模型,即

\left(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}\right)^K x = (I_n - \widetilde L)^K x,

实现了对原始信号的处理.研究表明,通过向每个节点引入自环边,矩阵L成功地缩小了基础图谱网络的频域特性.

APPNP 使用 PageRank获得K阶的固定滤波器。设f_θ(X)表示特征矩阵X上的两层全连接层的输出，PPNP的模型被定义为:
\mathbf{H}=\alpha\left(\mathbf{I}_{n}-(1-\alpha) \tilde{\mathbf{A}}\right)^{-1} f_{\theta}(\mathbf{X})由于个性化PageRank的特性，这种过滤器保持了局部性，因此适合于分类任务。也提出了APPNP，它取代了\alpha\left(\mathbf{I}_{n}-(1-\alpha) \tilde{\mathbf{A}}\right)^{-1} )中，用截断幂迭代法得到一个近似值。形式上，K跳聚合的APPNP定义为:
\boldsymbol{H}^{(\ell+1)}=(1-\alpha) \tilde{\boldsymbol{P}} \boldsymbol{H}^{(\ell)}+\alpha \boldsymbol{H}^{(0)}其中H^{(0)}=f_θ(X)。通过解耦特征变换和传播，PPNP和APPNP可以在不增加神经网络层数的情况下聚合来自多跳邻居的信息。

JKNet：首个深度图神经网络框架由Xu等人于2018年构建。在该架构的最后一层阶段中，JKNet通过融合不同图子结构特征的不同阶表示来进行学习与表征提取。研究表明：基于K层的传统GCN模型能够模拟自循环图˜G中进行K步随机行走的过程；而通过整合各层次全部表示的信息特性，则有效缓解了传统GCN模型存在的过度平滑问题。

DropEdge 最近的一项研究(Rong及其合著者, 2020年)表明, 随机从图\tilde{G}中移除若干边可能会减慢超平滑收敛的速度。定义\tilde{\mathbf{P}}_{\text {drop }}为移除任一条边后的重整化图对应的卷积矩阵，则其对应的数学表达式则可表示为：

\mathbf{H}^{(\ell+1)}=\sigma\left(\tilde{\mathbf{P}}_{\mathrm{drop}} \mathbf{H}^{(\ell)} \mathbf{W}^{(\ell)}\right)

3. GCNII Model

已有研究表明（Wu等人, 2019年），通过叠加K层基础型图卷积网络（vanilla GCN）可以在图谱域中模拟多项式滤波器\left(\sum_{\ell=0}^{K} \theta_{\ell} \tilde{\mathbf{L}}^{\ell}\right) \mathbf{x}。受限于固定系数这一特性，在多层GCN架构中存在局限性，导致过平滑现象的产生。为了实现深度GCN模型的能力提升需求，则必须使GCN能够表示任意系数的K阶多项式滤波器。我们证明这种可能性可通过两项简单技术实现：初始残差连接与恒等映射。具体而言，在第ℓ层中：

\mathbf{H}^{(\ell+1)} = \sigma\left( ((1-\alpha_{\ell}) \tilde{\mathbf{P}} \mathbf{H}^{(\ell)} + \alpha_{\ell} \mathbf{H}^{(0)}) ( (1-\beta_{\ell}) \mathbf{I}_{n} + \beta_{\ell} \mathbf{W}^{(\ell)} ) )

其中\alpha_{\ell}和{\beta_{\ell}}是两个超参数。\tilde{P} =\tilde{D}^{−1/2}\tilde{A}D^{−1/2}是具有重整化技巧的图形卷积矩阵。
注意，与Vanilla GCN模型(方程(1))相比，我们做了两点修改：

• 1)我们将平滑表示\tilde{P}H^{(\ell)}与第一层之间的初始残差连接进行结合；
  • 2)我们在\ell层权重矩阵W(\ell)中引入了恒等映射In。

初始剩余连接。 为了模仿ResNet中引入的跳跃连接机制[He et al., 2016]、[Kipf & Welling, 2017]均提出了通过整合平滑表示\tilde{P}H\ell与H^{(\ell)}来实现跳跃连接的方法。然而，在[Kipf & Welling, 2017]的研究中也表明这种设计仅能在一定程度上缓解过度平滑的问题；随着网络深度增加（随着堆叠的层越多），模型的整体性能仍会下降。

我们倾向于认为，在深度神经网络中采用剩余连接会导致信息传递效率低下，并建议应通过构建到初始表示H^{(0)}的直接连接来解决这一问题。即使我们堆叠了多个网络层，在这种情况下每个节点最终所得到的信息仍然能够保留来自输入层的一部分特征\alpha^\ell（其中\alpha^\ell可取值为0.1或0.2），从而保证每个节点最终表示至少包含输入特征的一小部分信息。此外我们还注意到H^{(0)}并不一定非要是特征矩阵X本身；当特征维度d较大时可以在X的基础上应用全连接层先对输入进行降维处理从而获得较低维度的初始表示H^{(0)}

最后，在个性化PageRank的研究中发现，在APPNP(Klicpera等人, 2019a)中引入了相似的技术以处理初始剩余连接的问题。然而,Klicpera等人, 2019a指出,反复进行非线性运算会导致模型过拟合这一现象的发生。因此,APPNP通过各层之间的线性组合实现了深度学习的基础框架这一目标。这表明仅凭初始残差无法拓展GCN模型达到更深的学习层次

恒等映射作为解决这一问题的关键手段。鉴于其局限性，在现有深度学习框架中缺乏有效的解决方案这一事实的基础上, 我们参考了ResNet网络中的思想, 采用了一种改进型的设计方案以提升模型性能并减少计算开销。于第\ell层, 我们将单位矩阵In加入到权重矩阵W^{(\ell)}$之中, 这一操作有助于维持梯度稳定性和加快收敛速度, 同时也能够有效缓解深度网络中的梯度消失问题, 这一策略不仅简化了网络结构, 而且还能提高模型的整体性能表现和泛化能力

• 类似于ResNet（Klicpera等人, 2019a）的设计理念, 恒等映射保证了深层GCNII模型至少与其实现相同性能的浅层版本.特别地,通过将β_ℓ设置得足够小,深度GCNII会忽略权重矩阵W^{(ℓ)},从而本质上模拟APPNP（公式（3））.
• 研究表明,特征矩阵不同维度间的频繁交互减少了模型在半监督任务中的性能表现.将平滑表示\widetilde{P}H^{(ℓ)}直接映射至输出空间未能维持这种交互关系.
• 在半监督学习中发现其具有显著优势. Hardt&Ma, 2017的研究表明,形如H^{(ℓ+1)}=H^{(ℓ)}(W^{(ℓ)}+I_n)的线性ResNet架构满足以下特性:
  1)最优权矩阵W^{(ℓ)}具有较小范数;
  2)唯一的临界点即全局极小值点.
  第一个特性表明我们能够通过施加严格的正则化来防止过拟合,而第二个特性则在基于有限训练数据的半监督学习场景下展现出良好的效果.

(Oono&Suzuki, 2020)通过理论分析表明,K层GCNS节点特征会收敛至一个子空间,这一现象导致信息丢失。值得注意的是,收敛速度与矩阵S的K次幂相关,其中s代表权矩阵W^{{(ℓ)}(ℓ=0,…,K−1)的最大奇异值。为了优化模型性能,我们将每个权矩阵W}{(ℓ)}替换为((1−β^ℓ W^{(ℓ)}) In + β_ℓ W^{{(ℓ)}),并对W}{(ℓ)}施加正则化处理,从而使得W^{(ℓ)}的范数减小。这样一来,(1−β_ℓ I_n + β_ℓ W^{{(ℓ)})的最大奇异值将趋近于1,进而导致s}K值不会显著增大,最终降低了信息丢失的风险。

确定β_\ell的方法旨在使权重矩阵的衰减程度随着层数的增长而动态调整。在实践中，则采用\beta_{\ell}=\log \left(\frac{\lambda}{\ell}+1\right) \approx \frac{\lambda}{\ell}这一公式来进行具体实现，并且其中\lambda被设定为一个超参数变量

与迭代收缩阈值相关联的方式进行连接。近年来有关于受优化启发而设计的新网络架构（Zhang and Ghanem, 2018；Papyan et al., 2017）的研究已取得进展。其核心理念在于：前馈神经网络可以被视为最小化某些函数的一种迭代优化过程，并假设采用更为先进的优化方法可能会有助于构建性能更优且更具解释性的网络架构（Li et al., 2018a）。基于此观点可知，在数值优化理论指导下构建高效且易于解析式的网络架构可能成为可能方向之一：例如我们将在下面展示，在我们的框架中采用恒等映射也是出于这一原因：我们相信Lasso是一种合理的选择：

\min _{x \in \mathcal{R}^{n}} \frac{1}{2}\|\mathbf{B} \mathbf{x}-\mathbf{y}\|_{2}^{2}+\lambda\|\mathbf{x}\|_{1}

类似于压缩感知理论，在本研究中我们假设x代表目标信号，并将测量矩阵B用于获取观测数据y。其中y记录了节点的基本属性而x则是嵌入网络尝试建模的目标变量。与传统的回归分析方法不同，在这种设定下测量矩阵B被定义为待优化参数，并通过反向传播机制进行动态调整以优化模型性能。这一研究方向与稀疏编码问题的核心理念高度一致，在以往的研究中已有诸多学者对此进行了深入探讨（Papyan等人, 2017年）。为了求解上述优化问题我们采用了迭代收缩阈值算法（Iterative Shrinkage-Thresholding Algorithm,ISTA）其中第(t+1)次迭代的具体更新规则如下：

\mathbf{x} at time step t+1 is equal to the projection operator onto the set defined by parameters \mu_t and \lambda, applied to the expression \left(\mathbf{x}_t - \mu_t (\boldsymbol{\Theta})^\top (\boldsymbol{\Theta}) \,\mathbf{x}_t + \mu_t (\boldsymbol{\Theta})^\top \,\boldsymbol{y}\right).

这里µ_t是步长，P_{β}(·)(β>0)是入门级软阈值函数：

P_{\theta}(z)=\left\{\begin{array}{lr} z-\theta, & \text { 当 } z \geq \theta \\ 0, & \text { 当 }|z|\right.
现在如果我们采用W来进行重新参数化，则上述更新方程的形式与我们之前采用的方法具有相似性。进一步说明的是，在这种情况下我们有X^{t+1}=P_{µtλ}((I+µ_tW)X_t+µ_tB^Ty)，其中项µ_tB^Ty相当于初始残差部分而(I+µ_tW)X_t则对应于我们的模型(5)中的恒等变换操作。在这里软阈值函数作为非线性激活单元的作用机制与ReLU激活函数具有类似的特性表现。综上所述 我们的网络架构设计特别是对恒等映射的运用 已经得到了迭代收缩阈值算法在求解套索问题时的有效解决方案 LASSO方法。

注解：
1.GCNII的第\ell层定义为:\mathbf{H}^{(\ell+1)}=\sigma\left(\left(\left(1-\alpha_{\ell}\right) \tilde{\mathbf{P}} \mathbf{H}^{(\ell)}+\alpha_{\ell} \mathbf{H}^{(0)}\right)\left(\left(1-\beta_{\ell}\right) \mathbf{I}_{n}+\beta_{\ell} \mathbf{W}^{(\ell)}\right)\right)
对vanilla GCN 模型公式 (equation(1))进行修改而来：

• 增加残链接
• 恒等映射

设计灵感：

1. 对ResNet中的残差模块和恒等映射进行优化。
2. 以解决Alice++网络（APPN）存在的问题为目标，在原有设计基础上补充恒等映射。

4. Spectral Analysis

4.1. Spectral analysis of multi-layer GCN.

考虑到具有残差连接的GCN架构：

\mathbf{H}^{(\ell+1)}=\sigma\left(\left(\tilde{\mathbf{P}} \mathbf{H}^{(\ell)}+\mathbf{H}^{(\ell)}\right) \mathbf{W}^{(\ell)}\right)

其中\tilde{\mathbf{P}}=其图形卷积矩阵采用了重整化策略（Wang等, 2019年）所提出的转移矩阵形式：

\frac{1_{n}+\bar{D}^{-1 / 2} \bar{A} \bar{D}^{-1 / 2}}{2}

这种转移矩阵模拟了贪婪的随机游走过程（方程6）。该随机游走过程表现出明显的收敛特性，并最终达到稳定状态（即过度平滑现象）。针对这一特性我们进行了深入分析，并通过实验验证了相关理论结论。具体而言：

• 我们推导出了平稳向量的闭式表达式；
• 分析表明：每个节点在其度数影响下表现出独特的收敛特性；
• 特别地：我们建立了以下理论定理。

定理1. 假设去环图\tilde{G}保持连通性。令\mathbf{h}^{(K)}=\left(2^{-1}\left(\mathbf{I}_{n}+\overline{\mathbf{D}}^{-1/2}\tilde{\mathbf{A}}\overline{\mathbf{D}}^{-1/2}\right)\right)^K\cdot\mathbf{x}用于表示对图信号x施加具有残差连接的K层重整化图卷积的过程。其中λ\tilde{G}被定义为去环图\tilde{G}的谱间隙——即归一化拉普拉斯矩阵\tilde{\mathbf{L}} = \mathbf{I}_n - \overline{\mathbf{D}}^{-1/2}\tilde{\mathbf A}\overline{\mathbf D}^{-1/2}的最小非零特征值——基于上述定义我们有以下结论：

当K值趋向于无限大时, h^{(K)}会趋近于\boldsymbol{\pi},其计算公式为\boldsymbol{\pi}=\frac{\left\langle\tilde{\mathbf{D}}^{1 / 2} \mathbf{1}, \mathbf{x}\right\rangle}{2 m+n},其中\tilde{\mathbf{D}}^{1 / 2} \mathbf{1}中的向量元素全部为一

其收敛速度基于以下方程进行计算：
\mathbf{h}^{(K)}=\pi \pm\left(\sum_{i=1}^{n} x_{i}\right) \cdot\left(1-\frac{\lambda_{\tilde{G}}^{2}}{2}\right)^{K} \cdot \mathbf{1}

在原始图G中顶点数量为m、边的数量为n。我们使用运算符±来表示对于每一个项h^{(K)}(J)及π(J)，其中j取值于1到n，
\left|\mathbf{h}^{(K)}(j)-\pi(j)\right| \leq\left(\sum_{i=1}^{n} x_{i}\right) \cdot\left(1-\frac{\lambda_{\tilde{G}}^{2}}{2}\right)^{K}

定理1的证明可以在补充材料中找到。

定理1包含两个推论：其中之一是当算法运行至第K步时，
表示为\boldsymbol{\pi}的向量值将趋近于
\frac{\left\langle\tilde{\mathbf{D}}^{1 / 2} \mathbf{1}, \mathbf{x}\right\rangle}{2 m+n}。
这种收敛现象导致结果过于光滑，
原因在于最终得到的向量\boldsymbol{\pi}仅限于
每个节点的程度以及初始信号x与矢量\tilde{\mathbf{D}}^{1/2}\mathbf{1}之间的内积。

收敛速率及其节点度方面，在公式（7）中可看出其收敛速率受总特征值之和\sum_{i=1}^{n} x_{i}以及谱间隙 \lambda_{\tilde{G}}共同影响。当深入探讨单个节点j的具体收敛情况时，则可将其最终状态表现为：

\mathbf{h}_{\text{k}}^{\text{(k)}}(j)=\sqrt{d_j + 1}\times \left(\sum _{\text{i}=1}^n \frac{\sqrt{d_i + 1}}{(2m + n)}x_i \pm \frac{\sum _{\text{i}=1}^n x_i\left(1 - \frac{\lambda ^2}{2}\right)^k}{\sqrt{d_j + 1}}\right)

从现象上看，在节点j的d_j较高（从而导致\sqrt{d_j + 1}较大）的情况下，则表明h^{(K)}(J)会更快地收敛到稳态π(J)。基于此观察结果，则提出以下假设。

猜想1： - 阶数越高的节点越容易出现过度平滑。

在我们的实验中，我们将在真实世界的数据集上验证猜想1。

4.2. Spectral analysis of GCNII

我们关注自环图\tilde{G}在频域中的特性。回顾时发现，在图信号x上施加的K阶多项式滤波器被定义为\left(\sum_{\ell=0}^{K} \theta_{\ell} \tilde{\mathbf{L}}^{\ell}\right) \mathbf{x}（Wu等人，2019年）。其中\tilde{L}代表的是归一化拉普拉斯矩阵\tilde{G}。θ_{k}表示多项式的系数参数。该种滤波器的实现方式使得K层GCN架构能够模拟固定系数θ下的K阶多项式滤波器特性。然而，在稍后将要展示的内容中表明，这种固定的系数设定限制了GCN架构在表达复杂特征方面的能力，并导致了过度平滑现象的发生。另一方面，在本研究中提出的新架构——K层GCNII模型则能够灵活表示任意系数设置下的K阶多项式滤波器特性

定理2

表现出色且略显过度光滑。

此外，在定理2中指出，在这种情况下（即当层数趋向于无穷大时），深度GCNII会收敛到一个特定的分布——该分布能够携带来自输入特征与图结构的关键信息。这一特性足以防止GCNII因过平滑而受到影响。具体而言，在整个过程中（即当层数趋向于无穷大时），h(K)=\left(\sum_{\ell=0}^{K} \theta_{\ell} \tilde{\mathbf{L}}^{\ell}\right) \mathbf{x}将被重新定义为h^{(K)}=\left(\sum_{\ell=0}^{K} \theta'_{\ell} \tilde{\mathbf{P}}^{\ell}\right) \cdot \mathbf{x}的形式。值得注意的是，在选择适当的参数θ'时（例如，在APPNP算法中（Klicpera等人, 2019a）或GDC算法中（Klicpera等人, 2019b）），当层数趋向于无穷大时（即当K→∞时），h(K)= \left(\sum_{\ell=0}^{∞} θ'_ℓ ̃P^ℓ）·x 将收敛到x的一个特定函数——其对应于邻接矩阵̃A及其输入特征向量x的个性化PageRank向量。

主要区别体现在：

1. θ是在输入特征与标签数据的基础上被学习得到的；
2. ReLU操作在每层结构中被应用。

5. Other Related Work

基于谱的方法在过去几年中受到了广泛关注。
1.2018c Li等人《Adaptive graph convolutional neural networks》
通过在训练阶段引入任务驱动的自适应图来增强模型的适应性

在2019年发表的研究中, 研究者团队采用了替代方案, 在图形神经网络领域取得重要进展

3 在2018年, Veliˇcković等研究者发表于《Graph Attention Networks》一文中,该论文提出了一种全局认知模型.该模型通过分析节点特征来推导每层边的权重参数.

4.2019年Abu-El-Haija等人，《A. Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing》通过融合不同距离的邻居信息推导出一种新的邻居混合关系学习机制。

5.2019年Gao&J团队发表在《Graph U-Nets》论文中,专注于将集合操作扩展至图神经网络领域.在无监督学习场景下,该研究通过最大化互信息的方法对图卷积编码器进行训练.

6. 在图嵌入模型中研究Pei于2020年提出了基于潜在维度空间的领域节点关系构建方法，并通过聚类分析提取出丰富的结构特征信息

7. 2019年Dave等人发表的论文《A. Neuralbrane: Neural bayesian personalized ranking for attributed network embedding》使用单个表示向量提取两个拓扑图嵌入中的信息以及节点属性。许多基于采样方法被提出用于提升GCN的扩展性。

8.2017年Hamilton等人，《 Inductive representation learning on large graphs.》该研究在每一层中采用特定数量的邻居节点。

黄 et al.在2018年开发了《Fastgcn: Fast learning with graph convolutional networks via importance sampling.》这一论文基于重要性采样设计了一个高效变体。

2019年Chiang及其团队在《Cluster-GCN: A Highly Efficient Method for Training Deep and Extensive Graph Convolutional Networks》一文中提出了该方法

6. Experiments

在这一部分中，我们将评估GCNII在各种开放图形数据集上与最先进的图形神经网络模型的性能。
Dataset and experimental setup.
我们使用三个标准引文网络数据集Cora、Citeseer和Pubmed进行半监督节点分类。在这些引文数据集中，节点对应于文档，边对应于引文；每个节点特征对应于文档的词袋表示，属于一个学术主题。对于全监督节点分类，我们还包括Chameleon、Cornell, Texas, and Wisconsin。这些数据集是Web网络，其中节点和边分别表示网页和超链接。每个节点的特征是相应页面的词袋表示。对于归纳学习，我们使用蛋白质-蛋白质相互作用(PPI)网络(Hamilton等人，2017年)，它包含24个图。在之前的工作(VELIˇCckovi‘c等人，2018年)的设置之后，我们使用20个图表进行训练，2个图表用于验证，其余的用于测试。表1汇总了数据集的统计数据。

不包括GCNII(5)的情况之外，在本研究中我们还包含另一种形式的模型 GCNII* 其采用不同的权重矩阵 \tilde{P} 和 H^{(\ell)} 来实现平滑表示

在第3节中提到，在我们所讨论的模型中定义了\beta_{\ell} = \log\left(\frac{\lambda}{\ell} + 1\right) ≈ \lambda / \ell ，其中λ被设定为一个超参数。

6.1. Semi-supervised Node Classification

Setting and Baselines.

我们采用学习速率为ε= ̇  的Adam SGD优化器（Kingma & Ba, 2015），并在预设的最大迭代次数下进行提前终止训练GCNII和GCNII*模型。在每个数据集中的全连接层结构相同的情况下，在每个数据集中对全连接层进行了相同的配置，并在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置，在每个数据集中对全连接层进行了相同的配置

与现有最优算法（SOTA）相比

对其他一系列深度模型进行了详细比较（Table 3）展示了不同网络层次下模型性能的具体表现。通过分别在JKNet、JKNet(Drop)以及inception(Drop)架构上进行了实验验证后发现，在CORA与Citeseer数据集上，随着网络层次的递增（即GCN-L层），模型的整体性能得到了显著提升（Table 3）。而在Pubmed数据集上，则显示出当网络结构被扩展至64层时，在Pubmed数据集上的性能表现维持在较高的水平（Table 3）。这种优异的表现得益于恒等映射技术的应用。

6.2. Full-Supervised Node Classification

我们对GCNII在全监督节点分类任务中的性能进行了考察，并遵循Pei等人（2020）的研究设计使用了Cora、Citeseer、Pubmed、Cornell、Texas和Wisconsin六个典型数据集进行实验验证。对于每个数据集中的各类别节点样本，在训练集占60%，验证集占20%，测试集占20%的比例下进行随机划分，并参考Pei等人（2020）建议的方法，在10次随机划分方案上综合评估了各模型在测试集上的表现指标值。所有模型的训练学习率均设置为固定值0.01，并将丢失率设定为固定值0.5；同时固定了隐藏层单元数量为64个，并基于验证集结果对其他超参数进行了优化筛选以获取最佳组合参数设置。完整的模型详细配置信息可参考补充材料部分进行查阅了解。在此研究的基础上我们还引入并考察了几种Geom-GCN变体模型（Pei等人, 2020），因为这些变体模型是其所属数据集中目前性能最优的代表方案

表5总结了各模型在分类任务中的平均准确率。研究团队参考了Pei等人(2020)的研究成果，在现有框架下进行了扩展。通过实验分析，在7个基准数据集中的6个案例中, 本研究提出的方法表现出了显著的优势, 这一发现凸显了所提出的深度GCN框架的有效性. 需要指出的是, 在威斯康星州的数据集测试中, 本方法较传统APPNP算法提升了约12%的性能指标. 这一显著提升的结果表明, 通过引入非线性激活函数的设计理念, 在多层网络结构中实现了预测性能较传统线性模型的重大突破.

6.3. Inductive Learning

在归纳学习任务中，在PPI数据集上基于9层GCNII和GCNII^*模型进行开发，并选定以下超参数组合：α取值范围设定在[0.001, 1.5]之间（α‘= ）；λ设定为1；学习率设定为1e^{-3}。考虑到训练数据量较大（velički et al., 2018），丢失率被设定为了2e^{-1}；同时令其权值衰减系数设为零以防止过拟合。在此基础上（VELIˇCckovič等人, 2018年），我们进一步增加了跳跃连接机制以加速网络收敛速度的提升过程。为了确保公平对比性（VELIˇckovič等人, 2018年），我们将该模型与以下先进架构进行了系统性评估：包括GraphSAGE (Hamilton等人, 2017)、VR-GCN (Chen等人, 2018b)、Gaan (Zhang等人, 2018)、GAT (VELIˇckovič等人, 2018)、JKNet (Xu等人, 2018)等七种主流算法进行了性能对比分析。表4详细列出了各指标对比结果。（此处表4应插入）。实验结果显示，在归纳学习任务中（VELIˇckovič等人, 2018年），本研究提出的GCNII架构显著超越了现有方法论框架下所有基准模型的表现水平——值得注意的是，在归纳学习任务中（VELIˇckovič等人, 2018年），通过增加网络深度我们成功实现了比现有方法更高的预测能力

6.4. Over-Smoothing Analysis for GCN

在之前的猜想中指出，在图论中随着节点的阶数升高（Order），更容易出现过度平滑的现象（phenomenon）。为了验证这一假设，在本研究中我们分别在Cora、Citeseer和Pubmed三个数据集上进行评估（assess）。具体而言，在每个图中我们将所有节点按照其度（Degree）进行分组（grouping），并将具有相同度范围的节点归为同一组（group）。这里采用区间划分的方式：将第i组定义为包含阶数位于区间[2i, 2i+1)内的所有节点（where i=0,1,…）。对于每一组而言，在图1中我们展示了不同网络深度下使用带有剩余连接（ResNet）的广度优先搜索神经网络模型所获得的平均准确率指标（accuracy metric）。通过观察实验结果我们可以得出以下几点结论：第一，在本研究中两层GCN模型的表现表明其性能会随着输入图谱特征空间维度的增长而有所提升（improve），这与预期结果一致（consistent），因为较高维度的空间能够提供更多关于邻接信息的潜在特征信息（feature information）。第二，在网络深度逐渐增加的过程中，高阶GCN模型对某些特定类型的样本表现出较差的学习能力（performance），具体表现为当模型拥有64层时无法对度值超过100的样本实现有效的分类目标达成（achieve）。这些实验结果进一步证实了我们的猜想：即当模型复杂度持续增加时会导致过光滑现象更加严重地影响到高阶GCN模型的表现效果。

6.5. Ablation Study

实验结果如图2所示,本研究对比分析了两项核心技术:残差连接机制与恒等映射策略.通过实验分析发现三个关键点:首先,在普通GCN架构中引入标识码嵌入可能会轻微削弱过度平滑现象的效果;其次,通过在基础GCN模型中添加初始残差连接机制可以有效缓解过度平滑问题;然而,即使仅使用两层网络结构也能达到最优性能水平.最后,综合采用恒等映射策略与初始残差连接机制能够显著提升网络深度对精度的影响.实验结果表明,这两种核心技术均为解决过平滑问题提供了重要思路

7. Conclusion

我们开发了GCNII这一创新模型，在深度学习领域具有重要地位。该模型通过简洁而高效的初始剩余连接机制与层次化单位映射设计，在防止过度平滑问题上展现出独特优势。基于理论分析并辅以实验验证可知，在K阶多项式滤波器表示能力方面 GCNII展现出显著优势。对于传统的多层GCNs 我们不仅从理论上进行了深入探讨还借助一系列实验验证了其有效性随着网络层数增加高阶节点确实更容易受到过度平滑的影响。在实际应用中 我们发现深度GCNII模型在半监督学习任务中表现尤为突出在全监督学习场景下也取得了令人瞩目的成绩这充分证明了该模型的有效性与广泛适用性未来的研究方向包括结合注意力机制进一步提升模型性能以及探究其在ReLU操作中的行为特点