引言

图数据广泛存在于我们生活中，社交网络、互联网、交通网等等都是天然的图数据。在阿里内部场景，用户物品的交互数据，安全风控领域的用户、评论、交易等都构成图，图可以说是数据最为广泛的存在形式。

深度学习在文本，语音，图像等数据上取得了很大成功，GNNs(图神经网络)是深度学习在图结构数据上的应用。对于图这一非欧空间的数据，如何将它和深度学习结合起来是GNNs首先要解决的问题。GNNs早期的研究主要集中在Spectral-based 方法上，这种方法理论比较充分，但是难以用于大规模场景。近些年以GraphSage[1]为代表的Spatial-based方法在性能，泛化性，灵活性等方面均体现出了优势。GraphSage通过采样子图进行按批次训练的方式在Pinterest推荐场景进行了实际应用，并取得了很好的效果[2]。此外，像DeepWalk等Graph embedding算法和TransE等知识图谱模型的训练都是基于采样的方法进行设计和训练。

阿里很多场景的数据都是十亿级别节点，百亿边的规模，针对阿里众多场景的实际需求和特点，我们设计开发了一个简洁易用，高性能的工业级大规模图学习系统graph-learn（https://github.com/alibaba/graph-learn）。Graph-learn主要面向spatial-based的GNNs算法，同时支持graph embedding, 知识图谱等常见图学习算法。我们将GNNs算法抽象为一个统一的算法框架。包括采样，聚合，组合，如Algorithm 1所示[3]。

采样一方面解决了大规模训练的问题，另一方面是进行深度学习批次训练的必要前提。采样向下对接图存储系统，向上对接算法模型，因此是整个graph-learn中的基础功能。

大规模采样的实现

采样和查询是graph-learn图引擎部分对外提供服务的基本接口，采样和查询构建于分布式图存储之上，以Python API的形式对外提供，如图1所示。查询包括图的节点和边的遍历，节点和边的属性、权重、标签等查询。采样分为邻居采样和负采样，邻居采样提供采样子图的功能，负采样主要面向非监督学习场景，系统直接提供采样负样本的功能，不需要用户额外产生负样本。

基于阿里内部大量业务场景的需求总结和实际应用，系统集成了若干种常用的采样和负采样方法(Built-in Samplers)。虽然这些采样方法基本覆盖了大部分需求，但是因为采样方法和算法效果关系密切，甚至直接关系到模型的成败，因此，开放采样编程接口，方便用户进行其他自定义采样方法(Custom Sampler)的探索是我们系统的一个重要功能以及GNN创新的一大方向。

图 1. graph-learn图引擎部分示意图

Graph-learn的图引擎是CS架构，具体的采样实现流程如图2所示：给定一批需要采样的源节点，首先通过Partitioner去查询包含这些源节点的子图在哪个server上，图中src id为1，3的被partition到了server 1上，2，4被partition到了server 2上。然后，将这些src ids发送到对应的server上，查询子图，并调用本地采样方法去执行采样操作。目前系统集成了若干种常见的采样算子，也可以支持用户自定义自己的采样算子。本地采样结束后，需要将采样后的结果按照原始src ids的顺序进行拼接返回。Partition目前使用系统内置的hash划分方法，将来我们会支持不同的Partition策略来进行更加高效的图划分，提高采样和计算性能。

图 2. graph-learn采样流程示意图

对于负采样来说，没有partition和stitch过程，一个batch的输入数据，会随机或者按照分布选择一个server，然后在这个选定server上进行负采样，这样可以做到全局负采样的效果[5]。

我们底层的数据结构使用Tensor的形式实现，支持常见数值类型和string类型的Tensor。基于Tensor这种规整的格式，系统可以将采样的Partition，Stitch和分布式执行过程自动化，因此，新增一个采样算子时只需要写具体的本地采样逻辑即可。

Graph-learn采用了分布式图存储和采样，使得规模可以轻松扩展到上百台机器，支撑起十亿节点，百亿边的日常任务。此外，针对不同的采样策略，我们采用了热点缓存，慢机迁移等众多优化，使得在规模提升的同时，能够保持高性能地采样。

采样算法介绍

邻居采样

Graph-learn支持异构图，同构图是异构图的一种特例，因此图采样需要指定meta path，系统按照指定的meta path采样得到多跳邻居，不同的采样算子按照不同算法来返回邻居。目前built-in的采样算子包括以下几种：
• random：随机采样邻居，每次在给定节点的所有邻居里随机选择一个邻居。
• edge_weight：按照边的权重为概率分布进行采样。
• topk：以edge_weight为大小对邻居进行排序，并返回topk个。邻居数不足要求个数会循环填充。
• in_degree：按照邻居的入度大小为概率分布进行采样。
• full neighbor: 返回给定点的所有邻居。

图3. （a)原始图；（b)目的节点的id对应的edge weight和in-degree统计表。

前四种采样都需要指定meta path，并且需要指定需要采的邻居个数，采样结果以dense的形式返回，这是由于采样后按batch训练的时候需要样本对齐。当然对于原始GCN[4]等需要获取源节点的所有邻居的算法，我们支持采样返回节点的所有邻居，而不做上采样/下采样，我们称这种采样为full neighbor采样，采样后的结果会以sparse的形式返回。

