图计算技术与标准化进展

近年来，随着互联网及移动互联网的发展，大量的数据从社交网络、在线服务、物联网应用等中产生出来。同时，随着传统行业向数字化转型，更多的数据也主动或者被动地被生产出来。传统上，数据在数据库中存储和处理，其中数据库又以关系型数据库为主，以表的方式来对数据之间的关系进行表征和分析。但实际上，在社交网络、金融应用里面，大量的数据是以“图”的方式，而非表的方式自然关联起来的，我们称之为关联关系数据。相比于关系模型计算模式，基于图模型的图计算是表示和处理关联关系数据的更优方式，因其在海量数据挖掘、复杂关联分析、实时查询等方面具有更好的性能和处理复杂事务的优势而得到了快速的发展，被广泛应用于金融、能源、电信和公共医疗等领域。

作者简介：
郭智慧，蚂蚁集团标准化专家，主要从事图计算、知识图谱、数据库、密码、云原生等领域的标准化工作，目前在牵头《大数据图数据库系统技术要求》国家标准制定，现任LDBC FinBench基准工作组主席等职务。
彭晋，蚂蚁集团技术标准总监，主要从事信息技术、信息安全、计算机网络等领域的标准化工作，现任全国信标委（TC28）委员、中国通信标准化协会（CCSA）理事、中国互联网金融协会网络与信息安全专委会委员等职务。

图计算概述

图计算定义

图（Graph）是一种非常直观的描述现实的结构，其基本构成包含三部分：顶点、顶点之间的关系、附加在顶点或关系上面的属性。顶点通过标签可以划分成不同类型，关系通过类型和方向进行标识，属性用于对顶点或关系的详情进行描述。

这里所说的图不同于通常所说的图形（Graphic），而是基于图论的一种数据结构，在现实世界中，很多数据都可以用图结构表示。图数据具有灵活性以及抽象性，可以很好地表述这些实体之间的关联关系。图计算（graph processing 或 graph computing）便是以图作为数据模型来研究客观世界当中事物与事物之间的关系，并对其进行完整地刻画、计算和分析的一门处理技术。

图1 图数据结构示意

图数据存在于我们生活的方方面面，如果将数据相关方分别定位为一个点，而他们之间的互相联系抽象为边，那不同事物之间的错综复杂的联系就构成了一幅幅“图数据”。图计算基于图数据模型，使用点边来表示、存储、处理数据，拥有灵活的数据抽象能力，能够更好地表达出“关系”的概念。

狭义的图计算是指对图数据进行计算和分析，可以简单等同于与图分析引擎或图处理框架。广义的图计算包括图数据的建模，图数据的存储、查询与管理（对应图数据库），图数据的计算与分析，以及基于图数据的应用与表示（知识图谱可以认为是图计算的拓展应用）等，本文描述的对象是广义的图计算。

图计算应用

相比于传统关系模型计算模式，图计算因其在海量数据挖掘、复杂关联分析、实时查询等方面具有较大的优势，被广泛应用于众多行业领域场景。包括：

金融领域，如金融风控、反洗钱等；

能源领域，如电网设备管理、电力故障分析等；

通信领域，如通信设备管理，通信设备运维等；

公共医疗领域，如健康医疗管理，智能诊断等；

生命科学领域，如研究分子活动路径，蛋白质之间作用等；

互联网领域，如个性化推挤、社交网络分析等；

网络安全领域，如安全事件分析、欺诈检测等；

科学计算领域，如空间几何，超大型仿真等；

知识计算领域，如知识图谱。

图计算相关技术

图模型

图模型（Graph Model）是图数据库表达图数据的抽象模型。目前图计算采用的图模型主要包括资源描述框架（Resource Description Framework, RDF）和属性图（Property Graph）两种。

RDF

RDF 全称为资源描述框架，是由万维网联盟（World Wide Web Consortium, W3C）提出的一组标记语言规范技术，基于 XML 语法及 XML Schema 的数据类型以便更为丰富地描述和表达网络资源的内容与结构。RDF 资源的三种表示形式分别为：URI、空白顶点（匿名资源）和 Unicode 字符串。

