论文地址：
https://openreview.net/pdf?id=bBff294gqLp
代码地址：
https://github.com/THUMNLab/NAS-Bench-Graph
一、背景
神经网络架构搜索（NAS）作为自动机器学习（AutoML）的一个重要组成部分，旨在自动的搜索神经网络结构。NAS的研究最早可以追溯到上世纪八十年代，随着算力的提升和神经网络的发展，自动搜索神经网络逐渐成为深度学习的的热门方向之一。NAS的研究主要分为三个方面：搜索空间，搜索算法，以及评估策略。
1.1 搜索空间
搜索空间与探究的问题息息相关，在计算机视觉中，NAS的搜索空间常常是一些CNN相关，如3x3卷积或5x5卷积。在图神经网络中，从宏观来说，我们可以搜索GNN的层数等，从微观来说，我们可以搜索GNN的message passing和aggregation function等。下图是一些代表的GNN搜索空间 (同质图，图分类，图推荐，以及异质图)。
如何针对不同实际问题，设计好的搜索空间是 GNAS 领域最重要的问题之一。
1.2 搜索算法
在搜索算法上，NAS 本质上要解决的是针对搜索空间的组合优化问题，比较典型的有强化学习（RL），进化算法（EA）贝叶斯优化（BO）以及将搜索空间连续化的可微搜索（Differentiable Search）等等。
1.3 评估策略
早期 NAS 方法直接以验证集上实际指标的来评估搜索出来模型的好坏，但是从头训练一个模型得到验证集上的性能比较昂贵，于是研究者开始使用代理指标（Proxy Metric）去替代真实的验证集性能，这些代理指标通常不需要太多计算开销。如何找到高效且接近真实验证集性能的代理指标也是 NAS 值得研究的问题。
1.4 NAS Benchmark
NAS Benchmark（如 NAS-Bench-101，NAS-Bench-201 等）主要思想是在搜索空间中穷尽搜索子网络，将子网的结构以及对应的验证集精度记录下来，形成一个表，研究人员使用的时候只需要通过查表就可以得到对应的验证集精度，这样就不需要重新训练和测试，降低了对计算资源的依赖，同时也为 NAS 的研究者提供公平比较。但是在 Graph 领域还没有类似的工作，本文是 Graph NAS Benchmark 的第一个工作。
二、方法介绍
2.1 搜索空间
本文在搜索的宏观架构上使用了以下九种结构：
每个节点有九种可选组合：GCN, GAT, GraphSAGE, GIN, ChebNet, ARMA, k-GNN, Identity（残差连接）以及 FC（Fully Connected Layer，不使用图结构），作者移除了同构的架构图产生了一个包含 26,206 种 GNN 的搜索空间。
2.2 数据集
本文在如下九个常见的节点分类数据集进行了实验：
2.3 分析
2.3.1 性能分布
本文可视化了所有数据集与推理延迟的关系，如下图，其中红色的部分代表着模型性能和模型推理延迟（一般来说模型越大延迟越高）的帕累托前沿（Pareto Front）：
作者发现尽管高性能的架构最终效果都差不多，但是越大的模型总是能获得更高的性能，并且作者计算了模型性能与模型大小的相关系数，发现是正相关的，因此我们在设计 GNN 时需要做出模型大小和效果的权衡。
2.3.2 架构分布
作者选择了表现 top 5% 的一个结构对宏观操作和 GNN 类型做了频率统计绘制了如下图。
从图（a）中我们可以看出 Cora、Citeeer 和 PubMed 倾向于选择两层 GNN，即 E、F、G 和 H（见 2.1）；PudMed 和 CS 也更喜欢选择在其他数据集中很难选择的 1 层的 GNN 如 I；Physics, Photo 和 Computers 数据集在选择上更均匀。ogbn-arXiv 和 ogbn-proteins 更喜欢选择更深的 GNN。
从图（b）中我们可以看出 GCN 和 GAT 几乎在所有数据集中选择频率最高；GIN 和 k-GNN 在理论上更接近 WL-test，但他们只在相对较小的数据集（Cora、Citeeer 和 PubMed）中容易被选中，作者给出的解释是这些 GNN 在聚合的过程中使用了大量 sum 聚合，不适用于大规模图中的节点级任务。
2.3.3 跨任务
作者选取不同数据集中 top 5% 的架构做了任务之间的相关性比较（其中重复率代表着 top 5% 的结构在两个不同间重叠的部分），并可视化如下图：
从图中可以看出 Cora、Citeeer 和 PubMed 通显示出很强的相关性。Physics, Photo, Computers 和 ogbn-arXiv 的相关性也很高。即使 Pearson 和 Kendall 很大，但前 5% 的重叠率也不高。也就是说我们在不同数据集之间直接迁移最有架构可能在另外一个数据集并不是最优。
2.3.4 搜索实验
本文做了以下搜索实验，有以下发现：
1. 所有搜索算法都优于前 5% 架构，表明从搜索的角度来说这些搜索算法都是有效的；
2. 没有一种搜索算法能在所有数据集上获胜。
与其他搜索相比，随机搜索仍然是一个强大的 baseline，甚至在两个数据集上表现最好，结果表明，我们需要对 GraphNAS 的进一步研究。
2.3.5 使用
本文所提供的 Benchmark 易于使用，下面是一个 python 代码的使用例子：
三、总结
这个工作作为第一个 GNAS 的 Benchmark，本文对 GNAS 领域的社区发展做出了贡献。同时本文从搜索出的结构出发，在不同的角度给出了设计节点级别的 GNN 的指导，对设计节点级别 GNN 做出了一定的贡献。但是本文也有其局限性，对于图级别的任务和异质图的任务，本文没有进行探索，我们期待在将来看到更多的相关工作。
参考
[1] Zhenyi Wang, Huan Zhao, and Chuan Shi. 2022. Profiling the Design Space for Graph Neural Networks Based Collaborative Filtering. In WSDM. 1109–1119.
[2] Jiaxuan You, Zhitao Ying, and Jure Leskovec. 2020. Design space for graph neural networks. NeurIPS 33 (2020).
[3] Chris Ying, Aaron Klein, Eric Christiansen, Esteban Real, Kevin Murphy, and Frank Hutter. Nas-bench-101: Towards reproducible neural architecture search. In ICML, pages 7105–7114. PMLR, 2019.
[4] Xuanyi Dong and Yi Yang. Nas-bench-201: Extending the scope of reproducible neural architecture search. In ICLR, 2019.
[5] T. Elsken, J. H. Metzen, F. Hutter, Neural architecture search: A survey, arXiv preprint arXiv:1808.05377
[6] Tianyu Zhao, Cheng Yang, Yibo Li, Quan Gan, Zhenyi Wang, Fengqi Liang, Huan Zhao, Yingxia Shao, Xiao Wang, and Chuan Shi† . 2022. Space4HGNN: A Novel, Modularizedand Reproducible Platform to Evaluate Heterogeneous Graph Neural Network. In SIGIR 2022
作者：梁峰绮
文章来源：公众号【北邮Gamma Lab】
快抢沙发！
