重新审视图神经网络：

我们拥有的只是低通滤波器

摘要

图神经网络已成为解决图结构数据机器学习问题的最重要技术之一。 最近关于顶点分类的工作提出了深度和分布式学习模型，以实现高性能和可扩展性。 然而，我们发现基准数据集的特征向量对于分类任务来说已经提供了相当丰富的信息，而图结构仅提供了一种对数据进行去噪的方法。 在本文中，我们开发了一个基于图信号处理的理论框架来分析图神经网络。 我们的结果表明，图神经网络仅对特征向量进行低通滤波，不具有非线性流形学习特性。 我们进一步研究了它们对特征噪声的适应能力，并提出了一些关于基于 GCN 的图神经网络设计的见解。

1简介

图神经网络（GNN）属于一类可以从图结构数据中学习的神经网络。 最近，用于顶点分类和图同构测试的图神经网络在多个基准数据集上取得了优异的成绩，并不断创下新的最先进性能Abu-El-Haija 等人 (2019)；基普夫和威灵（2017）； Veličković 等人 (2017);徐等人(2019). 从 ChebNet Defferrard 等人 (2016) 和 GCN Kipf and Welling (2017) 在顶点分类方面的早期成功开始，GNN 的许多变体被提出来解决以下问题：社交网络 Hamilton 等人 (2017);张等人 (2018a)，生物学 Veličković 等人 (2017, 2019)，化学 Fout 等人 (2017)； Gilmer 等人 (2017)，自然语言处理 Bastings 等人 (2017)；张等人 (2018b)、计算机视觉 Santoro 等人 (2017) 以及弱监督学习 Garcia 和 Bruna (2017)。

在半监督顶点分类中，我们观察到图卷积网络 (GCN) Kipf 和 Welling (2017) 中图卷积层的参数只会导致过度拟合。 在 SGC Wu 等人 (2019) 等简单架构和 DGI Veličković 等人 (2019) 等更复杂的架构中都报告了类似的观察结果。 基于这一现象，Wu等人（2019）提出将图神经网络简单地视为特征传播，并提出一种极其高效的模型，在许多基准数据集上具有最先进的性能。 Kawamoto等人(2018)对图分区设置下未经训练的类GCN GNN做出了相关的理论评论。 从这些先前的研究中，自然会出现一个问题： 为什么以及何时图神经网络可以很好地进行顶点分类？ 换句话说，即使没有训练，图神经网络模型的顶点特征向量是否也能正常工作？ 因此，我们能否找到基线图神经网络（例如 SGC 或 GCN）无法执行的现实反例？

在本研究中，我们从图信号处理的角度为上述问题提供了答案Ortega等人(2018)。 形式上，我们考虑图上的半监督学习问题。 给定一个图 $𝒢=(𝒱,ℰ)$，每个顶点 $i\in 𝒱$ 都有一个特征 $𝐱(i)\in 𝒳$ 和标签 $y(i)\in 𝒴$，其中 $𝒳$ 是$d$维欧几里得空间${ℝ}^d$和$𝒴=ℝ$用于回归，$𝒴=\{1,\mathrm{\dots },c\}$用于分类。 任务是学习一个假设，以根据特征 $𝐱(i)$ 预测标签 $y(i)$。 然后，我们描述了该问题的图神经网络解决方案，并深入了解最常用的基线模型 GCN Kipf 和 Welling (2017) 及其简化变体 SGC Wu 等人（2019）。

图1： 频率分量的精度

图2： gfNN的简单实现

图信号处理（GSP）将顶点上的数据视为信号，并应用信号处理技术来理解信号特征。 通过将信号（特征向量）和图结构（邻接矩阵或其变换）结合起来，GSP 启发了图结构数据学习算法的发展S human 等人（2012）。 在标准信号处理问题中，通常假设观测值包含一些噪声，并且潜在的“真实信号”具有低频 Rabiner 和 Gold (1975)。 在这里，我们对我们的问题提出了类似的假设。

Assumption 1。

输入特征由低频真实特征和噪声组成。 真实特征为机器学习任务提供了足够的信息。

我们的第一个贡献是在常用数据集上验证假设1（第3部分）。 图 1 显示了在具有不同频率分量的特征上训练的 2 层感知器 (MLP) 的性能。 在所有基准数据集中，我们看到只有少量频率成分有助于学习。 向特征向量添加更多频率分量只会降低性能。 反过来，当我们向特征中添加高斯噪声 $𝒩(0,{\sigma }^2)$ 时，分类精度会变得更差。

最近的许多 GNN 都是基于图信号处理的结果构建的。 最常见的做法是将（增强的）归一化邻接矩阵$I-\widetilde{ℒ}$与特征矩阵$𝒳$相乘。 产品$(I-\widetilde{ℒ})𝒳$被理解为特征平均和传播Hamilton等人（2017）；基普夫和威灵（2017）；吴等人(2019)。 在图信号处理文献中，这种操作在图上过滤信号，而不对归一化拉普拉斯矩阵显式执行特征分解，这需要$O(n^3)$时间Vaseghi (2008)。 在这里，我们将这种增强归一化邻接矩阵及其变体可互换地称为图过滤器和传播矩阵。

