点击上方卡片，关注“AI学术工坊”公众号
点击上方卡片，关注“AI学术工坊”公众号
各种重磅干货，第一时间送达
解耦图神经网络：同时训练多个简单的 GNN，而不是只训练一个各种重磅干货，第一时间送达
摘要
图神经网络 (GNN) 的效率极低，这是因为随着层数的增加，节点依赖性呈指数增长。这极大地限制了随机优化算法的应用，因此 GNN 的训练通常非常耗时。为了解决这个问题，我们提出将多层 GNN 解耦为多个简单模块，以便进行更高效的训练，该模块由经典的前向训练 (FT) 和设计的后向训练 (BT) 组成。在所提出的框架下，由于其简单性，每个模块都可以通过随机算法在 FT 中高效训练，而不会扭曲图信息。为了避免 FT 仅单向传递信息，并使用较深的模块充分训练浅层模块，我们开发了一种后向训练机制，使前一个模块能够感知后一个模块，该机制受到经典后向传播算法的启发。后向训练将反向信息传递引入解耦模块以及前向信息传递。为了研究解耦和贪婪训练如何影响表征能力，我们从理论上证明了线性模块产生的误差在大多数情况下不会在无监督任务上累积。理论和实验结果表明，所提出的框架效率高，性能合理，值得进一步研究。
论文链接：https://arxiv.org/pdf/2304.10126
论文标题：Decouple Graph Neural Networks: Train Multiple Simple GNNs Simultaneously Instead of One
作者：Hongyuan Zhang, Yanan Zhu, and Xuelong Li∗ , Fellow, IEEE
关键字
后向训练，高效训练，图神经网络。
引言
近年来，神经网络 [1]、[2] 由于其出色的性能，已被扩展到图数据，称为图神经网络 (GNN) [3]。由于 GNN 显著提高了图任务的结果，它已从不同方面得到了广泛的研究，例如图卷积网络 (GCN) [4]、[5]、图注意网络 (GAT) [6]、[7]、时空 GNN (STGNN) [8]、图自动编码器 [9]、[10]、图对比学习 [11] 等。
除了源自不同视角的变体之外，一个重要的主题是由众所周知的 GNN 效率低下所激发的。在经典神经网络 [2] 中，优化通常基于具有有限批量的随机算法 [12], [13]，因为样本彼此独立。然而，[14] 中定义的类似聚合的操作导致每个节点对其邻居的依赖性，并且一个节点的依赖节点数量随着层数的增长呈指数增长，从而导致批量大小意外增加。一些工作基于邻居采样 [14], [15], [16], [17] 和图近似 [18] 提出来限制批量大小，而一些方法 [19], [20] 尝试直接应用高阶图操作并牺牲最大的非线性。虽然 VRGCN [16] 尝试通过改进采样来控制方差，但训练稳定性是邻域采样方法 [14]、[15]、[17] 的一个问题。请注意，随着深度的增加，所需节点仍可能（缓慢）增长。Cluster-GCN [18] 找到具有大量连通分量的近似图，因此批次大小严格受上限限制。这些方法的主要挑战是采样过程中的信息缺失。简化方法 [19]、[20] 是有效的，但有限的非线性可能是这些方法的瓶颈。这些方法可以结合 GIN [21] 的思想来提高容量 [20]。
为了在保留精确图结构的同时应用随机优化，我们提出了一个框架，即堆叠图神经网络 (SGNN)，它将多层 GNN 解耦为多个简单的 GNN 模块，然后同时训练它们，而不是随着深度的增加将它们连接起来。受反向传播算法的启发，我们发现堆叠网络 [22] 与经典网络的主要区别在于没有训练信息从后者模块传播到前者模块。缺乏反向信息传递可能是堆叠模型性能限制的主要原因。贡献总结如下：（1）我们据此提出了一种反向训练策略，让前一个模块接收来自最终损失和后一个模块的信息，从而形成一个循环训练框架来控制偏差并正确训练浅层模块。(2) 在该框架下，多层 GNN 可以解耦为多个简单 GNN，本文将其称为可分离 GNN，这样每个训练步骤都可以使用随机优化，而无需对图进行任何采样或更改。因此，SGNN 可以同时兼顾非线性和高效率。(3) 我们研究了解耦和贪婪训练如何影响线性 SGNN 的表示能力。事实证明，当最终目标是图重建时，大多数情况下误差不会累积。
方法
受 SAE [22] 的启发，以及简化模型 [19]、[20] 对 GNN 非常有效的事实，我们因此重新思考了堆叠网络和多层 GNN 之间的实质性差异。总而言之，我们试图在本文中回答以下两个问题：
Q1：如何将复杂的 GNN 解耦为多个简单的 GNN 并联合训练它们？ Q2：解耦如何影响表征能力和最终性能？
我们将在本节讨论第一个问题，然后在第四节中详细阐述另一个问题。
A. 预备知识
所提模型的每个解耦 GNN 模型都被称为一个模块，为简单起见，第 个模块用 表示。向量和矩阵分别用粗体小写字母和大写字母表示。 表示 Frobenius 范数。给定一个图，让 为邻接矩阵， 为节点特征。典型的 GNN 层通常可以定义为
其中 是投影系数， 是 的函数。当我们讨论每个单独的模块时，为了简单起见，我们假设 。例如，GCN [4] 将 定义为 ， 是 的度矩阵。当集成多个层时，多个 GNN 层给出的学习到的表示可以写成
其中 是层数。假设邻居的平均数量为 。要计算 ，每个样本将需要 个额外样本。如果深度很大且图是连通的，则必须使用所有节点来计算一个节点。不受控制的批量大小会导致训练耗时。在 vanilla GNN 中，稀疏图上的计算复杂度为 )，其中 是迭代次数， 是 的维度。对于大规模数据集，时间和空间复杂度都过于昂贵。
B.堆叠图神经网络
虽然堆叠网络通常比多层网络具有更多参数，这通常表明堆叠网络可能更强大，但它们仅用作预训练的一种技术。具体来说，它们只是将当前网络学习到的表示转移到下一个网络，但没有反馈回来。这导致后续模块和最终目标不可见。由于前一个模块的不可靠性，堆叠模型通常用作无监督预训练模型。
重新思考网络的学习过程，多层通过基于梯度的方法同时优化，其中梯度由众所周知的后向传播算法计算[52]。该算法由前向传播（FP）和后向传播（BP）组成。FP计算BP所需的值，这可以看作是一个信息传递过程。请注意，FP类似于堆叠网络的训练。具体而言，将当前模块的输出传输到堆叠网络中的下一个模块就像在FP期间逐层计算神经元一样。受此启发，我们旨在设计一种类似BP的训练策略，即反向训练（BT），以便可以根据反馈调整前一个模块。我们的堆叠图神经网络（SGNN）的核心思想如图1所示。1）可分离性：效率的关键概念：在详细介绍 SGNN 之前，我们正式介绍如何通过 SGNN 加速 GNN 的关键概念和核心动机。
定义 3.1：如果 GNN 模型可以表述为
那么它就是一个可分离的 GNN。如果它可以进一步表述为
那么它是一个完全可分离的 GNN。
为了简单起见，将可分离 GNN 集定义为
以及完全可分离的 GNN 集
请注意，大多数单层 GNN 模型都是可分离的。例如，SGC [19] 是完全可分离的，其中 和 ，而单层 GIN [3] 是可分离的但不是完全可分离的，因为 通常成立。由一层组成的 JKNet [53] 也是可分离的，但不是完全可分离的。然而，单层 GAT [6] 不可分离，因为图操作与 相关。
可分离性实际上将 GNN 模型分解为 2 个部分，即图操作 和神经操作 。由于 GNN 中节点之间的所有依赖关系都是由图操作引起的，因此可以在可分离 GNN 中计算一次 （类似于预处理），然后将 GNN 转换为典型网络。计算 后，图中包含的信息已传递到 中，后续采样不会影响图的拓扑结构。因此，只要每个模块都是可分离的，我们就可以获得一个可以通过 SGD 优化的高效 GNN 模型。另一方面，完全可分离条件对于反向训练将信息传递到多个模块至关重要。由于大多数单层 GNN 是可分离的但不是完全可分离的，我们展示了如何修改可分离 GNN 以引入完全可分离性。
然后，我们通过展示如何处理 Q1 来正式阐明 SGNN 的核心思想。
**2) 前向训练 (FT)**：第一个挑战是如何为每个模块 设置训练目标。将 SGNN 应用于监督和无监督场景都至关重要。假设我们有一个可分离的 GNN 模块 ，设 为可分离 GNN 模块学习到的特征。对于无监督的情况，如果 是 GAE，则 FT 的损失公式为
其中 表示度量函数， 是映射函数。例如，[9] 引入的简单损失是 ，其中 是 Sigmoid 函数， 是 Kullback-Leibler 散度。其他选项包括但不限于对称内容重建 [10] 和图对比学习 [11]。对于具有监督信息的模块，引入投影矩阵 以将 维嵌入向量映射到具有 个类的软标签中。对于节点分类，损失可以简单地设置为
其中 是监督任务的监督信息。注意，如果 为常数，则上述损失等同于经典的 softmax 回归。损失也可以是链接预测、图分类等。虽然基础模块可以使用不同的损失，但为了简单起见，我们在本文中仅讨论所有模块使用同一种损失的情况。
3）反向训练（BT）：第二个挑战是如何同时训练多个可分离的GNN以确保性能。粗略地说，经典多层神经网络中所有层的梯度都是通过FP和BP重复传递信息而精确计算的。BP通过反馈让浅层感知深层。在SGNN中，FT中的尾部模块对头部模块是不可见的。因此，我们为SGNN设计了反向训练（BT）。为了实现反向信息传递，核心思想是通过定义预期特征来引入完全可分离性。对于可分离的GNN层作为SGNN中的模块
其中 ，我们的目标是调整其输入，以便前一个模块能够知道当前模块需要什么样的表示。但是， 不是可学习的参数。一种直接的方案是使用转换（）来调整模块的输入
其中 是可学习的方阵， 是非参数函数。显然， 可以看作是一个参数 GNN。为了保留 带来的高效率，我们进一步将修订后的 约束为完全可分离的 GNN，即
其中 。注意，如果 固定为 （或其他常数矩阵），则修改后的层相当于（7）中的原始可分离 GNN。总而言之，通过引入完全可分离性来修改可分离 GNN 层 ，如下所示
其中 表示从 到 的函数。记 ， 为预期特征。具体而言，令 为 在反向训练中学习到的预期特征，并作为 从 开始的预期输入。在前向训练中，信息的传递基于学习到的特征 ， 在反向训练中起着类似的作用。反向训练的损失试图缩小 的输出特征 与 的预期输入 之间的差异，
请注意， 仅在第一次前向训练后激活，导致 最终丢失，因为
并在每次反向训练期间更新。 的引入不会限制随机优化的应用，因为预期特征也可以在每次迭代中不受限制地进行采样。该过程总结为算法 1。
注意， 在 FT 期间保持为单位矩阵。这种设置导致跨 个基础模块的每次前向计算都等同于前向传播 层 GNN。换句话说，具有 个模块的 SGNN 可以看作是 层 GNN 的分解。有人可能会担心为什么不在 FT 中一起学习 和 。在这种情况下，我们更喜欢仅使用 来学习 的预期特征，并且 FT 中共同学习 的能力改进也可以通过 来实现，这相当于使用 GIN [21] 作为基础模块。
C.复杂性
由于每个基础模块都被视为可分离的 GNN，因此 的 FT 和 BT 都可以分为两个步骤，即图操作的预处理步骤和参数学习的训练步骤。将 Mt 的输出维度表示为 ，将原始内容特征的维度表示为 。计算 的预处理需要 成本。假设每个模块都经过 次迭代训练，批量大小设置为 。那么训练步骤的计算成本为 。请注意，仅考虑 GNN 映射，忽略损失的计算。总体而言，具有 个模块的 SGNN 的计算复杂度约为 。需要注意的是，该图在每个时期只使用一次，并且不对图进行采样，因此图结构被完全保留，而这在现有的快速 GNN 中是不可用的。 的系数仅为 。空间复杂度仅为 。因此，图规模的增长不会影响 SGNN 的效率。由于效率高，SGNN 的大多数实验都可以在配备 NVIDIA 1660 (6 GB) 和 16 GB RAM 的 PC 上进行。为了更好地阐明所提出的 SGNN 的优势，我们在表 I 中总结了各种高效 GNN 的特点。
实验
在本节中，我们进行实验来研究：（1）SGNN 的性能是否能够高效地接近原始 L 层 GNN 的性能；（2）解耦带来的非线性和灵活性的影响是什么。
为了充分回答上述两个问题，使用了节点聚类和半监督节点分类。需要强调的是，SGNN 既可用于传导任务，也可用于归纳任务。我们主要在传导学习的数据集上进行实验，因为效率低下的问题更容易出现在传导学习场景中。我们的实验使用了 4 个常见数据集，包括 Cora、Citeseer、Pubmed [25] 和 Reddit [14]。Cora 和 Citeseer 包含数千个节点。Pubmed 有近 2 万个节点，Reddit 包含超过 20 万个节点，分别是中型和大型数据集。四个常见数据集的详细信息如表 II 所示。在两个 OGB 数据集上的实验可以在第 V-D 节中找到。
A. 节点聚类
1）实验设置：我们首先验证 SGNN 在节点聚类上的有效性。我们将我们的方法与 10 种方法进行了比较，其中包括基线聚类模型 Kmeans、三个不考虑训练效率的 GCN 模型（GAE [9]、ARGA [54]、MGAE [43]）和六个带有 GAE 损失的快速 GCN 模型（GraphSAGE [14]、FastGAE [15]、ClusterGAE [18]、AGC [55]（SGC [19] 的无监督扩展）、S2GC [20] 和 GAE-S2GC）。
所用代码基于公开发布的实现。为确保公平，所有多层 GNN 模型均由两层组成，SGNN 由两个模块组成。对于可以通过随机算法训练的模型，小批量的大小设置为 128。学习率设置为 0.001，epoch 数设置为 100。我们将第一层的大小设置为 128，第二层的大小设置为 64。 初始化为单位矩阵， 默认设置为 。反向训练的次数设置为 5 或 10。为了研究反向训练的有效性，我们报告了对每个模块进行充分训练的实验结果，将其表示为 SGNN-FT，而采用所提出的反向训练的 SGNN 则表示为 SGNN-BT。
为了研究具有不同基础模型的 SGNN 的性能，我们选择完全可分离的 GNN S2GC 作为基础模型，并将该方法标记为 SGNN-S2GC。请注意，SGNN-S2GC 也使用提出的 BT 策略进行训练，这与 SGNN-BT 相同。原始 S2GC 不应用任何激活函数，而我们向每个 S2GC 基础模型的嵌入添加了与 SGNN-FT 相同的激活函数。由于 S2GC 不使用 GAE 框架，我们还添加了一个竞争对手，即 GAE-S2GC，它使用 S2GC 作为编码器，以确保公平性。对于 SGNN-S2GC 和 GAE-S2GC，所有额外的超参数都只是根据 S2GC 的原始论文为节点聚类和节点分类设置。我们不会手动调整 S2GC 的超参数。
所有方法运行五次，并记录平均分数。结果总结在表三中。
2）性能：从表三中，我们发现SGNN在大多数数据集上表现优异。如果发布的代码由于内存不足（OOM）而无法在Reddit上运行，我们会用“N/A”代替结果。特别是，SGNN-BT在Reddit上取得了很好的改进，效率很高。具体来说，它比著名的GraphSAGE高出约8％。SGNN-FT在某些数据集上的表现高于平均水平。它通常优于GraphSAGE，但无法超过SGC。由于多个模块导致更深的结构，SGNN的性能优于简单的GAE。由于多个模块带来的更多非线性，它也优于SGC。请注意，S2GC和SGC是强大的竞争对手，而SGNN可以轻松地将它们用作基础模块，因为它们是可分离的，这由SGNN-S2GC显示出来。很容易发现，与 S2GC 相比，SGNN-S2GC 通常能取得类似的结果。由于它比 SGNN-BT 慢，且性能提升不稳定，我们建议在实践中使用简单的 SGNNFT 代替 SGNN-S2GC。从表中我们发现，没有必要将 S2GC 修改为 GAE-S2GC，因为 GAE 架构根本没有提高 S2GC 的性能。从消融实验来看，SGNN-BT 的效果优于 SGNN-FT，这表明了向后训练的必要性。
我们还研究了模块数量 L 如何影响节点聚类精度，并在表 IV 中报告了 5 次运行的平均结果。为了确保公平，我们还展示了具有相同深度的 GAE 的性能，尽管更深的 GCN 和 GAE 通常返回不令人满意的结果。请注意，每层的神经元分别设置为 [256、128、64、32、16、16、16]。不难发现，与传统 GNN 相比，SGNN 对深度具有鲁棒性。
3) 效率：图 2 显示了 Pubmed 和 Reddit 上几个效率较高的 GNN 的消耗时间。我们没有忽略预处理操作，而是通过更合理的方式来衡量效率。我们将数据加载到 RAM 后记录总消耗时间，然后除以 GNN 的更新参数总数。测量结果可以反映出旨在将基于批处理的算法应用于 GNN 的各种训练技术之间的真正差异。应该强调的是 SGC 在消耗时间方面比 SGNN 更差的原因。关键点是它们的预处理操作成本不同。对于 阶 SGC， 的计算成本至少为 ，而具有 个一阶模块的 SGNN 对于相同的预处理操作完全需要 。由于停止标准总是不同的，该指标还提供了 SGC 与其他模型之间的公平比较。
B.节点分类
1）实验设置：我们还在四个数据集上进行了半监督分类实验。数据集的划分遵循[19]，如表II所示。我们将SGNN与GCN [4]，GAT [6]，DGI [56]，APPNP [57]，L2-GCN [40] FastGCN [15]，GraphSAGE [14]，Cluster-GCN [18]，SGC [19]，GCNII [58]和S2GC [20]进行比较。同样，我们用两个不同的基础模型测试SGNN，即SGNN-BT和SGNN-S2GC。实验设置与节点聚类的实验相同。对于GraphSAGE，我们默认使用均值运算符，如果使用额外的运算符，则添加一些符号。在引用网络上，学习率设置为0.01，而在Reddit上则为 。由于引文网络上训练节点少于 200 个，因此我们在每次迭代中对所有方法使用所有训练点，同时在 SGNN 的反向训练中将 256 个点采样为小批量以接近预期特征。在 Reddit 上，所有基于批处理的模型的批大小都设置为 512。我们不应用 [4] 中使用的早期停止标准，最大迭代遵循 SGC 的设置。每个模块的嵌入维度与节点聚类中的设置相同。为了公平起见，我们使用一阶运算报告由两个模块组成的 SGNN 获得的结果。前向训练损失在 (6) 中定义。此外，所有比较的模型都共享其小批量迭代器、损失函数和邻域采样器（适用时）的相同实现。 和 的平衡系数默认设置为 1。我们在表 V 和表 VI 中报告了在引文数据集上 10 次运行和在 Reddit 上 5 次运行的平均结果。超参数在 Cora 上优化的不同数据集上共享。
2）性能：表V中比较方法的结果取自相应论文。当实验结果缺失时，我们运行公开发布的代码，相应记录以†为上标。从表V和表VI中，我们得出结论，SGNN在引文网络上优于具有邻居采样的模型，例如GraphSAGE，FastGCN和Cluster-GCN，并且SGNN的性能超过了Reddit上的大多数模型。在简单的引文网络上，与其他基于批处理的模型相比，SGNN的准确率损失最小，接近GCN。由于每个模块的可分离性，批量采样不需要邻居采样，也不会导致图信息丢失。请注意，我们在实验中仅使用单层GCN作为基础模块，而一些获得竞争结果的高阶方法也可用于SGNN，例如SGNN-S2GC。SGNN-S2GC 的结果显示，通过采用更复杂的可分离 GNN 作为基础模型，SGNN 确实可以得到改进。
虽然有些方法取得了较好的效果，但在大规模数据集上，它们要么无法运行，要么结果不理想。此外，我们还在图2中展示了节点分类任务的效率比较。
3）可视化显示解耦的影响：在图3中，我们可视化了3模块SGNN和3层GCN的输出，以直接显示解耦不会导致平凡的特征，这与第四节中的理论结论相对应。为了展示SGNN和后向训练带来的非线性的好处，SGC，SGNN-FT和SGNN-BT的收敛曲线如图7所示。请注意，该图显示了最终损失的变化。在SGNN中，最终损失是ML的损失，而在SGC中它是唯一的训练损失。使用具有L阶图操作的SGC。从该图我们可以得出结论：（1）非线性确实会导致更好的损失值；（2）后向训练显着降低了损失。总之，经验上解耦不会造成负面影响。
C.可视化
我们还在图 4 和图 5 中提供了更多可视化效果。我们运行带有 3 个 GNN 模块的 SGNN，并通过 Cora 和 Citeseer 上的 t-SNE 将 的输入和输出可视化，以进行节点聚类和节点分类。这两个图的目的是通过实证研究解耦是否会导致残差和误差的积累。实验结果支持第四节中提供的理论结果。人们可能关注 （ 和 之间的权衡系数）对性能的影响。我们测试了具有不同 的 SGNN，从 ，发现 通常会导致良好的结果。因此，我们在本文中仅报告 的 SGNN 结果。此外，我们在图 8 中展示了 对 Cora 和 Citeseer 上节点聚类的影响。
此外，我们在图 6 中展示了不同时期的 的输出，以显示后向训练的影响。从图中我们发现 BT 确实影响了潜在特征，这在图 6(d) 中尤为明显。
D.在OGB数据集上的实验
我们进一步展示了在两个 OGB 数据集 OGB-Products 和 OGB-Arxiv 上进行节点分类的一些实验，这两个数据集是从 https://ogb.stanford.edu/docs/nodeprop/ 下载的。OGB Products 包含超过 200 万个节点，OGBArxiv 包含超过 15 万个节点。
需要强调的是，我们仅使用简单的单层 GCN 作为 SGNN 的基础模块。通过结合不同的模型（例如 GCNII、GIN 等），可以进一步提高性能。具体来说，我们仅在 Arxiv 上调整超参数，并且我们仅报告使用 Reddit 设置的 SGNN 结果。
备注：有人可能会担心，所提出的 SGNN 无法实现节点聚类等最先进的结果。应该强调的是，具有 L 个模块的 SGNN 应被视为 L 层 GNN 的变体。因此，将 SGNN 与 GCN 进行比较更为公平。从表 V、VI 和 VII 中，我们可以发现 SGNN 的性能可以高效地接近 GCN。SGNN 在节点聚类等监督任务上无法胜过其他模型的主要原因是难以为中间模块设计适当的训练损失。它本质上源于神经网络的黑盒特性，即哪种潜在特征更适合较深的层。从实验结果中，我们发现简单地将最终的监督损失设置为中间模块的训练损失并不是最佳方案。相反，在节点聚类上，我们证明了贪婪策略不会累积误差，实验结果验证了理论结论。
总结
在本文中，我们提出了堆叠图神经网络 (SGNN)。我们首先将多层 GNN 解耦为多个简单 GNN，本文将其正式定义为可分离 GNN，以确保批量优化的可用性而不会丢失图信息。现有堆叠模型的瓶颈在于信息传递只是单向的，因此开发了一种后向训练机制，使前一个模块能够感知后者。我们还从理论上证明了，对于无监督图任务，线性 SGNN 的残差在大多数情况下不会累积。理论和实验结果表明，所提出的框架不仅仅是一种有效方法，未来可能值得进一步研究。理论分析侧重于线性 SGNN，本文也没有研究泛化界限。因此，它们将是我们未来工作的核心。此外，由于 可以是任意损失，而 SGNN 无法达到最佳效果，因此如何为每个模块设置最合适的训练损失（尤其是在监督任务上）也将是我们未来工作中的一个重要课题。它可能有助于我们理解神经网络的工作原理。
