图计算

将数据按照图的方式建模可以获得以往用扁平化的视角很难得到的结果

图计算（Graph Processing）是将数据按照图的方式建模可以获得以往用扁平化的视角很难得到的结果。

基本概念

什么是图计算？

大数据时代，数据之间存在关联关系。由于图是表达事物之间复杂关联关系的组织结构，因此现实生活中的诸多应用场景都需要用到图，例如，淘宝用户好友关系图、道路图、电路图、病毒传播网、国家电网、文献网、社交网和知识图谱。

为了从这些数据之间的关联关系中获取有用信息，大量图算法层出不穷。它们通过对大型图数据的迭代处理，获得图数据中隐藏的重要信息。图计算作为下一代人工智能的核心技术，已被广泛应用于医疗、教育、军事、金融等多个领域，并备受各国政府、全球研发机构和巨头公司关注，目前已成为全球科技竞争新的战略制高点。

系统简介

·图可以将各类数据关联起来：将不同来源、不同类型的数据融合到同一个图里进行分析，得到原本独立分析难以发现的结果；

·图的表示可以让很多问题处理地更加高效：例如最短路径、连通分量等等，只有用图计算的方式才能予以最高效的解决。

然而，图计算具有一些区别于其它类型计算任务的挑战与特点：

·随机访问多：图计算围绕图的拓扑结构展开，计算过程会访问边以及关联的两个顶点，但由于实际图数据的稀疏性（通常只有几到几百的平均度数），不可避免地产生了大量随机访问；

·计算不规则：实际图数据具有幂律分布的特性，即绝大多数顶点的度数很小，极少部分顶点的度数却很大（例如在线社交网络中明星用户的粉丝），这使得计算任务的划分较为困难，十分容易导致负载不均衡。

随着图数据规模的不断增长，对图计算能力的要求越来越高，大量专门面向图数据处理的计算系统便是诞生在这样的背景下。

Pregel由Google研发是专用图计算系统的开山之作。Pregel提出了以顶点为中心的编程模型，将图分析过程分析为若干轮计算，每一轮各个顶点独立地执行各自的顶点程序，通过消息传递在顶点之间同步状态。Giraph是Pregel的一个开源实现，Facebook基于Giraph使用200台机器分析万亿边级别的图数据，计算一轮PageRank的用时近4分钟。

GraphLab出自于CMU的实验室，基于共享内存的机制，允许用户使用异步的方式计算以加快某些算法的收敛速度。PowerGraph在GraphLab基础上做了优化，针对实际图数据中顶点度数的幂律分布特性，提出了顶点分割的思想，可以实现更细粒度的数据划分，从而实现更好的负载均衡。其计算模型也被用在后续的图计算系统上，例如GraphX。

尽管上述的这些图计算系统相比MapReduce、Spark等在性能上已经有了显著的性能提升，但是它们的计算效率依然非常低下，甚至不如精心优化的单线程程序。

Gemini由清华大学计算机系的团队提出，针对已有系统的局限性，提出了以计算为中心的设计理念，通过降低分布式带来的开销并尽可能优化本地计算部分的实现，使得系统能够在具备扩展性的同时不失高效性。针对图计算的各个特性，Gemini在数据压缩存储、图划分、任务调度、通信模式切换等方面都提出了对应的优化措施，比其他知名图计算系统的最快性能还要快一个数量级。ShenTu沿用并扩展了Gemini的编程和计算模型，能够利用神威·太湖之光整机上千万核的计算资源，高效处理70万亿边的超大规模图数据，入围了2018年戈登·贝尔奖的决赛名单。

除了使用向外扩展的分布式图计算系统来处理规模超出单机内存的图数据，也有一些解决方案通过在单台机器上高效地使用外存来完成大规模图计算任务，其中的代表有GraphChi、X-Stream、FlashGraph、GridGraph、Mosaic等。

关键技术

图数据的组织

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

图数据的划分

将一个大图划分为若干较小的子图，是很多图计算系统都会使用的扩展处理规模的方法；此外，图划分还能增强数据的局部性，从而降低访存的随机性，提升系统效率。

对于分布式图计算系统而言，图划分有两个目标：

(1) 每个子图的规模尽可能相近，获得较为均衡的负载。

(2) 不同子图之间的依赖（例如跨子图的边）尽可能少，降低机器间的通信开销。

图划分有按照顶点划分和按照边划分两种方式，它们各有优劣：

(1) 顶点划分将每个顶点邻接的边都放在一台机器上，因此计算的局部性更好，但是可能由于度数的幂律分布导致负载不均衡。

(2) 边划分能够最大程度地改善负载不均衡的问题，但是需要将每个顶点分成若干副本分布于不同机器上，因此会引入额外的同步/空间开销。

所有的类Pregel系统采用的均为顶点划分的方式，而PowerGraph/GraphX采用的是边划分的方式。Gemini采用了基于顶点划分的方法来避免引入过大的分布式开销；但是在计算模式上却借鉴了边划分的思想，将每个顶点的计算分布到多台机器上分别进行，并尽可能让每台机器上的计算量接近，从而消解顶点划分可能导致的负载不均衡问题。

顶点程序的调度

在以顶点为中心的图计算模型中，每个顶点程序可以并行地予以调度。大部分图计算系统采用基于BSP模型的同步调度方式，将计算过程分为若干超步（每个超步通常对应一轮迭代），每个超步内所有顶点程序独立并行地执行，结束后进行全局同步。顶点程序可能产生发送给其它顶点的消息，而通信过程通常与计算过程分离。

同步调度容易产生的问题是：

(1) 一旦发生负载不均衡，那么最慢的计算单元会拖慢整体的进度。

(2) 某些算法可能在同步调度模型下不收敛。

为此，部分图计算系统提供了异步调度的选项，让各个顶点程序的执行可以更自由，例如：每个顶点程序可以设定优先级，让优先级高的顶点程序能以更高的频率执行，从而更快地收敛。

然而，异步调度在系统设计上引入了更多的复杂度，例如数据一致性的维护，消息的聚合等等，很多情况下的效率并不理想。因此，大多数图计算系统采用的还是同步的调度方式；少数支持异步计算的系统也默认使用同步方式进行调度。

计算与通信模式

图计算系统使用的通信模式主要分为两种，推动（Push）和拉取（Pull）：

(1) 推动模式下每个顶点沿着边向邻居顶点传递消息，邻居顶点根据收到的消息更新自身的状态。所有的类Pregel系统采用的几乎都是这种计算和通信模式。

(2) 拉取模式通常将顶点分为主副本和镜像副本，通信发生在每个顶点的两类副本之间而非每条边连接的两个顶点之间。GraphLab、PowerGraph、GraphX等采用的均为这种模式。

除了通信的模式有所区别，推动和拉取在计算上也有不同的权衡：

(1) 推动模式可能产生数据竞争，需要使用锁或原子操作来保证状态的更新是正确的。

(2) 拉取模式尽管没有竞争的问题，但是可能产生额外的数据访问。

Gemini则将两种模式融合起来，根据每一轮迭代参与计算的具体情况，自适应地选择更适合的模式。

应用

网页排序

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

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

社区发现

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

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

最短路径

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

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

全国各地天气预报查询

上海市

云南省

云南省

云南省

云南省