以图3为例，假设需要采样src id为1的节点的邻居，指定的邻居个数是2。那么random会从[2, 3, 4, 5]里随机采样两个；edge_weight以边权重为概率分布返回两个；in_degree采样以入度为概率分布返回两个；topk会返回边权重最大的两个，即[5, 4]。如果指定采样个数为6，则topk会做循环填充，返回结果为[5, 4, 3, 2, 5, 4]；full neighbor采样的话则会返回实际个数的全部邻居[2, 3, 4, 5]。

以上采样算法里按概率分布的采样均采用了AliasMethod[5]实现，因此复杂度都是常数时间。单机在512 batch size、采样10个1hop、15个2hop邻居id的情况下，耗时在毫秒级别。此外针对不同的策略系统有不同的优化，比如对于topk，我们在构图时就会预先按照edge weight为大小对底层存储表进行排序。

上面介绍的算法以node-wise(layer sampling)采样为主，node-wise采样随着采样的跳数增加，邻居数目会急剧上升，在多跳(>2)情况下尤其明显，因此近年来layer-wise的采样也被应用于不同GNN算法，如上图GCN算法所示[6]，我们也正在探索开发layer-wise(graph sampling)的采样，希望在多跳场景下带来进一步的性能优化和内存节省。

负采样

负采样就是给定源节点，返回和它不相连的目标节点。负采样同时支持本地和全局负采样，对于一个batch的样本要采样其负样本时，可以按照一定的概率分布选择一个server，然后在该server上采样。如果选择本地负采样，则只在本机进行负采样。目前built-in的负采样算子包括以下几种：
• random：随机采样和给定源节点不相连的目的节点。
• in_degree：按照目的节点的入度分布，返回与源节点不相连的目的节点。

按照入度分布的in_degree负采样实现上采用AliasMethod[5]，会在首次采样前提前构建好Alias Table，因此采样是常数时间复杂度。此外负采样我们默认是严格负采样，但是出于性能和极端情形的考虑，我们支持用户端设置一个阈值来控制严格程度。负采样可能对算法效果也会产生很大影响，因此负采样算子如何和图划分结合，如何高效负采样，以及按何种分布负采样都是值得探索和研究的地方。

自定义采样

上面介绍了graph-learn开发过程中，结合实际业务场景需求系统已经集成的邻居采样和负采样算子。虽然这些built-in的采样算子满足了大部分GNNs和其他图学习算法的需求，但是，考虑到每个具体业务场景的采样、负采样需求不同，而且采样、负采样策略对算法的构建和效果有着重要影响，因此我们也允许用户自定义采样算子。自定义采样算子主要流程包括：
a）在C++文件中注册并实现新Sampler

class MySampler : public Operator {
public:
  Status Process(const OpRequest* req, OpResponse* res) override {
    //TODO
  }
};
REGISTER_OPERATOR("my_sampler", MySampler);

b）在Python端调用已注册的算子

g.sample(count).by("my_sampler")...

应用场景

采样作为graph-learn的核心功能，在所有使用graph-learn的作业中都起着非常重要的作用。常见的用法是遍历图的点或者边产生正样本，然后采样给定节点的n-hop邻居对节点进行编码，对于非监督学习场景使用负采样来得到负样本并对负样本做类似的邻居编码。最后对采样后的结果进行特征的组合和reshape等处理成batch的数据，接入顶层算法模型。基于这一流程graph-learn目前支持GCN(包括采样版实现), GAT(包括采样版实现), GraphSage, 二部图GraphSage, DeepWalk, LINE, TransE等算法，并且可以方便扩展实现其他的图学习模型。

在阿里内部，graph-learn支撑了推荐，安全风控等众多业务场景，不同场景下有个位到十位数百分点的提升。此外，由于样本生产组装过程和训练同时进行，相比之前的离线处理完样本后再训练的流程，存储和训练时间也得到了很大节省。

总结和展望

本文对graph-learn的采样实现和各个采样算子做了简单介绍，采样在GNNs中起着重要作用，并已经在很多场景得到了实际应用。采样和算法效果以及模型设计息息相关，是GNNs探索创新的一个重要方向，目前的采样算子都是基于统计静态特征，后面我们会在采样和训练结合方面做一些探索。此外，将Graph Partitioning和采样，负采样一起考虑和优化也是系统发展的一个重要方向。

参考文献

[1] Inductive Representation Learning on Large Graphs. NIPS, 2017.
[2] Graph Convolutional Neural Networks for Web-Scale Recommender Systems. KDD, 2018.
[3] AliGraph: A Comprehensive Graph Neural Network Platform. VLDB, 2019.
[4] Semi-Supervised Classification with Graph Convolutional Networks. ICLR, 2017.
[5] Distributed negative sampling for word embeddings. AAAI, 2017.
[6] Accurate, Efficient and Scalable Graph Embedding. IPDPS，2019.

开源项目地址：https://github.com/alibaba/graph-learn
欢迎对图学习算法和系统感兴趣的同学加入我们 kun.zhao@alibaba-inc.com
本文作者：艾宝乐