作者：汪文杰（南京大学PASA大数据实验室）、朱振南（南京大学PASA大数据实验室）、朱光辉
研究背景
现实世界中，图结构数据无处不在，许多现实中的大数据例如社交关系、论文引用、生物蛋白质交互以及知识实体关联等都可以刻画成图数据。与此同时，图数据背后往往隐含着深度知识和价值，通过对图数据的智能化分析挖掘能够为行业/企业带来巨大的商业价值，实现多种高附加值的增值服务，例如社团发现、欺诈检测、关系预测、智能推荐等。图分析挖掘技术已成为大数据智能分析的基础，具有突出的实际应用价值，并已入选Gartner 2021年十大数据和分析趋势。近年来，凭借着优异的灵活性及模型性能，图神经网络（Graph Neural Network, GNN）[1]在许多重要的图分析挖掘任务中如节点分类、图分类以及链接预测等取得了巨大成功，并引起了学术界和工业界的广泛关注。GNN将深度学习应用在图数据上，其主要目标是结合图的拓扑结构以及节点特征，为图中的每一个节点学习一个低维的向量表示，这些低维表示可进一步用于解决下游的图分析挖掘任务。然而，给定一图数据集，设计一个有效的图神经网络模型是一个较为复杂的流程，如图1所示，在图神经网络中的每一层需要花费大量时间选择最合适的采样机制、聚合函数、注意力计算函数以及多头注意力中头的数量。图神经网络模型的架构设计和调参，犹如木匠制作家具，大部分依靠建模专家的人力和经验技巧，费时费力，缺少有效的方法，从而限制了图神经网络模型的普及应用。近年来，随着AutoML自动化机器学习技术[2]的兴起，学术界开始尝试将AutoML与图神经网络两个前沿领域进行结合（简称AutoGraph），实现图神经网络模型架构的自动化设计（即 Graph Neural Architecture Search）。在素有“数据世界杯”之称的KDD Cup，2020年首次举办了针对图结构数据的AutoGraph大赛。KDD Cup 2020 AutoGraph赛题负责人表示，“图神经网络的应用领域十分广泛，因此AutoGraph技术方案极具应用价值，是图神经网络建模快速落地的关键方法”。
当前挑战
目前已有部分工作尝试利用自动化机器学习的方法设计图神经网络，主要方法可分为两大类：组件级（component-level）和架构级（architecture-level）。然而，这两种方法均存在一定问题。首先，搜索空间是NAS方法的关键部件，设计合适的搜索空间是一个具有挑战性的问题。组件级方法主要对GNN中的关键组件如聚合函数进行搜索[3]，这种搜索算法虽然理解起来直观简单但是表达能力不够，搜索空间不能覆盖一些性能优异的GNN架构。其次，架构级方法聚焦整个图神经网络架构的搜索[4]，具有较大的搜索空间，因此可以采样出性能更好的架构。但是，由于搜索空间容量大，导致搜索效率较低。因此，设计搜索空间以及搜索方法时，应该考虑到架构性能和搜索效率之间的平衡。
01 基于渐进式空间剪枝的图神经网络架构搜索算法
本文从搜索空间的角度出发提出了一种高效的基于渐进式空间剪枝的图神经结构搜索方法，被称为PSP（Progressive Space Pruning）。PSP算法在初始阶段使用统一的搜索空间，并在迭代过程中采用剪枝算法逐步简化搜索空间。在这一过程中，对架构性能表现贡献度较低的候选算子将从搜索空间中去除。针对当前数据集表现性能较差的算子可以被认为是低质量算子，对其剪枝有利于在缩小的解空间内更快地接近最优解。另外，本文提出的架构搜索方法具有良好的可迁移性，最终得到的高质量搜索空间和搜索架构可以迁移到相似的图结构数据集上。本文在图神经网络架构自动化搜索方面的工作获得了KDD Cup 2020 AutoGraph挑战赛国际第二名的成绩。另外，该工作也已被数据管理和数据挖掘国际顶级会议IEEE International Conference on Data Engineering (ICDE 2022，CCF A类会议)长文录用。接下来详细介绍PSP算法。
02 搜索空间设计
搜索空间在NAS算法中起着至关重要的作用。GNN中每一层的搜索空间是由邻居采样算子、注意力计算算子、注意力机制的多头数量、消息聚合算子和激活函数组成。这样的搜索空间也被称为宏空间（macro-space）。然而，宏空间存在着组合爆炸的问题，GNN候选架构的数量随着层数的增加而呈指数级增长，使得搜索的计算成本大幅增长。PSP设计了一个基于单元（Cell）的微空间来提高搜索效率。图2展示了基于Cell的搜索空间。整个GNN架构由多个单元组成。左图中，最下方的单元表示输入的图数据集（Graph），随后为预处理单元（Pre-processing Cell），该单元使用多层感知机（MLP）对输入图节点数据进行转换。GNN进行消息传递前添加MLP层已被验证有利于最终性能的提升，所以将预处理单元作为GNN架构一部分。然后，将具有相同架构的普通单元（Normal Cell）堆叠起来，以此进行GNN中的消息传递和聚合操作。
最终搜索的目标不是整个图神经网络的架构，而是普通单元的架构。这样的搜索空间也被称为微空间（micro-space）。从图2右图可看出，普通单元的结构可以表示为一个有向无环图（DAG），本文设定为两层。每层由输入数据、节点聚合器和激活函数组成。其中，最为关键的节点聚合器主要通过采样（Smpl）、注意力机制计算（ATT）和聚合函数（AGG）进行消息传递功能。普通单元的最终输出是由层聚合器计算得到。为了减少节点聚合器中Smpl、ATT和AGG的多种候选组合的数量，该搜索空间利用了已有GNN架构的设计经验。例如，表示具有四头注意力机制的GAT模型[5]，表示采用加和聚合器的GraphSage模型[6]。
为了增强普通单元的结构多样性、消除过度平滑问题，本文在搜索空间中进一步引入了内部连接和外部连接。如图2右图所示，外部连接表示普通单元中每一层输入都可能来自于前两个单元其中一个；而内部连接意味着在普通单元中第1层的输入可能是第0层的输出。
03 搜索方法整体架构
如图3所示，PSP中搜索方法主要分为两个阶段，性能预测代理模型的构建阶段和搜索空间剪枝阶段。
图3 PSP算法整体架构
04 性能预测代理模型架构阶段
如图4所示，普通单元中的每个候选算子都被编码为一个独热编码特征。例如，“ layer0 is GAT_4 = 1”意味着算子被选为第0层的节点聚合器。在PSP算法的每轮迭代中，首先从当前的搜索空间中采样出M个架构。为了减少评估架构的成本，进一步采用预测模型GBDT作为代理模型来预测采样架构的准确性。根据预测出的架构性能，选择最优的k个架构进行重新训练和评估。然后，将这k个架构形式化为<架构-准确率>加入训练集，重新训练代理模型，增强其表达能力。
05 搜索空间剪枝阶段
给定一个GNN架构，可以根据代理模型的预测性能，计算出每个独热编码特征的SHAP值。此外，还可以依据多个样例计算出每个独热特征的平均SHAP值。如果 “ layer0 is GAT_4 = 1 ”的平均SHAP值为极负值，则可以得出结论：这个特征对架构的性能起到了负面的影响。因此，可以把该特征从当前的搜索空间中去除。从本质上看，PSP是一种启发式算法。在每轮迭代中，都会去除在当前采样的架构中表现不佳的候选算子，而不是在原始搜索空间中所有可能的架构中搜索。因此，从全局角度来看，最优架构内的算子有可能会被误剪枝。为了尽可能降低误剪枝的发生概率，本文对剪枝的算子数量进行了优化。具体来说，令p为每轮迭代中剪枝的算子数量。直观上看，p值过大会带来更加激进的剪枝策略，可能存在一些算子被误剪。p值过小会导致搜索空间缩减过于缓慢，不利于高效地产出更好的架构。因此，应该设计合理的p值。尽可能避免误剪枝且不至于使得搜索空间缩减过慢，本算法设置了以下规则：p值应该在每轮迭代中动态增加而不是固定不变。在最初的迭代过程中，由于代理模型还没有被训练充分，应该将p值谨慎地设置为较小值，以防止有潜力的算子被误剪枝。随着代理模型变得可信，在后续的迭代中设置逐步增长p值，以加快搜索过程。其次，对修剪的算子总数设置了一个阈值，即不能超过候选算子总数的一半。
06 实验评估
表1显示了全监督划分下的性能比较结果。从表中可以看出，本文提出的PSP算法在大部分数据集上都取得了优异的性能。另外，在人工设计的模型中，不存在在所有数据集上均能够取得优异性能的模型，这也从侧面验证了图神经网络架构搜索的必要性。对于NAS方法，SNAG在维基百科和WebKB数据集上的表现很差，而GraphNAS在三个WebKB数据集上的表现优于其他NAS方法。除Citeseer之外，PSP在所有数据集上都取得了最优的性能。在Citeseer数据集上，PSP与性能最高的模型（GCNII）之间的差异很小。值得注意的是，随机搜索算法在大多数据集上都能取得较好的表现，这验证了本文所设计的基于单元的搜索空间是非常有效的。
（加粗表示最优，下划线为当前组内最优，*表示在统计意义上比最高基线模型有大幅提升）
本文对搜索空间的质量进行定量评估。具体来说，从搜索过程每次迭代后得到的搜索空间中随机选择一定数量的架构，通过验证集节点分类错误率指标评估其性能，并计算出每轮迭代后搜索空间的累积概率分布（Cumulative prob）。该指标能够直观地描述搜索空间质量：累积概率越高，错误率越低，则从该搜索空间中采样的架构性能就越高，从而说明搜索空间的质量也越高。
图 5展示了在每一轮迭代过程后，从搜索空间中采样的架构累积概率分布，“origin”曲线代表原始的搜索空间，而以“prune_iter”命名的曲线代表第轮剪枝后的搜索空间。从图中可以看出，随着迭代过程的进行，累积概率分布曲线不断向左收缩。这表示随着低质量的算子被去除，PSP算法从搜索空间中采样到的分类错误率低的架构逐渐增多。这说明PSP算法能够逐步采样到更多性能优异的架构，即搜索空间的质量逐步提升，从而验证了搜索过程的有效性。
图5 每次迭代后搜索空间采样架构累积错误率分布
总结与未来展望
本文从搜索空间设计角度出发，研究提出了一种高效的基于渐进式空间剪枝的图神经网络架构搜索算法PSP。首先，研究提出了一个基于Cell的搜索空间。然后，研究提出了基于梯度提升树的渐进式剪枝策略。在每轮剪枝迭代中，移除对架构性能贡献较小或有负面影响的算子，并更新性能预测代理模型。最后，大量的实验结果从不同角度展示了PSP算法的优异性能。PSP算法的详细介绍可进一步参考ICDE 2022录用论文。本文提出图神经网络架构搜索算法目前主要针对于同质图场景，未来考虑设计在异质图上高效且表达能力强的算子，并将此算法运用在异质图场景上，提升模型性能。另外，随着图数据规模的逐步增大，未来也将针对大规模图结构数据，研究更加高效的图神经网络架构搜索方法。
参考文献
[1] Wu Z, Pan S, Chen F, et al. A Comprehensive Survey on Graph Neural Networks[J]. IEEE Transactions on Neural Networks and Learning Systems, 2019, 32(1): 4-24.[2] Hutter F, Kotthoff L, Vanschoren J. Automated Machine Learning: Methods, Systems, Challenges[M]. Springer, 2018.[3] Zhao H , Yao Q , Weiwei T U. Search to Aggregate Neighborhood forGraph Neural Network[C]//Proceedings of the 37th International Conference on Data Engineering (ICDE), 2021.[4] Gao Y, Yang H, Zhang P, et al. Graph Neural Architecture Search[C]//Proceedings of the Twenty-Ninth International Joint Conference on Artificial Intelligence (IJCAI). 2020: 1403-1409.[5] Velikovi P, Cucurull G, Casanova A, et al. Graph Attention Networks[C]//Proceedings of the International Conference on Learning Representations, 2018.[6] Hamilton W L, Ying R, Leskovec J. Inductive Representation Learning on Large Graphs[C]//Proceedings of the 31st International Conference on Neural Information Processing Systems. 2017: 1025-1035.
