Simple and Deep Graph Convolutional Networks

论文笔记 / 图学习
字数统计: 6.7k   |   阅读时长≈ 31 分钟

https://arxiv.org/abs/2007.02133

https://github.com/chennnM/GCNII

Simple and Deep Graph Convolutional Networks

我的启发：

  1. 这个方法存不存在什么弊端？
  2. 收敛速度和节点度的关系今后能不能利用上？

1. 简介

1.1 摘要

Graph convolutional networks (GCNs) are a powerful deep learning approach for graph-structured data. Recently, GCNs and subseque-nt variants have shown superior performance in various application areas on real world datasets. Despite their success, most of the current GCN models are shallow, due to the over-smoothing problem. In this paper, we study the problem of designing and analyzing deep graph convolutional networks. We propose the GCNII, an extension of the vanilla GCN model with two simple yet effective techni-ques: Initial residual and Identity mapping. We provide theoretical and empirical evidence that the two techniques effectively relieves the problem of over-smoothing. Our experiments show that the deep GCNII model outperforms the state-of-the-art methods on various semi- and full-supervised tasks. Code is available at https://github.com/chennnM/GCNII.

GCN是用于图结构数据的一种强大的深度学习方法。最近，GCN及其一些变体在不同领域的真实数据集上都取得了很好地表现。尽管GCNs已经比较成功了，但是由于过平滑问题，现有的GCN模型都比较shallow。在这篇文章中，我们研究并分析了如何设计深层GNN模型。我们提出了GCNII模型——通过Initial residual和Inentity mapping两个技术对GCN模型进行了改进。我们提供了理论上和经验上的证据表明这两个技术有效的缓解了过平滑问题。我们的实验表明深层GCNII模型可以在不同的半监督和全监督任务中取得最优的表现。代码发布在https://github.com/chennnM/GCNII。

1.2 背景

近些年来，GCNs及其各种变体被成功应用于社交网络、交通预测、生物、推荐系统、计算机视觉中。但是现有的大部分GCN模型都是shallow的，比如GCN和GAT都是在2层时取得最好的效果，这限制了GCN模型从高阶领域中提取信息的能力。但是，通过堆叠模型或者添加非线性层会导致模型性能下降，这也就是我们常说的**“over-smothing”现象——随着模型层数的增加，节点的表示收敛于同一个值，导致节点无法被区分**。

1.2.1 为什么产生过平滑？

https://blog.csdn.net/zhouchen1998/article/details/109741134

