图计算及其应用.pdf

封面页（此页面将由下图全覆盖，此为编辑稿中的示意，将在终稿 PDF 版中做更新）卷首语 近年来，基于图数据的计算（图计算）得到了学术界和工业界越来越多的关注，被认为是人工智能发展的一个重要方向。本专场围绕图计算系统、应用及前沿学术研究问题，首先介绍阿里巴巴开源的一站式图计算系统 GraphScope 的设计思想、基础能力以及未来发展方向；另外，邀请来自学术界和工业界的大咖，分享图计算最前沿的学术和技术热点；同时，邀请在业务中应用图计算技术的客户，分享图计算在真实业务场景中的应用案例及效果。目录 一、图计算发展的回顾与展望.5 二、GraphScope：人人可用的一站式图计算.15 三、Graph+Insight 在关联数据中发现商业价值.32 四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用.48 五、图计算在全域数据融合场景的实践.60 一、图计算发展的回顾与展望 5 一、图计算发展的回顾与展望 摘要：本文整理自上海交通大学安泰经济与管理学院数据与商务智能系讲席教授、数据与商务智能系系主任、欧洲科学院院士、IEEE Fellow 林学民，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为四个部分：1)子图罗列 Subgraph Enumeration 2)内聚子图 Cohesive Subgraphs 3)网络弹性 Network Resilience 4)二分图 Bipartite Graph 什么是图？这个图不是我们平时说的图形或者图像，这个图是点和边。点代表事物，边表示他们之间的关系。我们最早知道图是欧拉定理和格尼斯堡七桥问题，然后翻山越岭，经过历史的长河，我们来到了本世纪初的图数据库和大图计算。一、图计算发展的回顾与展望 6 现在各行各业都需要图，比如：Web Graph，Social Network、Protein Interaction Network 等等。下图是一个图的应用场景，左边是各种各样的应用，应用可以分解出基本算子，然后基本算子再分解出最基本算子，所以做系统就要把最基本算子处理好。1.子图罗列 Subgraph Enumeration 左边 P 是模式图，中间 G 是数据图，通常模式图比较小，可能就是几个点，数据图有可能非常大。下面是从 G 中找到所有和 P 同构的子图实例的三个样例。所以能想象，在实际应用中这种映射有可能会有成千上万，甚至上亿的量。下面来分享一下子图罗列在各行各业中的应用。1)实时周期检测 下图是几年前和阿里合作的实时周期检测项目，主要用于欺诈检测和洗钱检测。一、图计算发展的回顾与展望 7 2)检测指定社区 3)单 CPU 解决方案 一、图计算发展的回顾与展望 8 4)分布式技术 在分布式技术中没有哪一个算法是最好的，需要我们根据数据分布选择适合的算法。2.内聚子图 Cohesive Subgraphs 下图是曾经和阿里合作的一个项目，目的是抓住刷单的水军。这个问题我们是怎么解决的呢？其实就是将问题转化成抓 Bi-Clique 就可以了。所谓的 Clique 就是每两个点之间都有一条边，那么如何把所有的 Clique 或者最大的 Clique 找出来呢？这里就会有一个很大的难点。因为 Clique 和 Clique 之间是可以重叠的，这样就会使数目变得非常大。一、图计算发展的回顾与展望 9 在数据库他们会做各种各样的变种，比如 Quasi-Clique，那么如何定义他们呢？比如 clique 的边数是|v|(|v|)-1，那么 Quasi-Clique 就是|v|(|v|)-1。K-Plex 在 Clique 里它的度数等于 n-1，那么 K-Plex 每个点的度数就会大于等于 n-k。一、图计算发展的回顾与展望 10 K-clique 是子图中任意两个顶点之间的距离小于等于 k，K-club 同样也是任意两个顶点之间的距离小于等于 k，但是它的两点是指子群中两点的距离。K-Core 是指子图中每个点的度数大于等于 k。这个就比较简单，比如现在这个图里找一度数最小的点，如果度数等于或者大于 k 就 finish 了。小于 k 的，我们就把它除掉，再 update 度数。K-Truss 是 K-Core 的加强版，每条边上三角形的个数要大于等于 k-2。那么为什么说 K-Truss 是加强版呢？你能想象一个 K-Truss 一定是 k-1 Core，就是度数值一定是大于等于 k-1 的。K-Truss 的算法实际上和 K-Core 的差不多。算法复杂性就是把每条边上的三角形个数全部罗列出来，这也是一个多项式算法。一、图计算发展的回顾与展望 11 子图里的度数如果大于等于 p 乘以全局的度数就叫 P-Cohesion。K-edge Connected 是指一个图里去掉任意 k 减一条边，它仍然是联通的。所以 K-edge Connected Component 就是找最大的子图。这是一个分解算法，最坏的情形是 N 的三次方。一、图计算发展的回顾与展望 12 还有一个是 K-vertex Connected Component，这个我们暂时没有找到非常快的算法。如果你们对这个话题感兴趣，可以来一起提高它的性能。3.网络弹性 Network Resilience Friendster 曾经是一家比较大的社交网站，但在 2005 年突然就 collapse 了。这到底是为什么呢，其实原因非常不好找。就比如你去了一个 party，好吃的东西和一个聊得来的人并不会让你留很久。如果想要长时间呆留在 party，就需要很多这样的人才可以。假如我是 K-Core，给你的 budget 是 b，也就是让你想办法留下 b 个人。这个 b 不用满足 K-Core 条件，那么 b 要怎么选才能让 network 最大呢？一、图计算发展的回顾与展望 13 最终我们没有找出非常快速的精确算法，所以就找了个近似算法。这个论文发表在了 VLDB 2017 上。4.二分图 Bipartite Graph 所谓的 Bipartite Graph 就是把图分成两层，上面一层，下面一层。它们都没有边只有 cross 两层。一、图计算发展的回顾与展望 14 实际上它有很多应用，比如下图最左边的就是一个非常典型的 academic 的例子，上面是演员，下面是电影。二、GraphScope：人人可用的一站式图计算 15 二、GraphScope：人人可用的一站式图计算 摘要：本文整理自达摩院的资深技术专家与图计算团队的负责人于文渊老师，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为六个部分：1)实时离线一体图计算引擎 2)全新的图交互查询/模式匹配 IR 与引擎 3)图分析引擎的全新升级 4)图学习引擎的全新升级 5)图可视化解决方案 6)用户友好型与易用性提升 目前存在各种各样的图数据类型，如上图所示：网页链接图、生物结构图、社交网络图等。二、GraphScope：人人可用的一站式图计算 16 现实中的图计算任务是非常复杂的工作流程，不是仅仅靠一个简单的算法就能实现的。如上图示例：1)欺诈检测的工作流首先要通过 ETL 抽取数据，建模以后储存管理，并进行格式转换。2)开展图挖掘获取有效信息。3)利用图学习，即机器算法寻找共性特征；第四，展开图分析，通过标签扩散；最后，交互式分析与结果可视化。但是，在真实的应用场景中问题复杂，计算模式多样，解决方案碎片化；同时用户的门槛很高，学习难度也很大；海量数据的计算复杂度高且效率低。因此，解决图计算大规模应用的挑战是我们 GraphScope 系统开发的重要目标。二、GraphScope：人人可用的一站式图计算 17 GraphScope 的构建，始于 2020 年底。两年的时间里，我们结合了阿里的海量数据场景以及以达摩院团队和业界专家学者的合作成果，将各个团队的图计算工作整合在一起，最终形成了 GraphScope 系统。具体来说，GraphScope 的基本架构如上图所示。底层现在是 Vineyard 分布式内部存储，同时支持其他类型的存储。中间层为一系列高性能图计算引擎，并且用 Python 语言把各种各样的图计算的负载串联在一起，提供了一个统一的图模型和算法库。同时本系统可以和上下游的其他生态环节打通，使用户可以在使用系统的时候，能以很低的成本同时拷贝上下游的数据。团队目标是希望 GraphScope 成为用户开发图计算应用的第一站，通过开源努力打造一个业界图计算的标准。二、GraphScope：人人可用的一站式图计算 18 1)为用户建立简单、通用、灵活的编程模型，拓展 Gremlin 和 Python。2)支持丰富的图计算任务的类型，比如说图分析、图交互式查询、图模式匹配、图学习等。3)达到业界领先的性能；第四，有一个开放、易用的 Notebook 的环境；最后，与上下游的业务做深度结合，形成一个全生命周期的一个设计。12 月开源以来，GraphScope 入库了中国科协“科创中国”平台，在今年的 OSCAR开源产业大会上得到了“尖峰开源社区和开源项目”奖。两年时间里系统积攒了2000+Github stars，上百个各种各样的图分析和学习算法库，在阿里每天大概完成近 5 万的日常任务支持。同时，系统支持复杂的图模型，单个图的规模大小在阿里内部也超过了 50TB。总体开发效率对于工程师来说也是从几周加速到几个小时的时间。关于 GraphScope 平台，用户有很多问题，如下图所示：支不支持 JAVA？是否可以把算法放进来？支持 Spark 吗？数据怎么更新？如何支持在线推理？怎么直观管理生命周期？如何编辑交互式的图查询？不用 Python 可以吗？等等。因为我们要打造的是一个人人可用的图计算系统，如果大家还有新的问题与建议，也欢迎大家多给我们一些反馈。二、GraphScope：人人可用的一站式图计算 19 1.实时离线一体图计算引擎 首先，讲一讲 GraphScope 如何实现离线一体图计算引擎。关于 GraphScope 究竟是不是图数据库，这是一个常见的问题。杭州有很多关于图数据库的创业公司，大家也很容易联系到我们是否也是图数据库。但我们不是一个图数据库，GraphScope其实是一个图计算引擎。在真实的用户场景中，用户首先有一个实时的数据源会被处理，比如说互联网的用户日志，或者说银行的用户交易。这个数据会沉淀到一个主数据库，即 OLTP 的主数据库。二、GraphScope：人人可用的一站式图计算 20 举个例子，用户从银行 ATM 机取款，这笔操作一定是一个 transaction，就是存在事务的一个数据库里。随后这个数据库里会定期周期性地同步到一个数据仓或数据库里。这些数据包括一些实时的数据，例如日志等行为：在某应用中点了一个商品、点了一个链接、看了某个帖子。日志同样会被沉淀到数据库里。那么这些分析与查询，在传统意义上都叫 OLAP 请求。那么图处理在现实中是什么呢？一些模式 learning 的计算，数据从这个端口到那个端口可能要很长时间，比如在阿里最典型的场景里可能要一天或者两天的时间。但是这样会让 freshness 下降，fresh 是新鲜度数据，意思是数据传递从这里到那里经过两天的时间，数据可能就不这么新鲜了。目前解决这个问题最好的办法是做图数据库。换言之，数据都存在数据仓库里和数据库里，如果不想经过很长的链路加载，这时候就需要图数据库，即 graph database。但是，如果数据一旦涉及双写的问题，跨系统的 ACID 即数据的一致性很难保证。因此，GraphScope 是一个图计算引擎，可以从关系数据库中实时地把一个关系数据库的表投影成一张图，而用户的增删改查还是在关系数据库里来实现。GraphScope 系统本身不处理数据的增删改查，但是它可以通过 LOG 同步的方式永远和外部数据源的图保持一致；同时支持服务化能力、交互式查询、图分析、图学习。未来，我们希望 GraphScope 的 capability，即处理计算的类型可以更加丰富，这个是我们的下一部分的工作，预计 2023 年的第一个季度可以完成正式开源，大家敬请期待。二、GraphScope：人人可用的一站式图计算 21 2.全新的图交互查询/模式匹配 IR 与引擎 很多用户关心，GraphScope 支持图模式匹配吗？为什么查询这么慢？怎么调优？在偏数据图查询的场景里，我希望做一些解答，这也是我们下一步的工作。我们第一个想解决的问题是，如何更好的支持更多的图查询语言。我们的目标是解决用户的需要，用户增加一种图查询语言，需要一百多种不同的算子。那么如果引擎把这一百多种算子各自实现一遍，基本上是无法正常运行的。二、GraphScope：人人可用的一站式图计算 22 第二，是否能支持图模式匹配？第三，如何支持更好的系统的自动查询优化，即系统自动匹配一条最优路线？最后，如何支持更多类型的图查询，是采用高查询吞吐还是并行加速？那么如何在一个系统里让交互式查询引擎支持这么多能力呢？首先，我们在关系数据库的查询算子上做了一些和图相关的扩展，发现绝大多数现有的图查询语言的语义，其实都可以用非常有限的算子来实现。因此算子的空间从几百个甚至大几百个优化精简到几十个。并且这几十个的表达能力足够强到，把所有现在最常见的查询全都覆盖掉。第二，我们需要做一层更通用的查询优化器，预计是明年的第三季度。我们认为在这层查询只有算子的组合，可以自动基于图上的特征来做查询优化。优化之后我们分为两个路径，第一个叫 High QPS，目标是让这个系统在单位时间内能处理更多的图查询。另一条链路是 data parallel 的 plan，目标是单个查询的延时尽量小。第三，我们会构建一个通用的存储，预计明年的年终完成。它可以支持动态图、静态图、内存、外存。3.图分析引擎的全新升级 那么还有一些问题怎么解决呢？二、GraphScope：人人可用的一站式图计算 23 如图所示，如何高效地开发并让用户能执行更多种多样的复杂图分析的问题，以及如何适配已经有的 JAVA 等图算法；还有如何更好的融入像 Spark 为代表的大数据的这种处理生态。这个就是我们要解决的问题。对于这些问题，我们提供 FLASH 框架。真正的图计算系统中面临的分析问题非常多样化，不一定所有都是固定点计算，一些有非常复杂的控制流。那么我们的目标其实不仅仅是要达到一个很好的性能，同时我们还要让这个开发变得简单。所以我们提出了FLASH，它不仅是让开发简单，使得大家的代码行数可以都减少了，最多的情况下减少了 92%。大概只有不到 10%的代码行数，可以最高加速两个数量级。同时，基于 FLASH 我们提供了 72 个常见的各种全新的图算法，可以直接在GraphScope 里使用。二、GraphScope：人人可用的一站式图计算 24 我们现在有很多的图引擎，尤其计算引擎。除了 GraphScope 以外，很多的生产中用的引擎是在大数据套件中使用的，但是往往性能会比较差。是否能把 Sprak 上的一些应用运行在 GraphScope 上，并充分发挥 GraphScope 的性能，将这个生态打通呢？要解决这个问题，首先要解决如图所示的一些问题。即如何在 GraphScope 上通过各种 JAR 来实现 Java 的高效运行。二、GraphScope：人人可用的一站式图计算 25 如果不考虑性能，那么 JAVA 对 C+、c 语言、原生代码的调用都翻译成了一次跨语言的调用，但这中间就会有数倍的性能的磨损。那我们能不能解决这个问题呢？其实是可以的，我们和阿里云的编译器团队做了一套开源的 Fast FFI 的解决方案，自动地把 JAVA 和 C+之间的数据类型和方法对接，生成胶水代码。可以让 JAVA 代码很容易地去调用 C+里边的代码，保证它的安全性和易用性。同时，把 C+中的代码通过 LLVM 可以直接翻译到 JVM 上的 byte code，打通了 native code 和 JAVA code 之间的屏障。通过这一系列的工作，我们的性能基本上达到 C+在 JAVA 实现的性能与 JAVA 和 C+类似的能力。二、GraphScope：人人可用的一站式图计算 26 目前的支持主要是通过两条路径，一条是 GraphScope Java SDK 实现了性能提高；另一条是 GraphScope for Giraph 降低图计算任务的运行时间。同时我们也做了 Spark 支持，核心的一点是 Spark 是现在最广泛使用的大数据处理套件。它本身自带的图计算 GraphX 非常低效，基于 GraphScope 的跨语言能力赋能 GraphX 加速。同时更好的一点是内部的存储是直接作为 RDD 被 Spark 的下游任务直接使用，而不需要把这个数据载入到一个中间文件中。所以通过整体的方案实现了和 Spark 的对接。流程图如下所示：二、GraphScope：人人可用的一站式图计算 27 达到效果 Spark 的性能提升大概是 4.8 倍，端到端的性能提升大概是两倍。其中，端到端的意思是一个数据的转换、转码和重新加载的速度。就用户体验来说，和基本的 Spark 没有区别。4.图学习引擎的全新升级 GNN 的训练框架其实越来越多，各种类型的学术界和工业界都已经开发出来了。那么它没有一个很好的支持工业界的在线推理的方式，而我们能不能利用各种各样的像 GPU 这样的新兴的硬件呢？这些答案都是肯定的。首先我们做了一个升级，增加了高吞吐的采样引擎，这部分已经进入了主分支。同时，我们也已经完成了一个动态图推理的采样服务。使得我们在 GraphScope 上开发的模型可以很容易地服务客户。二、GraphScope：人人可用的一站式图计算 28 工业级分布式 GNN 训练中的挑战主要是计算与资源利用需求不对等。模型训练是在稠密的数据集上做计算，图采样是在很稀疏的图上做计算，对内存的要求会比较高。两边的不对等使得我们 GPU 要么内存带宽，要么 GPU 的计算能力使用效率不高。通信、存储等也是同样道理。为了解决这些问题，我们使用采样训练解耦、异构硬件加速和兼容 PyG 生态。二、GraphScope：人人可用的一站式图计算 29 采样训练解耦在逻辑上把图的采样过程和图的训练过程分为两个角色来分别执行，中间用一个渠道可以让他们通信。这个渠道可以是共享内存，比如说共享显卡的内存和共享主机的内存；也可以通过网络，也可以通过高速互联网络。通过这样一个解耦的方法实现它能灵活部署、独立伸缩，同时又能利用各种部署模式，使得高并发采样和采样训练异步的能力得以实现。我们也实现了异构硬件加速。比如说 GPU 上采样的支持，通过把特征做缓存，把图结构做切分等，充分利用 GPU 间的互联的特征，加速采样过程。二、GraphScope：人人可用的一站式图计算 30 兼容 PyG 生态是指，用户可以在没有任何修改的情况下，可以直接使用 PyG 上的现有的模型。5.图可视化解决方案 这部分工作是我们和来自蚂蚁集团的 AntV 团队一起来合作完成的。比如有一张图，图数据很大，怎么把它展示出来？如何进行探索？怎么让用户能交互式地把查询给表达出来，直观地把图的整个生命周期管理起来？二、GraphScope：人人可用的一站式图计算 31 比如可以管理图，建一个图的模型，导入图，进而分析图的数据。那么想做到这样，用户需要有一个类似于整个图的 bi 工具。在整个站点中实现一个 zero code 的对接到 GraphScope 上，然后让用户来实现上述功能。然后它也支持 Gremlin 的查询，pattern 的绘制，对 pattern 进行查询，点边条件过滤，扩展节点，在这个结果上进行探查。6.用户友好性与易用性提升 最后我们希望能实现对用户的友好性和易用性的提升，关键不在于我们的技术怎么样，而在于我们怎么样才能服务好用户。三、Graph+Insight 在关联数据中发现商业价值 32 三、Graph+Insight 在关联数据中发现商业价值 摘要：本文整理自蚂蚁集团数据可视化方向负责人林志峰，在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为四个部分：1)大势所趋技术价值和趋势 2)生机勃勃应用场景和生态 3)厚积薄发这些年的工作与沉淀 4)浅知拙见落地探索和应用实践 近 些 年，图 不 管 加 什 么 都 会 成 为 一 个 大 热，比 如 Graph+Database，Graph+Computing，Graph+Knowledge，Graph+Visualization 等。我自己所在的领域里，我发现可视化顶会论坛里，超过 30%以上都是跟图相关的一些论文，这就可以说明图是一个大热的课题。1.大势所趋技术价值和趋势 在过去 20 年的数据浪潮里，我相信这张图大家都不陌生。传统中我们通过 BI 工具从数据里获取洞察，BI 就成为了一个非常常用的工具。但随着数据规模的增大，以及更多关联数据的要求，我们慢慢发现，传统的数据库并不能满足高效的查询要求。刚才提到的图数据结构，它是刻画现实世界最理想的数据特征。不管是人与人之间的关系，企业之间的往来，点对点的物流，还是整个社会上下游的衔接，都可以用图的数据结构去描述，非常准确，同时也非常高效。三、Graph+Insight 在关联数据中发现商业价值 33 如果把这些数据放到传统的关系数据库里，就会发现它会带来很多存储冗余，表达稀疏以及复杂查询，这就会变得非常缓慢，并且非常复杂。但是如果用图引擎可能非常优雅的几行代码，就能把一个三度查询表达出来。正是因为这些局限性，我们经常在图数据库圈里看到这么一句话，关系数据库里存的不是关系，而是数据。下图是一个非常经典的模型，DIKW。原始数据经过数据加工，变成一个有意义的信息。当我们把这些信息组合起来成为一个知识，并从这个知识里挖掘到一些可以用于预测未来的因果关系，我们称它为智慧。但是经过几年后，我们慢慢发现在 Knowledge 和 Wisdom 之间，有巨大的鸿沟难以跨越。三、Graph+Insight 在关联数据中发现商业价值 34 更实际的是在这个过程中，我们发现从里面找到相关性的 Insight 会带来更多实际的业务价值，所以 Graph 和 Insight 的结合会越来越被重视。下面给大家看一个更加直观的例子，怎么从图里面获得洞察？下图是两个 mock 的虚拟数据，银行卡账号和交易明细。三、Graph+Insight 在关联数据中发现商业价值 35 字有点小大家可能看不清，但哪怕你能看清里面的每一个字母和数字，都不能快速的得到洞察。下面我们尝试把它可视化出来，我相信你可以立刻得到一些关键的点，或者说有一个大概的印象。阿拉伯数字大概是在 1200 年前后出现的，中国的甲骨文数字是在公元前 1600 年，最早的楔形文字是在公元前 3000 年，而洞穴壁画在公元前 4 万年就已经出现了。换句话说，人类习惯用图形、图像去表达，比用文字和数字足足早了 4 万年。各种科学实验也验证了，人类对于图形、图像识别能力的速度和效率比文字和数字高出1-2 个数量级。所以在我看来不管人类基因怎么突变，人类依赖图形、图像去获取信息依然还是我们最主要的渠道。眼睛是我们最主要的信息获取通道，我们大脑里超过 50%的组织是用于图像图识别和获取知识的，这是从人类自身的特点去看这个趋势本身的变化。那么我们在图方向坚持做那么久，有没有可能只是我们的一厢情愿。但好在顶级经营机构的一些趋势报告验证了我们的一些判断。在跟进图分析的这些年里，它几乎在 Gartner 的趋势报告里从未缺席。2019 年提到图分析是获得复杂关系多维数据洞察的关键技术；2020 年提到关系的使用将重构整个数据和分析的价值；2021 年预测了 50%的客户会有图分析的需求；直到 2022年更激进的说分析模型将取缔现有传统数据模型。虽然说的很激进，但市场已经给出答案。三、Graph+Insight 在关联数据中发现商业价值 36 2.生机勃勃应用场景和生态 我们国内外一些公司，其实他们核心依赖的技术跟图都极其相关。不管是 Google 的搜索，还是亚马逊的产品推荐，还是 Facebook 社交网络里的广告定位。换位到国内对标的企业大家对图也是强依赖的。比如 360，会用图去发现整个软件供应链链路上，存在的全网大规模固定资产中漏洞的传播路径。天眼查、企查查会提供给付费用户一些增值服务，比如关于企业关联关系、股权结构等。三、Graph+Insight 在关联数据中发现商业价值 37 从下图中，可以归纳出图应用的核心以及主要的四个应用场景。3.厚积薄发这些年的工作与沉淀 下图是 AntV 的技术栈。纵向分成三个域，分别是常规统计数据、关系数据、地理空间数据。三、Graph+Insight 在关联数据中发现商业价值 38 今天主要是分享一下关系数据。这个栈被分为了三层，从下到上分别是引擎层 G6、组件层 Graphin、平台层 GraphInsight。这三层的关系相信从名字上就能看到它们所面向的客户和场景。同时我也很自豪地说，AntV G6 这个引擎在 2017 年 6 月 26 发布至今，在全球开源可视化项目里排名世界第二。接下来我们会继续努力，希望早一天能代表中国登顶。当然这里也离不开阿里、蚂蚁以及社区的很多同学在这个方向投入。三、Graph+Insight 在关联数据中发现商业价值 39 这是 2020 年 11 月 22 日对外发布的第一份关于图可视化解决方案的白皮书。包括6 个文档，将近 18 万字的内容，是我们联合阿里，以及社区内外三十多个设计师、产品经理、技术人员，一起书写的关于图可视化分析的一些产品案例、经验总结。我们做这件事的初衷是希望在技术不断前进的同时，还能有一些认知上的迭代，也希望这个白皮书在未来能够继续迭代。三、Graph+Insight 在关联数据中发现商业价值 40 4.浅知拙见落地探索和应用实践 在业务落地的过程中，我们发现了两个业务团队的顾虑。第一个是整个投入的成本，因为毕竟是新技术，大家对图可能很陌生，不知道画一个图在 web 上需要多大的成本，然后未来能否持续迭代。另外一个是实际效果，因为传统的统计分析是有沉淀，有惯性的。今天我们用图的方式给一个呈现，用图的方式做数据挖掘和分析，究竟用户能不能接受，并且这种分析能不能真正带给业务效果，都是它们担心的。针对这两个问题，我们慢慢摸索到，能够让业务快速进行验证，是成为新技术落地的杀手锏。不管你是数据研发的同学、数据算法的同学、还是业务的分析师，能够用最短的路径、最高效的方式让他们看到数据，摸得着，玩的起来，慢慢这件事情就有戏了。所以这里会有两个最主要的卡点。第一个是关系数据究竟如何获取？另外一个是有了数据之后我如何去分析？三、Graph+Insight 在关联数据中发现商业价值 41 接下来我们先从“关系数据如何分析？”讲起。那么就不得不提到 GraphInsight，它可以零代码完成图分析洞察的业务验证，低代码支持功能模块的持续集成。什么是零代码？怎么去完成呢？我们还是拿刚才那份假数据，包括账号和交易明细点边的结合。三、Graph+Insight 在关联数据中发现商业价值 42 我们快速的把这两份数据导到系统里面，然后做一些简单数据映射的匹配。1 分钟就可以把一个非常枯燥的表格数据变成一个图可视化。核心就是告诉 GraphInsight这份数据哪些映射到点，哪些映射到边，他们属性的配置关系。迈出了这 1 分钟这一步之后，业务人员、研发人员就可以把它当作一个工作室，配各种节点的样式，把一些更加重要的属性映射出来。改变它的布局，颜色，甚至把一些业务的语义含义在图里面表达。那么一个带着互动能力的图分析雏形就出现了。接下来 3 分钟的调参配置，自定义样式，交互，布局，让关系图栩栩如生。这一步之后，更重要的来了，怎么去分析？这份数据里有没有更深层的含义？三、Graph+Insight 在关联数据中发现商业价值 43 这个时候可以用 GraphInsight 提供的分析资产。它是把图可视分析领域里，常用的分析手段全都封装成一些能力组件。在 GraphInsight 的资产平台里，可以随便挑选那些已有的分析能力，直接挂载到自己的应用里，直接使用。这个过程大概需要 6分钟。我们再重新回顾一下整个过程。从一个 excel 表，1 分钟的时间把它变成一张可见的图，3 分钟的时间把业务语义的数据映射给上面配置出来，最后花了 6 分钟时间从里面选一些资产做进一步的分析，得出洞察力。这是 GI 提供的一个零代码数据分析和能力。三、Graph+Insight 在关联数据中发现商业价值 44 接下来说一说“关系数据如何获取？”。如果要到真实的数据里，那真实的数据就可不是一个 excel 能够承载的，它需要连接一个数据源。目前 GraphScope 跟 GI 是打通的。大家可以非常高效的在 GI 里去把 GraphScope 配置进来，这样我们就会拥有的一个强大的图计算和存储引擎在后台为我们提供服务。有了这几步简单的一些配置，我们就会拥有数据查询服务的能力。三、Graph+Insight 在关联数据中发现商业价值 45 回到 GI 的研发，要做这么一个业务系统究竟是怎么一个过程？其实很简单，只需要四步。第一步，选择一个模板。这个模板更多的只是一个布局，比如你希望未来系统是什么样子，左右布局还是上下布局。第二步，选择分析资产。默认模板会提供一些分析资产，如果你觉得这些分析资产并不是你需要的，可以直接把它删掉，加入自己需要的资产。或者可以用一个空白模板去搭出自己的业务应用。三、Graph+Insight 在关联数据中发现商业价值 46 第三步，一键 sdk 导出。这是一份带 sdk 可以二次开发的代码，换句话说它对我们平台是完全无依赖的，你可以直接放到自己的业务系统里，它就可以直接部署和上线。最后，配置自己真实的数据源。这可能是唯一需要写代码的地方。那么刚才所看到业务系统就可以跟你自己的业务系统完美的融合了。三、Graph+Insight 在关联数据中发现商业价值 47 另外当遇到一些长尾的需求，我们的核心产品并不 cover 用户的时候，我们可以在GI 里像保存一个项目一样，把分析思路所沉淀下来的东西变成了一个模板。它就类似于你在 BI 里打开一张报表，它永远存在你的空间。所以从这个角度来说，GI 其实可以理解成一个 Web 版的 BI。最后来想畅想一下未来。我们希望在未来 1-3 年，能够探索出在图方向的可视化查询。3-5 年能够成为图分析领域的数字基建、助力图业务的商业价值增长。四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 48 四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 摘要：本文整理自阿里巴巴数据中台数据资产平台的何兴盛（河竹），在云栖大会“图计算及其应用”分论坛的分享。本篇内容主要分为四个部分：1)业务场景中的“大”图 2)基于子图挖掘的设备识别解决方案 3)离线子图采样系统 Graph View 4)总结 1.业务场景中的“大”图 立足于数据中台，我们每天都需要处理超大规模的数据，当我们落地图计算时也不例外。这里的“大”图有两层含义，一是图的数量特别多，举一个典型的例子，我们每天都要从近千亿的采集日志中提取百亿级别的图，然后在规定的时间内完成分析和计算。那么在这个数据规模下，一些比较通常概念下的指标计算也变得非常棘手。另外一个是单图的规模特别大。以用户商品交互网络为例，因为网络中的实体类型特别多，用户的行为又特别丰富。对于这种类型的图，我们经常会遇到几十亿的节点上沉淀了上万亿关系的边。那么针对这两类问题我们是怎么解决的呢？四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 49 马老师曾经说过，“small is powerful”。我们的思路也很类似，都是从子图出发。对于“图的数量多”的情况，我们就需要看一下它的基本组成成分，以及是否有显著的结构特征，然后我们再设计高并发的算法。对于“图的规模大”的情况，就需要有一个良好的子图抽样系统，从一个大图中提取出我们需要的子图，然后再完成后面的分析和计算。2.基于子图挖掘的设备识别解决方案 下面我将就“图的数量多”和“图的规模大”这两类问题的典型场景展开讲述。设备标识符是移动互联网领域中非常基础，同样也非常重要的一个信息，它的本质是对一个物理设备的具体描述。然后我们才能通过设备识别服务，对用户做一些个性化推荐、用户口径统计以及广告转化中的归因分析等等。但实际上因为种种原因，整个移动互联网上有多种解决方案在市场上并行。那就会导致我们在采集日志中会对同一个物理设备采集到多个设备识别符。下面举个例子，在正常的一个采集日志中，我们通常会采集设备标识符和用户行为商品信息等等，这里我们只需要关注设备标识符。如果两个设备标识符出现在同一条日志中，我们就认为它产生了连边。如果一条采集日志中有多个设备标识符，我们就认为它是一个全连接的结构。汇总一段时间的数据，其实就可以可视化出一个结果。就是我们希望把所有属于同一台物理设备的设备标识进行聚合，满足广告外投、用户画像等下游需求。从下图中我们可以看到它包含了多个连通分量，那联通分量是有多少呢？大家可以想一想整个移动互联网领域的设备有多少，问题的规模就会有多少，它们是成正比的。四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 50 第一是设备网络显著子图挖掘：基于采集特性，设备网络世界中是否存在显著的子图模式？大簇是否存在超家族特性？第二是超大规模联通分量识别：在降本增效的大背景下，如何稳定高效支撑千亿规模的联通分量识别？第三是大簇分解问题：针对一个设备大簇，如何对其进行切割，使得分割结果准确&稳定？那么如何解决以上三个问题呢？其实它们有一个共性，就是需要子图的匹配能力。也就是在一个给定的大图里面找到与一个给定小图同构的子图。以下图为例，假设有两个需要查询的小图，和两个待查询的大图。从图中我们可以看到，T1 中包含一个 Q1，T1 包含一个 Q2。简单来说这个算法的能力就是在输出T1 包含几个 Q1 和 Q2，然后我们会记录下它的个数和实例。四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 51 针对这种问题我们自研了的基于 ODPS 的子图模式匹配算法，我们采取了一种分解再合并的算法思路。比如下图中的例子，上面是一个小图，下面是一个待查询的大图。我们首先会按照一定的模式把上方的小图分解成多个三元组，然后通过类似的方式，把下面的大图也分解成三元组。接着对小图进行合并，使它回归到原始的结构。在小图的合并过程中我们发现，下面两个节点相同，且上面两个节点不同的进行了合并，合并后可以看到们它们回归到了原始的结构中。对于大图分解后的结构，我们按照这种条件进行合并，如果合并成功了，那就说明大图中也有一个相同的实例。那么对于一些比较简单的结构，一次迭代可能就可以完成。对于一些稍微复杂的结构，通过两次迭代也几乎能够满足所有结构。下面来说下显著模式挖掘与子图匹配算法。由于采集日志中一条数据最多采集的设备 ID 类型是有限的，因此需要考虑的子图规模具有上限。对于节点规模比较小的子图，我们可以穷举出它所有的结构。对于节点=4 的 motif，一般只保留 p1-p8 这八种结构。对于 size 为 5 和 6 的 motif，仅考虑全连接结构。最终我们需要考虑的图结构也就是从 p1-p10 这十种结构。四、小图撬动大图：千亿规模用户群体网络的子图挖掘与应用 52 下图是基于某个真实业务统计的结果，首先看下链式的结构。长度为 2，节点个数为 3 的链式结构，占 p1-p10 所有结构的 7.8%；长度为 3，节点个数为 4 的链式结构占比骤降到了 1.3%；长度为 4，节点个数为 5 的链式结构占比几乎到了 0。这就可以说明整个链式结构在设备网络中是很难出现的。所以就进一步证明了，一个大簇的网络直径一旦超过 5，它就一定是有问题的，我们要对其进行拆解。接下来我们再来看一下全连接的结构。从图中我们可以看到 p3-p6 的全连接结构占比已经超过了 60%，这就说明