图2 RDF三元组示意图

RDF 本质上是一个数据模型，它提供了一个统一的标准来描述Web上的资源，所谓资源可以指类（class）、属性（property）、实例（Instance）等等。RDF在形式上表示为SPO（subject, predicate, object）三元组（triple），即（主语/主体、谓语/属性、宾语/客体），用于描述具体的事物及关系，即实体以及实体之间的关系。RDF 也可以表示为一张带有标记的有向图，图中有顶点和边，顶点对应实体，边对应关系或者属性，关系指的是实体之间、实体与属性之间的关系。

属性图

属性图是一个由顶点、边、以及顶点和边上的属性组成的图。顶点也称为节点（Node），边也称为关系（Relationship）。在属性图中，顶点和边是最重要的概念。

图3 属性图示意图

顶点（Vertex）是图中的实体。它们可以保存任意数量的属性（键-值对）。可以用标签标记顶点，表示它们在域中的不同角色。顶点标签还可以用于将元数据（例如索引或约束信息）附加到某一类顶点。

边（Edge）在两个顶点实体之间提供定向的、命名的、语义相关的连接。在有向图中，边由方向、类型、起始顶点和目标顶点组成。与顶点一样，边也可以具有属性。在大多数情况下，边具有定量属性，如权重、成本、距离、评级、时间间隔或强度。两个顶点可以添加任意数量或类型的关系，保证属性图模型的灵活性。

▲ 属性（Property）：顶点和边都可以有一个或多个属性，属性是一个键值对（Key/Value Pair），保存在顶点或边上。在实践中，一般每个顶点都会包含一个 id 或 name 属性作为主键。

▲ 标签（Label）：指示一组拥有相同属性类型的顶点，值一般不同。

▲ 路径（Path）：一组有顶点、边以链状首尾相连的集合叫做路径。

图存储

如何存储图数据，对图数据的查询效率和处理效率都至关重要。常见的图数据存储方式包稀疏矩阵、括链表、排序树、哈希表等。

图4 常见图数据存储方式

稀疏矩阵

由于实际图的稀疏性，图计算系统通常使用稀疏矩阵的存储方法来表示图数据，其中最常用的两种是CSR（Compressed Sparse Row）和CSC（Compressed Sparse Column），分别按行（列）存储每行（列）非零元所在列（行），每一行则（列）对应了一个顶点的出边（入边）。

链表

链表是一种在存储单元上非连续、非顺序的存储结构。数据元素的逻辑顺序是通过链表中的指针链接次序实现。链表是由一系列的结点组成，结点可以在运行时动态生成。每个结点包含两部分：数据域与指针域。数据域存储数据元素，指针域存储下一结点的指针。根据指针域是否连接了多个方向又可具体细分为单向链表、循环链表、双向链表等。图数据库 Neo4j 是使用链表作为图数据存储结构的一个主要代表。

排序树

图计算存储在设计和实现上继承并发展了关系型数据存储的做法，例如使用 B+树、LSM树等树形结构来存储图数据，并通过连接（Join）的方式来查询图数据。以 RDF-3X、Virtuoso为代表的众多RDF图数据库就将主谓宾按照不同的排列顺序使用 B+树建立了不同的索引，并在不同查询中组合地使用不同的索引来获得最优的查询效率。

哈希表

与树形结构类似，哈希表（Hash table，也叫散列表）也是一种常用的索引结构。不同之处在于，哈希表的查找更快（常数级复杂度），但是无法支持范围查询。例如图数据库ArangoDB混合地使用了哈希表和链表来存储图数据。

NoSQL 数据库

也有很多图数据库在存储上直接使用了NoSQL数据库，例如HyperGraphDB使用了键值对存储、XQuery使用了文档存储、Titan和 JanusGraph都是有了宽列存储。

图算法

图算法有很多，最基本图算法可归纳为三种：路径发现算法、中心性算法、社区发现算法。之所以说是“最基本”，是因为它们是很多高级算法的底层基础。这三种算法是大的分类，每一种里面都有很多具体的算法。