https://zhuanlan.zhihu.com/p/124727955

  • 直觉上的理解

    一层GCN相当于对一阶邻域信息进行聚合，随着GCN深度的增加，对于连通图，每个节点都逐渐聚合了整个图的信息，所有节点的特征都会趋同化。

  • 从频域角度

    GCN可以看作一个低通滤波器（ Revisiting Graph Neural Networks: All We Have is Low-Pass Filters ），这种特性可以让信号变得更加平滑，但是平滑操作过多的话会导致节点特征趋同，丧失多样性。

    GCN中一种常用的正则化拉普拉斯矩阵定义为：Lsym~=I−D~−12LD~−12=I−L~s\tilde {L^{sym}}=I-\tilde D^{-\frac{1}{2}L\tilde D^{-\frac{1}{2}}}=I-\tilde L_s，\tilde L_s=U\tilde\and U^T特征值范围是0∼20\sim2，所以有：

    \tilde{L^{sym}}=I-\tilde L_s=I-U\tilde\and U^T=I-\tilde L_s=U(I-\tilde\and)U^T

    可以看出Lsym~\tilde{L^{sym}}的特征值范围是(−1,1)(-1,1)。 在信号与系统中，我们可以将信号转换到频域，通过频率响应函数滤波，再将信号转换到时域完成滤波的操作。这里的频率响应函数为(I-\tilde\and)\in(-1,1)。不难看出，它对信号进行了低通滤波。 (暂时不懂)

    堆叠K层GCN时，矩阵Lsym~\tilde{L^{sym}}被乘了k次，我们将其展开：

    \begin{aligned} \tilde{L^{sym}}^k&=(I-\tilde L_s)^k\\ &=U(I-\tilde\and)^kU^T\\ &=Udiag((1-\tilde\lambda_1)^k,(1-\tilde\lambda_2)^k,...,(1-\tilde\lambda_n)^k)U^T \end{aligned}

    其中(1−λ~i)k(1-\tilde\lambda_i)^k只有在当λ~i=0\tilde\lambda_i=0时，(1−λ~i)k≡1(1-\tilde\lambda_i)^k\equiv 1，其余情况下(1−λ~i)k(1-\tilde\lambda_i)^k的绝对值都不超过1，所以limk→+∞(1−λ~i)k=0\mathop{lim}\limits_{k\rightarrow +\infty}(1-\tilde\lambda_i)^k=0。

    由于拉普拉斯具有性质：n维拉普拉斯矩阵具有n个非负特征值，0特征值的个数等于连通图的个数。假设只有1个连通图，将特征值从小到大排列λ1≤λ2≤...≤λn\lambda_1\leq\lambda_2\leq...\leq\lambda_n，则有：

    limk→+∞(1−λ~1)k=0\mathop{lim}\limits_{k\rightarrow+\infty}(1-\tilde\lambda_1)^k=0

    此时有:

    limk→+∞Lsym~x=Udiag(1,0,...,0)UTx=<x⋅u1>u1=x^(1)⋅u1\begin{aligned} \mathop{lim}\limits_{k\rightarrow+\infty}\tilde{L^{sym}}x&=Udiag(1,0,...,0)U^Tx\\ &=<x·u_1>u_1\\ &=\hat x(1)·u_1 \end{aligned}

    u1=D12⋅1u_1=D^{\frac{1}{2}}·1，是矩阵L~s\tilde L_s特征值0对应的特征向量，该向量是一个处处相等的向量。所以，如果对一个图信号不断进行平滑操作，最终会得到一个没有区分性的、处处相等的图信号。

  • 从空域角度

    Representation Learning on Graphs with Jumping Knowledge Networks

    从空域角度，也就是从空间上来看，GCN本质上是在聚合邻居信息，对于任意一个节点，GCN每增加一层，相当于聚合了更高一阶的邻居节点的信息。我们将聚合的最高邻居节点的阶数称之为聚合半径，可以发现，随着GCN层数增加，节点的聚合半径也在变大，一旦达到某个阈值，该节点可覆盖的节点就会和全图节点一致。如果层数很多，每个节点覆盖的节点都会收敛到全图节点，这样就导致每个节点学习到的特征就趋同化。

上图是论文中的一个实验结果图。a和b分别对两个不同方块节点进行信息聚合，可以看到四层GCN后，两个节点虽然收敛半径一样，但是覆盖到的节点差距很大。如果我们对b在进行一次聚合后发现方块节点的覆盖节点迅速增加到图的中心区域，此时两个方块节点聚合的节点网络趋于一致，对其区分会很困难。

1.2.2 针对过平滑问题的现有工作

最近，一些工作也尝试着解决过平滑问题。

  1. JKNet

    通过skip connections整合每一层的输出，来保持节点表示的局部性。

  2. DropEdge

    通过去掉输入图中的部分边可以缓解过平滑的影响。

实验表明，上面这两种方法只能缓解过平滑问题，半监督任务中仍然是浅层模型取得最好结果。还有一些方法尝试构建深层简单神经网络。这些模型在每一层都是对邻居信息进行线性聚合，丢失了深层非线性架构的强大表示能力，这也就意味着它们本质上还属于浅层模型。

  1. SGC
  2. PPNP和APPNP
  3. GDC——对APPNP进行了拓展

1.2.3 作者解决方案

本文作者工作：

  • 作者基于Initial residual和Identity mapping提出了一种GCN改进模型GCNII——一个解决了过平滑问题的深度GCN模型。

  • Wu等人提出了通过堆叠K层，普通的GCN模型本质上模拟了一个有固定的系数的K-th阶多项式滤波器。作者证明了K层GCNII模型可以模拟一个有任意系数的K阶多项式谱滤波器。

  • 另外作者通过实验得到了普通GCN最终收敛得到的静态向量，分析表明在多层GCN模型中，度更高的节点更可能产生过平滑问题。

