【6篇文章串讲ScalableGNN】围绕WWW 2022 best paper《PaSca》

Scalable GNN

《Simplifying Graph Convolutional Networks》 ICML 2019

《SIGN: Scalable Inception Graph Neural Networks》 ICML 2020 workshop

《Simple Spectral Graph Convolution》ICLR 2020

《Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training》 arxiv’21 OGB曾经第一名

《Graph Attention Multi-Layer Perceptron》 arxiv‘21 同一作者

《PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm》 WWW 2022 best paper

现有GNN的缺陷

High Memory Cost

GNN中的特征传播操作（邻居聚合机制、消息传递机制）涉及一个较大的稀疏矩阵和特征矩阵的乘法，需要较多的时间；如果在训练时使用GPU加速，那么就必须把矩阵放在GPU的显存上，但这一需求对于大图是无法被满足的。比如OGB节点分类数据集中最大的ogb数据集的稀疏邻接矩阵大小超过50GB，目前只有80GB显存版本的Tesla A100才能存下，但是可以用250GB的内存运算，后者更容易得到。所以只能分布式的训练GNN，但这又会带来大量

High Communication Cost

GNN每一次的特征传播都需要聚合邻居特征，对于K层的GNN来说，每个节点需要聚合的K跳以内的邻居节点特征，涉及节点数量随着层数增加以指数增加，这在分布式场景下会带来大量的通信开销。对于稠密的的连通图，每个节点在每次训练的时候几乎需要聚合全图的节点信息。一些采样算法（GraphSAGE）能缓解这个问题，但是由于训练过程中递归的邻居聚合机制，这些算法还是造成高昂的通信成本。

可以看出性能瓶颈是通信开销，加GPU并不能有效加速训练。

Inconsistent Receptive Field expansion speed

不同节点的感受野扩展速度是不同的，因此不同节点最优感受野也是不同的。图a是随机选20个节点的测试结果，用SGC（只用第K层的feature）做的实验，记录连续运行的100次中预测正确的次数占总的次数的比例。可以看出不同节点的预测准确率随特征传播步数的增加而变化的趋势并不相同，如节点10，在传播步数为1时达到了预测准确率的最大值，随后预测准确率不断降低；而另有部分节点，如节点4，的预测准确率则随特征传播步数的增加而不断增加。即使趋势相同，不同节点最优的卷积层数也是不同的。因此不同传播步数的节点特征做加权求和时，应该给予不同的权重。

不同任务需要单独设计GNN结构

现有的GNN工作都是设计一种模型结构，在不同的任务场景（数据集）可能需要领域专家设计特定的模型结构、训练流程，建模成本高。

Scalable GNN总结

文章先归纳了Scalable GNN的架构范式。Sampling-based的方法不算Scalable GNN，因为这些模型在训练过程中还需要聚合邻居节点，分布式场景下通信开销避免不了。

model decoupling

有研究指出【SGC】，GNN的性能主要归功于各个层中的特征传播操作，而不是非线性变换操作。由此催生出了一系列解耦的GNN，他们在设计GNN模型时解耦了特征传播操作和非线性变换操作，在预处理时就预先做完所有的特征传播操作，在模型训练时就不必再费时费力地去传播特征。因此，在可扩展性方面，只要能够在预处理时完成特征传播操作中的稀疏矩阵稠密矩阵乘法，后续的模型训练可以很轻松地在单机单卡上进行。由于特征传播操作是在预处理过程中完成，因此不需要利用GPU进行加速，完全可以仅使用CPU进行矩阵乘法操作。

但是这些解耦的GNN在训练时没有区分不同节点的特异性。SIGN、S2GC、SAGN、GAMLP就考虑了特异性。

SGC——只考虑第K层的特征

《Simplifying Graph Convolutional Networks》 ICML‘19

在预处理阶段，SGC用K-step特征传播后得到的特征（只用第K层卷积的输出），作为节点的初始特征：$\overline{\mathbf{X}}\leftarrow {\mathbf{S}}^K\mathbf{X}$，$\mathbf{S}$是邻接矩阵。然后模型训练阶段只训一个1层的MLP作为分类器。

SIGN——考虑不同感受野

《SIGN: Scalable Inception Graph Neural Networks》 ICML‘20 workshop

SGC只用了K-step得到的特征作为节点的初始特征，显然对于所有节点不是最优的，SIGN将0～K-step所有的特征拼接起来，保留了所有感受野的特征：
Z = σ ( [ X Θ 0 , A 1 X Θ 1 , … , A r X Θ r ] ) Y = ξ ( Z Ω )

ZY​=σ([XΘ0​,A1​XΘ1​,…,Ar​XΘr​])=ξ(ZΩ)​
$\mathbf{\Theta }$和$\mathbf{\Omega }$都是训练参数。缺点是拼接操作需要的空间开销和卷积层数成正比。

S2GC——PPR+平均

《Simple Spectral Graph Convolution》ICLR‘20

$$\hat{Y}=\mathrm{softmax}\left(\frac{1}{K}\sum _{k=1}^K\left((1-\alpha ){\tilde{\mathbf{T}}}^k\mathbf{X}+\alpha \mathbf{X}\right)\mathbf{W}\right)$$
$T$还是邻接矩阵，S2GC实际上是近似的以概率 ($1-\alpha$)重启的PPR得到各层的特征，然后直接平均相加，作为节点的初始特征。