我们的第二个贡献表明，将图形信号与传播矩阵相乘对应于低通滤波（第4节，特别是定理3)。 此外，我们还表明观测信号和低通滤波器之间的矩阵乘积是真实信号优化问题的解析解。 对比近期图神经网络的设计原理Abu-El-Haija 等人 (2019)；基普夫和威灵（2017）； Xu等人(2019)，我们的结果表明图卷积层只是低通滤波。 因此，学习图卷积层的参数是没有必要的。 Wu 等人 (2019, Theorem 1) 也通过分析增强归一化邻接矩阵的频谱截断效应提出了类似的主张。 我们扩展这个结果来表明所有特征值单调收缩，这进一步解释了频谱截断效应的含义。

基于我们的理论理解，我们提出了一个名为gfNN（图过滤神经网络）的新基线框架来对顶点分类问题进行实证分析。 gfNN 包含两个步骤： 1. 通过与图过滤矩阵相乘来过滤特征； 2. 通过机器学习模型学习顶点标签。 我们使用图2中的简单实现模型展示了我们框架的有效性。

我们的第三个贡献是以下定理：

Theorem 2 （非正式，参见定理 7、8)。

在假设1下，SGC、GCN 和 gfNN 的结果与使用真实特征的相应神经网络的结果相似。

定理 7 意味着，在假设 1 下，gfNN 和 GCN Kipf and Welling (2017) 具有相似的高性能。 由于 gfNN 在学习阶段不需要邻接矩阵的乘法，因此它比 GCN 快得多。 此外，gfNN 还具有更强的噪声容忍度。

最后，我们将 gfNN 与 SGC 模型 Wu 等人 (2019) 进行比较。 虽然 SGC 在基准数据集上计算速度也快且准确，但我们的分析表明，当特征输入是非线性可分离时，它会失败，因为图卷积部分对非线性流形学习没有贡献。 我们创建了一个人工数据集来凭经验证明这一说法。

2 图形信号处理

在本节中，我们介绍图信号处理的基本概念。 我们采用了最新的不规则图上的图傅立叶变换公式Girault等人(2018)。

令 $𝒢=(𝒱,ℰ)$ 是一个简单的无向图，其中 $𝒱=\{1,\mathrm{\dots },n\}$ 是 $n\in \mathbb{Z}$ 顶点的集合，$ℰ$ 是边的集合。 设$A=(a_{ij})\in {ℝ}^{n\times n}$为$G$的邻接矩阵，$D=\mathrm{diag}(d(1),\mathrm{\dots },d(n))\in {ℝ}^{n\times n}$为$G$的度矩阵，其中$d(i)={\sum }_{j\in 𝒱}a(i,j)$为顶点$i\in 𝒱$的度数。 $L=D-A\in {ℝ}^{n\times n}$为$G$的组合拉普拉斯矢量，$ℒ=I-D^{-1/2}A{D}^{-1/2}$为$G$的归一化拉普拉斯矢量，其中$I\in {ℝ}^{n\times n}$为身份矩阵，$L_{\text{rw}}=I-D^{-1}A$为$G$的随机漫步拉普拉斯矢量。另外，对于带有 $\gamma >0$ 的 $\gamma \in ℝ$，让 $\tilde{A}=A+\gamma I$ 成为 附加邻接矩阵，它是通过在 $G$ 中加入 $\gamma$ 自循环得到的、$\tilde{D}=D+\gamma I$是相应的增强度矩阵，$\tilde{L}=\tilde{D}-\tilde{A}=L$、$\widetilde{ℒ}=I-{\tilde{D}}^{-1/2}\tilde{A}{\tilde{D}}^{-1/2}$、${\tilde{L}}_{\text{rw}}=I-{\tilde{D}}^{-1}\tilde{A}$是相应的增强组合矩阵、归一化矩阵和随机漫步拉普拉斯矩阵。

在图的顶点上定义的向量$x\in {ℝ}^n$称为图信号。 为了引入图傅立叶变换，我们需要在图信号空间上定义两个运算：变分和内积。 在这里，我们通过以下方式定义变体 $\mathrm{\Delta }:{ℝ}^n\to ℝ$ 和 $\tilde{D}$ 内积：

$\mathrm{\Delta }(x):={\displaystyle \sum _{(i,j)\in ℰ}}{(x(i)-x(j))}^2=x^{\top }Lx;{(x,y)}_{\tilde{D}}:={\displaystyle \sum _{i\in 𝒱}}(d(i)+\gamma )x(i)y(i)=x^{\top }\tilde{D}y.$ (1)

我们用 ${\Vert x\Vert }_{\tilde{D}}:=\sqrt{{(x,x)}_{\tilde{D}}}$ 表示由 $\tilde{D}$ 导出的范数。 直观上，变化$\mathrm{\Delta }$和内积${(\cdot ,\cdot )}_{\tilde{D}}$分别指定如何测量信号的平滑度和重要性。 特别是，我们的内积更加重视高度顶点，其中较大的 $\gamma$ 使重要性更加均匀。 然后我们考虑广义特征值问题（变分形式）：找到$u_1,\mathrm{\dots },u_n\in {ℝ}^n$，使得对于每个$i\in \{1,\mathrm{\dots },n\}$,$u_i$是一个解决方案如下优化问题：

$\text{minimize}\mathrm{\Delta }(u)\text{subject to}{(u,u)}_{\tilde{D}}=1,{(u,u_j)}_{\tilde{D}}=0,j\in \{1,\mathrm{\dots },n\}.$ (2)

解$u_i$称为第$i$个广义特征向量，对应的目标值${\lambda }_i:=\mathrm{\Delta }(u_i)$称为第$i$个广义特征值。 广义特征值和特征向量也是以下广义特征值问题（方程形式）的解：

$Lu=\lambda \tilde{D}u.$ (3)