符号定义：

  1. 连通无向图：G=(V,E)G=(V,E)，有n个顶点m条边。
  2. G~=(V,E~)\tilde G=(V,\tilde E)表示self-looped图。
  3. {1,...,n}\{1,...,n\}表示图中节点ID，djd_j和dj+1d_j+1表示图G和G~\tilde G中第j个节点的度。
  4. A表示邻接矩阵，D表示度矩阵，那么图G~\tilde G中的邻接矩阵和度矩阵分别为A~=A+I\tilde A=A+I和D~=D+I\tilde D=D+I
  5. X∈Rn×dX\in R^{n\times d}表示节点特征矩阵，每个节点vv关联一个d维特征向量XvX_v
  6. 正则化的拉普拉斯矩阵：L=In−D−1/2AD−1/2L=I_n-D^{-1/2}AD^{-1/2}

2. GCNII模型

Wu等人证明通过堆叠K层，GCN在图G~\tilde G模拟了一个K阶多项式滤波器(∑l=1KθlL~l)x(\sum_{\mathcal l=1}^{K}\theta_l\tilde L^l)x，其系数为固定的θ\theta。**这个固定的系数限制了多层GCN的表达能力，从而导致过平滑。**如果我们能让GCN模拟出一个有任意系数的K阶多项式滤波器，那么就能将GCN拓展成真正的深层模型。作者证明了可以通过Initial residual connection和Identity mapping两个简单技术就可以实现这个。作者定义GCNII模型如下：

\begin{equation} H^{(l+1)}=\sigma\Big(\tilde PH^{(l)}W^{(l)}\Big)\\ H^{(l+1)}=\sigma\Big(\Big((1-\alpha_l)\tilde PH^{(l)}+\alpha_lH^{(0)}\Big)\Big((1-\beta_l)I_n+\beta_lW^{(l)}\Big)\Big) \end{equation}

其中αl\alpha_l和βl\beta_l是超参数。和普通GCN相比，作者主要做了两点改进：

  1. 将P~H(l)\tilde PH^{(l)}和初始输入H(0)H^{(0)}进行了残差连接
  2. 给第l层的权重矩阵W(l)W^{(l)}添加了一个单位矩阵InI_n

2.1 Initial residual connection

为了模拟计算机视觉中的ResNet，Kipf&Welling在2017年使用残差连接，但是结果表明这种残差连接方式只能减缓过平滑问题，随着层数增加，模型性能还是会下降。

作者提出要和初始特征H(0)H^{(0)}构建残差连接，这样如果迭代很多层的话，最终得到的节点表示至少包含了一小部分节点的原始特征。在实际应用中，我们可以设置αl=0.1 or 0.2\alpha_l=0.1\ or\ 0.2。

Klicpera等人在APPNP模型中也在PageRank中采用了类似的初始残差连接方式。但是APPNP这篇论文中发现在特征矩阵上进行多层非线性操作会导致过拟合从而使得模型降低，因此APPNP模型中在不同层之间使用线性连接，所以APPNP本质上还是一个浅层模型。这启发了作者，仅仅和初始特征进行残差连接不足以将GCN变成一个深层模型，所以作者在此基础上添加了一个Identity mapping。

2.2 Identity mapping

为了修正APPNP模型的不足，作者借用ResNet中identity mapping的思想，在第l层给权重矩阵W(l)W^{(l)}添加一个单位矩阵InI_n。下面是作者提出该想法的动机和目的：

  1. 和ResNet的动机一样，identity mapping可以保证深层GCNII模型至少可以取得和浅层模型一样的表现（为什么？）。如果将βl\beta_l设置的很小，那么模型就会忽略权重矩阵W(l)W^{(l)}，本质上和APPNP模型类似。

  2. Klicpera等观察到特征矩阵不同维度的频繁地交互会导致模型在半监督任务中性能下降，直接将平滑表示P~H(l)\tilde PH^{(l)}映射成输出可以减少这类型交互。

  3. Identity mapping已经被证明了在半监督任务中十分有效。在Hardt&Ma的论文中说明了H(l+1)=H(l)(W(l)+In)H^{(l+1)}=H^{(l)}(W^{(l)}+I_n)形式的线性残差网络具有以下性质：

    • 优化权重矩阵W(l)W^{(l)}的norms很小
    • 只有重要的点是全局最小的

    第一个性质可以帮助在WlW^l添加正则化防止过拟合，第二个性质适用于训练数据很少的半监督任务。

  4. Oono等人从理论上证明了K层GCN提取到的节点特征会收敛到一个子空间，导致信息丢失。特征收敛的概率取决于sKs^K，其中s表示权重矩阵W(l)W^{(l)}的最大特征值。通过用(1−βl)In+βlW(l)(1-\beta_l)I_n+\beta_lW^{(l)}替代W(l)W^{(l)}可以让W(l)W^{(l)}的norm变小，(1−βl)In+βlW(l)(1-\beta_l)I_n+\beta_lW^{(l)}的特征值会接近1，因此最大特征值s会接近1，这样sKs^K会比较大，可以缓解信息损失。

