江苏龙网

  1. 首页 > 人文 > >

扩展图神经网络：暴力堆叠模型深度并不可取( 二 )


该论文的核心思想是 ， 为了用一个 L 层的 GCN 计算某个节点上的训练损失 ， 只需要聚合该节点 L 跳之内邻居节点的信息 ， 而在计算中不考虑图中更远一些的节点 。
但问题在于 ， 对于这种符合「小世界」模型的图（例如社交网络） ， 由某些节点 2 跳内的邻居组成的子图可能就已经包含数百万的节点了 ， 这使得我们很难将其存储在内存中 。
GraphSAGE 通过至多对 L 跳的邻居进行采样来解决该问题：从正在训练的节点开始 ， 该算法多次有放回地均匀采样 k 个 1 跳邻居；接着 ， 对于每一个该节点的邻居节点 ， 算法以相同的方式再采样 k 个邻居节点 ， 以此迭代式地采样 L 次 。 通过这种方式 ， 我们保证对于每个节点而言 ， 可以聚合有界的 L 跳规模为 O(k?) 的采样邻居节点 。
如果我们使用 b 个训练节点构建一个 batch ， 且每个节点的 L 跳邻居节点相互独立 ， 那么我们就会得到与图的规模 n 无关的空间复杂度 O(bk?) 。 使用 GraphSAGE 算法时 ， 一个 batch 的计算复杂度为 O(bLd2k?) 。
扩展图神经网络：暴力堆叠模型深度并不可取文章插图
图 1：GraphSAGE 的邻居节点采样过程 。 我们从完整的图中下采样得到包含 b 个节点的 batch （在本例中 ， b=2 ， 我们将红色和淡黄色的节点用于训练） 。 在右侧的图中 ， 我们采样得到 2 跳邻居节点图 ， 将其用于独立地计算红色和淡黄色节点的图嵌入和损失 。
GraphSAGE 有一个显著的缺点 ， 即采样得到的节点可能会出现很多次（由于有放回的抽样） ， 因此可能会引入大量冗余的计算 。 例如 ， 在上图中 ， 深绿色的节点在两个训练节点的 L 跳邻居中都出现了 。 因此 ， 在一个 batch 中 ， 该深绿色节点的嵌入会被计算两次 。
随着 batch 大小 b 和采样节点个数 k 的增长 ， 冗余计算的规模也会增大 。 此外 ， 对于每个 batch 而言 ， 尽管拥有 O(bk?) 的空间复杂度 ， 但只会利用 b 个节点计算损失函数 。 因此 ， 从某种程度上说 ， 对于其它节点的计算也是一种浪费 。
在 GraphSAGE 之后 ， 许多后续的工作重点关注改进 mini-batch 的采样过程 ， 从而减少 GraphSAGE 中的冗余计算 ， 并使得每个 batch 更加高效 。
ClusterGCN 和 GraphSAINT 是该研究方向最新的工作 ， 它们采用了「图采样」（与 GraphSAGE 的邻居节点采样相对应）技术 。
扩展图神经网络：暴力堆叠模型深度并不可取文章插图
在图采样方法中 ， 我们在每一个 batch 中采样得到原始图的一个子图 ， 然后在整个子图上运行类似于 GCN 的模型 。 在这里 ， 我们面临的挑战是 ， 需要保证这些子图保留了大多数原始的边 ， 并且能展现出有意义的拓扑结构 。
为了实现上述目标 ， ClusterGCN 首先对图进行了聚类；然后 ， 在每一个 batch 中 ， 该模型会在一个聚类上进行训练 。 这使得每个 batch 中的节点会联系得尽可能的紧密 。
GraphSAINT 则提出了一种通用的概率化的图采样器 ， 它通过在原始的图中采样子图来构建用于训练的 batch 。
我们可以根据不同的方案设计图采样器：例如 ， 该采样器可以执行均匀节点采样、均匀边采样 ， 或者通过使用随机游走计算节点的重要性、将其用于采样的概率分布从而进行「重要性采样」 。
请注意 ， 进行采样的好处之一是：在训练时 ， 采样可以作为一种边级别上的「dropout」技术 ， 它可以对模型进行正则化 ， 从而提升模型的性能 。 然而 ， 在推理时 ， 边 dropout 仍然需要看到所有的边 ， 而在上述方法中 ， 我们这些无法获得这些边的信息 。
图采样技术的另一个影响是 ， 它可以减少在邻居节点指数级增长的情况下 ， 存在的「信息瓶颈」及其造成的「过度挤压」现象 。


推荐阅读


上一篇：“苹果iOS”历年内置经典高清壁纸｜风景类

下一篇：「声卡跳线」得胜MX630搭载宿主机架跳线设置使用