因此，如果 $(\lambda ,u)$ 是广义特征对，则 $(\lambda ,{\tilde{D}}^{1/2}u)$ 是 $\widetilde{ℒ}$ 的特征对。 广义特征值越小，广义特征向量在变化$\mathrm{\Delta }$方面越平滑。 因此，广义特征值被称为图的频率。

图傅里叶变换是广义特征向量的基展开。 令 $U=[u_1,\mathrm{\dots },u_n]$ 为矩阵，其列为广义特征向量。 然后，图傅立叶变换$ℱ\mathrm{:}{ℝ}^n\mathrm{\to }{ℝ}^n$由$ℱx=\widehat{x}:=U^{\top }\tilde{D}x$定义，逆图傅立叶变换${ℱ}^{\mathrm{-}\mathrm{1}}$ 由${ℱ}^{-1}\widehat{x}=U\widehat{x}$ 定义。 请注意，这些实际上是自 $ℱ{ℱ}^{-1}=U^{\top }\tilde{D}U=I$ 以来的逆变换。

Parseval 恒等式 将数据范数及其傅立叶变换联系起来：

${\Vert x\Vert }_{\tilde{D}}={\Vert \widehat{x}\Vert }_2.$ (4)

令 $h:ℝ\to ℝ$ 为解析函数。 $h$指定的图过滤器是由频域中的关系$\widehat{y}(\lambda )=h(\lambda )\widehat{x}(\lambda )$定义的映射$x\mapsto y$。 在空间域中，上式等价于$y=h({\tilde{L}}_{\text{rw}})x$。其中 $h({\tilde{L}}_{\text{rw}})$ 是通过 $h$ 的泰勒展开式定义的；有关矩阵函数的详细信息，请参阅 Higham (2008)。

在图上的机器学习问题中，每个顶点 $i\in 𝒱$ 都有一个 $d$ 维特征 $𝐱(i)\in {ℝ}^d$。 我们将特征视为$d$图信号，并通过每个信号的图傅里叶变换来定义特征的图傅里叶变换。 令 $X={[𝐱(1);\mathrm{\dots },𝐱(n)]}^{\top }$ 为特征矩阵。 然后，图傅里叶变换用$ℱX=\widehat{X}=:U^{\top }\tilde{D}X$表示，逆变换用${ℱ}^{-1}\widehat{X}=U\widehat{X}$表示。 我们将$\widehat{X}={[\widehat{𝐱}({\lambda }_1);\mathrm{\dots };\widehat{𝐱}({\lambda }_n)]}^{\top }$表示为$X$的频率分量。

3 假设的经验证据1

本文的结果很大程度上依赖于假设1。 因此，我们首先在现实世界的数据集中验证这一假设：Cora、Citeseer 和 Pubmed Sen 等人 (2008)。 这些是引文网络，其中顶点是科学论文，边是引文。 我们考虑以下实验设置：1。 根据$\widetilde{ℒ}$计算图傅里叶基$U$； 2。 对输入特征添加高斯噪声：$𝒳\leftarrow 𝒳+𝒩(0,{\sigma }^2)$ for $\sigma =\{0,0.01,0.05\}$； 3。 计算第一个$k$频率分量：${\widehat{𝒳}}_k=U{[:k]}^{\top }{\tilde{D}}^{1/2}𝒳$； 4。 重构特征：${\widetilde{𝒳}}_k={\tilde{D}}^{-1/2}U[:k]{\widehat{𝒳}}_k$； 5。 训练并报告测试 2 层感知器在重建特征 ${\widetilde{𝒳}}_k$ 上的准确性。

图3： 2 层 MLP 在频率受限特征向量 (epochs=20) 上的平均性能。 带注释的“（最佳）”水平线显示了使用 gfNN 和在原始特征上训练的 2 层 MLP 的最佳性能。

在图3中，我们逐步添加归一化拉普拉斯频率分量来重建特征向量并训练2层MLP。 我们看到所有三个数据集都表现出低频性质。 2 层 MLP 的分类精度往往在光谱的前 20% 内达到峰值（绿色框）。 通过添加人工高斯噪声，我们观察到低频区域的性能相对稳健，这意味着很强的去噪效果。

有趣的是，当高频分量不包含对分类有用的信息时，图神经网络和简单 MLP 之间的性能差距要大得多。 在 Cora 数据集中，高频成分只会降低分类精度。 因此，我们的 gfNN 优于简单的 MLP。 Citeseer 和 Pubmed 具有类似的低频性质。 然而，这里的性能差距并不那么大。 由于 Citeseer 和 Pubmed 的添加噪声性能系列通常与原始 Cora 性能系列相似，因此我们预计原始 Citeseer 和 Pubmed 包含的噪声比 Cora 少得多。 因此，我们可以预期图过滤度在 Citeseer 和 Pubmed 案例中影响不大。

4 邻接矩阵相乘就是低通滤波

计算低频分量的成本很高，因为计算拉普拉斯矩阵的特征值分解需要 $O({|𝒱|}^3)$ 时间。 因此，合理的替代方案是使用低通滤波器。 许多关于图神经网络的论文迭代地乘以（增强的）邻接矩阵 ${\tilde{A}}_{\text{rw}}$ （或 $\tilde{A}$)来传播信息。 在本节中，我们看到此操作对应于低通滤波器。