对于超参βl\beta_l的选择需要保证随着模型层数的增加，权重矩阵逐渐衰减。在实际应用中，我们设置βl=log(λl+1)≈λl\beta_l=log(\frac{\lambda}{l}+1)\approx\frac{\lambda}{l}，其中λ\lambda是超参。

3. 谱分析

3.1 多层GCN的谱分析

考虑下面的GCN模型：

H(l+1)=σ((P~H(l)+H(l))W(l))H^{(l+1)}=\sigma\Big(\Big(\tilde PH^{(l)}+H^{(l)}\Big)W^{(l)}\Big)

Wang等人在“ daptive graphconvolutional neural networks”一文中提出：**上面的公式其实模拟的是一个转移矩阵为In+D~−1/2A~D~−1/22\frac{I_n+\tilde D^{-1/2}\tilde A\tilde D^{-1/2}}{2}的“lazy random walk”。这样一个lazy random walk最终会收敛成一个静态状态，从而导致过拟合（有待研究）。**作者得到了这个封闭的静态向量并分析其收敛率，得到一个结论：每个节点的收敛速度取决于其度。

3.1.1 定理1

假设自环图G~\tilde G是连通的，h(K)=(In+D~−1/2A~D~−1/22)K⋅xh^{(K)}=\Big(\frac{I_n+\tilde D^{-1/2}\tilde A\tilde D^{-1/2}}{2}\Big)^K·x表示对图信号进行带有残差连接的正则化图卷积操作，λG~\lambda_{\tilde G}表示图G~\tilde G的spectral gap，即正则化拉普拉斯矩阵L~\tilde L的最小非负特征值。我们有如下结论：

  • 随着K趋向于无穷大，h(K)h^{(K)}收敛于π=<D~1/21,x>2m+n\pi=\frac{<\tilde D^{1/2}1,x>}{2m+n}，D~1/21\tilde D^{1/2}1中的1表示全1向量。

  • 收敛速度取决于h(K)=π±(∑i=1nxi)⋅(1−λG~22)Kh^{(K)}=\pi\pm\Big(\sum\limits_{i=1}^nx_i\Big)·\Big(1-\frac{\lambda_{\tilde G}^2}{2}\Big)^K。

    注：±\pm操作表示∣h(K)−π∣≤(∑i=1nxi)⋅(1−λG~22)K|h^{(K)}-\pi|\leq\Big(\sum\limits_{i=1}^nx_i\Big)·\Big(1-\frac{\lambda_{\tilde G}^2}{2}\Big)^K

其中m和n分别表示原始图G中节点和边的数量。

根据定理1，我们可以得出两个结论：

  1. GCN的K阶表示h(K)h^{(K)}收敛于一个向量π=<D~1/21,x>2m+n\pi=\frac{<\tilde D^{1/2}1,x>}{2m+n}，由于该向量只包含两种信息：每个节点的度，以及原始图信号x和D1/21D^{1/2}1之间的内积，从而导致GCN过平滑（这个为什么？因为没有包含图结构信息，而初始节点特征都是1？）。

  2. 这个h(K)=π±(∑i=1nxi)⋅(1−λG~22)Kh^{(K)}=\pi\pm\Big(\sum\limits_{i=1}^nx_i\Big)·\Big(1-\frac{\lambda_{\tilde G}^2}{2}\Big)^K公式表明收敛速度取决于所有特征的和∑i=1n\sum_{i=1}^n以及spectral gapλG~\lambda_{\tilde G}。如果我们针对单个节点j，可以得到下列式子：

    h(K)(j)=dj+1(∑i=1ndi+12m+n±∑i=1nxi(1−λG~22)Kdj+1)h^{(K)}(j)=\sqrt{d_j+1}\Big(\sum\limits_{i=1}^n\frac{\sqrt{d_i+1}}{2m+n}\pm\frac{\sum_{i=1}^nx_i(1-\frac{\lambda_{\tilde G}^2}{2})^K}{\sqrt{d_j+1}}\Big)

    这表明：如果节点j的度djd_j越大，dj+1\sqrt{d_j+1}越大，h(K)(j)h^{(K)}(j)收敛到静态向量π(j)\pi(j)的速度越快。基于这个事实，我们可以得到下列推论：

    **推论1：**度高的节点遭受过平滑的可能性越大。

3.1.2 证明

引理1Chung：piK=(In+A~D~−12)Keip_i^{K}=(\frac{I_n+\tilde A\tilde D^-1}{2})^Ke_i表示自环图G~\tilde G中节点i的K-th转移概率向量，\lambda_\tilde G表示图G~\tilde G的spectra gap。piKp_i^K的j-th entry有如下限制：

\Big|p_i^{(K)}(j)-\frac{d_j+1}{2m+n}\Big|\leq\sqrt{\frac{d_j+1}{d_i+1}}\Big(1-\frac{\lambda_\tilde G^2}{2}\Big)^K

In=D~−1/2D~1/2I_n=\tilde D^{-1/2}\tilde D^{1/2}，GCN的K层表示如下：

h(K)=(In+D~−1/2A~D~1/22)K⋅x=(D~−1/2(In+A~D~−12)KD~1/2)K⋅x=D~−1/2(In+A~D~−12)K⋅(D~1/2x)\begin{aligned} h^{(K)} &= \Big(\frac{I_n+\tilde D^{-1/2}\tilde A\tilde D^{1/2}}{2}\Big)^K·x\\ &=\Big(\tilde D^{-1/2}\Big(\frac{I_n+\tilde A\tilde D^{-1}}{2}\Big)^K\tilde D^{1/2}\Big)^K·x\\ &=\tilde D^{-1/2}\Big(\frac{I_n+\tilde A\tilde D^{-1}}{2}\Big)^K·\big(\tilde D^{1/2}x\big) \end{aligned}

将D~1/2x\tilde D^{1/2}x按如下方式展开：

D~1/2x=(D+In)1/2x=∑i=1n(x(i)di+1)⋅ei\tilde D^{1/2}x=\big(D+I_n\big)^{1/2}x=\sum\limits_{i=1}^n\big(x(i)\sqrt{d_i+1}\big)·e_i

将上式代入hKh^{K}中得：

h(K)=D~−1/2(In+A~D~−12)K⋅∑i=1n(x(i)di+1)⋅ei=∑i=1ndi+1⋅D~−1/2(In+A~D~−12)K⋅ei\begin{aligned} h^{(K)}&=\tilde D^{-1/2}\Big(\frac{I_n+\tilde A\tilde D^{-1}}{2}\Big)^K·\sum\limits_{i=1}^n\big(x(i)\sqrt{d_i+1}\big)·e_i\\ &=\sum\limits_{i=1}^n\sqrt{d_i+1}·\tilde D^{-1/2}\Big(\frac{I_n+\tilde A\tilde D^{-1}}{2}\Big)^K·e_i \end{aligned}

我们注意到上式的后两项(In+A~D~−12)K⋅ei\Big(\frac{I_n+\tilde A\tilde D^{-1}}{2}\Big)^K·e_i刚好就是K-th转移概率向量pi(K)p_i^{(K)}。根据引理1，pi(K)p_i^{(K)}的第j个元素满足下列不等式：

\Big|p_i^{(K)}(j)-\frac{d_j+1}{2m+n}\Big|\leq\sqrt{\frac{d_j+1}{d_i+1}}\Big(1-\frac{\lambda_\tilde G^2}{2}\Big)^K

等价于下列公式：

p_i^{(K)}(j)=\frac{d_j+1}{2m+n}\pm\sqrt{\frac{d_j+1}{d_i+1}}\Big(1-\frac{\lambda_\tilde G^2}{2}\Big)^K

因此，h(K)h^{(K)}的第j个元素可以表示为：

\begin{aligned} h^{(K)}(j)&=\Big(\sum\limits_{i=1}^n\sqrt{d_i+1}x(i)·\tilde D^{-1/2}p_i^{(K)}\Big)(j)\\ &=\sum\limits_{i=1}^{n}\sqrt{d_i+1}x(i)\frac{1}{d_j+1}·\Big(\frac{d_j+1}{2m+n}\pm\sqrt{\frac{d_j+1}{d_i+1}}\Big(1-\frac{\lambda_\tilde G^2}{2}\Big)^K\Big)\\ &=\sum\limits_{i=1}^{n}\frac{\sqrt{(d_j+1)(d_i+1)}}{2m+n}x(i)\pm\sum\limits_{i=1}^nx(i)\Big(1-\frac{\lambda_\tilde G^2}{2}\Big) \end{aligned}

