KDD  2022 | Graph Neural Networks with Node-wise Architecture

“

文章信息

来源：Proceedings of the 28th ACM SIGKDD Conference on Knowledge Discovery and Data Mining (KDD 2022)
标题：Graph Neural Networks with Node-wise Architecture
作者：Zhen Wang, Zhewei Wei, Yaliang Li, Weirui Kuang, Bolin Ding
链接：https://dl.acm.org/doi/10.1145/3534678.3539387

”

内容简介

最近，GNN 的神经架构搜索 (NAS) 越来越受欢迎，因为它可以为给定的新图寻找最佳架构。本文提出了一个框架，其中参数控制器根据其局部模式决定每个节点的 GNN 架构。本文用深度、聚合器和分辨率控制器实例化本文的框架，然后详细说明学习主干 GNN 模型和控制器以鼓励他们的合作。根据经验，本文分别通过三个控制器引入的性能改进来证明节点架构的效果是合理的。此外，本文提出的框架在十个真实世界数据集中的五个上显着优于最先进的方法，其中这些数据集的多样性阻碍了任何基于图卷积的方法同时领先于它们。这一结果进一步证实了节点架构可以帮助 GNN 成为通用模型。

具体而言，本文在图 1 中展示了三个示例，从架构的三个不同方面证明了使用节点架构的必要性。

• (1) GNN 的不同节点可能需要不同的深度。比较图 1a 的两行，密集连接节点的消息传播速度比连接稀少节点的消息传播速度快得多。已经分析了这种现象，因为具有较大程度的节点随着图卷积操作的迭代而更快地产生过度平滑的节点嵌入。最近的工作研究了节点深度，以允许具有不同局部结构的节点具有不同的深度，同时避免过度平滑问题。这些作品从深度方面支持了本文的节点架构理念。
• (2) 不同的节点可能需要不同的聚合器。在图 1b 中，使用假设的类标签和传入消息，左侧的两个目标节点可以通过均值/和池成功区分，而右侧的两个节点需要一个最大值/最小值 池化。PNA使用这两对来激励 GNN 使用混合聚合器。在本文的案例中，本文强调以节点方式选择适当聚合器的必要性。
• (3) 本文提出了一个新概念，即 GNN 层的分辨率，即采样了多少邻居来聚合它们的消息。采样对于在大图上训练 GNN 模型是必要的，其中不同的分辨率通常会导致不同的计算图，从而导致应用 GNN 的架构。在实践中，广泛采用的邻居采样器对所有节点使用相同的 GNN 层预先指定的分辨率。然而，当一个节点的局部模式是图 1c 中所示的红色节点的情况时，从减少估计方差的意义上说，采样更多的 1 跳邻居比采样更多的 2 跳邻居要好。因此，该节点更喜欢第二层 GNN 的高分辨率，而对第一层的分辨率不敏感。

受这些观察的启发，本文研究如何以节点方式搜索最佳 GNN 架构。现有 NAS 方法的直接扩展将线性增加搜索空间的大小和节点的数量，这使得它在大规模图上难以处理。此外，这样的扩展只为训练期间可访问的节点搜索合适的架构，因此它无法在归纳设置下为测试节点生成合适的架构。为了应对这些挑战，本文提出了一个框架，其中架构的每个方面都有一个参数控制器，例如聚合器控制器，以决定应该应用哪种类型的聚合器。为了确定特定层节点的架构配置，控制器首先将节点的本地模式编码为上下文嵌入，然后根据它从搜索空间中进行选择。例如，当本文假设前一层节点的特征足以确定其在当前层所需的聚合器时，本文可以将前一层节点的嵌入馈送到聚合器控制器。直观地说，骨干 GNN 模型依赖于控制器来预测合适的架构，而控制器根据骨干模型捕获的节点的局部模式对每个节点进行预测。因此，本文设计了一种学习方法来促进主干模型和控制器之间的合作。由于本文的上下文感知控制器具有与节点数量无关的固定数量的参数，并且可以泛化到看不见的节点，因此所提出的框架即使在转导和归纳设置下的大规模图上也可以实现 GNN 模型的节点架构.值得注意的是，尽管本文用深度、聚合器和分辨率控制器实例化了所提出的框架，但为 GNN 架构的其他方面指定的控制器可以很容易地包含在本文的框架中。

作者在10个真实世界的图数据集上将本文提出的框架与最先进的方法进行比较。本文的方法在其中一半上实现了最佳性能，其中没有或最多一种基线方法可以达到本文的 95% 置信区间。此外，本文表现出色的数据集包括同质图和异质图，其中没有现有的基于图卷积的方法可以同时领先。同时，节点分辨率被证明可以提高 GNN 在大规模图上的性能。然后本文展示了控制器可以适当地将合适的节点深度、聚合器和分辨率与每个节点的局部模式相关联，这解释了节点架构如何提高 GNN 的性能。还从样本效率和运行时间的角度对实现这种节点架构的支付进行了经验评估。

具有节点架构的 GNNS

一般来说，现有的 NAS 线中的 GNN 工作会寻找最佳架构并将其平等地应用于所有节点。假设搜索到的架构对应于一个 GNN，该 GNN 在其第一层应用均值池，在其第二层应用最小池。在图 2 中，当本文将这种搜索到的架构应用于图时，应用于三个节点（A、E 和 G）的 GNN 模型将产生“普通 GNN”部分所示的计算图。然而，正如在第 1 节中所讨论的，应用相同的架构来处理所有节点可能并不令人满意，因此需要具有节点架构的 GNN。在介绍如何通过节点架构实现 GNN 之前，本文首先在图 2 中展示一个示例，以展示其与普通 GNN 的区别。对于深度，应用于节点 G 的 GNN 有四层，而应用于其他节点的 GNN 的深度为 2，其中差异可能来自它们不同的节点度数。对于聚合器，应用于节点 B 的 GNN 在其第一层使用均值池，而应用于节点 F 的 GNN 使用最小池。

上下文感知控制器

假设在每个 𝐿 层中都需要确定架构的一个方面，那么分布 由架构参数参数化，总维度为 。如果本文试图通过这种 NAS 方法的直接扩展来实现节点级架构，那么每个节点 都会有一个专用的随机变量 。因此，所需架构参数的总维度将随着节点数量而增加线性的，这在大图上是无法承受的。此外，在归纳设置中，测试节点在测试阶段之前是不可访问的，在此阶段测试节点的架构参数无法提前估计。

为了在大型图上实现具有节点架构的 GNN，本文提出了一个框架，该框架利用参数控制器来预测骨干 GNN 模型的合适架构。控制器根据可以反映其本地模式的上下文对每个节点进行预测。因此，不同的节点被允许具有不同的 GNN 架构。为了确定 GNN 架构的特定方面，本文用 表征节点分布 ，它将其输入编码到上下文嵌入中，以反映节点 在第 层的阶段并输出 上的分布。本文可以考虑负责 GNN 架构不同方面的控制器的不同输入，原则是输入应为确定合适的架构提供足够的证据。在本文的框架中，GNN 架构的任何方面都可以通过简单地添加相应的控制器来处理。本文从深度、聚合器和分辨率方面举例说明了所提出的上下文感知控制器，如下所示。

深度控制器本文为深度控制器 提出了两种不同的设计。在第一个设计中，给定最大允许深度，本文可以将搜索空间定义为 ，节点分布 ，最终节点表示 如下：

在另一种设计中，本文让控制器在每一层的搜索空间 中做出选择，其中“1”表示在该层终止。然后本文通过 定义节点和分层分布并计算最终节点表示一个节点如下：

其中产品表示在第 层被终止的概率，而不是之前的任何层。

聚合器控制器除了维度池化操作之外，本文还包括一个特殊的“self_msg”操作，它接收目标节点本身的消息，同时忽略任何传入消息。那么本文的聚合器控制器的搜索空间可以表示为 。使用聚合器控制器，每个消息传递迭代的第一步是根据 贡献。

分辨率控制器当本文在大型图上训练 GNN 模型时，采样是必不可少的，因为整个三跳邻域通常无法适应 GPU 内存，更不用说更大的邻域了。在本文中，本文考虑了最广泛采用的采样器之一——邻居采样器，其中在每一跳中采样固定数量的节点。本文将 GNN 层的分辨率定义为在相应跃点中采样的节点数，并将分辨率视为 GNN 架构的一个方面。那么分辨率控制器的搜索空间由几个具体的分辨率配置组成，例如，，其中“15-10-5”表示采样在 3、2 和 1 跳中分别有 15、10 和 5 个邻居。值得注意的是，在大多数情况下，采样仅用于训练而不是评估，其中估计的节点嵌入 和精确的节点嵌入 是基于采样的或整个邻域计算的，分别。在每次评估中，本文推断所有节点的确切节点嵌入并维护它们的最终节点表示，即 。本文假设 对于确定节点 的合适分辨率并为其选择分辨率提供了信息根据 。

实验分析

本文在表 1 中展示了结果，其中粗体字母表示每个数据集上的最佳结果。总体而言，NW-GNN 在十个数据集的一半上取得了最佳性能，其中没有一个或最多一个基线可以达到其 95% 的置信区间。

本文在表 2 中展示了实验结果，其中基线的性能（即“w/o”）直接从 OGB 的排行榜复制而来。带有本文的分辨率控制器（即“w/”）的 GraphSAGE 优于没有控制器的情况，其中一个标准。低于前者的平均值仍高于后者的平均值。这种比较证实了自适应节点分辨率在使用图形采样器训练 GNN 中的优势，这也表明了本文提出的分辨率控制器的有效性。

结果如表 3 所示，其中 NW-GNN 与 w.r.t 相当。GCN 在没有节点属性的情况下，在其他两种设置下以显着的优势超过所有基线。本文将这些优势归因于本文使用节点深度的能力，因此本文的方法可以通过直接近似真实标签的生成过程来进行预测。

本文在表 4 中展示了结果，其中 NW-GNN 在所有设置下都超过了所有基线。为了验证 NW-GNN 的优势来自其以节点方式选择聚合器的能力，本文在“简单壮举”下对 NW-GNN 进行了案例研究。环境。具体来说，本文将预测 groundtruth 聚合器视为 5 类分类任务，本文的控制器的准确率为 54%。同时，在聚合器被正确预测的测试节点上的 MAE 为 0.78，而在错误预测的节点上的 MAE 为 2.02。这些结果证实 NW-GNN 可以实现骨干 GNN 模型的节点聚合器。

总结

受对 GNN 应用程序的观察的启发，本文提出了一个框架来启用 GNN 模型的节点架构，其中设计的上下文感知控制器可以自动利用每个节点的本地信息。一系列实验表明，所提出的框架在六个真实世界数据集上优于最先进的方法。由于没有现有的基于图卷积的模型可以同时在这样的各种图的集合上获胜，本文可以确认节点架构可以使不灵活的 GNN 模型具有通用性。在本文中，本文重点展示了节点深度、聚合器和分辨率的影响以及相应的控制器如何工作。将来，可以添加更多额外的控制器作为所提出框架的其他实例，这值得进一步研究。