乘以归一化邻接矩阵对应于应用图过滤器$h(\lambda )=1-\lambda$。 由于归一化拉普拉斯算子的特征值位于区间$[0,2]$上，因此该操作类似于去除中频分量的带阻滤波器。 然而，由于归一化拉普拉斯算子的最大特征值是 $2$ 当且仅当该图包含非平凡二分图作为连通分量 （Chung，1997，引理 1.7） 。 因此，对于其他图，乘以归一化（非增广）邻接矩阵充当低通滤波器（即，高频分量必须减少）。

我们可以通过添加自循环（即考虑增强邻接矩阵）来增加低通滤波效果，因为它将特征值缩小到零，如下所示。

Theorem 3.

令 ${\lambda }_i\mathit{}\mathrm{(}\gamma \mathrm{)}$ 为 $\mathrm{(}\stackrel{\mathrm{~}}{D}\mathrm{,}L\mathrm{)}\mathrm{=}\mathrm{(}D\mathrm{+}\gamma \mathit{}I\mathrm{)}$ 的第 $i$ 广义特征值。 那么，${\lambda }_i\mathit{}\mathrm{(}\gamma \mathrm{)}$是一个非负数，并且在$\gamma \mathrm{\ge }\mathrm{0}$中单调非递增。 此外，如果${\lambda }_i\mathit{}\mathrm{(}\mathrm{0}\mathrm{)}\mathrm{\ne }\mathrm{0}$，则${\lambda }_i\mathit{}\mathrm{(}\gamma \mathrm{)}$严格单调递减。

请注意，$\gamma$ 不能太大。 否则，所有特征值将集中在零附近，即所有数据将被视为“低频”；因此，我们无法从低频分量中提取有用的信息。

图过滤器$h(\lambda )=1-\lambda$也可以从拉普拉斯正则化最小二乘法Belkin and Niyogi (2004)的一阶近似导出。 让我们考虑从观察 ${\{𝐱(i)\}}_{i\in 𝒱}$ 估计低频真实特征 ${\{\overline{𝐱}(i)\}}_{i\in 𝒱}$ 的问题。 然后，自然优化问题由下式给出

$\underset{\overline{x}}{\min }{\displaystyle \sum _{i\in 𝒱}}{\Vert \overline{𝐱}(i)-𝐱(i)\Vert }_{\tilde{D}}^2+\mathrm{\Delta }(\overline{X})$ (5)

其中$\mathrm{\Delta }(\overline{X})={\sum }_{p=1}^d\mathrm{\Delta }(\overline{𝐱}{(i)}_p)$。 请注意，从 $\mathrm{\Delta }(\overline{X})={\sum }_{\lambda \in \mathrm{\Lambda }}\lambda {\Vert \widehat{\overline{𝐱}}(\lambda )\Vert }_2^2$ 开始，它是先验分布为 $\widehat{\overline{𝐱}}(\lambda )\sim N(0,I/\lambda )$ 的最大后验估计。 该问题的最优解由$\overline{X}={(I+{\tilde{L}}_{\text{rw}})}^{-1}X$给出。 相应的滤波器是$h^{\prime }(\lambda )={(1+\lambda )}^{-1}$，因此$h(\lambda )=1-\lambda$是它的一阶泰勒近似。

5 低通滤波器的偏差-方差权衡

在本文的其余部分中，我们在假设1下建立了理论结果。 具体来说，我们提出一个更精确的假设如下。

Assumption 4 （假设1第一部分的精确版本）。

观察到的特征${\mathrm{\{}𝐱\mathit{}\mathrm{(}i\mathrm{)}\mathrm{\}}}_{i\mathrm{\in }𝒱}$由真实特征${\mathrm{\{}\overline{𝐱}\mathit{}\mathrm{(}i\mathrm{)}\mathrm{\}}}_{i\mathrm{\in }𝒱}$和噪声${\mathrm{\{}𝐳\mathit{}\mathrm{(}i\mathrm{)}\mathrm{\}}}_{i\mathrm{\in }𝒱}$组成。 真实特征$\overline{X}$的频率最多为$\mathrm{0}\mathrm{\le }ϵ\mathrm{\ll }\mathrm{1}$，噪声遵循高斯白噪声，即$Z$ 独立地相同地遵循正态分布$N\mathit{}\mathrm{(}\mathrm{0}\mathrm{,}{\sigma }^{\mathrm{2}}\mathrm{)}$。

使用这个假设，我们可以如下评估低通滤波器的效果。

Lemma 5.

假设假设4。 对于任何 ，概率至少为 $\mathrm{1}\mathrm{-}\delta$，我们有

${\Vert \overline{X}-{\tilde{A}}_{\text{𝑟𝑤}}^{k}X\Vert }_D\le \sqrt{kϵ}{\Vert \overline{X}\Vert }_D+O\left(\sqrt{\log (1/\delta )R(2k)}\right)𝔼[{\Vert Z\Vert }_D],$ (6)

其中 $R\mathit{}\mathrm{(}\mathrm{2}\mathit{}k\mathrm{)}$ 是具有随机初始顶点的随机游走在 $\mathrm{2}\mathit{}k$ 步骤后返回到初始顶点的概率。

(6) 右侧的第一项和第二项是应用滤波器产生的偏差项和产生的方差项分别来自过滤后的噪声。 在此假设下，偏差会增加一点，例如 $O(\sqrt{ϵ})$。 方差项会在 $O(1/{\mathrm{deg}}^{k/2})$ 中减小，其中 $\mathrm{deg}$ 是图形的典型度数，因为 $R(2k)$ 在小 $k$ 中通常表现为 $O(1/{\mathrm{deg}}^k)$ 。 因此，如果$\overline{X}$的最大频率远小于信噪比，我们可以通过乘以邻接矩阵，从噪声观测中获得对真实数据更准确的估计。 t1>${\Vert Z\Vert }_D/{\Vert \overline{X}\Vert }_D$。