因此有：

h^{(K)}=\frac{<\tilde D^{1/2}1,x>}{2m+n}\tilde D^{1/2}1\pm\sum\limits_{i=1}^nx(i)\Big(1-\frac{\lambda_\tilde G^2}{2}\Big)·1

定理1得证。

3.2 GCNII 的谱分析

对于自环图G~\tilde G，图信号x上的一个K阶多项式滤波器定义为(∑l=0KθlL~l)x\Big(\sum_{l=0}^K\theta_l\tilde L^l\Big)x，其中L~\tilde L是正则化拉普拉斯矩阵，θ\theta是多项式系数。

  • Wu等人证明了K层GCN模拟了一个带有固定系数θ\theta的多项式过滤器，作者证明了正是这个固定的系数限制了GCN的能力，导致过平滑问题。
  • 作者证明了K层GCNII模型模拟了具有任意系数的K阶多项式过滤器（也就是解决了GCN过平滑问题）

3.2.1 定理及证明

**定理2：**考虑自环图G~\tilde G和图信号x，K层GCNII可以模拟一个具有任意系数θ\theta的K阶多项式滤波器(∑l=0KθlL~l)x\Big(\sum_{l=0}^K\theta_l\tilde L^l\Big)x

**证明：**假设信号向量x是非负的，我们考虑一个弱化版本的GCNII：设置αl=0.5\alpha_l=0.5，权重矩阵(1−βl)In+βlW(l)(1-\beta_l)I_n+\beta_lW^{(l)}为γlIn\gamma_lI_n，其中γl\gamma_l是可学习参数，这样我们有：

H(l+1)=σ(D~−1/2A~D~−1/2(H(l)+x)γlIn)H^{(l+1)}=\sigma\Big(\tilde D^{-1/2}\tilde A\tilde D^{-1/2}\Big(H^{(l)}+x\Big)\gamma_lI_n\Big)

由于输入特征x是非负的，所以我们可以去掉激活函数ReLU（因为ReLU在x大于0时是线性的）：

H(l+1)=γlD~−1/2A~D~−1/2(H(l)+x)=γl((In−L~)⋅(H(l)+x))\begin{aligned} H^{(l+1)}&=\gamma_l\tilde D^{-1/2}\tilde A\tilde D^{-1/2}\Big(H^{(l)}+x\Big)\\ &=\gamma_l\Big(\Big(I_n-\tilde L\Big)·\Big(H^{(l)}+x\Big)\Big) \end{aligned}

因此，我们可以得到最终的表示为：

H(K−1)=(∑l=0K−1(∏k=K−l−1K−1γk)(In−L~)l)xH^{(K-1)}=\Bigg(\sum\limits_{l=0}^{K-1}\Bigg(\prod_{k=K-l-1}^{K-1}\gamma_k\Bigg)\bigg(I_n-\tilde L\bigg)^l\Bigg)x

而针对图G~\tilde G的一个多项式滤波器可以表示为：

(∑k=0K−1θkL~k)=(∑l=0K−1(∑k=lK−1θk(−1)l(kl)(In−L~)l))x\Bigg(\sum\limits_{k=0}^{K-1}\theta_k\tilde L^k\Bigg)=\Bigg(\sum\limits_{l=0}^{K-1}\Bigg(\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l}\bigg(I_n-\tilde L\bigg)^l\Bigg)\Bigg)x

要证明定理2，只需证明对于所有l=0,...,K−1l=0,...,K-1，都存在γl\gamma_l使得下列等式成立：

∏k=K−l−1K−1γk=∑k=lK−1θk(−1)l(kl),k=0,...,K−1\prod_{k=K-l-1}^{K-1}\gamma_k=\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l},k=0,...,K-1

对上式做变形：

