图计算

出自 MBA智库百科(https://wiki.mbalib.com/)

图计算（Graph Processing）

　　图计算（Graph Processing）是一类在实际应用中非常常见的计算类型。许多大数据都是以大规模图或网络的形式呈现，如社交网络、传染病传播途径、交通事故对路网的影响许多非图结构的大数据，也常常会被转换为图模型后进行分析。图数据结构很好地表达了数据之间的关联性。要处理规模巨大的图数据，传统的单机处理方式已经无力处理，必须采用大规模机器集群构成的并行数据库^[1]。。

　　图计算，简而言之就是将数据按照图的方式建模，以获得用扁平化的视角很难得到的结果，更适合海量数据的数字化时代。目前，包括华为、蚂蚁、AWS等公有云、数据库领域的巨头，都在大步推进图计算的商业化与应用场景探索。最近一段时间，一级市场也掀起了一股图计算的创业与投资热潮，冒出了Ultipa、创邻科技等多家创业企业。

　　2022世界人工智能大会论坛上，世界“最快”的图数据库TuGraph宣布开源。据悉，TuGraph由蚂蚁集团和清华大学共同研发，是图数据库权威测试世界纪录保持者，也是世界上有测试纪录的“最快”图数据库。开源技术指导委员会也同时成立，以共同建设图数据库应用生态。

　　蚂蚁集团图数据库负责人洪春涛介绍，这是一套分布式图数据库系统，可以支持万亿级边上的实时查询。此次开源的TuGraph单机版，具备完备的图数据库基础功能和成熟的产品设计，“相较于市场上常见的开源产品，TuGraph单机版的性能高10倍以上”。因此，它可以轻松支持TB级别数据和百亿级别大图，足以满足大多数业务场景需求。随着TuGraph的开源，开发者可以聚焦应用层，打造属于自己的图数据，从而提升行业整体技术应用水平^[2]。

　　相关基础知识：GAS 编程模型、BSP 模型、节点为中心编程模型、计算范型。

　　业界常见框架：Pregel、GraphChi、Spark GraphX、PowerGrah、Apache Giraph、Apache Hama。

　　伴随着元宇宙、人工智能、云计算、大数据等前沿科技的兴起，支撑这类概念的一系列“黑科技”也正在加速布局，图计算正是其中之一。

　　图计算这项技术在学术理论发展史上可追溯至18世纪，发展至今已然成为支撑未来科技发展不可缺席的技术力量。进入21世纪，随着大数据、元宇宙、人工智能等前沿科技的兴起和迅速发展，图计算在多个领域广泛应用。

　　与此同时，与之相关的学术科研、相关产业布局、资本赛道等方方面面热度均在提升，“黑科技”的神秘面纱正逐渐被揭开。

　　某种意义上来说，图计算并不算是新近建立的学科理论。图计算可以溯源至18世纪，学术界普遍认为，著名数学家欧拉对哥尼斯堡七桥问题的研究是这项技术的起源。

　　七桥问题是一道颇具趣味性的数学题，即如何能够在不走重复路的情况下，走遍哥尼斯堡一个公园里连接4块陆地的7座桥，形式上与益智小游戏中的一笔画游戏类似。数学家欧拉在解决这个问题的同时，将其发展成为数学中的图论。

　　其后，图计算在图论的理论基础上发展延伸。在图论中，图被定义为一个由“顶点”和“边”组成的多元组，若干顶点由边连接，表达之间的关联和交互，形成“图”。在数据视域下，将数据按照图的方式建模，以此来表达问题并予以解决的过程即为图计算。

　　“以图之名，链接万物。”研究机构CB Insights中国以此概括图计算的应用前景。据其近期发布的《2022中国图计算技术及应用发展研究报告》中信息显示，近年来图计算学术研究领域发展迅速，从2014年到2021年间，图计算领域论文数量呈现翻倍增长趋势，其中以中美两国学者为首。

　　清华大学、北京大学、中国科学院以及华中科技大学等高校及研究机构是国内的图计算领域研究主力，主要研究领域涵盖了图数据、操作系统、人工智能、大数据、分布式系统等多个方向。

　　科研学术力量的重点聚焦促进了图计算在产业市场层面的落地，如今国内已悄然形成巨头与垂直企业并进的市场格局。具体布局此类业务的企业中，蚂蚁、阿里、腾讯等互联网巨头，以及海致星图、欧拉智能等头部垂直初创企业，成为这两种不同类型市场参与者的典型代表。

　　“小到社交圈，大到元宇宙”，图计算一度成为各种科技论坛的热议话题，公众对其在应用层面的价值尤为关注，目前图计算的应用主要集中在金融、能源、政企、社交网络、搜索引擎、推荐系统等方面。

　　国内的新冠肺炎疫情防控工作中，各地卫健委通过大数据手段对部分病例、密接者活动轨迹进行精确追踪和分析最为公众所熟知，这其中也使用了图计算技术。

　　图计算技术在此项应用中，能够直观展示出相关人员的地理位置、活动轨迹等相关情况的数据。各个实体相当于图计算理论中的“点”，其相互之间的传播关系、关联关系，可以利用“图”的手段呈现出来，疫情的传播路径也在这一基础上得到准确绘制。

　　2020年的武汉疫情防控中，图计算技术被应用到大数据平台中，海致研发的知识图谱和数据中台为当地群体流调提供了便利。

　　海致集团总裁杨娟告诉《中国经济周刊》记者：“防疫科技人员可以在图之上进行计算、分析和挖掘，包括关系的发现、群体的识别、个体的更高维度分析、事件的传导和隐性知识的推理，帮助用户实现最快、最准、最全关系挖掘，以及知识推理、事件溯源。”

　　在元宇宙、人工智能等前沿科技成为科技领域热点的背景下，图计算技术在这些领域中的综合应用也成为学术讨论中的焦点。

　　“元宇宙的落地，有着不同的阶段和不同的路径，现在正在进行的是物理世界的数智化，图计算在其中发挥重要作用。”杨娟说，“在这个过程中，我们把万事万物，包括房屋、设备、人员、手机账户、车流、物流、行业知识融汇在一起做知识的提取和构建，形成能够映射真实物理世界的图谱，这些图谱之间相互交织连接在一起，在上面涌现出各种各样的业务场景、产业场景、生活场景、文旅场景、金融场景、政府场景等，从而将物理世界数字化和智能化。”

　　“图计算在元宇宙中的另一重要应用体现在数字人这一关键单元上。”杨娟说，“数字人是元宇宙中基础的交互单元，近年来数字人在视觉与语音、形象模拟、动作捕捉、场景渲染等方面的技术发展迅猛，但是数字人的互动、认知相关的部分，则仍然处于较为早期的阶段，很大程度上取决于我们能不能构建出足够丰富、足够延展、足够准确关联的超大规模知识图谱，让数字人真正拥有智慧和灵魂。”

　　中国工程院院士、清华大学计算机科学与技术系教授、海致科技首席科学家郑纬民在谈到人工智能的发展时表示，图计算是人工智能应用中认知智能的基石，“过去大数据处理都用SPARK，但是SPARK这个软件机损比较慢，还费内存，用图计算办法来处理复杂的问题，处理速度会比较快”。

　　郑纬民认为，更大规模、更复杂的数据实时进行计算是图计算的技术优势，高性能图计算是人工智能的核心。“图计算规模不断增长，比如说我们用导航的道路图很大，社交网络更大，Web图也很大，人的脑子更大，这都可以用图计算来解决问题。”

　　资本涌入“赛道”，图计算领域需要实质性的突破

　　“突破全内存高速数据引擎、高可靠数据存储引擎、分布式数据处理与任务调度架构、大规模并行图数据处理等关键技术，推动高性能数据库在金融、电信、能源等重点行业关键业务系统应用。”2021年11月，工信部发布了《“十四五”软件和信息技术服务业发展规划》，指示在数据库领域，应关注大规模并行图数据处理等数据库关键技术的突破。

　　政策的引导下，图计算在行业中的布局动作也吸引了资本的关注。

　　公开数据显示，2021年6月，国际知名的图数据库公司Neo4j完成由Eurazeo 领投、GV（原 Google Ventures）参投的 3.25亿美元F轮股权融资，创下图数据库与图计算赛道的最大单笔股权融资纪录。此次“破纪录”的投资事件引发业界一片热议。

　　视线转回国内，资本对图计算领域追捧与国外相比不遑多让。据CB insights中国观察，近3年中，国内图计算企业融资主要集中在pre-A至C轮，参与的投资方包括腾讯、高瓴创投、红点创投等多家机构，单笔投资额集中在数千万至数亿元左右。

　　据不完全信息显示，今年以来，国内图计算领域多家垂直企业获得大额融资。其中，年初海致科技完成超过5亿元的D轮融资，该轮融资由中国互联网投资基金领投，上海人工智能产业投资基金、高瓴创投、君联资本、微村智科、一村资本、亿宸资本、禾其资本跟投；2月，欧拉认知获GFC、启迪之星、方信资本数千万元人民币Pre-A轮融资；5月，渊亭科技获得达晨财智亿元人民币B轮融资。

　　“赛道”已然形成，如何在图计算领域实现真正的突破？

　　郑纬民著文分析，首先要坚持走自主创新之路，确保每一行代码都是安全可靠的；同时，政府部门的产业、税收政策和资金支持，要和社会资金、人力资源的投入共同发力，形成百花齐放春满园的局面；再者，要坚持应用拉动与创新驱动并重，走产学研结合的协同创新之路。通过应用引导学术研究的方向，确保科研成果快速转化为生产力；通过创新驱动完成技术的预研储备，培育并形成新的市场发展方向，确保技术的引领性和产品的竞争力。

　　网页排序

　　将网页作为顶点，网页之间的超链接作为边，整个互联网可以建模成一个非常巨大的图（十万亿级边）。搜索引擎在返回结果时，除了需要考虑网页内容与关键词的相关程度，还需要考虑网页本身的质量。

　　PageRank是最早Google用于对网页进行排序的算法，通过将链接看成投票来指示网页的重要程度。PageRank的计算过程并不复杂：在首轮迭代开始前，所有顶点将自己的PageRank值设为1；每轮迭代中，每个顶点向所有邻居贡献自己当前PageRank值除以出边数作为投票，然后将收到的所有来自邻居的投票累加起来作为新的PageRank值；如此往复，直到所有顶点的PageRank值在相邻两轮之间的变化达到某个阈值为止。

　　社区发现

　　社交网络也是一种典型的图数据：顶点表示人，边表示人际关系；更广义的社交网络可以将与人有关的实体也纳入进来，例如手机、地址、公司等。社区发现是社交网络分析的一个经典应用：将图分成若干社区，每个社区内部的顶点之间具有相比社区外部更紧密的连接关系。社区发现有非常广泛的用途，在金融风控、国家安全、公共卫生等大量场景都有相关的应用。

　　标签传播是一种常用的社区发现算法：每个顶点的标签即为自己的社区，初始化时设置自己的顶点编号；在随后的每一轮迭代中，每个顶点将邻居中出现最频繁的标签设置为自己新的标签；当所有顶点相邻两轮之间的标签变化少于某个阈值时则停止迭代。

　　最短路径

　　在图上发现顶点与顶点之间的最短路径是一类很常见的图计算任务，根据起始顶点与目标顶点集合的大小，又可分为单对单（一个顶点到一个顶点）、多对多（多个顶点到多个顶点）、单源（一个顶点到所有其它顶点）、多源（多个顶点到所有其它顶点）、所有点对（所有顶点到其它所有顶点）等。对于无权图，通常使用基于BFS的算法；对于有权图，比较常见的有SPFA算法、Bellman-Ford算法等。

　　最短路径的用途十分广泛：在知识图谱中经常需要寻找两个实体之间的最短关联路径；基于黑名单和实体之间的关联可以发现其它顶点与黑名单之间的距离；而所有点对的最短路径可以帮助衡量各个顶点在整个图的拓扑结构所处的位置（中心程度）。

　　如：利用图计算在微信支付负责风控和异常识别，通过图算法和关系网络识别资金异常行为，保障微信支付用户的资金安全^[4]。

• 流式计算
• 即席分析