从特征融合的视角设计图神经网络的拓扑结构

©作者 | 卫岚宁，赵欢，贺志强

论文标题：

Designing the Topology of Graph Neural Networks: A Novel Feature Fusion Perspective

论文链接：

https://arxiv.org/pdf/2112.14531.pdf

代码链接：

https://github.com/AutoML-Research/F2GNN

该论文已经被国际顶级数据挖掘会议 WebConf 2022 （CCF-A）接收，欢迎大家关注。如有任何问题，欢迎联系 [e-mail]。该论文第一作者卫岚宁是第四范式的研究实习生。

简介

近年来 GNN（Graph Neural Network）成为工业界和学术界非常热门的一个研究方向。GNN 设计中有两个重要维度需要考虑，即 aggregation operation 设计和拓扑结构（topology）设计。目前大家多关注在前者上，对于后者，通常采用堆叠的方式，即一个 GNN 通常由 aggregation operation 堆叠而成，通过这样的方式 GNN 可以触及更高阶的邻居节点，进而获得 higher-level 的特征。但是随着模型层数加深，很容易出现 over-smoothing 的问题，即相连节点的特征可区分性降低，模型效果下降。

一部分方案通过增加 skip-connection 的方式来改善这一点。除了堆叠方式之外，仍有部分方案尝试用多分支的形式来构建 GNN，这类方案能够充分挖掘 local neighbor 的信息，但是因其每层中聚合操作过多，在获取 higher-level 特征上需要更多的计算资源。因此，在设计图神经网络的拓扑结构时一个重要的目标便是整合这两类方案并扬长避短。

▲ 图1：两种拓扑结构设计示意图。左侧为基于堆叠的模式，右侧为基于多分支的模式。

但是如今并没有图神经网络拓扑结构设计的系统性方案。一般来说，一个神经网络的设计结构可以用 computational graph 来表示，如下图所示，其中节点代表了操作，有向边把这些操作相连构成了神经网络的拓扑结构。在 GNN 中，这些边可以解释为对于不同阶特征的使用。除此之外，和 CNN 中不同，GNN 中会引入各类 fusion strategy，通过整合这些不同阶的信息来提升模型性能 [1][2][4]，即现有的图神经网络拓扑结构之间的差异是由特征选择和特征融合方案导致的。

▲ 图2：computational graph示意图[3]

基于上述，我们设计一个特征融合框架（feature fusion framework）并用特征选择和特征融合策略来统一现有的拓扑结构设计，因此上述的拓扑结构设计目标就转换为如何设计特征选择和特征融合策略来扬长避短。考虑到现有的图数据的多样性，GNN 在不同的数据上表现各有优劣，因此我们引入 NAS（neural architecture search）来自适应的设计拓扑结构。基于特征融合框架，我们设计了新的搜索空间（search space），并基于这个搜索空间改进了搜索算法。

在本文中，我们提出了新的方案 F2GNN（Feature Fusion GNN）从特征融合的视角来设计图神经网络的拓扑结构，我们在八个数据集上做了实验，其中包括五个同配图（homophily）和三个异配图（heterophily），结果显示自动化设计拓扑结构可以改善 GNN 的性能并且能够规避两类设计方案的劣势，尤其是 over-smoothing 的问题。

背景介绍

现有的 GNN 通常是基于堆叠聚合操作得到，但是随着堆叠层数的加深，实验发现模型的效果在逐渐降低，究其原因是不断聚合导致相邻节点的特征过度平滑，区分性降低。为了解决这个问题并提高模型效果，一些方案通过增加跳跃连接（skip-connection）的方式引入了 GNN 浅层的区分性高的特征，比如 JKNet [4] 和 DAGNN [5] 在 GNN 最后整合所有层的输出，GCNII [6] 则是通过跳跃连接在每一层中都引入原始特征，ResGCN [7] 和 DenseGCN [7] 中的跳跃连接设计则是参考了 ResNet 中的残差连接和 DenseNet 中的密集连接。

除了上述堆叠操作构建 GNN 之外，一部分方案转向多分支的思路，即一层中多个分支并列计算。比如 MixHop [8]，一层中三个分支用到了不同阶的邻居节点，PNA [9]则是在一层中用到了四个分支，每个分支有不同的聚合函数，在 IncepGCN [10] 和 InceptionGCN [11] 中 GNN 是由多个分支组成，每个分支上堆叠不同数量的聚合操作。

