1.2.2 图计算概述

图计算是在计算机科学发展后才开始伴随图论的发展而发展的，我们可以简单地把图计算发展史按时间线串联起来：

❑ 二战期间，盟军（特别是英军）开始大规模使用运筹学（Operational Research）技术来优化兵力、武器、战备物资等战争资源的投入，其中大量的路径规划、最优解问题皆是通过人工以及借助简单的工具演算出来的。

❑ 二战中后期，第一代计算机的出现使计算效率倍增。

❑ 20世纪50年代至70年代，随着大型机与小型机的出现，图算法开始大量出现，涉及的领域相当广泛。

➢ 染色问题（四色地图染色问题通过计算机暴力计算得以证明）。

➢ 寻路问题：最短路径、七桥问题、最小生成树等。

➢ 网络最大流与最小割问题等。

➢ 组合数学中的覆盖问题、线性规划问题等（地图上色问题实际上也可以看作用组合数学去解决的一类特殊问题）。

➢ 图分解问题：例如把一个无向图分解为最小的森林或生成树问题，被称为荫度（Arboricity）。

➢ 计算几何中的可见性问题：例如知名的博物馆问题（Art Gallery Problem或Museum Problem）—最少需要多少守卫可以完全覆盖全博物馆的安保监视。

❑ 1980至2010年，随着个人计算机的出现，并且进入摩尔定律的黄金发展阶段，底层硬件的算力快速提升，数据处理能力（广度与深度）的提升带动了图算法的研究与发展，我们今天已知的超过100种算法的原始论文大多数都是在这一时期发表的。当然，这段时间的后半程也伴随着互联网架构的出现，它彻底颠覆了小型机时代的架构，分布式系统、分布式计算、图计算框架开始出现—它们的目的是用较低的成本处理较大量的数据，最为人熟知的是由Yahoo！在2006年开源的Hadoop项目，其设计之初的灵感来自谷歌2003～2004年间发表的两篇分别涉及分布式系统计算与存储逻辑设计的论文（MapReduce+GFS）。而谷歌基于这种分布式逻辑构建的大规模图计算系统Pregel所服务的最早也是最重要的图算法就是PageRank（一般直译为网页排序，实际上Page是双关指代，也指其作者Larry Page，他是谷歌的两位创始人之一），这可以看作互联网架构中最核心的算法。

❑ 2010年前后至今，在这一时期内，云计算与大数据两大热点先后出现，直接带动了全球IT行业发展方向的调整，这其中最主要的特点有两个：一是（软件）开源项目大行其道。几乎所有云计算与大数据项目中的主要模块都是由开源软件构成的，从操作系统到中间件再到上层的可视化管理组件，鲜有例外。二是硬件架构的COTS特点，即Commercial Off-The-Shelf，中文指非定制化的商业现货服务器与工作站。通过分布式架构，很多场景中做到了用数量越来越庞大但单机价格低廉的COTS设备实现对海量用户与数据的服务和处理。而实际上，这两个特点对于图计算而言并不能做到通吃—这和图算法的特点各不相同有关，有的算法非常浅层，有的则要求穿透得很深。浅层的系统适合用大规模、水平分布式架构来处理，而深层的系统应用集中式架构来处理。所谓物尽其用，如果不加甄别地试图用一套（单调的）底层硬件来解决全部问题，显然是幼稚的。而事实上，类似荒谬的事情每一天都在重演，这也可以解释为什么有那么多客户刚做完一个项目就需要开启新的替代项目，反反复复，不可谓不浪费资源。贯穿本书始终，我们会为读者详细分析每一种算法的特点以及它所适用的架构支撑逻辑。

读者对于（计算机）算法应该并不陌生，所谓算法指的是包含有限步骤的可以被计算机执行并解决某个（类）问题的一系列指令。图算法可以被看作算法的子集，所有的图算法或多或少都与图论或图计算在逻辑上有相关性。从循序渐进的角度看，我们先来了解一下图计算所关注的要点：图计算到底要算什么、输入是什么、输出是什么、怎么算。

（1）算什么