∏k=K−l−1K−1γk=∑k=lK−1θk(−1)l(kl),k=0,...,K−1γK−l−1∏k=K−lK−1γk=∑k=lK−1θk(−1)l(kl),k=0,...,K−1γK−l−1=∑k=lK−1θk(−1)l(kl)/∏k=K−lK−1γk,k=0,...,K−1γK−l−1=∑k=lK−1θk(−1)l(kl)/∑k=l−1K−1θk(−1)l−1(kl−1),k=0,...,K−1\begin{aligned} \prod_{k=K-l-1}^{K-1}\gamma_k&=\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l},k=0,...,K-1\\ \gamma_{K-l-1}\prod_{k=K-l}^{K-1}\gamma_k&=\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l},k=0,...,K-1\\ \gamma_{K-l-1}&=\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l}\Big/\prod_{k=K-l}^{K-1}\gamma_k,k=0,...,K-1\\ \gamma_{K-l-1}&=\sum\limits_{k=l}^{K-1}\theta_k(-1)^l\binom{k}{l}\Big/\sum\limits_{k=l-1}^{K-1}\theta_k(-1)^{l-1}\binom{k}{l-1},k=0,...,K-1 \end{aligned}

上式作除法操作需要保证∑k=l−1K−1θk(−1)l−1(kl−1)\sum_{k=l-1}^{K-1}\theta_k(-1)^{l-1}\binom{k}{l-1}不为0，如果为0，我们可以设置γK−l−1\gamma_{K-l-1}足够大保证上述公式仍然有很好地近似。但是上式分母为0的概率很小，因为这意味着K阶过滤器忽略了l跳邻居的所有特征。

至此，定理2证明完毕。

3.2.2 分析讨论

定理1表明了K层普通GCN模拟了一个具有固定参数的K阶多项式滤波器P~Kx\tilde P^Kx，P~\tilde P表示正则化后的图卷积矩阵。过平滑是由于P~Kx\tilde P^Kx会收敛到一个和输入信号x无关的分布中，从而导致梯度消失。DropEdge减缓了收敛速度，但是随着K趋向于无穷大，最终还是会出现过平滑问题。

定理2表明深层GCNII会收敛到一个同时包含输入特征信息和图结构信息的分布，这使得即使K趋向于无穷大，GCNII不会遭受过平滑问题。准确地说，定理2表明K层GCNII模拟了一个具有任意系数的K阶多项式滤波器h(K)=(∑l=0KθlL~l)⋅xh^{(K)}=\Big(\sum_{l=0}^K\theta_l\tilde L^l\Big)·x，通过选取合适的θ\theta，即使K趋向于无穷大，h(K)h^{(K)}也可以同时包含输入特征和图结构信息。

4. 实验

GCNII变体：GCNII∗GCNII^*

H(l+1)=σ(((1−αl)P~H(l)+αlH(0))((1−βl)In+βlW(l)))H^{(l+1)}=\sigma\Big(\Big((1-\alpha_l)\tilde PH^{(l)}+\alpha_lH^{(0)}\Big)\Big((1-\beta_l)I_n+\beta_lW^{(l)}\Big)\Big)

H(l+1)=σ((1−αl)P~H(l)((1−βl)In+βlW1(l))+αlH(0)((1−βl)In+βlW2(l)))H^{(l+1)}=\sigma\Big((1-\alpha_l)\tilde PH^{(l)}\Big((1-\beta_l)I_n+\beta_lW_1^{(l)}\Big)+\alpha_lH^{(0)}\Big((1-\beta_l)I_n+\beta_lW_2^{(l)}\Big)\Big)

一、数据集

  1. 半监督节点分类：Cora，Citesseer和Pubmed三个citation数据集，这三个数据集中节点表示文件，边表示citation，节点特征为文件的bag-of-words表示。
  2. 全监督节点分类：Chameleon，Cornell，Texas和Wisconsin四个网络数据集，节点表示网页，边表示页面之间的超链接，节点特征是对应页面的bag-of-words表示。
  3. inductive学习：使用PPI（蛋白质）网络，包含24个图，其中20个图用于训练，2个图用于验证，其余的用于测试。

二、半监督节点分类

三、全监督节点分类

四、inductive学习：9层GCNII

五、消融实验：initial residual连接和Identity mappin的作用

打赏
  • 版权声明： 本博客所有文章除特别声明外，著作权归作者所有。转载请注明出处！
  • Copyrights © 2021-2022 Yin Peng
  • 引擎: Hexo   |  主题:修改自 Ayer
  • 访问人数: | 浏览次数:

请我喝杯咖啡吧~

支付宝
微信