WWW-2021, .1145/3442381.3449953
图神经网络（GNNs）在图结构数据学习中受到了相当多的关注。设计良好的传播机制是GNN最基本的组成部分。虽然大多数GNN基本上遵循信息传递的方式，但人们已经努力发现和分析它们的基本关系。
具有节点集 V 和边集 E 的图G =（V，E），边集V，n=|V|是节点数。这些节点是由该特征来描述的。矩阵X∈R n × f ^{n×f} n×f，其中 f 为节点特征的维数。G的图结构可以用邻接矩阵A∈R n × n ^{n×n} n×n来描述，其中，如果节点 i 和节点 j 之间有一条边，则为 A i j A_{ij} Aij = 1，否则为0。对角度矩阵记为 D=diag（d1，···，dn），其中 d i = ∑ j A i j d_i =sum_j A_{ij} di=∑jAij。我们使用 A ~ = A + I tilde A=A+I A~=A+I 来表示添加了自循环的邻接矩阵和 D ~ = D + I tilde D=D+I D~=D+I。然后归一化的邻接矩阵是 A ~ ^ = D ~ − 1 / 2 A ~ D ~ − 1 / 2 hat{tilde{A}} = tilde D ^{−1/2}tilde A tilde D ^{−1/2} A~^=D~−1/2A~D~−1/2。相应地， L ~ = I − A ~ ^ tilde L = I − hat{tilde{A}} L~=I−A~^是归一化对称正半定图拉普拉斯矩阵。
经过设计良好的不同gnn的传播机制基本上遵循相似的传播步骤，即节点特征在一定的深度上沿着网络拓扑进行聚合和转换。在这里，作者将k层的传播机制主要总结为以下两种形式。
对于具有层级特征变换的gnn（例如GCN），k层传播过程可以表示为：
其中 Z 0 = X Z^{0}=X Z0=X和Z是K-layer传播后的输出表示。而 ⟨ ⟩ K left langle rightrangle_{K} ⟨⟩K通常依赖于特定的GNN模型，表示K个卷积后的广义组合运算。 A g g { G ; Z ( k − 1 ) } Agg { G; Z^{(k−1)}} Agg{G;Z(k−1)}是指沿第k次卷积运算聚合（k−1）层输出Z（k−1），Trans（·）是相应的层特征变换运算，包括非线性激活函数ReLU和层特定的可学习权重矩阵W。
一些深度图神经网络（如APPNP ，DAGNN ）解耦了分层的Trans（·）和 A g g { G ; Z ( k − 1 ) } Agg { G; Z^{(k−1)}} Agg{G;Z(k−1)}，并在连续的聚合步骤之前使用一个分离的特征变换：
其中 Z ( 0 ) = T r a n s ( X ) Z ^{(0)}= Trans (X) Z(0)=Trans(X)，Trans（·）可以是原始特征矩阵X上的任何线性或非线性变换运算。
此外，组合操作 ⟨ ⟩ K left langle rightrangle_{K} ⟨⟩K通常是双重的：对于像GCN、SGC和APPNP这样的gnn， ⟨ ⟩ K left langle rightrangle_{K} ⟨⟩K直接利用了第K层的输出。对于使用来自其他层的输出的gnn，如JKNet和DAGNN， ⟨ ⟩ K left langle rightrangle_{K} ⟨⟩K可能表示对来自K层的一些（或全部）输出的池化、连接或注意操作。
实际上，包括聚合和转换在内的传播过程是gnn的核心。网络拓扑和节点特征是在传播过程中改进学习表示的两个最重要的信息源：网络拓扑通常对输入节点信号起低通滤波器的作用，使两个连接节点[16]的特征平滑。这样，学习到的节点表示就能够捕获图结构的同质性。对于节点特征，它本身包含复杂的信息，如低频信息和高频信息。节点特征可以灵活地用来进一步约束学习到的节点表示。例如，APPNP将原始节点特征添加到每个层学习到的表示中，这可以很好地保存个性化的信息，以减轻过度平滑。
以上分析表明，尽管不同的gnn具有不同的传播机制，但事实上，它们通常潜在的目标是实现两个目标：从特征中编码有用的信息和利用拓扑的平滑能力，这可以正式表述为以下优化目标：
这里，ξ 是非负系数，ζ 通常从[0,1]中选择，H是对原始输入特征矩阵X的变换，F1和F2被定义为任意的图的卷积核。Z是传播后的表示，对应于最小化目标O时的最终传播结果。
在这个统一的框架中，第一部分 O f i t mathcal O_{fit} Ofit 是一个拟合项，通过设计不同的图卷积核f1和f2，灵活地将H中的信息灵活地编码到学习到的表示Z。图卷积核F1和F2可以从I、 A ~ ^ hat {tilde{A}} A~^、 L ~ tilde L L~中选择，分别具有全通、低通、高通滤波的能力。第二项 O r e g mathcal O_{reg} Oreg 是一个图拉普拉斯正则化项，约束两个连接节点的学习表示变得相似，从而可以捕获同质性， O f i t mathcal O_{fit} Ofit 来自于以下图拉普拉斯正则化：
下面，作者从理论上证明了一些典型的gnn的传播机制实际上是我们提出的统一框架的特殊情况，如表1所示。这个统一的框架建立了一些典型的gnn之间的联系，能够从全面的角度来解释当前的gnn。
以上分析是针对连续K层图卷积运算，这里作者也关注了单层图卷积运算（GC运算），其传播机制如下：
JKNet 是一种深度图神经网络，利用不同区域的信息。这种体系结构有选择地将来自不同层的聚合与输出处的连接/最大集中/注意相结合，即将表示法“跳转”到最后一层。
为了方便起见，我们以类似的方式简化了第k个（k∈[1，K]）层图的卷积操作，忽略了σ(x) = x的非线性激活，并共享每个层的W* = W (0)W (1)···W（k−1）。那么第k层临时输出为 A k ~ ^ X W hat{tilde{A^k}}XW Ak~^XW*。利用最后一层的注意机制，JKNet的k层传播结果可以写为：
其中α1，α2，…，αK是可学习融合权值（ ∑ k = 1 K α k = 1 sum_{k=1}^{K} alpha_k = 1 ∑k=1Kαk=1），为了便于分析，我们假设第k层的所有节点共享一个共同的权值αk。
定理3.4。使用等式中的F1 = I、F2 = A ~ ^ hat{tilde{A}} A~^、ζ = 1和ξ∈（0，∞）(3)，JKNet的传播过程优化了以下目标：
这里的H = XW*是经过简化后的线性特征变换。
证明。同样地，我们可以设置等式的导数（20）相对于Z到零，得到最优Z为：
请注意，det（I + ξ L ~ tilde L L~）>0，因此矩阵{I + ξ L ~ tilde L L~} − 1 ^{−1} −1存在。则相应的封闭形式的解可以写成：
由于∀ξ > 0的 (ξ / 1+ξ) < 1，而矩阵 A ~ ^ hat{tilde{A}} A~^的绝对特征值以1为界，因此其所有的正幂都有有界的算子范数，那么逆矩阵可以用K→∞分解如下：
使用H = XW*，有以下扩展：
我们可以改变coefficientξ∈（0，∞）来拟合融合权重α1，α2，···，αK.当K层足够大时，JKNet在等式中的传播机制（19）近似对应于目标的等式 (20)。
定理3.5。在等式中使用F1 = F2 = I，ζ = 1和ξ∈（0，∞）(3)，DAGNN的传播过程优化了以下目标：
其中，H = fθ (X)为特征矩阵上的非线性变换，保留分数s0、s1、···、sK近似为ξ∈（0，∞）。
证明。设置等式的导数（26）从Z到零，得到的封闭解为：
通过类似于JKNet的分解过程，有了以下扩展：
请注意，我们可以更改ξ∈（0，∞）以适应保留分数。然后，DAGNN的传播机制近似对应于目标等式 (26)。
为了清晰起见，作者总结了表1中不同gnn与相应的目标函数之间的总体关系。可以看出，作者提出的框架抽象了代表性gnn之间的共性。基于这个框架，可以更容易地理解他们之间的关系。例如，定理3.1中SGC对应的优化目标只有一个图正则化项，而定理3.3中APPNP对应的优化目标同时具有拟合项和图正则化项。目标函数的显式差异很好地解释了deep APPNP（PPNP）在过平滑问题上优于SGC（GCN），因为另外需要学习到的表示对原始特征进行编码。
另一方面，作者提出的框架通过对目标优化函数进行数学建模，显示了gnn的一个大图景。考虑到不同的现有gnn可以适应这个框架，gnn的gnn变体也可以很容易地出现。我们所需要的就是在这个框架内根据特定的场景设计不同的变量（例如，不同的图卷积内核F1和F2），可以很容易地推导出相应的传播，并且可以自然地设计新的gnn架构。新设计的模型具有一个目标目标函数，更易于解释，更可靠。
基于统一的框架，作者发现当前大多数gnn简单地在特征拟合项中将F1和F2设为I，这意味着它们需要将H中的所有原始信息编码到z中。然而，事实上，H可能不可避免地包含噪声或不确定信息。注意到JKNet传播目标，利用F2= A ~ ^ hat{tilde{A}} A~^，可以编码低频信息在H到Z中。在现实中，情况更复杂，因为很难确定什么信息应该编码，只考虑一种类型的信息不能满足不同下游任务的需要，有时高频或所有信息甚至是有用的。在本节中，我们将重点设计新的f1和f2，以便在该框架下灵活地编码更全面的信息。
作者首先考虑在原始和低通滤波空间中建立H和Z的关系。
为了最小化等式中的目标函数（29），作者设置了等式的导数（29）从Z到零，推导出相应的封闭解如下：
可以重写等式（30）使用 A ~ ^ hat{tilde{A}} A~^作为：
考虑到矩阵反演导致的封闭解的计算效率低下，我们可以使用以下迭代逼近解，而不构造稠密逆矩阵：
它在等式中收敛于封闭形式的解（31）当k→∞和使用α∈（0,2/3）时，所有的系数都总是正的。
利用推导的两种传播策略（31）和等式（32），我们提出了两种新的封闭形式和迭代形式的gnn。请注意，作者将所提出的模型表示为带有低通滤波图卷积核（GNN-LF）的GNN。
闭合式GNN-LF。利用等式中的封闭形式的传播矩阵（31），我们用µ∈[1/2,1)、α∈（0,2/3）和H = fθ (X)定义了以下传播机制：
这里我们首先得到一个非线性变换结果H特性与MLP网络X fθ（·），并使用设计传播矩阵 { { µ + 1 / α − 1 } I + { 2 − µ − 1 / α } A ~ ^ } − 1 {{µ+ 1/α−1}I+ {2−µ−1/α}hat{tilde{A}}}^{−1} {{µ+1/α−1}I+{2−µ−1/α}A~^}−1 传播H和AH，然后我们可以得到表示编码特性信息从原始和低频空间。
迭代式GNN-LF。利用等式中的形式传播机制（32），我们可以用µ∈[1/2,1)，α∈（0,2/3）设计一个深度和计算效率高的图神经网络：
作者直接使用k层输出作为传播结果。这种迭代传播机制可以看作是基于分层 A ~ ^ hat{tilde{A}} A~^的邻域聚合，在特征矩阵H和滤波后的特征矩阵 A ~ ^ hat{tilde{A}} A~^H上有残差连接。请注意，解耦了层级转换和聚合过程，这有助于缓解过度平滑问题。
GNN-LF迭代和GNN-LF闭合有以下关系：
当K→∞时，左项趋于0，右项变成几何级数。该级数收敛，因为 A ~ ^ hat{tilde{A}} A~^的绝对特征值界为1，然后是等式（35）可重写为：
这正好是计算GNN-LF-闭的方程。
GNN-LF的训练也与其他gnn相同。例如，它评估了半监督多类节点分类任务中所有标记示例的交叉熵损失。
与GNN-LF类似，现在考虑在原始和高通滤波空间中保持H和Z的相似性。为了便于后续的分析，我们选择了以下目标：
类似地，β也是一个平衡系数，设置β∈（0，∞），使 I + β L ~ = V ∗ Λ ∗ V ∗ T I + βtilde{L}=V^*Λ^*{V^∗}^T I+βL~=V∗Λ∗V∗T也是一个对称的正半定矩阵，而矩阵 { I + β L ~ } 1 / 2 = V ∗ Λ ∗ 1 / 2 V ∗ T {I + βtilde{L}}^{1/2}=V^*{Λ^*}^{1/2}{V^∗}^T {I+βL~}1/2=V∗Λ∗1/2V∗T具有类似于 I + β L ~ I + βtilde{L} I+βL~的过滤行为。在等式中可以看到（37），通过调整平衡系数β，设计的目标可以灵活地约束Z和H在原始空间和高频空间中的相似性。
计算出的封闭形式的解为：
它也可以重写为：
考虑到逆矩阵的计算效率低下，作者在不构造密集逆矩阵的情况下给出了以下迭代近似解：
利用推导的两种传播策略（39）和在等式中（40），我们提出了两种新的封闭形式和迭代形式的gnn。类似地，我们使用GNN-HF来用高通滤波图卷积核表示GNN。
GNN-HF-闭合式。利用等式中的封闭形式的传播矩阵（39），我们定义了以下具有封闭传播机制的新型图神经网络：
注意，β∈（0，∞）和α∈(0,1]。通过将传播矩阵 { ( β + 1 / α ) I + ( 1 − β − 1 / α ) A ~ ^ } − 1 {(β + 1/α)I +(1−β−1/α)hat{tilde{A}}}^{−1} {(β+1/α)I+(1−β−1/α)A~^}−1直接应用于H和 L ~ tilde{L} L~H矩阵上，可以从原始空间和高频空间中得到表示编码特征信息。
GNN-HF-迭代式。利用迭代传播机制，我们有了一个具有β∈（0，∞）和α∈(0,1]的深度和计算效率高的图神经网络。
我们直接使用k层输出作为传播结果。同样，这种迭代传播机制可以看作是基于分层 A ~ ^ hat{tilde{A}} A~^的邻域聚合，以及特征矩阵H和高频滤波特征矩阵 L ~ tilde L L~H上的残差连接。并解耦了传播过程中的分层转换和聚合过程。
GNN-HF迭代式和GNN-HF闭合式有以下关系：
在本节中，我们研究了图谱域中的几种传播机制，以检验它们的表达能力。将具有f个输入信道的图信号 X ∈ R n × f X∈R^{n×f} X∈Rn×f上的K阶多项式滤波器定义为：其中，θk为对应的多项式系数。作者假设图信号X是非负的，X可以通过线性变换转换为输入信号H。我们的目的是比较不同gnn的多项式系数θk，并表明具有K阶灵活多项式滤波器系数的GNN-LF/HF具有更好的光谱表达能力。为了简洁，作者主要分析了GNN-LF的滤波器系数，而SGC、PPNP、GNN-HF的光谱分析见附录。
从定理4.2的分析中，我们得到了GNN-LF-iter在等式中的扩展传播结果（35），已证明收敛于传播结果gnn-lf-用K→∞关闭。将此传播结果进行分析，当K→∞时，我们有以下过滤表达式：
如果展开上述方程，则 L ~ k tilde{L}^k L~k（k∈[0，K]）上的滤波器系数可以归纳为以下形式：
从上述对GNN-LF的分析结果中，我们发现滤波器系数的表达形式依赖于不同的k，并由两个可调因子α和µ决定，这提高了光谱滤波器的表达能力，进一步缓解了过平滑问题。
GNN-HF的分析与GNN-LF的分析相似，为了简洁，作者在附录中分析了它们。
正如相关论文所指出的，过度平滑问题的原因是典型的GCN收敛于随机游动的极限分布，与输入特征隔离，使节点随着层数的增加而表示不可分割。[4]还从多项式滤波器系数的角度给出了另一个理解，并指出灵活的和任意的滤波器系数对于防止过度平滑是必要的。
我们可以发现： 1) SGC或k层图卷积运算具有固定的常数滤波系数，这限制了表达能力，进一步导致过度平滑。2) PPNP对SGC（GCN）具有更好的滤波表达能力，因为k阶的滤波系数随因子α一起是可变化的。3)与PPNP和SGC（GCN）相比，GNN-LF/HF在可调因子α、µ或β的影响下更具表现力，提高了多项式滤波器任意系数的拟合能力，有助于GNN-LF/HF缓解过平滑问题。从PPNP [14]、GNN-LF在等式中的极限分布来看（36），等式中的GNN-HF（53），我们还可以发现，它们都收敛于一个同时包含输入特征和网络结构信息的分布。这一特性还有助于减少过度平滑对PPNP/GNN-LF/GNN-HF的影响，即使层数趋近于无穷大。
本文研究了不同gnn传播机制的内在关系。作者建立了不同的gnn之间的联系和一个灵活的目标优化框架。所提出的统一框架提供了一个理解和分析不同gnn的全局视角，这进一步使我们能够识别当前gnn的弱点。在此基础上，提出了两种具有可调卷积核的具有低通和高通滤波能力的新型gnn，并分析了其优异的表达能力。大量的实验很好地证明了这两种gnn在真实世界数据集上优于最先进的模型。
本文发布于:2024-01-31 14:11:57，感谢您对本站的认可！
本文链接：https://www.4u4v.net/it/170668152029096.html
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系，我们将在24小时内删除。
| 留言与评论（共有 0 条评论） |
