如何斩获KDD Cup两冠一季？美团广告团队公开解决方案( 六 )

由于依赖拉普拉斯矩阵， GCN 等谱域方法并不能很好地处理有向图，有向图无法直接定义拉普利矩阵及其谱分解，因此该团队将有向图的边进行反转改为无向图。 GCN 方法简单且有效，该团队将 GCN 应用到所有数据集上，大部分数据集能取得较好的效果。
相较于堆叠多层获取多阶邻域信息的 GCN 方法， TAGConv 通过邻接矩阵的多项式拓扑连接来获取多阶邻域信息，公式如下所示：
可以发现，其通过预先计算邻接矩阵的 k 次幂，在训练过程中实现多阶邻域卷积并行计算，且高阶邻域的结果不受低阶邻域结果的影响，从而加快模型在高阶邻域中的学习。就实验结果来看，其在稀疏图上能快速收敛，相比于 GCN 能够达到更好的效果。
相较于利用傅立叶变换来设计卷积核参数的谱域方法，空域方法的核心在于直接聚合邻居结点的信息，难点在于如何设计带参数、可学习的卷积核。 GraphSAGE 提出了经典的空域学习框架，通过图采样与聚合来引入带参数可学习的卷积核，其核心思想是对每个结点采样固定数量的邻居，这样就可以支持各种聚合函数。均值聚合函数的公式如下所示，其中的聚合函数可以替换为带参数的 LSTM 等神经网络：
由于 GraphSAGE 带有邻居采样算子，因此 Aister 团队引入该图神经网络来极大地加速稠密图的计算。就实验结果而言，其在稠密图上的运行时间远小于其他图神经网络，并且由于采样能一定程度上避免过拟合，因此它在有些稠密图上能够达到较好的效果。
GAT 方法将 Attention 机制引入图神经网络，公式如下所示：

本文插图

本文插图
其通过图结点特征间的 Attention 计算每个结点与其邻居结点的权重，通过权重对结点及其邻居结点进行聚合作为结点的下一层表示。
通过 Masked Attention 机制， GAT 能处理可变个数的邻居结点，并且其使用图结点及其邻居结点的特征来学习邻居聚合的权重，有效利用结点的特征信息进行图卷积，泛化效果更强，它参考了 Transformer 引入 Multi-head Attention 的做法来提高模型的拟合能力。 GAT 利用结点特征来计算结点与邻居结点间的权重，因此在带有结点特征的数据集上表现优异，但如果特征维度多就会使得 GAT 计算缓慢，甚至出现内存溢出的现象。这就需要在特征维度多的情况下对 GAT 的参数进行搜索限制，要求其在一个参数量更小的空间下搜索。
2. 超参快速搜索
由于超短时间预算的挑战，该团队需要设计一个超参快速搜索方法，来保证花较少的时间就可以对每个图模型进行参数搜索，并且在每个数据集上尽可能地使用更多的图模型进行训练和预测。如图 12 所示，该团队将参数搜索分为线下搜索和线上搜索两部分。

本文插图
图 12：超参快速搜索
该团队在线下搜索时，针对每一个图模型在多个数据集上使用一个大的搜索空间去确定图结构和参数边界，保证每个数据集在这个边界中都有较好的效果。
具体而言，他们基于有向图 / 无向图、稀疏图 / 稠密图、带特征图 / 无特征图等不同图类型对不同模型的大多数参数进行了搜索，确定了几个重要的超参数，例如对于稀疏图，调整 TAGConv 多项式的阶数，可使其卷积感受野更大，迅速对数据集进行拟合。该团队在线下主要确定了不同图模型学习率、卷积层数、隐层神经元个数这三个重要参数的边界。
由于线上的时间预算限制，该团队基于线下的参数边界