SAGN——不同感受野attention求和

《Scalable and Adaptive Graph Neural Networks with Self-Label-Enhanced training》 arxiv’21

把SIGN中的拼接操作换成了attention的加权和，对不同感受野特征加权求和，之后的文章都follow这一范式。

GAMLP——设计attention

《Graph Attention Multi-Layer Perceptron》 arxiv‘21

1、Smoothing Attention

可以理解为用无限次特征传播后的节点特征$X_i^{(\infty )}$作为参考向量，然后算attention：
$${\tilde{\mathbf{X}}}_i^{(l)}={\mathbf{X}}_i^{(l)}\Vert {\mathbf{X}}_i^{(\infty )},{\tilde{w}}_i(l)=\delta \left({\tilde{\mathbf{X}}}_i^{(l)}\cdot s\right),w_i(l)=e^{{\tilde{w}}_i(l)}/\sum _{k=0}^K{e}^{{\tilde{w}}_i(k)}$$
其中$s\in {\mathbb{R}}^{1\times d}$ 是可训练参数。较大的$w_i(l)$意味着节点$v_i$的 l-step 传播特征与无限次传播状态距离较远，成为噪声的风险较小。具有较大的$w_i(l)$的传播特征对特征组合的贡献应该更大。

2、Recursive Attention

递归计算特征传播过程中的信息增益：

${\tilde{\mathbf{X}}}_i^{(l)}={\mathbf{X}}_i^{(l)}\Vert {\sum }_{k=0}^{l-1}{w}_i(k){\mathbf{X}}_i^{(k)},{\tilde{w}}_i(l)=\delta \left({\tilde{\mathbf{X}}}_i^{(l)}\cdot s\right),w_i(l)=e^{{\tilde{w}}_i(l)}/{\sum }_{k=0}^K{e}^{{\tilde{w}}_i(k)}$

较大的$w_i(l)$意味着特征${\mathbf{X}}_i^{(l)}$ 对 $v_i$的当前状态更为重要（相较于前层组合特征占比更高）。

3、JK Attention

将所有step的特征输入到MLP，MLP输出的结果作为参考向量，计算attention：
$$\begin{gathered} {\tilde{X}}_i^{(l)}=X_i^{(l)}\Vert E_i,{\tilde{w}}_i(l)=\delta \left({\tilde{X}}_i^{(l)}\cdot \mathrm{s}\right),w_{\mathrm{i}}(l)=e^{{\tilde{w}}_i(l)}/\sum _{k=0}^K{e}^{{\tilde{w}}_i(k)} \\ {\mathbf{E}}_i=\mathbf{MLP}\left({\mathbf{X}}_i^{(1)}\Vert {\mathbf{X}}_i^{(2)}\Vert \dots \Vert {\mathbf{X}}_i^{(K)}\right) \end{gathered}$$

Scalable GNN模型设计空间

《PaSca: a Graph Neural Architecture Search System under the Scalable Paradigm》 WWW 2022 best paper

以上介绍的Scalable GNN都是一种特定的模型架构，根据上述工作，可以总结出一个Scalable GNN的模型设计空间，然后可以定义搜索目标（准确度和速度），搜索出适合当前任务场景的Scalable GNN。

Scalable GNN的模型设计可以分为三个阶段：

1、预处理阶段

Aggregation step（$K_{pre}$）是指最多用几层卷积得到的特征。

Graph aggregator（$G{A}_{pre}$）是指邻居聚合机制用什么邻接矩阵，比如标准化后的 A、PPR等。

上面介绍的SGC、SIGN、SAGN、GAMLP用的就是A；S2GC用的是PPR。

2、模型训练阶段

Message aggregators（$MA$）是指如何利用得到的k-steps的特征。None就是只用最后一层的（SGC）；Mean就是S2GC；Concatenate就是SIGN；Weighted就是SAGN；Adaptive就是GAMLP。只用某一层的是不太好的，因为不同节点最优的感受野不同。

Transformation step（$K_{trans}$）是指MLP的层数。

3、后处理阶段

这里的$K_{pos}$和$G{A}_{post}$和预处理阶段的$K_{pre}$和$G{A}_{pre}$相同，目的是为了 Label Propagation，将模型预测的分类概率分布再传播若干次，类似于APPNP，不过是在训练之后直接对模型输出传播。

整个模型设计空间包含18万种模型架构，上述总结的Scalable GNN都是这个设计空间下的具体实例：

模型结构自动化搜索系统（自动搜超参）

这部分文章篇幅很少。分为两个引擎：一个是搜索引擎，一个是评估引擎。

搜索引擎是基于贝叶斯优化实现模型结构的推荐。首先定义优化目标：准确度和训练速度。然后建模观测到的模型结构和优化目标的关系（尝试建立一个映射），返回一个能平衡多个优化目标的模型结构，让评估引擎去验证。

评估引擎就是把模型训一遍，然后把结果返回给搜索引擎，这样搜索引擎的观测结果又多了一条。

实验结果

通信开销

模型准确度与效率：

PaSca搜到的模型可以比较好的平衡训练效率和模型准确度。右图可以看出不解耦的GCN相较于解耦的GCN，性能没有显著优势，但是效率差了一百多倍。

ScalableGNN没有over-smoothing，因为深层的卷积的输出是做为一个初始特征使用的，Attention可以关注也可以不关注。