前文中提到的图算法能解决的问题相当广泛，如寻路、最短路径、染色、最优解发现、最大流、最小割集、统筹规划等都是典型的要算什么。这些问题都可以经过指令步骤、参数等的调整来适应改变的需求，如寻找最长路径、最短路径、全部路径、时序路径、转账环路、洗钱路径、违规风险操作路径等。

（2）输入是什么

图计算的输入数据可以非常简单，比如可以是单纯的点与边的罗列。在最极端的情况下，只含有点的数据集合所表达的就是表数据—每个顶点就是表中的一行。复杂的图数据则可能融合了多个系统、多张表、多个表字段的数据，并且这些数据可以进入不同的图数据集中，形成一个多图集（Multiple Graph Set）的复杂图数据。显然，复杂图数据处理起来的复杂度相对偏高，但好处是能避免因将所有数据混为一谈而带来的数据治理、数据处理的灾难。

（3）输出是什么

一言以蔽之，图计算的输出结果更加高维。因为它可能在一个查询或算法执行后返回一系列的结果及动作，例如返回顶点（实体）、边（关系）、路径、子图（子网），并且对输入数据集进行回写操作（在数据库层面就是库更新操作，可能会改写某些点与边的属性、图集的属性等），返回多个文件，同时向一些数据接口流式返回结果等。

（4）怎么算

图计算怎么算是一个宏大的课题，本书的主要内容都与此相关。如果用最精简的文字来描述，笔者倾向于梳理为如下几条线索：

❑ 面向元数据（Metadata）的操作。具体指针对某个或某类点、边或其属性的读写操作，以及各种函数运算，包含但不限于聚合类型运算。

❑ 面向高维数据的操作。任何高维数据都会最终拆解为低维（元）数据，这本身就让针对高维数据的计算变得更为复杂。高维数据操作主要分为邻居计算、路径计算、组网计算等，从数据遍历方式上则可归纳为广度优先、深度优先、广深结合和模板组合四大类方式，其中的模板组合方式可以看作通过定义具体执行的步骤与点、边过滤逻辑来实现智能化的遍历，这种方式也是图计算被称作图增强智能的重要体现。

图计算通常并不单独存在，它需要与其他系统组件协同工作，如图存储、图查询语言、图查询与分析调用接口、多语言驱动等。毕竟，单纯的图计算可能仅仅是一个图算法的具体实现，而在工业界应用中，会把图算法封装到一整套工具箱中来实现开箱可算、赋能业务的目的。有兴趣的读者可以关注笔者的《图数据库原理、架构与应用》一书，其中有对以上问题的详细解答。

做了以上的概念澄清与梳理后，相信读者对于图计算为数据关联而生的论述（图1-13）应该不陌生了。

为了表述上的简洁，本书中我们将图计算视为图数据库（Graph Database）的主要功能，但在具体的应用场景中，我们依然有必要明确图计算与图数据库之间的异同。学术界所指的图计算与工业界所指的图数据库（或图计算）之间存在明显的差异，而这种差异如果不加甄别会对具体应用场景的处理效果产生巨大影响。图计算与图数据库之间的差异是很多刚接触图的人不容易厘清的。尽管在很多情况下，图计算可以和图数据库混用、通用，但是它们之间存在着很多的不同。

图计算可以简单地等同于图处理框架（Graph Processing Framework）、图计算引擎（Graph Computing Engine），它的主要工作是对已有的数据进行计算和分析。图计算框架多数都出自学术界，这与图论和计算机学科自20世纪60年代以来的学科交叉并一直在不断演化有关。图计算框架在过去20年的主要发展趋势是在OLAP（OnLine Analytical Processing，联机分析处理）场景中进行数据批处理。

图数据库的出现要晚得多，最早可以称为图数据库的，也要追溯到20世纪90年代了，而真正的属性图或原生图技术在2011年后才出现。图数据库的框架主要可以分为三大部分：存储、计算与面向应用的服务（如数据分析、决策方案提供、预测等）。其中计算的部分包含图计算，但图数据库通常可以处理AP（分析处理）与TP（事务处理）类操作，也就是说可以兼顾OLAP与OLTP（两者的结合也衍生出了新型HTAP类型的图数据库，后面的章节中会详细介绍其原理）。如果非常粗略地总结，从功能角度看，图数据库是图计算的超集。