图5 常见图算法

路径发现算法，用于探索顶点之间的最佳路径，主要有下面5个方面，每个方面都有一些具体的算法。

▲ 最短路径。给定两个顶点，找出二者之间的最短路径。

▲ 单源最短路径。给定一个顶点，探索其到其他每个顶点的所有最短路径。

▲ 全最短路径。探索每个顶点到其他每个顶点的所有最短路径。

▲ 最小生成树。探索能将所有顶点连接起来的最短路径。

▲ 随机游走。从某个顶点出发，随机选择下一个顶点，在整个图里面随机遍历，直到满足某个条件。

中心性算法，用于探索在图中具有影响力的顶点，常见的有下面4个方面。

▲ 度中心性。最简单的一种中心性探索，看一个顶点与其他顶点的连接数量，数量越多表示影响力越大。根据实际需要，可能会区分入度与出度，入度指的是别的顶点指向自己的连接数量，出度指的是自己指向别人的连接数量。

▲ 接近中心性。探索一个顶点到其他所有顶点的最短路径的总和，数值越小表示影响力越大。举例来说，如果想在一个城市开一个超市，那么超市到周边各个小区的交通用时越少，就表示越处于中心位置。

▲ 中介中心性。探索经过一个顶点的最短路径的数量，数量越多表示影响力越大。举例来说，这样的顶点，通常处于一个桥的位置，将不同的村庄连接起来。

▲ PageRank。PageRank是Google提出的用于解决网页排名的算法，基本思路是：一个网页被很多其他网页所链接，说明它受到普遍的承认和信赖，那么它的排名就高。因为这里使用了网页、网页的关系，所以同样的思路可以引入到图计算中，来判断某个顶点的影响力，即PageRank的分值越高表示影响力越大。

社区发现算法，用于探索图中具有紧密联系的群体。社区，指的是一个子图，这个子图内部各个顶点之间的连接程度远远高于这些顶点跟外部其他顶点之间的连接。社区发现类似于机器学习里面的聚类，只是在聚类里面我们更加侧重于数据点的属性，而在社区发现中侧重于顶点之间的关系。比较常见的有下面4种算法。

▲ 连通分量（Connected Component）。用于发现连通顶点的集合，通常拿到一个图之后，我们首先便会看看它有多少个连通组件。对于某个连通组件，如何进一步探索其内部有多少社区便是下面几个算法要解决的问题。

▲标签传播算法（Label Propagation）。基本思路是：

初始时，为每个顶点分配一个标签；

每一次迭代都要计算新的标签，规则是：统计顶点所有邻居的标签，出现次数最多的标签将被设置成这个顶点的新标签，如果有多个就随机选择一个；

经过多次迭代，直到所有的顶点都满足：顶点的标签是它的邻居标签中出现次数最多的（或最多的之一）。

▲ 基于模块度的算法（Louvain Modularity）。模块度是评估一个社区网络划分好坏的度量方法，物理含义是社区内顶点的连边的权重之和与随机情况下的连边的权重之和的差距。

▲ 基于信息编码的算法（Infomap）。Infomap想解决的问题是如果在一张图上做随机游走（不限步数的游走），如何用最短的编码来描述随机游走产生的路径。

图查询

图数据查询

按照查询范围的递增顺序，面向图数据的查询可以大体分成单点查询、邻居查询、路径遍历、子图匹配和全图分析这几类。

图6 图数据查询分类

▲ 单点查询

单点查询涉及单个顶点或者边。例如查询一个点或者一条边的所有标签或者所有属性值、查询一个点或边的某个给定的属性、获取图中的所有标签、判断一个点或者一条边是否具有某个给定的标签。单点查询常用于社交网络工作负载（例如，获取新浪微博某个用户的昵称、注册时间等信息）和一些基准测试（例如，测量顶点查找时间与吞吐量）。

▲ 邻居查询