▲ 图3：GNN设计示意图

除了手工设计的拓扑结构，RandWire [12] 将神经网络看作 DAG，通过随机生成 DAG 来构建 CNN，RAN [14] 使用了同样的思路来设计 GNN。相比之下，F2GNN 从特征融合的角度来看拓扑结构设计，是一个系统性学习图神经网络拓扑结构方案的框架。同时引入了 NAS 来实现拓扑结构设计自动化。

本次工作的方法

3.1 特征融合框架

GNN 设计需要考虑拓扑结构和聚合操作的设计，而拓扑结构设计的关键便是特征选择和特征融合方案，基于此，我们提出了一个特征融合框架来统一现有的 GNN 拓扑结构设计方案。这个框架内包含一个输入模块，一个输出模块和 N 个 SFA 模块。

如下图所示，输入模块 0 使用一个两层 MLP 来做预处理，SFA（Selection, Fusion, Aggregation，N=4 为例）模块则是用于数据处理和拓扑结构设计，对于编号为 i 的 SFA 模块来说，它前置了 i 个模块，因此我们提供了 i 个 selection 操作来决定是否使用这些输入特征，随即附上一个 fusion 操作来整合特征选择结果，整合后的结果送入聚合操作之中。至此，这个模块的输出可以表示

为。和 SFA 相比，输出模块 5 则是把聚合操作替换为一个两层 MLP 用于模型输出。

▲ 图4：特征融合框架示意图

现有的 GNN 中使用的拓扑结构可以被这个特征融合框架涵盖在内。下表详细展示了三种方案的特征融合公式，拓扑结构展示和基于 F2GNN 框架的模拟结果，

▲ 表1：基于F2GNN框架的拓扑结构设计

3.2 基于该框架的 GNN 设计

手工设计的 GNN 倾向于在每一层使用相同的聚合操作，而基于 NAS 设计的 GNN 倾向于使用 layer-wise 的聚合操作，基于此，我们提供了两种 GNN 设计方案。一是同时设计 GNN 中的拓扑结构和聚合操作，此类方案记为 F2GNN，搜索空间中的操作集合如下所示，二是基于预设的聚合操作设计拓扑结构，比如 GraphSAGE 和 GAT, 这两类方案分别记为 F2SAGE 和 F2GAT，搜索空间只有特征选择和特征融合两项。

▲ 表2：搜索空间中的操作

在设计搜索算法时，我们考虑使用可微搜索算法，其中重要的设计就是松弛函数。基于如下操作，离散空间可以被松弛为连续空间，其中 是集合 中第 个操作 的权重。

selection 操作集合中有两个相反的操作，即 ZERO 操作表示没有选择当前输入，而 IDENTITY 则表示这个输入被当前模块选中。基于这个松弛函数，mixed selection 结果可以表示为如下。

当 ZERO 操作的权重 大于 IDENTITY 的权重 时，表示 ZERO 操作应该被选中，但是此时 预期是 0 但是得到了 ，IDENTITY 操作对 ZERO 的结果影响很大，并且这个误差会随着计算流程推进而逐渐扩大，导致模型的选择不准确。

考虑到这个问题，我们尝试在计算操作权重时引入温度 ，即 ，其中 为操作 的对应的 supernet 参数。当选择一个较小的温度参数时，操作权重 c 倾向于一个 one-hot 向量，减少彼此之间的影响。

实验

现有的 GNN 都是基于同质性（homophily）假设，即相连的节点一般具有相同的标签，同质性程度可以表示为 ，其中 表示图中边的集合， 是节点 的标签。通常低同质性的图( )可被称为异质性（heterophily）图。

在本文中，该工作在八个数据集上做了验证，其中包含了五个同质性数据集和三个异质性数据集。数据集的统计性质如下表所示。

▲ 表3：数据集的统计性质

4.1 F2GNN的实验效果

如下表所示，在任意聚合操作下，自动化设计的拓扑结构（Random 和我们的方案）总是能取得比固定拓扑结构更好的结果。这展示了自动化设计拓扑结构的重要性。其次，和随机设计拓扑结构（Random）相比，我们的方案能够取得更好的效果，这也展现可微搜索算法在其中的重要性。

