Alibaba Innovative Research (AIR) > Big Data & Data Mining
图算法的自动增量化方法

业务背景

图数据作为一种抽象数据结构,可以直观建模现实世界中各种实体对象间的联系和依赖关系。社交网络、网页链接、知识图谱都是用图数据进行建模的典型例子。图计算是分析、挖掘海量关联数据的有效手段,在阿里内部的业务如搜索风控、社交推荐上有丰富的应用场景。

目前集团内部实际应用中所需要处理的图数据规模已达十亿级以上,且常见的大规模图数据在不断进行快速迭代更新。若每次均重复调用已有全量计算方法处理更新后的全图会在诸如模式匹配等较复杂的图查询上产生极大开销。相比于全量计算,增量计算旨在快速处理图数据的更新并避免不必要的重算,从而大幅提高图计算的效率。在现实业务中,常见的离线任务通常针对过去一年的历史数据进行分析计算,而在每周调用离线任务计算时相比上次调用仅仅增加了一周的数据,这种场景下应用增量计算可以成功缩减计算资源。例如蚂蚁金服反洗钱团队已尝试利用PageRank算法在异构关系图中对洗钱团伙成员的重要程度进行打分排序。由于成员及资金间的关联关系在短时间内变化较小,设计针对PageRank的动态算法可显著避免全量更新PageRank数值中存在的大量冗余计算。此外在风控场景中,团伙挖掘团队根据给定的黑种子(用户)对其他相关风险团伙成员进行挖掘。其中涉及到基于HITS(Hyperlink-Induced Topic Search)算法的实时社区搜寻。这些都是适用于增量图计算的典型实例。 

在另一方面,为高效处理大规模图数据当前涌现出大量优秀的分布式图计算系统,诸如Pregel,PowerGraph,Giraph++,GiraphUC,Maiter,PrIter,Gemini等。但这些系统均假定在计算过程中图数据不会发生变化。因此如何使分布式图计算引擎具备在动态图上进行增量计算的能力也是亟待解决的问题。

虽然增量算法效率更高,但其算法设计对初学者尚有较高的门槛。同时为每类具体的图查询都从头开始设计一个增量(动态)算法难度较大。如何降低增量算法的开发难度,解锁增量计算在图计算场景的应用,并将其嵌入分布式图计算引擎是一个具有重要业务价值和值得深入研究的课题。

拟解决问题

  • 全面分析分布式图计算的编程范式,基于范式给出分布式图算法可增量化的条件及分类。
  • 设计一个分布式增量图计算框架:(a)该框架可覆盖上述可增量化的分布式图算法;(b) 用户只需在框架中实现图算法的全量计算逻辑,框架可自动推导其增量计算逻辑。
  • 研究分布式增量图计算的优化方法。在典型的图计算应用中(如PageRank、 HITS等),通过上述框架所生成的分布式增量图算法达到与算法专家手动实现的增量图算法可类比的性能。

期望交付物

对该学术合作,我方期望的交付物如下:

  • 一个支持自动增量化图计算的系统化方法或框架,可以将顺序图算法自动增量化;
  • 或者是实现了支持自动增量化图计算的分布式系统原型;
  • 在领域内国际顶会或期刊(CCF-A类)发表高质量的学术论文 1 篇。

Scan QR code
关注Ali TechnologyWechat Account