邻居查询表现为检索给定顶点的所有边、检索某条边连接的顶点；并且可以对邻居查询增加限制条件来获取更精细的结果，如查询具有给定标签的边。例如，查询新浪微博中某位大 V 的所有粉丝、查询某位用户所感兴趣的话题、查询某位用户的朋友，都可以对应到查询本地邻居。

▲ 路径遍历

路径遍历查询可以探索邻居查询之外更大的图数据，路径遍历查询通常从单个顶点或者一个规模较小的顶点集合开始，遍历图的一部分数据，我们通常称遍历起始的顶点或顶点集合为根顶点或锚点。在查询时用户可以增加限制条件来规定需要检索与遍历的图数据。例如查询一个人的朋友的朋友的朋友（三度朋友）、查询一个人的三度朋友中喜欢打排球的人等。路径遍历查询是一个非常常用的图数据库查询任务，因此常用于性能基准测试。

▲ 子图匹配

子图匹配要求从整个图中找出所有与给定的查询模板匹配的子图。子图的形状可能是一条链，也可能是一个环，亦或是更复杂的树和图。查询模板对应的子图可能包含较为具体的限制条件，例如一个具体的顶点；也可能是较为宽泛的限制条件，例如某类顶点，甚至没有任何限制条件。

▲ 全图分析

全图分析查询通常称为 OLAP（实时分析处理），这类查询通常会涉及整个图的查询（涉及所有顶点与所有边，但不一定涉及每个属性）。由于全图分析在不同的领域有着广泛地应用，因此不同的基准测试通常会加入这一类查询。很多图数据库都会支持全图分析，图计算系统更是特别注重于解决全图分析查询，如 Pregel、GraphX、Gemini等。全图分析常用于全局模式匹配、最短路径、最大流量或最小割、最小生成树、图直径、最远距离、连通分支、PageRank等。

图查询语言

可以看到，与关系模型以及其它 NoSQL 数据模型相比，基于图数据模型的查询具有更高的复杂度，这就对查询语言提出了更高的要求。基于图数据模型的查询业界尚没有统一认可的查询语言。目前主流的查询语言包括Cypher、Gremlin、SPARQL等。

图7 图数据查询语言

▲ Cypher

Cypher 是 Neo4j 提出的图查询语言，它允许用户从图数据库中存储和检索数据。Cypher 语法提供了一种可视化的逻辑方式来匹配图中顶点和关系的模式。它是一种受 SQL 启发的声明性语言，用于使用 ASCII-Art 语法描述图中的可视模式。它允许我们声明想要从图数据库中选择、插入、更新或删除什么，而不需要精确地描述如何做到这一点。通过 Cypher，用户可以构建表达性强且高效的查询来处理所需的创建、读取、更新和删除功能。

支持 Cypher 的图计算系统（图数据库）包括Neo4j、RedisGraph、AgensGraph、 TuGraph等。

▲ Gremlin

Gremlin 是 Apache ThinkerPop 框架下的图遍历语言。Gremlin具有许多语言变体，允许开发人员以 Java、JavaScript、Python、Scala、Clojure 和 Groovy 等许多现代编程语言原生编写 Gremlin 查询。Gremlin 是图遍历语言，其执行机制是在图中沿着有向边进行导航式的游走。这种执行方式决定了用户使用 Gremlin 需要指明具体的导航步骤，所以 Gremlin 是过程式语言。与受到 SQL 影响的声明式语言 Cypher 不同，Gremlin 更像一种函数式的编程。

支持 Gremlin 的图计算系统（图数据库）包括：JanusGraph、InfiniteGraph、CosmosDB、DataStax Enterprise（5.0+）、Amazon Neptune。

▲ SPARQL

RDF 规范定义了 RDF 的 SPARQL 查询语言的语法和语义。SPARQL 可用于表示不同数据源之间的查询，无论数据是作为 RDF 本机存储还是通过中间件作为 RDF 查看。 SPARQL 包含查询所需和可选图模式及其连接和析取的功能。SPARQL 还支持通过源 RDF 图进行可扩展的值测试和约束查询。SPARQL 查询的结果可以是结果集，也可以是 RDF 图。

▲ GQL