▲ 表4：实验效果对比

▲ 图5：不同数据集上搜索的GNN结构

搜索到的 GNN 如图 5 所示，我们观测到以下现象：（a）不同聚合操作和数据集需要不同的拓扑结构; （b）预处理模块 0 产生的特征都被输出模块用到；（c）模型的高性能受益于多分支模式，比如每层中两个聚合操作; （d）H2GCN [15] 中表明在异配图数据中 GNN 效果甚至可能比不过 MLP，在Actor数据集中我们也搜索到了一个 MLP 的神经网络，意味着图结构被完全抛弃掉，搜索到的 GNN 和现有结论吻合，这也是现有的自动化 GNN 设计中没有考虑到的问题。

4.2 拓扑结构设计自动化的优势

和堆叠方式相比，自动化拓扑结构设计可以缓解过平滑问题。我们用 MAD（Metric for Smoothness）[16] 来衡量过平滑的程度。如下图所示，随着层数加深，基于堆叠方式构建的 GNN 效果会逐渐降低并且 MAD 的结果通常会比较低。三个 baseline都是通过利用不同阶的信息来增强节点特征的区分性，更高的准确率和 MAD 值说明了这一方案的可行性。我们的方案 F2SAGE 则是自适应的设计拓扑结构，这也意味着在此过程中不同阶节点特征的自适应利用，实验结果也表明 F2SAGE 对于这一问题的缓解。

▲ 图6：在Cora数据集和GraphSAGE预定义聚合操作上的过平滑实验

其次，多分支设计模式是在 higher-level 特征获取过程中更耗费资源。我们首先将 F2SAGE 对节点特征的利用情况做了可视化， 表示模块 i 中用到了 level j 的特征，为 0 则代表没有利用。如下图所示，当有 4（8）个 SFA 模块时，F2SAGE 可以获得 2（5）阶的信息，然后在同样 4（8）个聚合操作下，PNA 只能获得 1（2）阶的信息。

在聚合函数 GraphSAGE（GAT）上，我们的方案比 PNA 效果更好并且参数量少了 35%（15%）。这足以体现自动化拓扑结构设计在高阶信息利用上的灵活性。从图中我们可以观察左侧部分颜色更深，即大多数模块会更倾向于使用浅层的区分性更好的节点特征，这进一步佐证了我们的方案可以通过自适应的利用浅层节点特征来缓解过平滑问题。

▲ 图7：F2SAGE在Cora数据集上的特征利用情况，N表示为SFA模块数目

4.3 消融实验（Ablation study）

首先我们验证了 fusion 操作的重要性。如下表所示，我们使用了三个固定的 fusion 操作做对比。相比较于自适应的设计，使用固定的 fusion 操作会导致模型效果降低，这说明为神经网络选择合适的 fusion 操作来整合不同阶的信息是有意义的。

▲ 表5：Fusion操作的消融实验

其次，我们验证了本文中使用的搜索算法。考虑到 selection 中两个相反的候选操作带来的严重 optimization gap 的问题，我们在松弛函数中引入了温度的设计来缓解这一问题。如下表所示，我们使用了不同的温度来比较 supernet 和 childnet 之间的效果差异，作为对比，我们新增了 F2AGG 的方案，它是在 IDENTITY 和  SUM 操作上搜索聚合操作的方案。

将 设置为 1 时，supernet 和 childnet 之间的差异非常大，并且此时 childnet 中全是 ZERO 操作，没有 IDENTITY 操作被选中，而 F2AGG 中两者差异很小，随着 逐渐减小，IDENTITY 操作对 ZERO 的影响逐渐减少，因此 F2SAGE 中两者差异也随之减小。和 GNN 中常用的搜索空间对比，F2SAGE 中包含了 selection 的设计维度，其中有两个完全相反的无参数的操作，通过调整温度，可以改善这一设计带来的 optimization gap 问题。

▲ 表6：Cora数据集上supernet和childnet的validation准确率对比

在AutoGraph Challenge上的结果

