Twitter团队最新研究：快速高效的可扩展图神经网络SIGN

今天给大家介绍的是Twitter研究团队发表的一篇论文，该研究针对大规模图神经网络训练的问题，提出的一种新的结构更加简单的模型——SIGN，这种模型的提出使得计算复杂度大大降低，能够有效地处理大规模图结构，在多个开放的数据集上与主流的模型进行评估对比，SIGN更具有竞争优势。

1

背景

在图上进行的深度学习，也称为几何深度学习(GDL)或者图表示学习(GRL)，在短短几年的时间就从最初的籍籍无名发展成为机器学习最突出的领域之一。图深度学习模型在各种不同的领域都非常成功，其中包括社交网络链路预测、社交媒体虚假新闻预测、人物交互、粒子物理、药物重定位、发现抗癌食品等。但是通常越简单的结构在许多应用中越能发挥重要作用，特别是图卷积网络(GCN)。图卷积网络旨在将CNN推广到图结构数据中，目前已经在图上开发了很多类似卷积运算的模型，例如第一代图卷积网络模型-频谱图卷积神经网络(Spectral graph CNNs)，基于切比雪夫多项式的ChebNet等。而目前的研究主要集中在小规模数据集上，对于能够扩展到例如Facebook、Twitter等大规模社交网络图上的模型研究相对较少。解决大规模数据集已经成为GNN广泛应用的一个主要挑战。对于普通的神经网络而言，损失函数通常都能够拆分到每一个观测样本上面，实现并行计算，而GNN每一个节点的损失都依赖于其他节点的信息，并且节点邻居的数量往往是随度数的增加呈现指数级增长的，从而导致计算量大和存储困难等缺点。目前是通过图采样的方法来降低训练GNN的成本，譬如GraphSAGE、ClusterGCN和GraphSAINT等，但是图采样技术会引起损失。

在这篇文章中，作者提出了一种新的可推广至大规模图结构的模型——SIGN(Scalable Inception Graph Neural Networks)，并且这个模型在设置不同值的情况下还能扩展为GCN、S-GCN、ChebNet等模型。这种思想受到Inception网络的启发，预先设置不同大小的卷积核，可以很快地进行训练和推理。尽管这种新型结构简单，但是在大规模图数据集上不仅可与目前性能最佳的模型相媲美，而且显著加快了训练速度。

2

相关工作

（1）符号说明

将一个无向有权图定义为

，其中W为n*n的邻接矩阵（对称矩阵），

为度矩阵，表示每个节点的度数之和(对角阵)，并且假设每个节点具有d维的特征，X为包含所有节点特征向量的矩阵（n*d）。使用归一化的拉普拉斯矩阵：

（Symmetric normalized Laplacian）[使用拉普拉斯矩阵的原因之一是其为半正定矩阵，为特征分解做准备]。而每一个节点的拉普拉斯量可以表示为以下的局部加权平均值：

这里可以参考拉普拉斯算子和拉普拉斯矩阵的关系，拉普拉斯算子计算了周围点与中心点的梯度差，可以计算一个点到它所有自由度上微小扰动的增益，则通过图来表示就是任意一个节点i变化到节点j所带来的增益，并将这种增益进行归一化。接下来对拉普拉斯矩阵进行谱分解，

，

很明显为正交的特征向量，对角阵为特征值。这里将特征向量视为傅里叶变换的基（因为这里的特征向量是n个线性无关的正交向量），那么图上的傅里叶变换可表示为

，而利用卷积实现类比，将卷积运算推广到图上可得到如下表示：

其中为Hadamard product（哈达马积），对于两个维度相同的向量、矩阵、张量进行对应位置的逐元素乘积运算。

（2）图卷积的发展

Spectral graphCNNs：简单粗暴地将图上的傅里叶变换变成卷积核，存在的弊端（1）在进行前向传播的时候，需要进行特征分解和矩阵乘积运算，达到

的复杂度（2）需要n个卷积核（3）卷积核不具有spatiallocalization（4）在图上学习到的卷积核不具有扩展性。

ChebNet：将卷积核巧妙的设计成

，其优点在于（1）卷积核只有K个参数，一般K远小于n（2）在矩阵变换后，不需要进行特征分解，由于仍需要计算