2019 年 6 月，隶属 ISO/IEC 联合技术委员会的全球诸多国家性标准机构开始就标准图查询语言 GQL 项目提案进行表决，有七个国家派出专家参与这项为期四年的项目，有望在 2023 年形成图查询语言的国际标准。

GQL 的全称是“图查询语言”，这种新语言将由监管 SQL 标准的同一个国际工作组开发和维护。GQL 高度依赖现有的语言。GQL 项目是自 SQL 之后的第一个 ISO/IEC 国际标准数据库语言项目。GQL 的主要灵感源自 Cypher（现在实现的版本有十多个，包括六款商业产品）、Oracle 的 PGQL 和 SQL 本身，以及用于只读属性图查询的 SQL 新扩展。

▲ 其他查询语言

除了上述查询语言外，目前业界相当一部分产品使用自己开发定义的查询语言，如PGQL（Oracle）、GSQL（TigerGraph）、G-CORE（LDBC）等。

图数据计算模型

图数据计算模型即针对图数据和图计算特点设计实现的计算模型，一般应用于图计算系统中。按照计算对象，图数据计算模型可以分为顶点中心计算模型、边中心计算模型、路径中心计算模型和子图中心计算模型四类。其中顶点计算模型提出时间最长，且被多个图计算系统引用，因此将其按计算任务调度方法进一步分为同步计算模型、异步计算模型和混合计算模型三类。

图8 图数据计算模型

顶点中心计算模型

在图计算模型提出之前，图数据分析系统基本都采用 MapReduce 架构，然而 MapReduce 框架无法满足图计算的需求，无法解决图数据的耦合性、稀疏性和图计算的频繁迭代操作等特点带来的数据划分重组频繁、通信开销过大和计算并行性受限等问题。为解决以上问题，Google 在 2010 年首先基于 BSP 模型提出了顶点中心计算模型，即将图算法细粒度划分为每个顶点上的计算操作。顶点中心计算模型将频繁迭代的全局计算转换成多次超步运算，且所有的顶点独立地并行执行计算操作，数据间依赖关系仅存在于两个相邻的超步之间。

▲ 同步顶点中心计算模型

同步顶点计算模型基于图计算局部性差、顶点计算量小、并行性差异大的特点提出，将图算法的每一次迭代转换为图中每一个顶点执行一次超步（superstep）运算。一次超步运算包括三个步骤：

（1）接收当前顶点所有入边上的邻居（in-neighbor）在上一个超步中发出的信息；

（2）根据接收到的信息计算当前顶点的新值，即执行程序员自定义的 compute 函数；

（3）向当前顶点所有出边邻居（out-neighbors）发送更新消息。同步顶点计算模型所有顶点完成一次超步运算后同步更新顶点信息，之后进入下一次超步运算。

同步顶点中心计算模型解决了 MapReduce 分布式框架无法有效支持迭代型图算法的局限性，为并行图计算系统设计提供了新的思路，使得大规模图算法的实现更加简洁明了。然而，全局同步顶点中心计算模型要求每次超步运算需等待全局数据同步，使得算法计算效率受最慢顶点计算速度限制，计算资源利用率有待进一步提高。

▲ 异步顶点中心计算模型

2010 年，卡内基·梅隆大学的学者基于异步图计算模型提出了异步图计算系统 GraphLab，并在 2012 年发布了改进系统 distributed GraphLab，实现了分布式异步图计算模型。异步计算模型与同步计算的迭代设计相同，仍为 BSP 三步操作模型，但是在接收上一轮超步计算的消息时，不再是由邻居顶点推送更新的数据，而是由计算顶点采用“拉”的方式选择性地读取邻居顶点的消息。一次超步运算包括三步操作：

（1）获取当前顶点的邻居信息（关联边或邻居顶点）；

（2）执行用户定义计算操作；

（3）更新当前顶点所有可写邻居（关联边或邻居顶点）的信息。

异步顶点中心模型提高了计算资源利用率，随着图数据规模的增加，其计算优势更加显著。但异步顶点中心模型同时引入了维护数据一致性的开销，数据一致性策略实现复杂，且容易产生冲突和错误。因此大部分图计算系统选择同时实现同步和异步顶点计算模型。