图计算与图数据库还有个重要的差异点：图计算通常只关注和处理静态的数据，而图数据库则必须能处理动态的数据。换言之，在保证数据动态变化的同时，还要保证数据的一致性，并满足业务需求。这两者的区别基本上也是AP和TP类型操作的区别之所在。

静态与动态数据的区别有它们各自的历史成因，多数图计算框架都源自学术界，其关注的要点和场景与工业界的图数据库有很大的不同。前者在创建之初，很多都是面向静态的磁盘文件，通过预处理、加载进磁盘或内存后处理；而对于后者，特别是在金融、通信、物联网等场景中，数据是不断流动、频繁更新的，静态的计算框架不可能满足各类业务场景的诉求。这也催化了图数据库的不断迭代，从OLAP为主的场景开始，直至发展到可以实现OLTP类型实时、动态数据的处理。

另外，图计算框架所解决的问题和面对的数据集出于历史原因，通常都是一些路网数据、社交网络数据。尤其是社交网络中的关系类型非常简单（如关注），任意两个用户间只存在1条边，这种图也称为简单图或单边图。而在金融交易网络中，两个账户之间的转账关系可以形成非常多的边（每一条边代表一笔交易），这种图我们称为多边图（Multi Graph）。显然，用单边图来表达多边图会造成信息缺失，或者需要通过增加大量的点、边来实现同样的效果（得不偿失，且会造成图处理效率的低下）。

再者，在图计算框架中一般只关注图本身的拓扑结构，并不需要理会图上点、边复杂的属性问题。而这对于图数据库而言则是必须关注的，例如，很多查询、分析与算法逻辑都需要面向点、边及各自的属性字段进行过滤和剪枝等操作。

表1-1罗列了图计算与图数据库（可以看作两条技术路线、两个阵营）之间的差异。

最后，图计算与图数据库还有以下两个差异：

1）图计算框架中能提供的算法一般而言都比较简单，换言之，图中的处理深度都比较浅层，如PageRank（网页排序）、LPA（Label Propagation Algorithm，标签传播算法）、连通分量、三角形计数等。图计算框架可能会面向海量的数据，并且在高度分布式的集群框架之上运行，但是每个算法的复杂度并不高。图数据库所面对的查询复杂度、算法丰富度远超图计算框架，例如5层以上的深度路径查询、k邻查询、复杂的随机游走算法、大图上的鲁汶社区识别、图嵌入算法、复杂业务逻辑的实现与支持等。

2）图计算框架的运行接口通常是API调用，而图数据库则需要提供更丰富的编程接口，例如API、各种语言的SDK、可视化的图数据库管理及操作界面，以及最为重要的图查询语言。熟悉关系型数据库的读者一定不会对SQL感到陌生，而图数据库对应的查询语言是GQL，通过GQL可以实现复杂的查询、计算、算法调用和业务逻辑。

显然，从图计算到图数据库几乎等同于从学术界的发表论文向工业界实战的转换过程，前者更注重实验数据是否能服务于论文结果或者结论与推导过程是否逻辑自洽，而后者则更注重工程性、系统稳定性、时效性、用户体验等维度的挑战。

以图算法为例，绝大多数图算法都源自学术界的论文，然而这些原始算法大多数都是在极小的数据集上进行实验的，例如只有几十个或几千个点、边的超小规模图集，但是一旦在真实的工业界场景中使用，面对万倍甚至百万倍于实验室级别的数据，算法本身通常需要大幅改造，例如：

❑ 改造为可以并行（多线程）执行，以提升运行时效性。

❑ 改造为可以支持大规模分布式系统（目标同上）。

❑ 通过近似计算等算法改造来降低算法复杂度（目标同上）。

此外，很多源自学术界的算法在设计之初并没有考虑到一些具体应用场景，如LPA，原先只能传播一个标签，而具体落地的场景中可能会要求多个标签传播，最后按照最终传播概率为每个顶点保留多个标签并进行排序，这个时候就需要算法改造。

算法并不是一成不变的，它是有生命周期的，是可以不断迭代的，正如同图论一样，作为一门学科，它也在不断地发展。

---

[1] 在没有特殊说明的情况下，本书log函数默认以2为底。