，复杂度仍为

（3）卷积核具有很好的spatial localization。

GCN:改进的GCN卷积核为

，在ChebNet中，K=1时整个公式可以简化为

，这样会导致数值不稳定和梯度爆炸/消失，所以加入归一化项

，是具有自环的图的邻接矩阵（相当于加1）。

S-GCN：为节点分类任务而设计的，

，在2019年，Wu等人提出具有大卷积核的模型实际上等效于具有多个小卷积核模型，将其改进为

。

（3）图采样

传统的图卷积神经网络算法，如GCN、GAT、MoNet等在面对大型图时都是无法使用的，Graph sampling（图采样）对应规模较大的图取得了一定的成功，Graphsampling主要分为Node-wise sampling（如GraphSAGE）、Layer-wise sampling和Graph-wise sampling（如目前的state-of-art方法GraphSAINT）。

3

模型

首先SIGN并不是基于采样的模型，因为采样会产生误差，而是从最近的两个发现中获得的灵感：（1）S-GCN模型虽然很简单，但是很有效，并且与具有多个卷积层的模型有相似的效果。（2）GCN聚合机制具有简单的卷积核，但是在精度上却和基于更复杂聚合函数的模型相媲美。据此，SIGN模型如下所示：

其中，

是一个固定的n*n维的传播矩阵，这里可以理解为将ChebNet中拉普拉斯矩阵的变型

中

的假设为2，并进行修正，就得到B的表示。都是可以通过反向传播学习到的参数，|是合并操作（concatenation），

都是非线性函数，后者可以根据具体的任务而选择，例如softmax或者sigmoid。

因为可以提前计算，用分布式计算例如Apach Spark可以加快计算速度。上述公式和Inception模型很像，由参数r确定不同的大小的卷积核，特别的，r=0对应于Inception中的1*1卷积（相当于进行线性变换，起到降维的目的）。也正是因为这种类比，称这种模型为SIGN。

更为巧妙的是，这个模型高度概括了ChebNet, GCN, and S-GCN这些特殊情况，譬如将激活函数设置为如下形式：

则只需改变公式中的一些值，就可以进行推广。具体的值设置如下：

下表是SIGN模型和目前的主流算法在时间复杂度上的比较：

4

实验

作者先在四个大型公开数据集进行实验：Reddit，Flickr，Yelp和PPI。在Reddit和Flickr数据集上研究节点多分类问题：前者的任务是根据用户评论预测在线帖子的社区；Flickr是基于在线图像的描述和共同属性对图像进行分类。Yelp和PPI是多标签分类问题：前者的目的是根据客户评论来预测业务属性，而后者的任务则是从人体组织蛋白的相互作用中预测蛋白质功能。具体的数据集如下表所示：

作者将SIGN和GCN，FastGCN，Stochastic-GCN，AS-GCN，GraphSAGE等七种方法进行了比较。下表是在四个大型数据集上比较的结果：

这里在10次迭代中计算出的F1得分平均值和标准差。能够看出在Reddit上SIGN具有最先进的性能，同时在其他数据集上也始终保持竞争优势。

下表是SIGN模型和目前的主流算法在Reddit数据集上训练时间的比较

尽管在预处理阶段它比GraphSAINT稍慢，但SIGN花费的时间只是一小部分，比GraphSAINT和GraphSAGE高出两个数量级。整个程序是在Pytorch中进行的，但GraphSAINT3和ClusterGCN4的实现是在Tensorflow中的，是比PyTorch快六倍的并且GraphSAINT的预处理是并行的，但是作者的不是。

其次尽管作者的目标是大型图，也尝试了较小但优良的转导数据集，以将SIGN与传统GNN方法进行比较。比较结果如下表所示：

试验结果表明SIGN在较小的数据集上也具有竞争力，其性能优于经典方法，并且与当前的最新方法（DIGL）接近。

5

总结

SIGN的特点在于模型的简单性、高效性、适合大规模图结构。因此，SIGN非常适合于工业化的大型系统。这种模型在通用图学习基准上获得了竞争性结果，同时与其他方法相比，其训练速度明显加快，推理速度提高了两个数量级，同时适用于转导学习和归纳学习，而且都取得了较大的进步。

参考资料

https://arxiv.org/abs/2004.11198