▲ GAS（gather、apply、scatter）顶点中心计算模型

同步和异步计算模型均以顶点作为计算中心，将边作为信息传递的路径，因此，这种节点模型的计算能力受图数据中顶点和边分布特点限制。Gonzalez 等人提出了 GAS 顶点中心计算模型，解决图计算的上述问题。

GAS 计算模型沿用同步顶点中心计算模型中超步的概念，并且通过划分大度数顶点在单个计算顶点内实现并行计算。每一次的超步运算分为三个步骤：

（1）信息收集（gather）和汇总（sum），即收集计算顶点的邻接顶点和边上的信息，执行用户自定义汇总函数将得到的信息汇总到主顶点；

（2）应用（apply）和更新（update），即由主顶点执行用户自定义的计算操作，并将镜像顶点更新为计算所得的新值；

（3）分发（scatter），即由主顶点和镜像顶点将更新信息推送给各自相关联的邻居顶点和边。

GAS 计算模型通过切分顶点可以有效降低超步运算带来的通信开销并提高计算并行性。GAS 计算模型通过划分顶点实现了顶点内并行计算，其计算并行性比异步顶点中心模型更好。当分析计算的图数据中顶点之间的度存在显著差异时，GAS 计算模型的计算优势也更加显著。

边中心计算模型

顶点中心模型提高了图计算系统实现图数据计算分析的能力，但是在实际应用中仍面临一些问题：

（1）为提高计算顶点随机访问邻居的速度，图计算系统一般将完整图数据载入内存，因此当图数据规模过大时，通常在分布式系统中实现顶点中心计算模型，即对实现系统设备资源要求过高；

（2）当图数据中边数目远远大于顶点数目时，每次超步运算中的信息更新和分发操作的时间开销将远大于顶点计算时间，通信成为图计算的主要瓶颈，限制了完成主要计算操作的速度。

为解决设备资源受限和边数目远大于顶点数目时的图数据分析计算问题，洛桑联邦理工学院在 2013 年提出边中心模型，并将其应用于图计算系统 XStream。边中心计算模型将图算法构建为在图数据的边列表上的流式迭代计算，每一次迭代地完成计算、排序和更新三步操作：

（1）读取边列表流，完成用户定义的计算操作，输出更新信息到目的顶点列表中；

（2）应用将目的顶点列表重排序（shuffle）为更新消息流；

（3）读取更新消息流和源顶点列表，更新源顶点值。三步操作在一次迭代计算中顺序执行。

边中心计算模型将图算法的迭代计算转换为可在边列表上顺序执行，避免了随机读写数据对内存资源的高要求，从而解决了顶点中心计算模型面临的资源受限和通信开销过大的难题。边中心计算模型的流式顺序计算特点使得在全局图数据上的计算可以分块实现，顺序访问存储在硬盘上的数据，降低了图数据分析计算对内存容量的要求，即可在单机上实现对大规模图数据的分析处理。此外，边中心计算模型将每次迭代计算生成的目的顶点更新消息序列进行重排序，获得按源顶点合并排序的更新消息流，则更新消息数不大于顶点数，大大简化了消息更新同步的开销。

路径中心计算模型

边中心计算模型和顶点中心计算模型分别将图算法转换为可在顶点和边上执行的迭代计算，但同时也将图计算的并行性限制在了顶点和边层次上。然而图算法在图结构上是沿节点到边再到顶点的顺序计算的，因此，华中科技大学服务计算技术与系统实验室提出更接近理想图计算分析的模型——路径中心计算模型，并将其应用于图计算系统 PathGraph。

路径中心计算模型以路径为计算单元，即从源顶点出发到目的顶点的边序列。路径中心计算模型将图数据组织为前向边遍历树（forward-edge traversal tree）和后向边遍历树（reverse- edge traversal tree），从而将图计算转换为在树上的迭代计算。路径中心计算模型基于前向遍历树和后向遍历树的每次迭代运算分为两步：

