图计算及其应用

封面页 （此页面将由下图全覆盖，此为编辑稿中的示意，将在终稿PDF版中做更新） 阿里云开发者“藏经阁”海量电子手册免费下载 近年来，基于图数据的计算（图计算）得到了学术界和工业界越来越多的关注，被认为是人工智能发展的一个重要方向。 本专场围绕图计算系统、应用及前沿学术研究问题，首先介绍阿里巴巴开源的一站式图计算系统GraphScope的设计思想、基础能力以及未来发展方向；另外，邀请来自学术界和工业界的大咖，分享图计算最前沿的学术和技术热点；同时，邀请在业务中应用图计算技术的客户，分享图计算在真实业务场景中的应用案例及效果。 一、图计算发展的回顾与展望5 二、GraphScope：人人可用的一站式图计算15 三、Graph+Insight在关联数据中发现商业价值32 四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用48 五、图计算在全域数据融合场景的实践60 一、图计算发展的回顾与展望 摘要：本文整理自上海交通大学安泰经济与管理学院数据与商务智能系讲席教授、数据与商务智能系系主任、欧洲科学院院士、IEEEFellow林学民，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为四个部分： 1)子图罗列SubgraphEnumeration 2)内聚子图CohesiveSubgraphs 3)网络弹性NetworkResilience 4)二分图BipartiteGraph 什么是图？这个图不是我们平时说的图形或者图像，这个图是点和边。点代表事物，边表示他们之间的关系。 我们最早知道图是欧拉定理和格尼斯堡七桥问题，然后翻山越岭，经过历史的长河，我们来到了本世纪初的图数据库和大图计算。 现在各行各业都需要图，比如：WebGraph，SocialNetwork、ProteinInteractionNetwork等等。下图是一个图的应用场景，左边是各种各样的应用，应用可以分解出基本算子，然后基本算子再分解出最基本算子，所以做系统就要把最基本算子处理好。 1.子图罗列SubgraphEnumeration 左边P是模式图，中间G是数据图，通常模式图比较小，可能就是几个点，数据图有可能非常大。下面是从G中找到所有和P同构的子图实例的三个样例。所以能想象，在实际应用中这种映射有可能会有成千上万，甚至上亿的量。 下面来分享一下子图罗列在各行各业中的应用。 1)实时周期检测 下图是几年前和阿里合作的实时周期检测项目，主要用于欺诈检测和洗钱检测。 2)检测指定社区 3)单CPU解决方案 4)分布式技术 在分布式技术中没有哪一个算法是最好的，需要我们根据数据分布选择适合的算法。 2.内聚子图CohesiveSubgraphs 下图是曾经和阿里合作的一个项目，目的是抓住刷单的水军。这个问题我们是怎么 解决的呢？其实就是将问题转化成抓Bi-Clique就可以了。 所谓的Clique就是每两个点之间都有一条边，那么如何把所有的Clique或者最大的Clique找出来呢？这里就会有一个很大的难点。因为Clique和Clique之间是可以重叠的，这样就会使数目变得非常大。 在数据库他们会做各种各样的变种，比如Quasi-Clique，那么如何定义他们呢？比如clique的边数是|v|(|v|)-1，那么Quasi-Clique就是γ|v|(|v|)-1。 K-Plex在Clique里它的度数等于n-1，那么K-Plex每个点的度数就会大于等于n-k。 K-clique是子图中任意两个顶点之间的距离小于等于k，K-club同样也是任意两个 顶点之间的距离小于等于k，但是它的两点是指子群中两点的距离。 K-Core是指子图中每个点的度数大于等于k。这个就比较简单，比如现在这个图里找一度数最小的点，如果度数等于或者大于k就finish了。小于k的，我们就把它除掉，再update度数。 K-Truss是K-Core的加强版，每条边上三角形的个数要大于等于k-2。那么为什么说K-Truss是加强版呢？你能想象一个K-Truss一定是k-1Core，就是度数值一定是大于等于k-1的。 K-Truss的算法实际上和K-Core的差不多。算法复杂性就是把每条边上的三角形个数全部罗列出来，这也是一个多项式算法。 子图里的度数如果大于等于p乘以全局的度数就叫P-Cohesion。 K-edgeConnected是指一个图里去掉任意k减一条边，它仍然是联通的。所以K-edgeConnectedComponent就是找最大的子图。这是一个分解算法，最坏的情形是N的三次方。 还有一个是K-vertexConnectedComponent，这个我们暂时没有找到非常快的算 法。如果你们对这个话题感兴趣，可以来一起提高它的性能。 3.网络弹性NetworkResilience Friendster曾经是一家比较大的社交网站，但在2005年突然就collapse了。这到 底是为什么呢，其实原因非常不好找。 就比如你去了一个party，好吃的东西和一个聊得来的人并不会让你留很久。如果想要长时间呆留在party，就需要很多这样的人才可以。 假如我是K-Core，给你的budget是b，也就是让你想办法留下b个人。这个b不用满足K-Core条件，那么b要怎么选才能让network最大呢？ 最终我们没有找出非常快速的精确算法，所以就找了个近似算法。这个论文发表在了VLDB2017上。 4.二分图BipartiteGraph 所谓的BipartiteGraph就是把图分成两层，上面一层，下面一层。它们都没有边只有cross两层。 实际上它有很多应用，比如下图最左边的就是一个非常典型的academic的例子，上面是演员，下面是电影。 二、GraphScope：人人可用的一站式图计算 摘要：本文整理自达摩院的资深技术专家与图计算团队的负责人于文渊老师，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为六个部分： 1)实时离线一体图计算引擎 2)全新的图交互查询/模式匹配IR与引擎 3)图分析引擎的全新升级 4)图学习引擎的全新升级 5)图可视化解决方案 6)用户友好型与易用性提升 目前存在各种各样的图数据类型，如上图所示：网页链接图、生物结构图、社交网络图等。 现实中的图计算任务是非常复杂的工作流程，不是仅仅靠一个简单的算法就能实现的。如上图示例： 1)欺诈检测的工作流首先要通过ETL抽取数据，建模以后储存管理，并进行格式转换。 2)开展图挖掘获取有效信息。 3)利用图学习，即机器算法寻找共性特征；第四，展开图分析，通过标签扩散；最后，交互式分析与结果可视化。 但是，在真实的应用场景中问题复杂，计算模式多样，解决方案碎片化；同时用户的门槛很高，学习难度也很大；海量数据的计算复杂度高且效率低。因此，解决图计算大规模应用的挑战是我们GraphScope系统开发的重要目标。 GraphScope的构建，始于2020年底。两年的时间里，我们结合了阿里的海量数据场景以及以达摩院团队和业界专家学者的合作成果，将各个团队的图计算工作整合在一起，最终形成了GraphScope系统。 具体来说，GraphScope的基本架构如上图所示。 底层现在是Vineyard分布式内部存储，同时支持其他类型的存储。中间层为一系列高性能图计算引擎，并且用Python语言把各种各样的图计算的负载串联在一起，提供了一个统一的图模型和算法库。同时本系统可以和上下游的其他生态环节打通，使用户可以在使用系统的时候，能以很低的成本同时拷贝上下游的数据。 团队目标是希望GraphScope成为用户开发图计算应用的第一站，通过开源努力打造一个业界图计算的标准。 1)为用户建立简单、通用、灵活的编程模型，拓展Gremlin和Python。 2)支持丰富的图计算任务的类型，比如说图分析、图交互式查询、图模式匹配、图学习等。 3)达到业界领先的性能；第四，有一个开放、易用的Notebook的环境；最后，与上下游的业务做深度结合，形成一个全生命周期的一个设计。 12月开源以来，GraphScope入库了中国科协“科创中国”平台，在今年的OSCAR开源产业大会上得到了“尖峰开源社区和开源项目”奖。两年时间里系统积攒了2000+Githubstars，上百个各种各样的图分析和学习算法库，在阿里每天大概完成 近5万的日常任务支持。同时，系统支持复杂的图模型，单个图的规模大小在阿里内部也超过了50TB。总体开发效率对于工程师来说也是从几周加速到几个小时的时间。 关于GraphScope平台，用户有很多问题，如下图所示：支不支持JAVA？是否可以把算法放进来？支持Spark吗？数据怎么更新？如何支持在线推理？怎么直观管理生命周期？如何编辑交互式的图查询？不用Python可以吗？等等。 因为我们要打造的是一个人人可用的图计算系统，如果大家还有新的问题与建议，也欢迎大家多给我们一些反馈。 1.实时离线一体图计算引擎 首先，讲一讲GraphScope如何实现离线一体图计算引擎。关于GraphScope究竟是不是图数据库，这是一个常见的问题。杭州有很多关于图数据库的创业公司，大家也很容易联系到我们是否也是图数据库。但我们不是一个图数据库，GraphScope其实是一个图计算引擎。 在真实的用户场景中，用户首先有一个实时的数据源会被处理，比如说互联网的用户日志，或者说银行的用户交易。这个数据会沉淀到一个主数据库，即OLTP的主数据库。 举个例子，用户从银行ATM机取款，这笔操作一定是一个transaction，就是存在事务的一个数据库里。随后这个数据库里会定期周期性地同步到一个数据仓或数据库里。这些数据包括一些实时的数据，例如日志等行为：在某应用中点了一个商品、点了一个链接、看了某个帖子。日志同样会被沉淀到数据库里。那么这些分析与查询，在传统意义上都叫OLAP请求。 那么图处理在现实中是什么呢？一些模式learning的计算，数据从这个端口到那个端口可能要很长时间，比如在阿里最典型的场景里可能要一天或者两天的时间。但是这样会让freshness下降，fresh是新鲜度数据，意思是数据传递从这里到那里经过两天的时间，数据可能就不这么新鲜了。 目前解决这个问题最好的办法是做图数据库。换言之，数据都存在数据仓库里和数据库里，如果不想经过很长的链路加载，这时候就需要图数据库，即graphdatabase。但是，如果数据一旦涉及双写的问题，跨系统的ACID即数据的一致性很难保证。 因此，GraphScope是一个图计算引擎，可以从关系数据库中实时地把一个关系数据库的表投影成一张图，而用户的增删改查还是在关系数据库里来实现。GraphScope系统本身不处理数据的增删改查，但是它可以通过LOG同步的方式永远和外部数据源的图保持一致；同时支持服务化能力、交互式查询、图分析、图学习。 未来，我们希望GraphScope的capability，即处理计算的类型可以更加丰富，这个是我们的下一部分的工作，预计2023年的第一个季度可以完成正式开源，大家敬请期待。 2.全新的图交互查询/模式匹配IR与引擎 很多用户关心，GraphScope支持图模式匹配吗？为什么查询这么慢？怎么调优？在偏数据图查询的场景里，我希望做一些解答，这也是我们下一步的工作。 我们第一个想解决的问题是，如何更好的支持更多的图查询语言。我们的目标是解决用户的需要，用户增加一种图查询语言，需要一百多种不同的算子。那么如果引擎把这一百多种算子各自实现一遍，基本上是无法正常运行的。 第二，是否能支持图模式匹配？第三，如何支持更好的系统的自动查询优化，即系统自动匹配一条最优路线？最后，如何支持更多类型的图查询，是采用高查询吞吐还是并行加速？ 那么如何在一个系统里让交互式查询引擎支持这么多能力呢？ 首先，我们在关