基于高效采样算法的时序图神经网络系统（一）

图数据是一种非结构化的数据，但能够蕴含很多结构化数据中无法蕴含的信息。图数据无处不在，世界上大部分数据都能够用图数据来表达。为了高效的提取图特征，图神经网络是一种非常重要的图特征提取方式。图神经网络在各个领域被广泛应用，例如：金融网络、交通网络、教育网络等。

时序图是包含时间属性的图数据。在金融交易领域，时间属性是反欺诈、反套现等众多应用场景的重要属性。因此如何对时序图神经网络进行高效的训练和推理成为了非常重要的问题。基于以上问题，本文提出了一种基于高效采样算法的时序图神经网络系统。

首先我们介绍用于时序图神经网络采样的高效采样方法。采样常常被用于深度学习中以降低模型的训练时间。然而现有的采样算法在图神经网络中将会带来额外的采样开销。现有的图神经网络采样算法模型有三种：节点采样、分层采样和子图采样。

图 1. 节点采样

图 2. 分层采样

正如图 1 所示，节点采样中每个点在每一层都不会共享邻居。因此随着层数的增加，每层点数都会出现指数级别的增长。

如图 2 所示，分层采样中每个点会共享邻居，因此，分层采样中点的数据线性增长。

对于子图采样，以下代码展示子图采样的过程。子图采样首先使用一个队列在存储候选的点（边），在每轮采样过程中，子图采样根据每个点的概率分布采样出一个点，随后在这个点的邻居中随机采样一个点，从而在队列中对采样得到的点进行替换。

我们可以发现，在子图采样的过程中，对于每一轮采样，常用的采样算法，例如逆变换采样或者别名表采样，都需要重新计算当前候选数据的概率分布。因此现有的采样算法需要在子图采样的每轮花费 O(n)的时间复杂度。从而整体上子图采样的时间复杂度为 O(n^2)。在一个具有 1.4 billion 条边的数据集上，现有的采样算法需要花费一个多小时来进行子图采样。这样的采样开销是无法接受的。

为了解决子图采样中动态计算概率分布的高额开销问题，本文提出了高效的采样算法——线段二分采样。我们使用类似于线段的区间查询数据结构来维护子图采样中队列里每个点（边）的采样概率分布。如图 3 所示，我们在线段二分采样数据结构中存取一段点（边）的权值之和，因为每个点（边）的采样概率为它的权值除以所有点（边）的权值之和。对于维护过程，每次删点以及替换操作只需要在覆盖这个点（边）的“线段“中进行更新。由于覆盖每个点的”线段“最多有 log(n)个，因此每次删点以及替换过程都会需要 O(log(n))的时间复杂度。在整体上，线段二分采样算法仅仅需要 O(nlog(n))时间复杂度。

在现实数据集中，线段二分搜索相比于现有的采样算法能够获得最高 38.8 的加速比。

在下期分享中，我们将具体介绍时序图神经网络中的训练优化， 敬请期待。

更多 AI 技术内容，欢迎关注公众号 Baihai IDP