（1）消息分发（Scatter），即父顶点沿前向边遍历树更新子顶点或出边信息；

（2）信息收集（Gather），即父顶点沿后向边遍历树收集子顶点或入边信息。

路径中心计算模型从数据结构决定图算法计算顺序的角度出发，设计前向边遍历树和后向边遍历树，简化了图计算时顶点访问入边邻居和出边邻居的查找操作。因此，相比边中心计算模型，当图顶点规模在百万级以上和边规模在亿级以上的数据集上测试 BFS、PageRank、联通子图等图算法，路径中心计算模型的计算速度提高了1~2倍。但是全局数据同步设计限制了计算并行性，同步数据会带来大量通信开销，导致计算资源利用率低。

子图计算模型

路径中心计算模型相比以顶点或边作为计算中心的模型更接近图结构上的理想计算状态，然而以上计算模型都面临两个问题：

（1）所有顶点只有自己的直接邻居信息，图中传递的更新消息每次只能扩散一层，因此从源顶点到目的顶点的一次更新消息需要多次迭代才能完成，消息更新过慢会带来额外的计算时间开销；

（2）顶点或边均产生大量的通信开销，超步内执行计算操作的顶点或边均产生更新消息，每次超步运算结束后，大量的更新消息带来了全局数据同步的等待或维持数据一致性的开销。

为解决以上问题，IBM 阿尔马登研究中心于 2013 年在图计算系统 Giraph++中提出子图中心计算模型，将完整图结构上的计算转换为多个子图上的迭代超步运算。子图中心计算模型完成图划分后，在多个子图上并行执行迭代图计算，一次超步运算执行两步操作：

（1）子图并行执行用户定义计算操作，并输出计算结果；

（2）包含相同顶点的子图间更新顶点信息。

步骤（2）可在所有子图的步骤（1）操作结束后同步执行，或者在保持数据一致性前提下异步执行。

子图中心计算模型通过子图划分方法，将图算法转换为多个子图上的迭代计算，成功减少了计算时的通信开销和迭代操作次数。

图处理系统

针对图数据的处理系统可以大体分为两类，图数据库、图计算系统。图数据库适合需要对子图进行并发操作的场景。图计算系统适合需要对全图进行迭代式计算的场景。

图数据库

在众多不同的数据模型里，关系数据模型自 20 世纪 80 年代就处于统治地位，而且出现了不少巨头，如 Oracle、MySQL，它们也被称为关系数据库管理系统（RDBMS）。然而，随着关系数据库使用范围的不断扩大，也暴露出一些它始终无法解决问题，其中最主要的是数据建模中的一些缺陷和问题，以及在大数据量和多服务器之上进行水平伸缩的限制。

因此，近年来诞生了 Neo4j、InfiniteGraph 等专注于图结构化存储与查询的图数据库。与传统的关系型数据库相比，图数据库善于处理大量的、复杂的、互联的、多变的网状数据，效率远远高于传统型数据库，性能约有百倍以上的提升。

图数据库的主要职能是管理图数据，因此需要支持高效的对顶点/边的查询与更新；为了方便用户的使用，通常还需要增加对事务（transaction）的支持，从而保证并发操作下的正常运作。比较有代表性的图数据库包括Neo4j、ArangoDB、Virtuoso、Neptune、JanusGraph、TigerGraph、TuGraph等。

图计算系统

图计算系统是对图结构数据进行针对性优化并高效计算的系统。在当前的大数据分析领域，需要处理的图数据规模往往高达数十亿以上，并且图数据结构复杂多变，需要支持大规模、高效图计算的系统以应对上述挑战。依据大规模图计算系统的使用场景以及计算平台架构的不同，我们将其分为单机内存图计算系统、单机外存图计算系统、分布式内存图计算系统和分布式外存图计算系统。

图9 图计算系统分类

▲ 单机内存图处理系统

此类图计算系统单机运行，可直接将图完全加载到内存中进行计算。但是单机的计算能力和内存空间总是有限，故只能解决较小规模的图计算问题，比较有代表性的系统有 2013 年发布的 Ligra 和 Galois，以及 2015 年发布的 GraphMat 和 Polymer。