近期我们将这项工作应用在了 AutoGraph Challenge in KDD Cup 2020 中来对比工业界和学术界的自动化图神经网络的差异。这个比赛中共有 15 个不同领域的节点分类数据集，5 个公开数据集是可下载的，5 个 feedback数据集在平台上提供用以验证，5 个 private 数据集用以最后的测试。

▲ 表7：数据集统计

我们基于预定义的 GCN 操作来搜索拓扑结构，其中 SFA 模块数目为 4，记为 F2GCN（L4）。工业界的方案中专注于模型集成和特征工程，和第一名的方案相比，我们专注于用 NAS 来搜索图神经网络的拓扑结构，只用了其 45.1% 的参数取得了其 97.3% 的效果。具体结果如下表所示，更多详细细节请参考论文 [17]。

▲ 表8：效果对比

▲ 表9：参数量对比

结论

在本文中，我们从特征融合的视角来看图神经网络的拓扑结构设计，设计了特征融合框架并用特征选择和特征融合两个操作来统一现有的拓扑结构设计方案，至此，图神经网络的拓扑结构设计转化为这两个操作的设计。

我们借助了 NAS 来实现拓扑结构设计的自动化，在搜索空间中我们为每一个设计维度提供了候选操作，并且改善了搜索算法来缓解 selection 操作带来的严重 optimization gap 问题。我们在八个数据集上做了实验，自动化拓扑结构设计可以大幅提升模型性能。和两类手工设计的拓扑结构相比，我们的方案对不同阶特征的利用更灵活，并且可以极大缓解 over-smoothing 的问题。

在未来的工作中，我们会将其应用在更大的数据集中，比如 OGB，同时评测当前工作在不同的下游任务中的性能。

参考文献

[1] Simplifying Architecture Search for Graph Neural Network. CIKM-CSSA 2020

[2] Search to aggregate neighborhood for graph neural network. ICDE 2021

[3] Exploring Randomly Wired Neural Networks for Image Recognition. ICCV 2019

[4] Representation Learning on Graphs with Jumping Knowledge Networks. ICML 2018

[5] Towards deeper graph neural networks. KDD 2020

[6] Simple and deep graph convolutional networks. ICML 2020

[7] Deepgcns: Can gcns go as deep as cnns?.ICCV 2019

[8] Mixhop: Higher-order graph convolutional architectures via sparsified neighborhood mixing. ICML 2019

[9] Principal Neighbourhood Aggregation for Graph Nets. NeurIPS 2020

[10] Dropedge: Towards deep graph convolutional networks on node classification. ICLR 2020

[11] InceptionGCN: receptive field aware graph convolutional network for disease prediction. IPMI 2019

[12] Exploring randomly wired neural networks for image recognition. ICCV 2019

[13] Differentiable Dynamic Wirings for Neural Networks. ICCV 2021

[14] Don’t stack layers in graph neural networks, wire them randomly. Arxiv 2020

[15] Beyond homophily in graph neural networks: Current limitations and effective designs. NeurPS 2020

[16] Measuring and relieving the over-smoothing problem for graph neural networks from the topological view. AAAI 2020

[17] Bridging the Gap of AutoGraph between Academia and Industry: Analysing AutoGraph Challenge at KDD Cup 2020. Arxiv 2022

本组其他相关工作

本文探索了 NAS 在图神经网络拓扑结构设计上的应用，除此之外，本组还有以下新工作：

1. AutoSF: Searching scoring functions for knowledge graph embedding. ICDE 2020. (AutoSF) 2. Interstellar: Searching Recurrent Architecture for Knowledge Graph Embedding. NeurIPS 2020. (Interstellar) 3. Search to aggregate neighborhood for graph neural network. ICDE 2021. (SANE) 4. Simplifying Architecture Search for Graph Neural Network. CIKM-CSSA 2020 (SNAG) 5. DiffMG: Differentiable Meta Graph Search for Heterogeneous Graph Neural Networks. KDD 2021. (DiffMG) 6. TabGNN: Multiplex Graph Neural Network for Tabular Data Prediction. KDD-DLP 2021. (TabGNN) 7. Pooling architecture search for graph classification. CIKM 2021 (PAS) 8. Profiling the Design Space for Graph Neural Networks based Collaborative Filtering. WSDM 2022 9. KGTuner: Efficient Hyper-parameter Search for Knowledge Graph Learning. ACL 2022

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：[e-mail] 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·