该定理还建议选择$k$。通过将右侧最小化$k$，我们得到：

Corollary 6。

假设 $𝔼\mathit{}\mathrm{[}{\mathrm{\Vert }Z\mathrm{\Vert }}_D\mathrm{]}\mathrm{\le }\rho \mathit{}{\mathrm{\Vert }\overline{X}\mathrm{\Vert }}_D$ 对应于某些 $\rho \mathrm{=}O\mathit{}\mathrm{(}\mathrm{1}\mathrm{)}$。 令$k^{\mathrm{*}}$由$k^{\mathrm{*}}\mathrm{=}O\mathit{}\mathrm{(}\log \mathit{}\mathrm{(}\log \mathit{}\mathrm{(}\mathrm{1}\mathrm{/}\delta \mathrm{)}\mathit{}\rho \mathrm{/}ϵ\mathrm{)}\mathrm{)}$定义，并假设存在常量$C_d$和$\overline{d}\mathrm{>}\mathrm{1}$，使得$R\mathit{}\mathrm{(}\mathrm{2}\mathit{}k\mathrm{)}\mathrm{\le }{C}_d\mathrm{/}{\overline{d}}^k$为$k\mathrm{\le }{k}^{\mathrm{*}}$。 然后，通过选择$k\mathrm{=}{k}^{\mathrm{*}}$，(6)的右侧是$\stackrel{\mathrm{~}}{O}\mathit{}\mathrm{(}\sqrt{ϵ}\mathrm{)}$。 ∎

由此得出的结论是，我们可以通过多次乘以 ${\tilde{A}}_{\text{rw}}$ 来获得准确度 $\tilde{O}(\sqrt{ϵ})$ 的真实特征估计。

6 图过滤神经网络

在上一节中，我们看到低通滤波特征 ${\tilde{A}}_{\text{rw}}^{k}X$ 是对真实特征的高概率准确估计。 在本节中，我们分析该操作的性能。

令多层（两层）感知器为

$h_{\text{MLP}}(X|W_1,W_2)$ $={\sigma }_2({\sigma }_1(X{W}_1)W_2),$ (7)

其中${\sigma }_1$是entry-wise ReLU函数，${\sigma }_2$是softmax函数。 请注意，${\sigma }_1$ 和 ${\sigma }_2$ 都是收缩图，即 ${\Vert {\sigma }_i(X)-\sigma (Y)\Vert }_D\le {\Vert X-Y\Vert }_D$。

在假设1的第二部分下，我们的目标是获得类似于$h(\overline{X}|W_1,W_2)$的结果。 最简单的方法是使用观察到的特征训练多层感知器$h_{\text{MLP}}(X|W_1,W_2)$。 该方法的性能评估如下：

$\parallel h_{\text{MLP}}(\overline{X}|W_1,W_2)-h_{\text{MLP}}(X|W_1,W_2){\parallel }_{\tilde{D}}\le \parallel Z{\parallel }_D\rho (W_1)\rho (W_2),$ (8)

其中$\rho (W)$是$W$的最大奇异值。

现在，我们考虑将图过滤器${\tilde{A}}_{\text{rw}}^k$应用于特征，然后使用多层感知器进行学习，即$h_{\text{MLP}}(h({\tilde{L}}_{\text{rw}})X|W_1,W_2)$。 使用引理5，我们得到以下结果。

Theorem 7。

假设假设4和推论6中的条件。 通过选择 $k$ 作为推论 6, 的概率至少为 $\mathrm{1}\mathrm{-}\delta$，

$\parallel h_{\text{𝑀𝐿𝑃}}(\overline{X}|W_1,W_2)-h_{\text{𝑀𝐿𝑃}}({\tilde{A}}_{\text{𝑟𝑤}}^{2}X|W_1,W_2){\parallel }_D=\tilde{O}(\sqrt{ϵ})𝔼[\parallel Z{\parallel }_D]\rho (W_1)\rho (W_2).$ (9)

∎

这意味着如果真实数据的最大频率很小，我们会得到类似于最优解的解。

与GCN的比较

在同样的假设下，我们可以分析两层GCN的性能。 GCN 由下式给出

$h_{\text{GCN}}(X|W_1,W_2)$ $={\sigma }_2({\tilde{A}}_{\text{rw}}{\sigma }_1({\tilde{A}}_{\text{rw}}X{W}_1)W_2).$ (10)

Theorem 8.

在与定理 7 相同的假设下，我们有

$\parallel h_{\text{𝑀𝐿𝑃}}(\overline{X}|W_1,W_2)-h_{\text{𝐺𝐶𝑁}}(X|W_1,W_2){\parallel }_D\le \tilde{O}(\sqrt[4]{ϵ})𝔼[\parallel Z{\parallel }_D]\rho (W_1)\rho (W_2).$ (11)

这个定理意味着GCN对于真实特征也具有类似于MLP的性能。 因此，在$ϵ\to 0$和$Z\to 0$的限制下，所有MLP、GCN和gfNN都具有相同的性能。

在实践中，gfNN 相对于 GCN 有两个优势。 首先，gfNN 比 GCN 更快，因为它在训练期间不使用图。 其次，GCN 存在对噪声过度拟合的风险。 当噪声太大而无法通过一阶低通滤波器${\tilde{A}}_{\text{rw}}$降低时，使用噪声特征训练内部权重$W_1$，这会过度拟合噪音。 我们在7.2节中验证了这一点。

与SGC比较

回想一下，2 度 SGC 由下式给出

$h_{\text{SGC}}(X|W_1)={\sigma }_2({\tilde{A}}_{\text{rw}}^{2}X{W}_2),$ (12)

即，它是一个具有单层感知器的 gfNN。 因此，通过同样的讨论，SGC 具有与应用于真实特征的感知器（而不是 MLP）类似的性能。 这就澄清了SGC的一个问题：如果真实特征是不可分离的，SGC就无法解决问题。 我们在实验E2（第7.3节）中验证了这个问题。

7实验

为了验证我们在前几节中的主张，我们设计了两个实验。 在实验E1中，我们向真实数据集的特征向量添加不同级别的白噪声，并报告基线模型之间的分类准确性。 实验E2研究了一个具有复杂特征空间的人工数据集，用于演示SGC等简单模型何时无法分类。

有两种类型的数据集：通常用于图神经网络基准测试的现实世界数据（引用网络、社交网络和生物网络）Sen 等人（2008）；杨等人(2016); Zitnik 和 Leskovec (2017) 以及从两个圆圈数据集人工合成的随机图。 我们通过将每个数据点变成一个顶点并连接欧氏距离中最近的 5 个顶点来创建两个圆数据集的图结构。 表 1 概述了每个数据集。

表格1： 用于顶点分类的真实世界基准数据集和合成数据集

Dataset	Nodes	Edges	Features	Classes	Train/Val/Test Nodes
Cora	2,708	5,278	1,433	7	140/500/1,000
Citeseer	3,327	4,732	3,703	6	120/500/1,000
Pubmed	19,717	44,338	500	3	60/500/1,000
Reddit	231,443	11,606,919	602	41	151,708/23,699/55,334
PPI	56,944	818,716	50	121	44,906/6,514/5,524
Two Circles	4,000	10,000	2	2	80/80/3,840

7.1神经网络

我们将我们的结果与基准数据集上的一些最先进的图神经网络进行比较。 我们使用 Adam 优化器 Kingma 和 Ba (2015) (lr=0.2, epochs=50) 训练每个模型。 我们使用 32 个隐藏单元作为 GCN、MLP 和 gfNN 的隐藏层。 其他超参数设置与SGC Wu 等人(2019)类似。

gfNN 我们的简单模型有三个图形过滤器：左范数 ($\mathrm{▼}$)、增强归一化邻接 ($\mathrm{▲}$)和双边 ($\mathrm{◆}$)。

SGC Wu 等人 (2019) 简单图卷积 ($\mathrm{■}$) 通过消除神经网络中的非线性并仅求平均来简化图卷积神经网络模型特征。

GCN Kipf 和 Welling (2017) 图卷积神经网络 (✖) 是最常用的基线。

图4： Cora（左）、Citeseer（中）和 Pubmed（右）数据集的基准测试准确性。 噪声水平是通过添加到特征中的白噪声的标准偏差来测量的。

7.2 图滤波器的去噪效果

对于表 1 中的每个数据集，我们将白噪声 $𝒩(0,{\delta }^2)$ 引入到 $\delta$ 在 $(0.01,0.05)$ 范围内的特征向量中。 根据定理 8 和定理 7 的含义，GCN 由于其一阶去噪特性，应该表现出对特征噪声的低容忍度。 随着噪声水平的增加，我们在图 4 中看到，GCN、逻辑回归 (LR) 和 MLP 往往对噪声更加过度拟合。 另一方面，gfNN 和 SGC 仍然具有相当的噪声容忍度。

7.3 图过滤器的表现力

由于图卷积只是去噪，我们预计它对非线性学习几乎没有贡献。 因此，我们实现一个简单的二维两圆数据集来看看图过滤是否可以具有非线性流形学习效果。 基于数据点之间的欧几里得距离，我们构造一个 $k$-nn 图作为底层图结构。 在这个特定的实验中，我们将每个数据点连接到 5 个最近的邻居。 图 5 演示了 SGC 如何无法对简单的 500 个数据点集进行直观分类。

图5： 遵循两个圆圈模式的 500 个生成数据样本的决策边界

另一方面，SGC、GCN 和我们的模型 gfNN 在大多数基准图数据集上的表现相当。 表 2 比较了随机/测试集的训练精度（Reddit 的 f1-micro）。 我们看到所有这些图神经网络都具有相似的性能（一些小的改进可能会受到超参数调整的影响）。 因此，我们认为当前图神经网络的基准数据集具有相当“简单”的特征空间。

在实践中，我们的分析和实验结果都表明图卷积层应该被简单地视为一个去噪滤波器。 与最近涉及 GCN Abu-El-Haija 等人 (2019) 的设计趋势相反； Valsesia 等人 (2019)，我们的结果表明，简单地堆叠 GCN 层可能只会使模型更容易出现特征噪声，同时具有与简单 MLP 相同的表达能力。

表2： 随机训练/验证/测试分组的平均测试准确度（5 次）

	Denoise	Classifier	Cora	Citeseer	Pubmed	Reddit	PPI	Two Circles
