共计 3841 个字符，预计需要花费 10 分钟才能阅读完成。
本文首发于 Nebula Graph Community 公众号
常常看技术文章的小伙伴可能会留意到除了正在浏览的那篇文章，在文章页面的注释下方或者右侧区域会有若干同主题、同作者的文章等你浏览；常常逛淘宝、京东的小伙伴可能发现了，一旦你购买或者查看过某个商品之后，猜你喜爱的举荐商品会贴近你刚拔草的商品…这些日常生活中常遇到的事件，可能是由一个名叫图学习的“家伙”提供技术支持。
图学习，顾名思义是基于图的机器学习，依照本期我的项目介绍的参赛队伍——图学习趣味小队队长杨鑫的话就是，图学习是一个通过深度学习办法，基于图的构造与属性生成一个向量作为点、边或者整个图的表征。
在之前 Nebula Hackathon 2021 年的参赛我的项目中，图学习趣味小队“豪气”地说要让 Nebula Graph 具备反对图学习的能力，在本文接下来的内容中，你将理解到他们是怎么实现这一指标的。
图学习小课堂
在讲述我的项目实现之前，我的项目负责人杨鑫先给大家上了一课“图解图学习”。
以获取顶点的向量表征为例来解说下图学习过程，第一步须要对图中顶点街坊进行采样拿到街坊的拓扑构造以及属性；第二步便是通过自定义的聚合函数聚合街坊顶点蕴含的信息进行计算；最初一步基于聚合信息失去图中各顶点的向量示意。
杨鑫示意，掂量一个图学习算法的好坏是通过生成向量中蕴含图中顶点属性及拓扑构造的丰盛水平来判断的。
故事的开始
在抉择图学习框架时，图学习趣味小队有本人的一套选型规范：首先它是开源组件，不便二次开发，其次它反对分布式，最初框架自身和图数据库的耦合水平要低不便定制化开发。通过深刻调研，因为 DGL（链接：https://www.dgl.ai/）同底层的图数据库耦合过高，PYG（链接：https://pytorch-geometric.readthedocs.io/en/latest/）不反对分布式，最终他们采纳了 Euler（GitHub 地址：https://github.com/alibaba/euler），而在 Nebula Hackathon 2021 中，图学习趣味小队的重点工作便是用 Nebula Graph 替换 Euler 原生图数据库，让社区用户能够基于 Nebula Graph 低成本尝试图学习能力。
设计思路
在方案设计上，架构分为三层：底层是 Nebula Graph 图数据库，中间层是图采样算子层，为下层 Euler 图算法提供多种采样图数据的能力。图采样算子则是他们本次工作的重点——重写 22 个 TF 采样算子、6 种 nGQL 采样语法。
高强度的开发量
以全局带权采样语法设计为例，
这里采纳了预计算（离线）+ 计算下推（实时）的形式来实现全局采样，次要过程为（上图 1-4）
- graphd 提交异步构建工作给 metad；
- metad 下发工作给各个 storaged 节点进行计算；
- storaged 将计算结果上报给 metad 汇总；
- metad 通过心跳将后果同步给 graphd。
具体开展来讲，在图学习训练过程中，数据采样是一个十分高频的操作，采样性能好坏对图学习训练耗时影响很大。
在这里，杨鑫他们采纳别名采样算法作为全局带权采样语法的外围算法，它的基本原理是首先对进行采样的全副数据依据各自的权重计算出一份采样表，采样表由行号（sid）、vid1、采样概率（prob）、vid2 四局部组成，其中行号是从 0 开始的编号，vid1、vid2 示意能够被采样的某个顶点的 vid；采样流程是首先在表中随机抉择一行，而后再随机生成一个 0~1 之间的值 p，如果 p < prob，则本次采样的数据是 vid1，否则采样 vid2。
目前图学习是基于动态图数据训练，因而咱们能够通过预计算的形式离线生成一份别名采样表，而实时采样过程简化为基于预计算的采样表做两次随机采样，工夫复杂度由 O(n) 降到 O(1)，能够极大地提高采样效率。
上面是基于 Nebula Graph 实现的全局带权采样具体实现，跟 Nebula Graph 的索引重建逻辑很类似。
- Graph 服务调用 Meta 服务启动一个异步构建采样表工作，并反对异步工作的状态查问。
- Meta 服务的作用是管制异步工作的执行，包含调配每个 Storage 节点须要解决的数据（依据 partition 的 leader 散布决定）、异步触发各个 Storage 节点进行采样表的计算、记录工作的执行状态、记录全局信息（点、边权重和）、通过心跳逻辑将全局信息缓存在 Graph 服务中。
- Storage 服务的工作是生成所负责数据的采样表。采样表的计算是整个流程中的外围逻辑，计算过程须要对所有点、边编号，并依据权重大小对点、边进行分类，很显然这些数据是无奈全副存储在内存中的，所以咱们在 Storage 中减少了一个采样统计信息 RocksDB 实例来存储采样表、点边总数、点边权重、计算两头变量等数据。以计算某一类点的采样表的过程为例：
第一步遍历全图来统计这一类点的权重和数量，同时为了给生成采样表做筹备，将点的序号（点的读取程序）、vid、权重等数据存储在了图中（B1）构造中。其中 key 的数据结构是 type + tagid + sid，type 标识了数据是 B1 类型，tagid 就是点的 tag，sid 是点的序号，跟采样表的 key 构造雷同。
第二步将数据分类，依据权重值以点的总数的倒数为界将所有的点分成两局部，别离以（B2）、（B3）的构造存储，key 的组成与 (B1) 构造相比就是 type 值不同。
第三步别离遍历（B2）、（B3），依据别名采样算法的实践来计算每个点的采样概率 prob。这里每个点是用 sid 来标识的，也就是说实际上是在计算第 sid 个点的采样概率，概率值作为采样表的一部分会更新到（B1）构造中。
第四步将两头变量（B2）、（B3）构造删除掉，开释磁盘空间。
利用采样表进行实时采样的过程就比较简单了。实现采样表的预计算后会将点、边权重的统计信息上报到 Meta 服务存储，而后通过心跳告诉 Graph 服务将这些数据缓存在本地。依据这些数据能够计算出点、边在各 Storage 服务上所占的权重比例，将用户指定的采样数量按比例调配到各 Storage 服务，而后在 Storage 服务上通过两次的随机数操作采样到足够数量的数据后返回，最初在 Graph 服务上进行数据聚合，这样就实现了一次带权采样。
另外为了进步异步工作的健壮性，还实现了失败重试、工作反复限度、重建采样表后脏数据清理、导出采样表等性能。
提到我的项目设计以及重写其余算子过程中遇到的问题，图学习趣味小队队长杨鑫示意因为 Nebula Graph 的数据都存储在磁盘中，要用 Nebula Graph 替换 Euler 原生内存图数据库，革新后的 Euler 在采样效率上必定要低于原生 Euler， 因而怎么保障革新后 Euler 的图学习训练耗时尽可能靠近原生 Euler 是要解决的首要问题，至多得保障两者采样性能不能有数据级上的差距 。
原生 Euler 中的图学习算法由 Python 实现，通过 TensorFlow 的 OP 机制来调用 C++ 实现的采样算子，而后在采样算子内间接调用内存图数据库获取数据，这样就实现了一次数据采样。
图趣味小队最后的计划是将采样算子用 Python 实现，这样一次数据采样过程就变成了图学习算法间接调用采样算子，而后在采样算子内则通过 Nebula Graph 的 Python 客户端执行采样语法获取数据。这样革新后的零碎会有更清晰的解决流程，然而通过测试他们发现其训练耗时要远大于原生 Euler，具体到训练过程中的每次数据采样上，其耗时是原生 Euler 的几十倍，这样的后果显然是不能满足要求的。通过剖析各阶段执行耗时他们发现，数据采样的耗时要远大于采样语法的执行耗时，所以他们认为是 Python 客户端在反序列化上耗费了大量工夫。因而图趣味小队进行了第一次优化， 应用 fbthrift fastproto 替换 Nebula Graph 原生客户端的序列化组件 ，优化后的性能进步了一倍，整体训练耗时的确有所升高，然而这样的后果却依然无奈满足他们的应用要求。
这时候用上了第二个计划，重写 C++ 版本的采样算子，在采样算子中通过 Nebula Graph 的 C++ 客户端执行采样语法获取数据，相比第一个计划多了一些适配工作，算子的重写次要是适配 C++ 客户端的输入输出，另外革新了 C++ 客户端以便采样算子的调用。
这也是他们最终的计划，这样革新后的 Euler 尽管在训练耗时上依然高于原生 Euler，然而差距管制在了二倍以内，合乎预期。
有意思的 Hackathon
当谈到本次有什么值得图学习趣味小队注意的我的项目时，队长杨鑫示意比拟关注的是大油条东北虎队伍的我的项目——如何吊打 Nebula 的深度查问，这个我的项目的优化思路对他们很有借鉴意义。
因为在理论应用中，图趣味小队所在团队的业务方有很多的多跳查问需要，包含 GO 查问、FINDPATH 查问等。这本应该是 Nebula Graph 所善于的局部，在大部分场景下也的确如此，然而在遇到出度很大的顶点的时候，查问性能会急剧好转。其次要起因还是基于目前 Nebula Graph 的架构，多跳查问只能先将一跳的后果集汇总到 Graph 服务后能力进行下一跳计算，齐全不能将多跳计算下推。而这个我的项目正好给他们提供了一个解决这个难题的思路。
附：图学习趣味小队我的项目设计文稿：https://docs.qq.com/doc/DVnZQUVBzd1dmS0lS。
交换图数据库技术？退出 Nebula 交换群请先填写下你的 Nebula 名片，Nebula 小助手会拉你进群~~
关注公众号
