2.3 微批次（Mini-batches）2.4 数据变换（Data Transforms）3 GCN实现 3.1 谱方法GCN实现（Cora引...
方法就是前面GraphSAGE的minibatch算法的1到6行,设定采样深度和采样数量,遍历 G_S 中的每个节点进行采样,即利用了GraphSAGE算法的前半步。然后结合接下来的一层GCN和一层GraphSAGE聚合(即后半步),我们可以思考一下:这里处理的很巧妙,如果用纯粹的两层GraphSAGE算法,虽然有数据增强,但无法利用到 G 中的权重信息,而...
MiniBatchKmeans
mini-batch算法的效率可以用“嵌入利用率”的概念来表征,它与batch或within-batch links的节点之间的连接数量成正比。这一发现促使作者使用图聚类算法来设计batches,该算法旨在构造节点分区,以使在同一分区中的节点之间比不同分区中的节点之间具有更多的图连接。基于图聚类思想,提出了Cluster-GCN算法,一种基于高效图聚类...
ScalableGCN是一种由阿里妈妈提出的在大规模图上加速Mini-Batch GCN训练速度方法。 它的主要思路是利用前向计算和反向计算的Cache,在mini-batch之间共享中间层表示的计算结果,同时维护每个顶点的异步更新的通路,达到在与GCN层数成线性关系的时间内训练GCN模型的目的。
GraphSAGE乍一看像是一个KK层的GCN,但是它通过合理的采样使得更便于计算,也极大地减小了运算和存储的代价。(以下直接按照minibatch的setting进行说明) 首先每次会先抽取一个minibatch,因为每层会聚集一阶邻居(one-hop neighbours)的信息,所以KK层至多会涉及到KK阶邻居,于是我们先将minibatch中结点的至多K+1K+1阶邻居...
算法2 介绍了训练过程中 mini-batch: 输入为小批量节点集合 M;深度为 K; 输出为 Embedding zu ; 第1 行到第 7 行为集合 M 中的节点计算节点邻域,这边注意遍历顺序(K...1),这和 GraphSAGE 一个道理; 第8 行到第 14 行为 K 层卷积操作;
对于多个 GPU,首先将每个 mini-batch (模型架构图的底部)划分为相等大小,每个 GPU 将负责一部分 mini-batch,并使用相同的参数来进行计算。在反向传播时,汇聚所有 GPU 上每个参数的梯度然后执行同步的 SGD 运算。作者针对 Pinterest 的数据规模将 mini-batch 的大小设置为 512 到 4096 之间。此外,作者还参考了...
GCN:Full-batch gradient descent 需要计算整个所有节点的梯度,也需要存储所有 Embedding ,所以导致 O(NFL)O(NFL) 内存需求; 在每个 epoch 只更新一次参数,所以 SGD 的收敛速度缓慢; memory: bad time per epoch: good convergence: bad Mini-batch SGD 每次更新只基于一个 mini-batch 的梯度,它可以减少内存...
小批量随机梯度下降(Mini-batch stochastic gradient descent)可以缓解这一问题。然而,生成Mini-batch的过程应该考虑到GCN模型中的层数,因为具有k层的GCN的k阶邻居必须存储在内存中,以便进行精确的过程。对于非常大且紧密相连的图数据集,可能需要进一步的近似。