GCN	1st order	Non-linear	$80.0\pm 1.8$	$69.6\pm 1.1$	$79.3\pm 1.3$	OOM	OOM	$83.9\pm 3.1$
SGC	2nd order	Linear	$77.6\pm 2.2$	$65.6\pm 0.1$	$78.4\pm 1.1$	$94.9\pm 1.2$	$62.0\pm 1.2$	$54.5\pm 4.4$
gfNN	2nd order	Non-linear	$80.9\pm 1.3$	$69.3\pm 1.1$	$81.2\pm 1.5$	$92.4\pm 2.2$	$62.2\pm 1.5$	$84.6\pm 2.5$

8讨论

很少有工作能够解决 GCN 架构的局限性。 Kawamoto等人(2018)采用平均场方法分析统计物理的简单GCN模型。 他们得出的结论是，反向传播既不能提高基于 GCN 的 GNN 模型的准确性，也不能提高可检测性。 Li等人(2018)实证分析了有限标记数据设置下的多层GCN模型，并指出GCN在标记数据太少或堆叠层太多的情况下效果不佳。 虽然这些结果为 GCN 提供了富有洞察力的观点，但它们并没有充分回答以下问题： 我们什么时候应该使用 GNN？.

我们的结果表明，如果假设 1 成立，我们应该使用 GNN 方法来解决给定问题。 从我们的角度来看，源自 GCN 的 GNN 只是执行噪声过滤并从去噪数据中学习。 根据我们的分析，我们提出了 GCN 和 SGC 可能无法执行的两种情况：噪声特征和非线性特征空间。 反过来，我们提出了一种在这两种情况下都能很好地发挥作用的简单方法。

最近，基于 GCN 的 GNN 已应用于许多重要应用，例如点云分析 Valsesia 等人 (2019) 或弱监督学习 Garcia 和 Bruna (2017)。 随着输入特征空间变得复杂，我们主张重新审视当前基于 GCN 的 GNN 设计。 我们不应该将 GCN 层视为计算机视觉中的卷积层，而需要将其简单地视为一种去噪机制。 因此，简单地堆叠 GCN 层只会给神经网络设计带来过度拟合和复杂性。

附录A证明

定理证明3。

由于 $(D+\gamma I,L)$ 的广义特征值是正半定矩阵 ${(D+\gamma I)}^{1/2}L{(D+\gamma I)}^{1/2}$ 的特征值，因此它们是非负实数。 为了获得收缩结果，我们使用 Courant-Fisher-Weyl 的最小-最大原理 [Bhatia，2013，推论 III。 1.2]：对于任何，

${\lambda }_i({\gamma }_2)$ $=\underset{H:\text{subspace},\dim (H)=i}{\min }\underset{x\in H,x\ne 0}{\max }{\displaystyle \frac{x^{\top }Lx}{x^{\top }(D+{\gamma }_{2}I)x}}$ (13)

$\le \underset{H:\text{subspace},\dim (H)=i}{\min }\underset{x\in H,x\ne 0}{\max }{\displaystyle \frac{x^{\top }Lx}{x^{\top }(D+{\gamma }_{1}I)x}}$ (14)

$={\lambda }_i({\gamma }_1).$ (15)

这里，第二个不等式如下，因为 对于所有 $x\ne 0$ 因此，如果 $x^{\top }Lx\ne 0$ 即 ${\lambda }_i({\gamma }_1)\ne 0$，则不等式是严格的。 ∎

Lemma 9.

如果$X$的频率最多为$ϵ$，则为${\mathrm{\Vert }h\mathit{}\mathrm{(}ℒ\mathrm{)}\mathit{}X\mathrm{\Vert }}_D^{\mathrm{2}}\mathrm{\le }{\max }_{t\mathrm{\in }\mathrm{[}\mathrm{0}\mathrm{,}ϵ\mathrm{]}}\mathit{}h\mathit{}\mathrm{(}t\mathrm{)}\mathit{}{\mathrm{\Vert }X\mathrm{\Vert }}_D^{\mathrm{2}}$。

证明。

根据帕塞瓦尔恒等式，

${\Vert ℒX\Vert }_D^2$ $={\displaystyle \sum _{\lambda \in \mathrm{\Lambda }}}h(\lambda ){\Vert \widehat{𝐱}(\lambda )\Vert }_2^2$ (16)

$\le \underset{t\in [0,ϵ]}{\max }h(t){\displaystyle \sum _{\lambda \in \mathrm{\Lambda }}}{\Vert \widehat{𝐱}(\lambda )\Vert }_2^2$ (17)

$=\underset{t\in [0,ϵ]}{\max }h(t){\Vert \widehat{X}\Vert }_2^2$ (18)

$=\underset{t\in [0,ϵ]}{\max }h(t){\Vert \widehat{X}\Vert }_D^2.$ (19)

∎

引理5的证明。

代入$X=\overline{X}+Z$，我们得到

${\Vert \overline{X}-{\tilde{A}}_{\text{rw}}^{k}X\Vert }_{\tilde{D}}$ $\le {\Vert (I-{\tilde{A}}_{\text{rw}}^k)\overline{X}\Vert }_{\tilde{D}}+{\Vert {\tilde{A}}_{\text{rw}}^{k}Z\Vert }_{\tilde{D}}.$ (20)

根据引理 9，第一项以 $\sqrt{kϵ}{\Vert \overline{X}\Vert }_D$ 为界。 根据 Parseval 恒等式 (4)，第二项的计算公式为

${\Vert {\tilde{A}}_{\text{rw}}^{k}Z\Vert }_{\tilde{D}}^2$ $={\displaystyle \sum _{\lambda \in \mathrm{\Lambda }}}{(1-\lambda )}^{2k}{\Vert \widehat{𝐳}(\lambda )\Vert }_2^2$ (21)

