PAMI（IEEE Transactions on Pattern Analysis and Machine Intelligence）模式分析与机器智能-2021 IF: 17.730
Filippo Maria Bianchi Daniele Grattarola Lorenzo Livi Cesare Alippi
Abstract
流行的图神经网络基于多项式频谱滤波器在图上实现卷积操作。在本文中，我们提出了一种新型的图卷积层，其灵感来自于自回归移动平均（ARMA）滤波器，与多项式滤波器相比，它提供了更灵活的频率响应，对噪声更稳定，并能更好地捕捉全局图结构。我们提出了一个具有递归和分布式表述的ARMA滤波器的图神经网络实现，获得了一个卷积层，它可以有效地训练，在节点空间中定位，并在测试时可以转移到新的图上。我们进行了频谱分析来研究所提出的ARMA层的过滤效果，并报告了四个下游任务的实验情况：半监督节点分类、图信号分类、图分类和图回归。结果表明，与基于多项式滤波器的图神经网络相比，ARMA层带来了明显的改进。
1. Introduction
图神经网络（GNN）是一类位于深度学习和结构化数据方法之间的模型，它通过考虑离散对象（节点）之间的任意关系（边）来进行推理。GNN结合图上局部邻域内的节点特征来学习节点表征，这些表征可以直接映射为分类标签或实际数值，或结合生成图嵌入，用于图分类和回归。
这项工作的重点是在谱域中用非线性可训练滤波器实现卷积的GNN。这种滤波器有选择地缩小或放大图形信号的傅里叶系数（节点特征的一个实例），然后将节点特征映射到一个新的空间。为了避免昂贵的频谱分解和频域投影，最先进的GNN将图形滤波器实现为低阶多项式，直接在节点域学习。多项式滤波器具有有限的脉冲响应，在局部节点邻域上对图形信号进行加权移动平均滤波，允许快速分布式实现，如基于切比雪夫多项式和兰佐斯迭代的实现。多项式滤波器的建模能力有限，由于其平滑性，不能对频率响应的急剧变化进行建模。最重要的是，高阶多项式是达到高阶邻域的必要条件，但它们往往计算成本更高，最重要的是，过拟合训练数据使模型对图信号或底层图结构的变化很敏感。一类更通用的滤波器是自回归移动平均滤波器（ARMA），与参数数量相同的多项式滤波器相比，它提供了更多的频率响应，并能解释高阶邻域。
**note：**多项式滤波器：1.建模能力有限，由于其平滑性，不能对频率响应的急剧变化进行建模。2.计算成本高。3.过拟合。
在本文中，我们解决了现有的由多项式滤波器启发的图卷积层的局限性，并提出了一种基于ARMA滤波器的新型GNN卷积层。我们的ARMA层实现了一个非线性和可训练的图形滤波器，它概括了基于多项式滤波器的卷积层，并通过对滤波器频率响应的灵活设计，为GNN提供了增强的建模能力。ARMA层以较少的参数捕获全局图结构，克服了基于高阶多项式滤波器的GNN的局限性。
**note：**ARMA滤波器：1.增强的建模能力。2.参数少。
ARMA滤波器在节点空间中没有被定位，需要计算矩阵求逆，这在GNN的背景下是难以实现的。为了解决这个问题，提议的ARMA层依赖于递归公式，这导致了快速和分布式的实现，利用了对张量的有效稀疏操作。由此产生的滤波器不是在由给定拉普拉斯引起的傅里叶空间中学习的，而是在节点空间中定位的，并且与底层图结构无关。这使得我们的GNN能够在归纳推理任务的测试阶段处理具有未见过的拓扑结构的图。
在半监督的节点分类、图信号分类、图分类和图回归任务中，对所提出的ARMA层的性能进行了评估。 结果表明，配备ARMA层的GNN在每个下游任务中都优于配备多项式滤波器的GNN。
2.背景:图谱滤波
我们假设一个有$M$个节点的图由对称邻接矩阵$A∈R^{M×M}$来描述，并将图信号$X∈R^{M×F}$称为与图节点相关的所有特征（$R^F$中的向量）的实例。令$L = I_M - D^{-1/2}AD^{-1/2}$是图的对称归一化拉普拉斯（其中$D$是度数矩阵），频谱分解$L = \sum^M_{m=1} λ_mu_mu^T_m$ . 图滤波器是根据作用于每个特征值$λ_m$的频率响应$h$，在$L$的特征向量基础上修改$X$的成分的算子。滤波后的图形信号为:
$ L = UAU^T~~~~L^K=UA^KU^T$
$$ \overline{X} = \sum^M_{m=1} h(λ_m)u_mu^T_mX = Udiag[h(λ_1),...,h(λ_M)]U^TX~~~~~(1)$$
note:
这一表述启发了Bruna等人的开创性工作，他们在神经网络中实现了谱图卷积。他们的GNN从头到尾学习了一个实现为$h=Bc$的滤波器的参数，其中$B∈R^{M×K}$是一个基样条函数，$c∈R^K$是一个控制参数的向量。这样的滤波器不是本地化的，因为对特征向量的完全投影产生了无限长的路径，而且滤波器考虑了每个节点与整个图形的相互作用，而不是那些仅限于节点附近的相互作用。由于这与经典卷积滤波器的局部设计形成了鲜明的对比，后续工作引入了具有平滑系数的光谱滤波器的参数化，以实现空间定位。然而，公式（1）中的频谱过滤的主要问题是计算的复杂性：不仅$L$的特征分解在计算上是昂贵的，而且每当过滤器被应用时都要计算与$U$的双重乘积。值得注意的是，即使$L$是稀疏的，公式（1）中的$U$也是满秩的。最后，由于这些频谱滤波器依赖于特定的拉普拉斯频谱，它们不能被转移到其他结构的图上。由于这个原因，这种频谱GNN不能用于下游任务，如图分类或图回归，其中每个数据是一个具有不同拓扑结构的图。
2.1基于多项式滤波器的GNN及其局限性
所需的滤波器响应$h(λ)$可以用$K$阶的多项式来近似。
$$ h_{POLY}(λ)=\sum^K_{k=0}\omega_kλ^k ~~~~~~(2)$$
它对图形信号进行加权移动平均。这些滤波器克服了频谱表述的重要限制，因为它们避免了特征分解，而且它们的参数与拉普拉斯频谱无关。多项式滤波器在节点空间中被定位，因为过滤后的信号中每个节点的输出是节点与其$K-hop$邻居的线性组合。
假设多项式$K$的阶数很小，且与图中节点的数量$M$无关。
为了在节点空间中表达多项式滤波器，我们首先回顾一下，任何对角矩阵，如拉普拉斯的$k$次方，可以通过取其特征值的幂来计算，即$L^k = Udiag[λ^k_1, . . . , λ^k_M ] U^T$。由此可见，滤波操作变成了:
$$ \overline{X}=(\omega_0I+\omega_1L+\omega_2{L^2}+...+\omega_K{L^K})X=\sum^K_{k=0}\omega_kL^kX ~~~~~~~~(3)$$
公式（2）和（3）表示一个通用的多项式滤波器。在现有的多项式类别中，切比雪夫多项式经常被用于信号处理，因为它们可以减弱截止频率附近不需要的振荡，在我们的例子中，这就是拉普拉斯的特征值。快速局部GNN滤波器可以通过切比雪夫扩展$T_k(x)=2xT_{k-1}(x)-T_{k-2}(x)$来近似所需的滤波器响应，从而形成卷积层，进行过滤操作:
$L = I_M - D^{-\frac{ 1 }{2}} AD^{-\frac{ 1 }{2}}$
$$ \overline{X}=\sigma(\sum^{K}_{k=0}T_k(\widetilde{L})XW_k) ~~~~(4)$$
$\overline{X}=\sigma((T_0W_0+T_1W_1)X)=\overline{X}=\sigma((W_0+\widetilde{L}W_1)X)= \sigma((I-\widetilde{L})XW))=\sigma((I-(L-I))XW)=\sigma((I_M + D^{-\frac{ 1 }{2}} AD^{-\frac{ 1 }{2}})XW)$
其中，$\widetilde{L}=2L/λ_{max}-I_M$，$σ(-)$是一个非线性激活（例如，sigmoid或ReLU函数），$W_k∈R^{F_{in}×F_{out}}$是k个可训练的权重矩阵，将节点特征从$R^{F_{in}}$映射到$R^{F_{out}}$。
$k$度多项式滤波器的输出是每个顶点的$k-hop$邻域内输入的线性组合。由于超出$k-hop$邻域的输入对过滤操作的输出没有影响，为了捕捉图上较大的结构，有必要采用高度多项式。然而，高阶多项式的内插和外推性能很差，因为它们过度拟合已知的图形频率，即拉普拉斯的特征值。这阻碍了GNN的泛化能力，因为它对噪声和图形拓扑结构的微小变化变得敏感。此外，在训练和推理过程中，评估一个高度的多项式在计算上是很昂贵的。最后，由于多项式是非常平滑的，它们不能模拟具有急剧变化的滤波器响应。
Kipf & Welling提出了一个特殊的一阶多项式滤波器，用于半监督的节点分类。在他们的GNN模型中，称为图形卷积网络（GCN），卷积层是切比雪夫滤波器的简化版本，通过考虑$K=1$和设置$W=W_0=-W_1$，从公式（4）中获得。
$$ \overline{X} = \sigma(\hat{A}XW) ~~~~~~~(5)$$
此外，$\widetilde{L}$被$\hat{A} = \hat{D}^{-1/2} \widetilde{A}\hat{D}^{-1/2}$取代，其中$\widetilde{A} = A + γI_M$（通常，$γ = 1$）。修改后的邻接矩阵$\hat{A}$包含自循环，通过确保一个节点是其一阶邻接的一部分，并且其特征在卷积后被保留（在一定程度上），从而补偿了多项式中0阶项的删除。高阶邻域可以通过堆叠多个GCN层来达到。一方面，GCNs减少了过拟合和高阶多项式的切比雪夫滤波器的沉重计算负荷。另一方面，由于每个GCN层都会进行拉普拉斯平滑，经过几次卷积后，节点特征在图形上变得过平滑，最初的节点特征会丢失。
3.图形信号的有理过滤器
ARMA滤波器可以很好地近似任何所需的滤波器响应$h(λ)$，这要归功于合理的设计，与多项式滤波器相比，它可以模拟更多种类的滤波器形状。一个$K$阶的ARMA滤波器的滤波响应，在下文中表示为$ARMA_K$:
$$ h_{ARMA_K}(λ) = \frac{\sum^{K-1}{k=0}p_kλ^k}{1+\sum^{K}{k=1}q_kλ^k} ~~~~~~~~~(6) $$
在节点空间中转换为以下过滤关系:
$$\overline{X} =(I+\sum^{K}{k=1}q_kL^k)^{-1}(\sum^{K-1}{k=0}p_kL^k) X ~~~~~~~~(7)$$
请注意，通过设置$q_k=0$，对于每一个$k$，我们可以恢复一个多项式滤波器，它被认为是模型的$MA$项。纳入这些系数编码的额外$AR$项使ARMA模型对噪声具有鲁棒性，并允许捕捉图上更长的动态，因为$\overline{X}$反过来取决于节点特征的几个传播步骤。与相同程度的多项式滤波器相比，这是捕捉图上更长的依赖关系和更多的全局结构的关键。
公式（7）中的矩阵求逆计算起来很慢，并且产生一个密集的矩阵，使我们无法使用稀疏乘法来实现GNN。在本文中，我们遵循一种直接的方法来避免计算求逆，这种方法可以很容易地扩展到神经网络的实现。具体来说，我们通过迭代一阶递归来近似$ARMA_1$滤波器的效果，直到收敛。
$$ \overline{X}^{(t+1)} = aM\overline{X}^{(t)}+bX~~~~~~~(8)$$
其中：
$$ M = \frac{1}{2}(λ_{max}-λ_{min})I-L~~~~~~~(9) $$
公式（8）中的递归在图信号处理中被采用来对图信号进行低通滤波，但它也等同于标签传播和个性化网页排名中使用的递归更新，通过具有重启概率的随机行走来传播图上的信息。
按照公式（8）中的推导，我们从公式（8）的收敛性来分析$ARMA_1$滤波器的频率响应。
$$\overline{X} = \lim_{t \to \infty}[(aM)^t \overline{X}^{(0)}+b\sum^t_{i=0}(aM)^iX]~~~~~~~~~(10) $$
$M$和$L$的特征向量是相同的，而特征值的关系如下。$µ_m = (λ_{max} - λ_{min})/2 - λ_m$，其中$µ_m和λ_m$分别代表$M和L$的第$m$个特征值。由于$μ_m∈[-1, 1]，对于|a| < 1$，公式（10）的第一项，$(aM)^t$，在$t → ∞$时归零，与初始点$ \overline{X}^{(0)}$无关。第二项，$b \sum^t_{i=0}=(aM)^i$，是一个几何序列，收敛于矩阵$b(I - aM)^{-1}$，特征值为$b/(1 - aµ_m)$。由此可见，$ARMA_1$滤波器的频率响应为:
$$ h_{ARMA_1}(µ_m) = \frac{b}{1-aµ_m} ~~~~~~~~~(11) $$
通过对$K$个$ARMA_1$滤波器求和，有可能恢复公式（7）中$ARMA_K$滤波器的分析形式。由此产生的滤波操作是
$$ \overline{X} = \sum^K_{k=1}\sum^{M}_{m=1} \frac{b}{1-a_kµ_m}u_mu^T_mX~~~~~~~~~(12)$$
$$ h_{ARMA_K}(µ_m) = \sum^K_{k=1} \frac{b_k}{1-a_kµ_m} ~~~~~~~~~(13) $$
通过将一些系数设置为0，可以得到公式（6）中分子和分母的不同阶数（≤K），由此可见，当所有系数$q_k$被设置为0时，ARMA滤波器概括为多项式滤波器。
4.ARMA神经网络层
在图形信号处理中，公式（8）中的滤波器系数$a和b$通过线性回归进行优化，以再现所需的滤波器响应$h^∗(λ)$，这必须由设计者预先提供。在这里，我们考虑一种机器学习方法，不需要指定目标响应$h^∗(λ)$，而是通过优化一个与任务相关的损失函数，从数据中端到端学习参数。重要的是，我们还引入了非线性因素，以提高可以学习的滤波器响应的表示能力。
所提出的ARMA1滤波器的神经网络配方通过图形卷积跳（GCS）层来实现公式（8）的递归更新，定义为:
$$ \overline{X}^{(t+1)} = \sigma(\widetilde{L}\overline{X}^{(t)}W+XV)~~~~~~~(14) $$
其中$σ(-)$是一个非线性激活函数，如ReLU、sigmoid或双曲正切（tanh），$X$是初始节点特征，$W∈R^{F^{out}×F^{out}}和V∈R^{F^{in}×F^{out}}$是可训练参数。修改后的拉普拉斯矩阵$\widetilde{L}$是通过在公式（9）中设置$λ_{min} = 0和λ_{max} = 2$来定义的，然后$\widetilde{L}= M$。这是一个合理的简化，因为$L$的频谱位于$[0, 2]$，可训练参数$W和V$可以补偿引入的小偏移。公式（14）中的展开递归对应于共享相同参数的GCS层的堆叠。
每个GCS层在节点空间中都是本地化的，因为它执行的过滤操作取决于相邻节点之间的局部交换，并且通过跳连接，也取决于初始节点特征$X$。GCS层的计算复杂性与边的数量呈线性关系（在时间和空间上），因为该层可以有效地实现为$\widetilde{L}和\overline{X}(t)$之间的稀疏乘法。
$ARMA_1$滤波器的神经网络表述是通过迭代公式（14）得到的，直到收敛，即直到$||\overline{X}^{(T+1)} - \overline{X}^{(T)}|| < \epsilon $，其中$ \epsilon$ 是一个小的正常数，$T$是收敛时间。定理1保证了公式（14）中更新的收敛性，该公式与$ARMA_1$滤波器的原始递归公式有联系。
Theorem 1. 只要$||W||_2<1$，并且$σ(-)$是一个非扩张性的映射，那么无论初始状态$\overline{X}^{(0)}$如何，方程(14)都会收敛到一个唯一的固定点。
证明： 令$\overline{X}^{(0)}_a$和$\overline{X}^{(0)}_b$是两个不同的初始状态，$||W||_2<1$。在应用公式（14）进行$t+1$步后，我们得到状态$X^{(t+1)}_a和\overline{X}^{(t+1)}_b$。如果非线性$σ(-)$是一个非扩展图，如ReLU函数，则以下不等式成立:
如果非线性$σ(-)$也是一个压缩函数（例如，sigmoid或tanh），那么（15）中的第一个不等式是严格的。
由于根据定义，$\widetilde{L}$的最大奇异值≤1，所以$||\widetilde{L}||_2||W||_2<1$,因此，(15)意味着公式(14)是一个收缩映射。根据Banach定点定理，收敛到一个唯一的固定点，因此，初始状态的不重要。
从定理1可以看出，有可能选择一个任意的$ \epsilon>0$，对其
$$ \exists T_\epsilon<\infty s.t.~ ||\overline{X}^{(t+1)} - \overline{X}^{(t)}||2\leqslant \epsilon, \forall t\geqslant T{\epsilon}$$
因此，我们可以很容易地实现一个迭代的停止标准，在有限的时间内满足这个标准。
与公式（12）中的ARMA滤波器的表述类似。$ARMA_K$卷积层的输出是通过合并$K$个平行的GCS层的输出来获得的。
4.1实现
每个GCS堆栈$k$可能需要不同的、可能很高的迭代次数$T_k$来收敛，这取决于节点特征$X$的值和权重矩阵$W_k和V_k$。这使得神经网络的实现变得很麻烦，因为计算图是动态的，在训练过程中每次用梯度下降更新权重矩阵时都会发生变化。此外，如果$T_k$很大，为了通过时间的反向传播来训练参数，神经网络必须多次展开，这就引入了一个高计算成本和梯度消失的问题。
一个解决方案是遵循储备池计算的方法，即每个堆栈中的权重矩阵$W_k和V_k$是随机初始化的，并且没有经过训练。我们注意到，随机权重的初始化保证了$K$个GCS堆栈实现不同的过滤操作。为了弥补训练的不足，高维特征被利用来产生丰富的潜在表征，以分解数据中的变化因素。然而，具有高维特征空间的随机架构在推理时内存效率低，计算成本高。
本工作中考虑的第二种方法是完全放弃收敛的要求，将迭代次数固定为一个常数$T$，因此在每个GCS堆栈k中，$T_k=T$。这样，我们得到一个易于实现、快速训练和评估的GNN，并且不受稳定性问题的影响。值得注意的是，定理1的约束$||W||_2 < 1$可以通过在损失函数中加入L2权重衰减正则化项来放松。
即使通过堆叠少量的GCS层$T$，由于非线性和可训练的参数，我们期望GNN能够学习大量的节点表征。 作为非线性，我们采用ReLU函数，与压制非线性相比，它通过促进梯度流动提高了训练效率。
鉴于迭代次数有限，初始状态$\overline{X}^{(0)}$现在影响到最终的表示$\overline{X}^{(T)}$。一个自然的选择是用$\overline{X}^{(0)}=0∈R^{M×F^{out}}$或者用节点特征的线性变换来初始化状态$\overline{X}^{(0)}=XW^{(0)}$，其中$W^{(0)}∈R^{F^{in}×F^{out}}$取代堆栈第一层中的$W$。我们采用了后者的初始化，这样节点特征也会被第一个GCS层传播。我们还注意到，可以设置$W^{(0)}=V$来减少可训练参数的数量。
$ARMA_K$卷积层的输出计算为:
$$ \overline{X} = \frac{1}{K} \sum^K_{k=1}\overline{X}^{(T)}_k ~~~~~~~(16)$$
其中，$\overline{X}^{(T)}_k$是第$k$个堆栈中最后一个GCS层的输出。图1描述了提出的$ARMA$图卷积层的方案。
图1. ARMA卷积层。相同的颜色表示权重是共享的。
为了鼓励每个GCS堆栈学习具有与其他堆栈不同的响应的过滤操作，我们对每个GCS层的跳过连接$XV_k$应用随机的丢弃。这导致了学习一组异质的特征，当这些特征组合起来形成$ARMA_K$层的输出时，就会产生强大的、富有表现力的节点表示。我们注意到，GCS堆栈每一层的参数共享赋予了GNN一个强大的正则化，有助于防止过拟合，并大大降低了模型的复杂性，即可训练参数的数量。最后，由于GCS堆栈是相互独立的，ARMA层的计算可以分布在多个处理单元上。
4.2性质以及与其他方法的关系
与直接在谱域中定义的滤波器相反，ARMA滤波器不明确地依赖于$L$的特征向量和特征值，使它们对底层图结构的扰动具有鲁棒性。由于这个原因，正如一般的有理过滤器所正式证明的那样，所提出的$ARMA$过滤器是可转移的，也就是说，它们可以应用于在训练期间没有看到的具有不同拓扑结构的图。
我们架构中的跳过连接允许堆叠许多GCS层，而没有过度平滑节点特征的风险。由于权重共享，ARMA架构与用于处理连续数据的具有剩余连接的递归神经网络有相似之处。
与直接在节点域操作的GNN类似，每个GCS层计算顶点$i$的过滤信号$\overline{X}^{(t+1)}_i$，作为其1跳邻域$j∈N(i)$的信号$x^{(t)}_j$的组合。这样的换元聚合解决了未定义的顶点排序和不同的邻域大小的问题，使得所提出的算子的换元是等值的。
ARMA中的跳过连接在堆栈的每个GCS层$t$中注入初始节点特征$X$，这与跳过连接不同，跳过连接将前一层$X^{(t-1)}$的输出作为输入，或者将GNN堆栈中的所有层直接连接到输出。
ARMA层可以自然地处理时变的拓扑结构和图形信号，方法是用一个随时间变化的输入$X^{(t)}$取代公式（14）中的常数项$X$。
最后，我们讨论了所提出的ARMA GNN和CayleyNets之间的关系，CayleyNets是一种GNN架构，它也近似于一个有理过滤器的效果。具体来说，节点空间中的Cayley多项式的过滤操作是
为了用一连串的可微分操作来近似公式（17）中的矩阵反演，CayleyNets采用了固定数量的雅可比迭代$T$。在实践中，雅可比迭代将每个项$(L + iI)(L - iI)^{-1}$近似为具有固定系数的$T$阶多项式。因此，由CayleyNet执行的过滤操作的形式为
我们注意到，公式（17）和（18）稍微简化了Levie等人提出的原始表述，但使我们能够更好地理解CayleyNet实际执行的操作类型。具体来说，公式（18）实现了一个$KT$阶的多项式过滤器，如公式（3）中的过滤器。
由于这个原因，CayleyNets与公式（4）中的Chebyshev滤波器有很强的相似性，因为它在应用非线性之前使用一个（高阶）多项式来传播图上的节点特征为$KT$跳。另一方面，拟议的ARMA层中的每一个平行堆栈$K$只传播当前的节点表征$\overline{X}^{(t)}$跳，并在应用非线性之前将它们与节点特征$X$相结合。
5. ARMA层谱分析
在这一节中，我们展示了提出的ARMA层如何实现具有大量频率响应的过滤操作。由于非线性的存在，第3节中得出的ARMA滤波器的滤波响应不能被利用来分析我们的GNN公式。因此，我们首先回顾一下，滤波器改变了由$L$诱导的特征基上的图形信号$X$的分量（根据Sylvester定理，这与由$\widetilde{L}$诱导的分量相同）。参照公式（1），$X$首先被$U^T$投射到$L$的特征空间上，然后滤波器$h(λ_m)$改变$X$在每个特征向量$u_m$上的分量值，最后$U^T$映射回节点空间。通过在公式（1）中对$U^T$进行左乘，我们可以得到
$$ U^T \overline{X} = diag[h(λ_1),...,h(λ_M)]U^TX , \sum^M_{m=1}u^T_m\overline{X}=\sum^M_{m=1}h(λ_m)u^T_mX.~~~~~~(19)$$
当$\overline{X}$是ARMA层的输出时，$U^T\overline{X}$定义了原始成分$U^T X$是如何被GNN改变的。因此，我们可以用数字计算ARMA层的未知滤波器响应，即$U^T \overline{X}$和$U^T X$之间的比率。我们将经验滤波器响应$\widetilde{h}$定义为:
其中，$\overline{X}_f$是输出$\overline{X}_k$的$f$列，$X_f$是图形信号$X$的$f$列，$u_m$是$L$的一个特征向量。
经验滤波器的响应使我们能够分析ARMA层实现的滤波类型。我们首先比较公式(8)中的递归，根据公式(11)，它收敛到一个具有响应${h_{ARMA_1}(µ_m)}^M_{m=1}$的$ARMA_1$滤波器，与第k个GCS栈的经验响应${ \widetilde{h}{m,k}}^M{m=1}$。为了便于解释结果，我们将GCS层的输出特征数量设置为$F_{out} = 1$，在公式（14）中让$W = a$和$V = b1_{F_{in}}$。注意，我们与公式（8）保持一致，其中$a和b$是$ARMA_1$滤波器的参数。下面我们考虑Cora引文网络中的图和节点特征。我们注意到，本节中的例子与第6节中提出的半监督节点分类任务的结果无关，任何其他数据集都可以用来代替Cora。
图2(a, b)显示了在改变层数$T$时，两个不同的GCS堆栈的经验响应$ \widetilde{h}_1和 \widetilde{h}_2$。随着$T$的增加，$ \widetilde{h}_1和 \widetilde{h}_2$变得与$ARMA_1$滤波器的分析响应更加相似，在这两幅图中用黑线表示。这支持了我们的主张，即$\widetilde{h}$可以估计GNN过滤操作的未知响应。
图2. 在$(a，b)$中，两个GCS堆栈的经验滤波器响应，T=1，2，3；黑线表示具有类似参数的$ARMA_1$滤波器的分析响应。在（c）中，是T=1、2、3层的GCN的经验响应。在$(d，e)$中，输入图形信号$X$的原始分量（黑色），以及由两个GCS堆栈处理的T=1，2，3的图形信号$\overline{X}$的分量（彩色）。 在（f）中，由GCN处理的$\overline{X}$的分量为T=1，2，3层。
图2$(d，e)$显示了两个GCS堆栈如何在傅里叶基础上修改$X$的成分。特别是，我们用黑色描述了与每个图形频率$μ_m$相关的分量$u^T_mX, m = 1, . . . , M$与每个图形频率$µ_m$相关。我们用颜色描述分量$u^T_m\overline{X}$，它显示了GCS对与每个频率相关的分量的堆叠过滤程度。图2(a)和2(d)中的响应和信号分量是在$a=0.99和b=0.1$的情况下得到的，而在图2(b)和2(e)中，$a=0.7和b=0.15$。
在图2(c)中，我们展示了由GCN堆叠产生的经验响应。正如最近的工作中所强调的那样，通过堆叠一个或多个GCN获得的滤波具有对称放大频谱的最低和最高频率的不良效果。这是由于GCN滤波器的响应，在线性情况下是$(1-λ)^T$，当$T$为奇数时，可以承担负值。这种影响通过将$γIM$与邻接矩阵相加而得到缓解，它增加了权重为$γ$的自循环，缩小了图形滤波器的谱域。对于高的$γ$值，GCN的作用更像是一个低通滤波器，可以防止高频震荡。这是由于自循环限制了信息在图中的传播和邻居之间的交流。然而，即使添加了$γIM$，GCN也几乎完全切断了中频，然后再次放大了高频，如图2（f）所示。
GCN的堆栈在实现不同的过滤操作方面缺乏灵活性，因为修改GCN响应的唯一自由度包括手动调整超参数$γ$以缩减频谱。另一方面，不同的GCS堆栈可以产生异质的滤波器响应，这取决于每个堆栈中的可训练参数的值。这就是为提出的ARMA层提供强大的建模能力，它可以学习大量的滤波器响应，通过结合$K$个GCS堆栈有选择地缩小或放大图形的傅里叶成分。
与$ARMA_1$滤波器类似，每个GCS堆栈表现为一个低通滤波器，随着频率的增加，逐渐阻尼傅里叶成分。然而，我们回顾一下，高通和带通滤波器可以作为低通滤波器的线性组合来获得。为了在实践中显示这种行为，在图3中，我们报告了两个不同的$ARMA_K$滤波器获得的经验滤波器响应和修正的傅里叶分量，$K = 3$。
图3. 虽然每个GCS堆栈表现为一个低通滤波器，但一个$K=3$的$ARMA$层可以实现不同形状的滤波器。(a)中的$ARMA$层实现了高通滤波操作，对低频进行阻尼。(b)中的$ARMA$层实现了一个带通滤波操作，主要允许中频。
6.实验
我们考虑四个下游任务：节点分类、图信号分类、图分类和图回归。我们的实验重点是比较所提出的ARMA层与基于多项式滤波器的GNN层，即Chebyshev和GCN，以及CayleyNets，后者与ARMA一样，都是基于有理谱滤波器。作为额外的基线，我们还包括图注意网络（GAT）、GraphSAGE和图同构网络（GIN）。与这些方法的比较有助于将提议的ARMA GNN置于当前的技术水平中。我们还提到，在我们的工作被审查时，已经出现了其他与我们的方法有关的带有图卷积滤波器的GNN。
为了确保公平和有意义的评估，我们比较了用固定的GNN架构获得的性能，其中我们只改变了图形卷积层。 特别是，我们固定了GNN的容量（隐藏单元的数量），在每个数据集中使用相同的分割，以及相同的训练和评估程序。最后，在所有的实验中，我们对多项式/有理数过滤器使用相同的多项式阶数K，或者对GCN、GA T、GIN和GraphSAGE层使用K层的堆叠。实验中考虑的每个数据集的细节和每个模型的最佳超参数将推迟到第7章。
ARMA层的公开实现可在开源GNN库Spektral(TensorFlow/Keras)和PyTorch Geometric中找到。
6.1节点分类
首先，我们考虑在三个引文网络上进行传导性节点分类。Cora, Citeseer, 和Pubmed。输入是一个由邻接矩阵$A∈R^{M×M}$描述的单一图，节点特征$X∈R^{M×F_{in}}$，以及一个节点子集$M_l⊂M$的标签$y_l∈R^{M_l}$，目标是无标签节点的标签$y_u∈R^{M_u}$。节点特征是代表文本文件的稀疏词包向量。$A$中的二元无向边表示文档之间的引文链接。模型使用每个文档类别$(y_l)$的20个标签进行训练，性能评估为对$y_u$的分类精度。
其次，我们对蛋白质-蛋白质相互作用（PPI）网络数据集进行归纳节点分类。该数据集包括20个用于训练的图，2个用于验证，2个用于测试。与过渡性设置相反，测试图（以及相关的节点特征）在训练期间不被观察。此外，每个节点可以属于一个以上的类别（多标签分类）。
我们使用一个2层的GNN，引文网络有16个隐藏单元，PPI有64个单元。在引文网络中，我们利用了高丢弃率和L2-norm正则化来防止过拟合。表1报告了用一个新的分类方法获得的分类准确率。
直推节点分类是一项半监督的任务，它要求使用一个简单的模型和强大的正则化，以避免在现有的少数标签上过拟合。与Chebyshev等更复杂的滤波器相比，这是GCN成功的关键。由于其灵活的表述，提出的ARMA层可以实现适当的复杂程度，并在每个任务上表现良好。另一方面，由于PPI数据集较大，在训练期间有更多的标签可用，因此需要更少的正则化，而更复杂的模型则具有优势。与GCN相比，Chebyshev滤波器和CayleyNets取得了更好的性能，就反映了这一点。在PPI上，ARMA明显优于其他所有模型，因为它具有强大的建模能力，可以学习具有不同形状的滤波器响应。由于GAT、GraphSAGE和GIN中的每一层都只结合了一个节点的特征和它的一阶邻域的特征，与GCN类似，这些架构需要堆叠更多的层来达到高阶邻域，并受到同样的过平滑问题的影响。
我们注意到，表6中报告的ARMA层的最佳深度$T$在每个数据集中都很低。6在每个数据集中都很低。我们认为一个原因是图中的平均最短路径很小（见表5）。事实上，图中的大多数节点只需要几个传播步骤就可以到达，这并不奇怪，因为许多真实的网络是小世界网络。
图4显示了配置了GCN、Chebyshev、CayleyNet和ARMA层的GNN模型的训练时间。 ARMA层利用稀疏运算，与$L$中的节点数成线性关系，可以在与切比雪夫滤波器相当的时间内完成训练。另一方面，CayleyNet比其他方法慢，这是因为基于雅可比迭代的复杂表述导致了高阶多项式。
6.2图信号分类
在这个任务中，$N$个不同的图信号$X_n∈R^{M×F_{in}}，n=1， . . . , N$，定义在具有邻接矩阵$A∈R^{M×M}$的同一个图上，必须被映射到标签$y_1, . . . y_N$ 。我们按照MNIST和20news数据集的相同设置来进行这些实验。
MNIST 为了模仿经典的CNNs在规则的二维网格上运行，我们在MNIST图像的784个像素上定义了一个8-NN图。为了确定一个顶点$v_j$是否属于一个顶点$v_i$的邻域$N(v_i)$，我们计算像素（顶点）$i和j$的二维坐标之间的欧氏距离。
每个图形信号是一个矢量的图像$x∈R^{784}$。该架构是$GNN(32)-P(4)-GNN(64)-P(4)-FC(512)FC_{Softmax}(10)$，其中$GNN(n) $表示具有$n$个滤波器的GNN层，$P(s)$是具有位移的池化操作，$FC(u)$是具有$u$个单元的全连接层（最后一个FC具有Softmax激活）。池化是通过分层频谱聚类算法（GRACLUS）实现的，它将第$l$层的图形信号$\overline{X}^{(l)}$映射到一个新的节点特征空间$x^{(l+1)} ∈R^{M_{l+1}×F_{l+1}}$。
Tab. 2报告了使用GCN、Chebyshev、CayleyNet或ARMA获得的结果。结果是10次运行的平均值，显示ARMA与Chebyshev和CayleyNet相比，取得了略高的、几乎完美的准确性，而GCN的性能则明显较低。与PPI实验类似，更大的数据量使得更强大的架构可以被更精确地训练，并且与更简单的GCN相比取得更好的性能。
20news 该数据集由18,846个文件组成，分为20个类别。每个图形信号是由语料库中$10^4$个最常出现的词的词包代表的文件，通过Word2vec嵌入。$10^4$个节点的底层图形由一个16NN的邻接矩阵定义，如公式（21），不同的是，顶点邻接是由嵌入向量之间的欧氏距离而不是像素坐标计算的。我们报告了使用单一卷积层（GCN、Chebyshev、CayleyNet或ARMA）获得的结果，然后是全局平均集合和Softmax。如在，我们对Chebyshev使用32个通道。相反，对于GCN、CayleyNet和ARMA，只用16个过滤器就能获得更好的结果。表2中报告的分类精度显示，ARMA明显优于GCN和CayleyNet。
在这个实验中，我们使用了$K=1和T=1$的ARMA层的特殊配置（见表12），这相当于一个带有跳过连接的GCN。跳过连接允许对原始节点特征的贡献进行不同的加权，与邻居的特征相比。值得注意的是，与其他下游任务相反，20news图是由词嵌入的相似性生成的。这样一个人工图总是将一个嵌入向量与它的前16个邻居联系起来。我们认为，对于某些词来说，这些链接可能不是很相关，使用跳过的连接可以使它们的权重降低。
与节点分类数据集类似，20news图的平均最短路径也很低（见表11）。另一方面，MNIST图的直径要大得多，这是因为它的结构很规则，具有非常局部的连接性。这可以解释为什么对于MNIST来说，ARMA层的最佳深度$T$比其他任务都要大（见表12），因为要混合图上的节点特征需要几个步骤。
6.3 图分类
在这个任务中，第$i$个数据是由一对${A_i, X_i},i = 1, . . N$表示的图，其中$A_i∈R^{m_i×M i}$是一个带有$M_i$节点的邻接矩阵，$X_i∈R^{m_i×F}$是节点特征。每个样本必须用一个标签$y_i$进行分类。我们在五个不同的数据集上测试这些模型。我们使用节点度、聚类系数和节点标签作为额外的节点特征。对于每个数据集，我们采用固定的网络结构$GNN-GNN-GNN-AvgPoolFC{Softmax}$，其中$AvgPool$表示一个全局平均池层。我们用嵌套的10倍交叉验证法计算模型性能，重复运行10次，在每个折中使用$10%$的训练集进行早停。表3报告了平均准确率，包括使用GAT、GraphSAGE和GIN作为卷积层得到的结果。与多项式滤波器（Chebyshev和GCN）相比，配备了拟议的ARMA层的GNN实现了最高的平均精度。与同样基于有理滤波器实现的CayleyNets相比，ARMA不仅实现了更高的平均精度，而且标准差也更低。这些经验结果表明，我们的实现是稳健的，并证实了第4节中讨论的拟议ARMA层的可转移性。
6.4 图回归
这项任务类似于图分类，不同的是，现在的目标输出$y_i$是一个实值，而不是一个离散的类标签。我们考虑$QM9$化学数据库，其中包含超过13万个分子图。节点代表重原子，无定向的边代表它们之间的原子键。节点有离散的属性，表示四个可能的元素之一。回归任务包括预测一个分子的给定化学性质，给定其图形表示。至于图的分类，我们对嵌套的10折的80-10-10训练-验证-测试分割的性能进行评估。预测每个属性所采用的网络结构是$GNN（64）-AvgPool-FC(128)$。我们在表4中报告了10次独立运行的均方误差（MSE），相对于9个分子特性的预测。可以注意到，每个模型都达到了非常低的标准偏差。原因之一是训练数据量非常大，这使得GNN能够学习到一个概括性很强的配置。与之前的任务相反，这里GCN、Chebyshev和CayleyNet之间并没有明显的赢家，因为它们中的每一个在某些任务上的表现都比其他的好。另一方面，ARMA在预测每个分子特性时总是能达到最低的MSE。
8 结论
本文介绍了ARMA层，一种基于有理图滤波器的新型图卷积层。与基于同阶多项式滤波器的GNN层相比，ARMA层建立了更具表现力的滤波器响应模型，并能解释更大的邻域。我们的ARMA层由并行的循环操作堆栈组成，通过有效的稀疏张量乘法，近似于具有任意阶数K的图滤波器。我们报告了对我们的神经网络实现的频谱分析，这为所提出的方法提供了宝贵的见解，并表明我们的ARMA层可以实现大量的过滤器响应。实验表明，所提出的ARMA层在大量的图形机器学习任务上优于现有的GNN架构，包括那些基于多项式滤波器和其他更复杂的模型。=
标签：滤波器,卷积,多项式,overline,神经网络,GNN,节点,ARMA From： https://blog.51cto.com/u_16346809/8853873