▲ 单机外存图计算系统

此类图计算系统单机运行，但是将存储层次由 RAM 拓展到外部存储器如 SSD、Flash、SAS、HDD 等，使其所能处理的图规模增大。但受限于单机计算能力和外存存储系统的数据交换的带宽限制，该类系统无法在可接受的情形下处理超大规模的图数据。典型的单机外存图计算系统有 GraphChi、TurboGraph、X-Stream、PathGraph、GridGraph 和 FlashGraph。

▲ 分布式内存图计算系统

此类图计算系统将图数据全部加载到集群中的内存中计算，理论上随着集群规模的增大其计算性能和内存容量都线性增大，能处理的图数据也按线性扩大。图分割的挑战在分布式系统愈加明显，再加上集群网络总带宽的限制，所以整体性能和所能处理的图规模也存在一定的缺陷。这类图计算系统主要包括同步计算模型的 Pregel 及其开源实现 Piccolo，同时支持同步和异步的系统 PowerGraph、GraphLab 和 GraphX。PowerSwitch 和 PowerLyra 则对 PowerGraph 做了改进，Gemini 则借鉴了单机内存系统的特性提出了以计算为核心的图计算系统。

▲ 分布式外存图计算系统

此类图计算系统将 Single-machineout-of-coresystems 拓展为集群，能够处理边数量级为 trillion 的图，目前有 2015 年发布的 Chaos。

图学习

图学习，即基于图的机器学习，旨在将图的结构信息整合到机器学习模型中。随着以深度学习为代表的人工智能技术广泛应用，且图结构具有更强的表达能力，图学习成为了一个热点话题，也在因果关系、可解释性方面带来了突破进展。现在，图学习已经被应用在了搜索推荐、广告、金融风控、智能交通、医疗、城市等各个领域。另一方面，图学习也面临着一些新的技术挑战，例如数据规模庞大、点和边的异构性、多模态的属性特征、结构或属性随时间动态变化等。

图表征学习

图学习的传统方法是表征学习。图表征学习（Graph Embedding），就是将图中的每一个顶点都表示成一个低维向量，并使该向量能够尽可能多的保存图的结构和内容信息。该表示向量可以作为特征用于后续的学习任务，如链接预测、顶点分类等。

图10 图表征学习

对于图表征学习这一问题，学界已经开展了非常多的研究工作。这些工作针对同构图、异构图、属性图、动态图等不同类型的数据，提出了各式各样的方案，包括经典算法 DeepWalk、LINE、Node2Vec 等。这些工作的基本做法是基于随机游走生成数据，然后通过训练优化参数，生成概率模型。

图神经网络

另一种图学习的重要类型是图神经网络。传统的神经网络只能解决欧式空间的问题，要求数据是完整、整齐、规则的。例如一张照片，每个像素点固定与八个点相邻，因此每个点可以对应一个等长向量，包含了它本身的信息和邻居信息。而图神经网络（GNN），将经典神经网络模型如 Recurrent Neural Networks（RNN）、Convolutional Neural Networks（CNN）等扩展到了图上。它解决的是非欧式空间的问题，这是因为图结构是不规则的，每个点的邻居个数不一样，导致局部的维度不定长。

图11 图神经网络

与图表征学习试图学习出每个点的 embedding 不同，图神经网络的目的其实是学习出聚合函数，所有点通过同一个函数就可以利用局部信息计算出自身的 embedding。即使是图结构发生变化，甚至是完全新的图，也能用原来的函数计算出有意义的结果。有关图神经网络，也已经诞生了一系列经典算法，包括图卷积网络（Graph Convolution Networks，GCN）、图注意力网络（Graph Attention Networks）、图自编码器（ Graph Autoencoders）、图生成网络（ Graph Generative Networks）和图时空网络（Graph Spatial-temporal Networks）等。图神经网络已应用于计算机视觉、推荐系统、智能交通、分子化学等领域。

本文来自“国家技术标准创新基地智能计算”，转载请注明。