$={\displaystyle \sum _{\lambda \in \mathrm{\Lambda },p\in \{1,\mathrm{\dots },d\}}}{(1-\lambda )}^{2k}\widehat{z}{(\lambda ,p)}^2$ (22)

通过[Laurent 和 Massart，2000，引理 1]，我们有

$\mathrm{Prob}\left\{{\displaystyle \sum _{\lambda ,p}}{(1-\lambda )}^{2k}(\widehat{z}{(\lambda ,p)}^2/{\sigma }^2-1)\ge 2\sqrt{t{\displaystyle \sum _{\lambda ,p}}{(1-\lambda )}^{4k}}+2t\right\}\le e^{-t}.$ (23)

将$t=\log (1/\delta )$替换为$\delta \le 1/2$，我们得到

$\mathrm{Prob}\left\{{\displaystyle \sum _{\lambda ,p}}{(1-\lambda )}^{2k}\widehat{z}{(\lambda ,p)}^2\ge 5{\sigma }^{2}nd\log (1/\delta ){\displaystyle \frac{{\sum }_{\lambda }{(1-\lambda )}^{2k}}{n}}\right\}\le 1-\delta .$ (24)

请注意 $𝔼[\parallel Z{\parallel }_D^2={\sigma }^{2}nd$ 和

${\displaystyle \frac{{\sum }_{\lambda }{(1-\lambda )}^{2k}}{n}}={\displaystyle \frac{\mathrm{tr}({\tilde{A}}_{\text{rw}}^{2k})}{n}}=R(2k)$ (25)

因为${\tilde{A}}_{\text{rw}}^{2k}$的$(i,j)$条目是从$i\in 𝒱$开始的随机游走在$j\in 𝒱$上$2k$的概率步骤，我们得到引理。 ∎

定理证明7。

根据 $\sigma$ 的 Lipschitz 连续性，我们有

$\parallel h_{\text{MLP}}(\overline{X}|W_1,W_2)-h_{\text{MLP}}({\tilde{A}}_{\text{rw}}^{k}X|W_1,W_2){\parallel }_D$ $\le {\Vert \overline{X}-{\tilde{A}}_{\text{rw}}^{k}X\Vert }_D\rho (W_1)\rho (W_2).$ (26)

通过引理5，我们得到结果。 ∎

Lemma 10.

如果$X$的频率最多为$ϵ$，则存在$Y$，使得$Y$的频率最多为$\sqrt{ϵ}$ 和${\mathrm{\Vert }\sigma \mathit{}\mathrm{(}X\mathrm{)}\mathrm{-}Y\mathrm{\Vert }}_D^{\mathrm{2}}\mathrm{\le }\sqrt{ϵ}\mathit{}{\mathrm{\Vert }X\mathrm{\Vert }}_D^{\mathrm{2}}$。

证明。

我们通过截断大于$\sqrt{ϵ}$的频率分量来选择$Y$。 然后，

${\Vert \sigma (X)-Y\Vert }_D^2$ $={\displaystyle \sum _{\lambda >\sqrt{ϵ}}}{\Vert \widehat{\sigma (X)}(\lambda )\Vert }^2$ (27)

$\le {\displaystyle \frac{1}{\sqrt{ϵ}}}{\displaystyle \sum _{\lambda }}\lambda {\Vert \widehat{\sigma (X)}(\lambda )\Vert }^2$ (28)

$={\displaystyle \frac{1}{\sqrt{ϵ}}}{\displaystyle \sum _{(u,v)\in E}}{\Vert \sigma (x(u))-\sigma (x(v))\Vert }_2^2$ (29)

$\le {\displaystyle \frac{1}{\sqrt{ϵ}}}{\displaystyle \sum _{(u,v)\in E}}{\Vert x(u)-x(v)\Vert }_2^2$ (30)

$=\sqrt{ϵ}{\displaystyle \sum _{\lambda }}\lambda {\Vert \widehat{x}(\lambda )\Vert }_2^2$ (31)

$\le \sqrt{ϵ}{\displaystyle \sum _{\lambda }}{\Vert \widehat{x}(\lambda )\Vert }_2^2$ (32)

$=\sqrt{ϵ}{\Vert X\Vert }_D^2.$ (33)

∎

定理证明8。

${\Vert \sigma (\overline{X}{W}_1)W_2-{\tilde{A}}_{\text{rw}}\sigma ({\tilde{A}}_{\text{rw}}X{W}_1)W_2\Vert }_D$ (34)

$\le \left({\Vert \sigma (\overline{X}{W}_1)-{\tilde{A}}_{\text{rw}}\sigma (\overline{X}{W}_1)\Vert }_D+{\Vert {\tilde{A}}_{\text{rw}}\sigma (\overline{X}{W}_1)-{\tilde{A}}_{\text{rw}}\sigma ({\tilde{A}}_{\text{rw}}X{W}_1)\Vert }_D\right)\rho (W_2)$ (35)

$=\left({\Vert {\tilde{L}}_{\text{rw}}\sigma (\overline{X}{W}_1)\Vert }_D+{\Vert \overline{X}-{\tilde{A}}_{\text{rw}}X\Vert }_D\rho (W_1)\right)\rho (W_2)$ (36)

$\le \left(O({ϵ}^{1/4}){\Vert \overline{X}\Vert }_D+R(2){\Vert Z\Vert }_D\right)\rho (W_1)\rho (W_2).$ (37)

∎