快速高效的可扩展图神经网络SIGN
|
图神经网络（GNN）是一种新型的ML模型，专门用于处理图数据。在不同领域，GNN可成功实现领域内关系及相互作用建模，如社会科学，计算机图形与视觉，粒子物理学，化学和医学。但是令人失望的是，对GNN模型的研究和应用都是在规模较小的图上进行的(比如被广泛使用的引用网络数据集-Cora，该数据集仅仅包含约5K节点[1])，大规模图数据的研究却很少受到关注。与之矛盾的是，在实际工业场景中，需要处理的确实超大规模的图，例如包含数亿节点和数十亿边的Twitter或Facebook社交网络，先前的研究工作很难用于这些图的处理分析。 简单来说，图神经网络的核心就是邻域聚合，即整合邻居节点的特征。将特征维数为d的n个节点表示为 n×d 的矩阵X，经典的GCN模型[2]就是通过整合邻居节点的特征实现某一节点的表示，这就是图神经网络中的卷积操作： Y = ReLU(AXW) 其中，W是所有节点共享的可学习参数矩阵，A是线性扩散算子，等于邻域中特征的加权平均值[3]。与传统CNN类似，可以将这种模式依序排列实现多层网络。图神经网络可用于节点预测（如检测社交网络中的恶意用户），边预测（如推荐系统中的链接预测），整个图的预测（如预测分子图的化学性质）。另外，通过以下形式构架一个两层的GCN，可实现节点分类任务： Y = softmax(A ReLU(AXW)W’) 那么，将图神经网络扩展到大规模图难在哪里呢？在上述节点预测问题中，节点作为GNN的训练样本。传统的机器学习通常假设样本是服从某一分布的、相互独立的。这样，可以根据单个样本分解损失函数，并采用随机优化技术批次处理训练数据（mini-batches）。现今几乎每个深度神经网络都是用mini-batches批次训练。 然而在图中，节点通过边相互连接，这使得训练集中的样本并不完全独立。此外，由于节点间的依赖性，采样可能会引入偏差（例如，可能会使某些节点或边被采样的概率更大），需要对此“副作用”进行处理。还有很重要的一点，采样过程中必须保证采样子图的有效结构，确保GNN可以处理。
但之前的许多研究工作忽略了这些问题，如GCN、ChebNet[2]、MoNet[4]和GAT[5]等直接使用全批次数据进行梯度下降，这就导致必须将图的整个邻接矩阵和节点特征保存在内存中。即使中等大小的图，L层GCN模型的时间复杂度为?（Lnd²）和空间复杂度为?（Lnd +Ld²）[7]，更不必说大规模图了。 （编辑：常州站长网） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |
