背景
大规模图数据分析是当前的一大研究热点。随着大数据时代的到来，在人们日常生活中、工业界和学术界产生的数据越来越复杂，传统的关系型数据模型和欧几里得数据模型难以用来描述和建模许多具有复杂关系的实体和对象，而图结构模型则恰好能够弥补这一弊端。
首先对图（Graph）进行一个简单的定义：一个图G=（V, E）是一个二元组，其中V为顶点集，E为边集，边表示顶点之间的关系。在实际应用中，顶点和边可以都是相同的类型（分别），也可以包含许多不同的类型，同时，顶点和边都可以包含许多不同的属性。因此，通过关系包含属性这一利器，图结构模型可以更方便地用来建模大量具有复杂关系的数据。
图分析是通过存储、分析、综合和处理图数据来解决复杂问题的一个计算机领域，其擅长挖掘人、物、实体之间的关联关系，拥有广泛的应用场景，如社交网络分析、知识图谱、物流调度和推荐系统等。在本文中，我们所介绍的图分析系统主要用于解决两类图分析问题：图计算和图挖掘。图计算问题通常可以通过线性代数进行建模表示，将图建模成一个邻接矩阵，同时将每一个顶点的状态表示成一个向量，比如PageRank是一个典型的图计算问题，其基于稀疏矩阵和向量乘的迭代来进行计算，除此之外，单源点最短路径(SSSP)、连通组件和中介中心度等也是一些非常典型的图计算问题。而图挖掘问题则与图计算问题有较大区别，图挖掘问题旨在从一个图中挖掘出一些复杂的结构，而非进行值计算，比如频繁子图挖掘、counting motifs和clique挖掘等。
现实世界中的图通常非常大（上亿节点，上百亿条边），需要进行的查询分析也非常复杂；此外，由于图数据的非结构化特性，使得图数据访问局部性差，并行复杂。因此，开发设计一个高性能、可扩展、易用性强的图分析框架/系统成为了当前系统研究者的一大研究热点。
近些年来，在学术界和工业界中已经涌现出了一大批图编程框架，如Pregel[1]、Ligra[3]、GraphChi[7]、Gemini[6]、X-Stream[2]和Arabesque[4]等。从系统架构上来说，这些编程框架有的是分布式框架，如Pregel和Gemini等；有的是基于共享内存的单机图系统，如Ligra等；也有基于磁盘的单机图计算系统，如GraphChi和X-Stream等。从编程模型来说，大量的图计算系统都使用了vertex-centric的编程模型，如Pregel、GraphLab和PowerGraph[5]等；同时，也有一些图编程框架采用了edge-centric的编程模型，比如X-Stream；另外一些图系统采用了点边混合计算的编程模型，如Ligra和Gemini；其次，由于vertex-centric和edge-centric等编程模型无法适用于图挖掘问题，因此一些图挖掘系统采用了embedding-centric的编程模型，比如Arabesque；另外，一些基于磁盘或SSD的图系统采用了一些其它的编程模式，比如Graphene采用了IO-request-centric的编程模型。从并行模型上来说，整体同步并行计算模型（简称BSP）是图分析系统中最常见的并行模型，比如Pregel、Ligra、X-Stream和Arabesque等许多系统都采用了该并行模型；同时，一些图系统采用了异步并行模型（简称AP），如GraphLab和Maiter；另外，延迟同步并行模型（简称SSP）也是一种可采纳的方案，特别是适合于机器学习中的图分析问题。
本文剩余部分的内容主要如下：在本文的第二部分，我们将介绍图分析框架中常用的编程模型；在第三部分，我们将介绍图分析框架中主要采用的系统架构；在第四部分，我们将介绍图分析框架常用的并行模型；最后，我们将分别从编程模型、系统架构和并行模式三个方面对现有的一些图分析系统进行介绍和总结。
编程模型
图分析系统/框架的提出是为了用户和研究人员能够更加方便地进行图算法开发，解决图分析问题，因此，编程模型对于系统的易用性起着至关重要的作用。同时，编程模型也由系统架构和系统所要解决的问题所决定。
Vertex-Centric
Vertex-centric，即以顶点为中心。在vertex-centric的编程框架里，通过在输入图的所有节点上迭代计算一个用户自定义函数（UDF）来完成图算法的计算，即Think Like A Vertex（TLAV），UDF的输入值通常包括节点的本地数据以及来自邻居节点的数据。当迭代达到一定次数或者所有节点都达到收敛状态时，计算终止。简单来说，在vertex-centric的编程模型中，节点每一轮计算通常包括三个阶段：从邻居节点收集信息（或者接收邻居节点的信息）；执行本地计算；将计算产生的新的结果分发/发送给邻居节点。基于vertex-centric的编程模型，用户能够实现许多不同类型的图算法，尽管不如传统的图论算法那样易于表达，但是基于该编程模型，易于提高框架的可扩展性和算法的并行性。
Edge-Centric
Edge-centric是另一种常见的图计算框架编程模型，正如vertex-centric是以顶点为中心，同理，edge-centric即以边为中心。在edge-centric的编程模型中，用户自定义函数作用在边上，每次输入一条边，读取源节点的数据进行计算，计算出update，此阶段称为scatter阶段；scatter阶段结束之后，将每一个update apply到相应边的目的节点上，此阶段称为gather阶段，重复执行以上两个阶段，直到达到收敛状态，算法结束。基于edge-centric的编程模型，能够改善vertex-centric导致的负载不均衡问题，同时对于out-of-core的图系统，能够减少磁盘的随机访问，提高IO效率。
点、边混合计算
此外，还有一类图计算框架，同时结合了vertex-centric和edge-centric的编程模型，因此，用户在开发图算法时，可以混合使用vertex-centric和edge-centric的编程API，从而能够提高图算法开发的灵活性和易用性。
Embedding-Centric
正如上文所阐述过的，图挖掘问题不同于图分析问题，图挖掘算法通常需要从输入图中挖掘出满足算法指定性质的pattern。在图挖掘算法计算过程中，中间状态子图的数目会随原图的大小成指数增长；此外，进行高效的同构检查以及生成完整且唯一的embedding集具有很大的挑战。因此，传统的vertex-centric和edge-centric的编程模型都无法很好的应用到图挖掘算法中。一个embedding是输入图的一个子图，在该编程模型中，系统根据用户自定义的算法遍历所有需要进行扩展的embedding，对满足过滤条件（可能是输出）的embedding进行处理，然后输出最终符合算法条件（满足特定pattern）的embedding。
系统架构
系统架构是图分析框架的一个重要特征，不同的架构具有不同的工作方式以及优缺点。目前，图分析系统最常见的三种架构包括分布式架构，单机共享内存架构以及单机out-of-core（基于磁盘）的架构。
分布式架构
在大数据时代，需要进行计算分析的大图通常具有上亿的节点和边，单机无法容纳下一个完整的图以进行分析，因此可行的解决方案之一就是将图分析框架实现为分布式架构。在分布式架构的图分析框架中，通常采用master-worker的工作机制，其中一台机器作为master，剩余机器作为worker，master负责协调工作，worker负责计算。在算法开始前，master会采用一定方式，比如hash partition，将图分成不同的partition并分配给worker，每个worker在本地进行计算，并通过网络与其他机器进行通信。在算法执行过程中，master控制算法的执行过程，比如何时开始下一个超步，何时算法结束等。
分布式架构具有良好的可扩展性，能够处理超大规模的大图。但是，分布式架构需要面临的一个问题是巨大的通信开销以及启动开销，特别是，当图不是很大时，系统的启动开销可能会远大于算法的计算开销。另外，在分布式架构中，任何一台机器都有可能在任何时候发生故障或崩溃，因此，系统还需要具备良好的容错机制。
单机共享内存架构
尽管单机系统无法扩展到同分布式集群一样的内存大小，但是随着硬件的不断发展，目前，一个普通的服务器也能够拥有上百GB的内存，足够容纳下目前已报道的任何大图。同时，与分布式集群相比，基于共享内存的单机系统具有更低的通信开销；与分布式集群中的单机相比，通常具有非常高的性能；基于共享内存实现的并行图算法代码，通常比分布式版本简单。另外，在基于共享内存的系统中，系统需要良好的一致性模型，在并发执行过程中，避免数据竞争。
单机out-of-core架构
对于普通用户而言，要想访问和使用一个计算机集群资源不是那么容易，同时普通个人电脑也无法拥有像服务器那样上百GB的内存。因此，受内存大小限制，基于共享内存架构的图分析系统难以在普通个人电脑上进行大图分析。现如今，一台普通的个人电脑通常也有几百GB到几个TB的硬盘大小。所以，为了解决前面的内存大小限制，最直接的做法就是将外存（硬盘）作为内存的扩展，来完成大图分析，而这正是基于磁盘的单机图分析系统的基本工作原理。在基于磁盘的单机图系统中，图数据存储于外存中，并分成多个partition，在图算法执行过程中，通常每次将一个partition加载到内存中，进行计算，然后再写回外存，这为算法的一轮迭代。算法一轮轮迭代下去，直到收敛，算法结束。对于该类架构的图分析系统来说，IO通常是系统最大的性能瓶颈，这是因为：一方面，外存的访问速度要比内存慢很多，达到几个数据量以上，而在算法执行过程中，需要进行很多遍IO；另一方面，在图算法的执行过程中，会产生大量的随机访问，由于磁盘的随机访问性能比顺序访问要差很多，进一步影响了IO性能。对于以上IO性能瓶颈，通常有两种比较常规的改进方法：一种方法是将计算与IO重叠，另一种方法是尽可能进行顺序IO，减少随机IO（可有不同方法来实现）。
并行模式
BSP模型
整体同步并行模型（简称BSP模型）是图分析系统中使用最广泛的并行模型。在BSP模型中，算法的迭代计算被分成一系列的超步，在每一个超步内，每一个图节点接收来自上一个超步的邻居节点的消息，然后执行一个用户自定义函数，并将执行后节点的更新值发送给邻居节点，发送出去的消息要在下一个超步才能收到。BSP模型简化了并行算法的分析，基于BSP模型易于实现各种并行的图算法。
然而，在BSP模型中，由于全局同步屏幕的存在，会导致“流浪者”的出现，即某些worker性能不如其它worker，导致在一个超步内的执行时间比其它worker大很多。因此，在BSP模型中，超步的速度（每一个超步的执行时间）由性能最差的worker决定，这有可能成为系统的性能瓶颈。
AP模型
为了消除“流浪者”问题，异步并行模型（简称AP模型）被应用到了图分析系统中。在异步并行模型中，没有全局同步屏障，节点能够立即访问收到的消息并进行计算，因此，“速度”较快的worker不用等待“流浪者”，可以不停向前执行。
但是，在异步并行模型中，可能会产生大量的过时计算，即由消息触发的计算很快过时了，由于更新的消息的到来。过时的计算通常是冗余的，并且会增加许多不必要的计算和通信开销。另外，与BSP模型相比，AP模型的代码编写和调试更加困难，算法分析和一致性分析更为复杂，特别低，某些图算法在异步并行模型下无法收敛。
异步并行模型更适合于机器学习中的算法，因为机器学习算法的结果通常是模糊的，只需要计算出一个模型能够很好地模拟数据即可，至于模型参数究竟是多少并不重要。
SSP模型
延迟同步并行模型（简称SSP模型）是一个有界异步模型。在SSP模型中，放宽了一致性要求，允许“速度”较快的worker“超过”较慢的worker最多c步，c为一个固定的参数，即最快的worker与最慢的worker迭代次数的差值不超过c。SSP模型同异步并行模型一样，会产生过时计算，但是，该模型能够消除BSP模型中存在的“流浪者”现象带来的性能瓶颈，同时保留了BSP模型中的同步机制。
图分析系统
下面，我们将主要从系统架构、编程模型和并行模式三个方面对现有的一些图分析系统进行介绍和总结。
Pregel
由Google提出的大规模分布式图计算框架Pregel，是第一个基于vertex-centric的图分析平台，采用了BSP模型进行同步执行。
在Pregel中，每一个节点有一个value，图算法的执行由多个超步组成，在一个超步内，每一个节点首先接收来自上一个超步的所有邻居节点的消息，然后进行计算，计算完成之后，再将消息发送给邻居节点，发送出去的消息将在下一个超步中被邻居节点接收到。在一个超步内，所有节点并行执行。因此，在每一个超步内，图节点所做的工作包含接收消息，进行计算和发送消息三个部分，其由用户自定义的Compute函数来完成。另外，顶点存在两种不同的状态，活跃状态和非活跃状态，只有活跃状态的节点会执行Compute函数，当活跃节点调用voteToHalt时（达到一定迭代次数或收敛），节点从活跃状态变为非活跃状态，当所有节点都变为非活跃状态时，计算结束。
Pregel系统采用了master-worker机制，其中一台机器充当master，其余的机器作为worker，worker与master之间，以及worker与worker之间，可以相互通信。Master负责将图分为多个partition并分配给worker，每个worker将自己对应的partition加载进内存中，然后算法开始执行，master负责控制超步的开始和结束，以及算法的终止。另外，Pregel系统中提供了combiner机制和aggregator机制。Combiner可以在消息发送方（比如worker）对多个消息进行“累加”，以减少通信开销，提升系统性能；aggregator用于超步中全局信息的收集和分发，可以利用该机制来判断算法是否达到收敛状态。
对于分布式系统来说，容错机制尤为重要。Pregel系统通过检查点机制来实现系统容错，每个worker在一个超步开始前，会将自己分区的节点值写入非易失性存储器。Master间歇性地向worker发送ping消息，worker收到ping消息后必须立刻回复master。一旦master某次发出ping消息后未收集齐所有worker的回复，master则判定系统内有worker崩溃。检测到worker崩溃后，master会将图算法的执行回退至worker崩溃前。
GraphLab
GraphLab是一个异步共享内存的分布式图系统，采用vertex-centric的编程方式，但与Pregel不同的是，在GraphLab中，顶点程序能够直接访问当前节点的数据，以及邻边和相邻节点的数据。GraphLab提供了一种异步、动态的图并行计算，从而能够在计算机集群上高效地运行许多机器学习和数据挖掘算法。
许多机器学习和数据挖掘（MLDM）算法能够用图数据来进行建模，通过这种方式，能够很方便地表达数据依赖。此外，大多数MLDM算法会迭代地更新一组参数，这些更新依赖于基础图结构。同步图计算系统比如Pregel会在一次迭代结束时并行更新所有参数，其中的输入数据均来自上一次迭代；而GraphLab使用最新的参数值异步更新参数。基于异步并行的模型，能够消除同步计算中由于“流浪者”出现可能带来的性能问题，从而使得许多MLDM算法从中收益，比如置信传播、PageRank等。
GraphLab引入了Gather、Apply和Scatter（GAS）的计算模型。在gather阶段，顶点从邻居及其入边那儿读取数据，并进行“累加”；在apply阶段，顶点使用收集到的值以及旧值来进行计算新的值；最后，在scatter阶段，再将新值分发出去。
PowerGraph
许多真实世界的图呈幂定律分布，即大多数顶点拥有非常少的邻居，而一小部分顶点拥有非常多的邻居，这种现象给高效的分布式并行图分析带来了非常大的挑战。因为，在分布式图系统中，通常按顶点对图进行划分，使得每一个partition中的顶点数量尽可能相等，而在这种情况，由于某些顶点边非常多，其它大部分顶点边较少，就会出现worker之间存储和计算的不均衡，以及worker之间通信的不对称。
为了应对这些挑战，Gonzalez等提出了PowerGraph，一个分布式图计算系统。PowerGraph结合了Pregel和GraphLab的特效，不仅支持BSP计算模型，同时也支持高效的异步计算模型。PowerGraph使用vertex-cut的方式来对图进行partition。对于度比较高，也就是邻居比较多的顶点，PowerGraph会将其分为多个部分，每个部分包括顶点的其中一部分边并存储在集群的一台机器上。在图算法计算过程中，顶点程序在顶点的每一个部分上并行计算，更新的节点数据通过网络进行交换。利用这种方式，度比较高的节点的边数据可以在集群的多个机器上平均分配，从而有助于实现负载均衡并减少通信开销。由于顶点数据（主数据）及其副本（镜像）之间存在通信，并且顶点副本会增加系统的存储开销，因此需要仔细确定顶点的划分数目，以减少网络和存储开销。
GraphChi
GraphChi是一个基于磁盘的单机图计算系统，采用vertex-centric的编程模型。为了能够在一台个人计算机上处理具有数十亿条边的大图，我们不得不使用磁盘来扩展内存。然而，由于图数据的非结构化特性，以及图算法具有很差的局部性，因此，如果设计不当，那么大图分析的性能将会很差，令人无法接受。
为了能够实现基于磁盘高效的大图处理，GraphChi首先通过预处理重排图数据在磁盘上的位置，然后使用了一种新颖的计算模型来执行图算法，从而能够尽可能的顺序访问图数据，仅有少量的随机访问。同时，GraphChi使用了异步计算模型，有助于加快某些算法的收敛速度。另外，GraphChi通过选择性调度来减少图遍历算法中的IO次数，从而进一步提高性能。
在预处理阶段，GraphChi按照每个interval的边数大致相等并且可以放入内存的规则将顶点划分为多个interval（顶点集）。然后，根据interval，将边分成多个shard，每个shard存储一个interval的所有入边。在一个shard内，边按源节点ID进行排序。预处理完成之后，GraphChi采用并行滑动窗口算法（PSW）从磁盘加载图数据，并在顶点上执行并行计算。在一次迭代过程中，PSW按interval为单位进行计算，每次处理一个interval的所有顶点。当在一个interval上执行时，该interval的所有入边都会从磁盘上顺序地加载到内存中，由于所有的入边按源节点ID排序并且出边在其它的shard上面，因此还需要多次顺序访问来获得该interval的出边。实验结果表明，GraphChi可在个人计算机上运行，并且与具有多台机器的分布式图系统相比，具有可比甚至更好的性能。
X-Stream
GraphChi使用磁盘作为内存扩展，在大图处理方面取得了非常好的性能。但是，其预处理开销很大，需要对shard里的边进行排序。因此，X-Stream提出了edge-centric的计算模型，该模型不需要对边进行预处理，并且能够充分利用磁盘的顺序访问带宽。
X-Stream同样是 一个基于磁盘的单机大规模图计算系统，但是不同于GraphChi的vertec-centric计算模型，其采用了edge-centric的计算模型，计算过程中的状态同样保存在顶点上。Edge-centric的计算模型能够顺序访问图的边集，从而更好地利用磁盘带宽，然而会导致对顶点数据的随机访问。为了减少顶点数据随机访问带来的开销，X-Stream使用了streaming partition的方法，其将顶点分成多个子集，从而每一个子集的数据能够存储在高速存储中（对于内存中的图来说是cache，对于磁盘上的图来说是内存）。每一个顶点集（子集）与一个边partition相关联，该边集存储顶点集的所有出边。在scatter阶段，X-Stream处理所有的stream partition，对于每一个partition，将其顶点加载到内存中，然后stream磁盘上的边并生成更新，更新写入输出缓冲区；在shuffle阶段，对于输出缓冲区的每一个更新，将其追加到目的partition的本地输入缓冲区；在gather阶段，每一个partition从输入缓冲区读取更新，并更新节点状态。
Ligra
Ligra是一个基于共享内存的轻量单机图计算系统，适合于迭代计算。Ligra提供了一套基于顶点集合和边集合的编程接口，用户可以分别调用这两个原语对所有活跃的顶点或活跃的边进行处理，处理的具体内容取决于用于自定义函数。对于活跃边集的处理，Ligra巧妙地利用了push和pull两种处理模式在并行图计算环境下所具有的不同优劣，在运行时根据用户提供的阈值能够在两种模式之间进行切换。
Ligra采用了点边混合计算的编程模型，提供了两个编程接口vertexmap和edgemap。Vertexmap对一个活跃顶点集进行处理，一个用户自定义函数作用在该顶点集的每一个顶点上，对该顶点进行处理。同理，edgemap对一个活跃边集进行处理，一个用户自定义函数会作用在每一条边上，对边进行处理。但与vertexmap不同的是，edgemap具有push和pull两种不同的处理模式。在push模式下，会遍历每一个活跃节点，函数作用在活跃节点的所有出边上。push模式可以实现选择性调度，从而在活跃顶点出发的边比较少时跳过那些不需要参与计算的边，不利之处是需要用锁或原子操作来保证并发环境下数据修改的正确性，引入了额外的开销，这种模式适合于frontier较小的情况，活跃顶点集稀疏表示。在pull模式下，会遍历每一个目的节点，检查其源节点是否在活跃顶点集中，如果在，函数作用在该边上。Pull模式的优点在于数据的修改没有竞争，而劣势是必须查看所有的边，即使很多时候大多数边都不参与计算，这种模式适合于frontier较大的情况，活跃顶点集稠密表示。因此，Ligra能够根据用户提供的阈值，根据需要参与计算的边数，选择其中一种最为合适的模式进行计算，从而提高系统的性能。
Gemini
分布式图分析系统如Pregel、PowerGraph在获得了扩展性的同时性能较为低效，使用了上百核集群资源的分布式程序甚至不如精心优化的单线程程序；另一方面，扩展性却又至关重要，在处理规模较大的数据时，我们有时不得不通过多台机器的内存来容纳需要处理的图。由陈文光等的研究发现，分布式系统的瓶颈并不在于其着重优化的通信，而是在于计算部分，于是设计并实现了Gemini，一个以计算为核心优化目标的分布式图计算系统。
Gemini借鉴了Ligra中类似的思想，采用了push和pull两种不同的计算模式混合计算，将其从单机共享内存扩展到了分布式环境中。Gemini将两种模式下的计算过程细分成发送端和接收端两个部分，从而将分布式系统的通信从计算中剥离出来。
图数据的划分是所有分布式图计算系统的核心。Gemini采用了一种十分简单的划分方法：将顶点集进行块式划分，将这些块分配给各个机器，然后让每个顶点的拥有者（相应机器）维护相应的出边/入边。这种块式划分的方式保留了图的局部性特征；同时，由于每一个机器负责的均是一块连续的顶点，消除了分布式系统中图划分后顶点编号转换的开销。
GridGraph
GridGraph[8]是一个基于磁盘的单机大规模图分析系统。GridGraph将顶点集划分为p个一维分组，并根据所有边的出发顶点和目标顶点将边集划分为pxp个二维分组，组织成网格的形式。所有划分出来的数据块在运行时会在逻辑上合并形成更大的块以获得最佳的IO效率。GridGraph在处理时使用一种称为流式更新的一阶段模型，在扫描每条边时直接将更新实时作用到目标顶点上，因此只需对边进行一次只读的扫描即可完成一轮迭代的计算。同时，GridGraph实现了选择性调度来减少无用边的处理，可以显著地提升很多迭代算法的性能：当某个分组不包括活跃顶点时，从该顶点分组出发的所有边分组均可被跳过。最后，双层划分的引入则解决了系统应该选择粗粒度还是细粒度进行网格划分的矛盾，使得GridGraph可以同时在IO量、局部性和选择性调度上均获得较为满意的结果。
在编程API上面，GridGraph借鉴了Ligra，提出了一种名为流式更新的一阶段处理模型，其中包含两个主要的流处理算子：streamVertices和streamEdges。GridGraph在调用streamEdges时对边分组逐个的进行处理。在处理网格中第i行和第j列的的边数据时，系统需要让第i个和第j个顶点分组的数据处于内存中。在计算过程中，会有两个不同的窗口分别在顶点分组和边分组上滑动，故名为双滑动窗口。同时，为了减少IO数量，GridGraph引入了双层划分，在原先pxp划分的基础上，系统再叠加一个qxq的粗粒度划分。在使用了双层划分后，GridGraph先在粗粒度划分的网格上按列优先进行顺序处理，并在每个大格子的内部按照列优先的顺序处理细粒度的边分组。这样，GridGraph无需增加预处理开销即可实现双层的网络划分，并使得系统不需要以IO量的增加为代价便能获得较好的数据局部性和选择性调度效果。
GraphMat
GraphMat[9]一个高效的单机图计算系统。该框架同时结合的vertex-centric计算模型和矩阵计算模型的优势：用户可以使用最为熟悉的vertex-centric编程方式来编写图算法，之后，GraphMat在后端将其映射成下层高效的稀疏矩阵运算，从而既提高了用户的编程效率，又保证了算法的性能。
FlashGraph
近年来，基于固态硬盘（SSD）的外存扩展成为了图分析系统研究领域的一大热点。FlashGraph[10]是一个基于SSD阵列的单机大规模图计算系统。FlashGraph是一个半外存系统，其在内存中维护算法中的顶点状态，并在SSD中存储边数据。FlashGraph能够达到与内存图计算系统同等的性能，并且性能优于其他out-of-core的图计算系统。此外，FlashGraph采用vertex-centric的计算模型，并按需请求边列表，这是因为，SSD的顺序访问和随机访问之间的性能差距比普通机械硬盘要小很多。
为了达到与内存图计算媲美的性能，FlashGraph使用SSD阵列来实现高吞吐量和低存储延迟。但是，SSD的吞吐量和IO性能还是远远不如内存。为了应对这些挑战，FlashGraph建立在SAFS文件系统上，用该文件系统来重构IO调度、数据存储以及数据缓存，以实现现代NUMA多处理器的高并行性。
在FlashGraph中，边数据存储在SSD上，可以选择性地对其进行访问，同时应用了紧凑的边数据格式以减少IO量。SSD阵列由SAFS管理；为了提高性能，在SAFS中添加了异步用户任务IO接口，该接口允许在页面缓存中进行通用计算，因此可以减少访问页面缓存中的数据带来的开销以及内存占用。此外，FlashGraph通过将IO与计算重叠来减少IO开销。图引擎负责顶点程序的调度。为了优化性能，图引擎会合并顶点程序的相邻IO请求，这不仅减少了IO数量，同时还能进行顺序IO。
Graphene
Graphene[11]是另一个基于SSD的单机图计算系统。Graphene提出了以IO请求为中心的计算模式，在每一次迭代中，对IO请求返回的数据进行处理。以IO请求为中心的计算模式旨在图算法的编写以及IO任务的管理。同时，Graphene将所有的图数据看做512bytes的数据块，并使用bitmap进行索引，从而能够快速地进行排序、复制和合并IO请求等；Graphene采用了异步IO的方式，通过提交尽可能多的IO请求以充分利用闪存设备的IO带宽。在内存中，Graphene使用2MB大小的Direct HugePage（DHP）来存储图数据和元数据结构，比如IO buffer和bitamp。DHP的设计使得多个IO请求能够共享一个DHP，并且能够TLB miss率，对系统性能有较大提升。 另外，Graphene提出了row-column平衡的2维partition方法，保证每一个partition能够包含相同数目的边。通过这种图的partition方式，能够保证每一个SSD存储均衡；为了保证work balance，Graphene引入了work stealing机制。
LUMOS
LUMOS[12]是一个dependency-drive的基于磁盘的单机图计算系统。LUMOS引入了future value computation技术来减少磁盘IO，同时保证同步处理语义。顶点计算可以细化为两个关键部分：第一步，收集邻居节点进来的值，并进行聚合；第二步，使用收集到的值来计算顶点新的值。如果我们需要把所有（入）邻居顶点的值都收集到，再进行聚合，那么会限制future computation。因此，LUMOS采用部分聚合的方式，摆脱了需要所有incoming 顶点值的前提。当部分聚合收到所有需要的值以后，再来计算顶点值，计算出的值即可传递到后续的迭代中。
Arabesque
Arabesque是一个分布式的图挖掘系统。在图挖掘算法中，子图的数目会随着图的大小成指数增长，vertex-centric的模型难以应用到图挖掘算法中，这是因为，vertex-centric的模型可扩展性差，每一个embedding都需要复制到所有未来需要利用局部信息进行扩展的节点，同时，high-degree的顶点会成为“热点”，导致负载不均衡。因此，Arabesque采用了embedding-centric的编程模型。
Embedding-centric的API使得该系统能够有高度可扩展的实现。Arabesque通过将所有的embedding在所有的worker上均匀分布来实现扩展，从而避免某些worker成为“热点”。另外，Arabesque基于embedding canonicality的概念，引入了coordination-free的探索策略，从而能够避免大量的冗余工作和通信开销。
Arabesque引入了filter-process的计算模型。给定一个输入图，系统能够自动访问所有由用户自定义算法所决定的需要扩展的embedding，并以分布式的方式进行探索。系统会将所有的embedding传入由两个函数filter和process组成的应用中，filter作用在一个embedding上，返回true或false，表明embedding是否需要被处理，如果返回true，则process函数会对该embedding进行处理，返回一系列用户自定义值。
RStream
Rstream[13]是第一个基于磁盘的单机图挖掘系统，其使用磁盘来存储图挖掘的中间数据。RStream的编程模型借鉴了Datalog和GAS模型：Datalog中的关系操作能够将小的结构组成大的结构，使得用户能够很方便的开发图挖掘算法，而GAS是一个支持迭代图处理的编程模型，具有良好定义的终止语义。RStream通过将关系代数加入到GAS模型中，提出了一个新颖的编程模型GRAS，基于该模型，用户能够很方便的开发各种图挖掘算法。
GRAS即在GAS的基础上加入了relational阶段。RStream借鉴了X-Stream中的图的划分方法和工作方式。为了保持关系语义，RStream的编程界面将顶点集、边集以及update集合当做关系表。在scatter阶段，系统会生成update表。类似X-Stream，在该阶段，顶点表被加载到内存中，并通过stream对边表进行处理生成update，然后通过shuffle处理将所有的update shuffle到对应的顶点表update表中。之后，用户自定义的relational阶段会在每一个stream partition的update表和边表上执行，关系阶段的数目是自定义的。Relational阶段会产生一系列新的update表，其将作为gather-apply阶段的输入，来对每一个顶点计算新的tuple值，这些tuple值将在每一次迭代结束后保存到顶点表中。
AutoMine
AutoMine[14]是另一个单机图挖掘系统，为大规模图挖掘应用提供了高级抽象以及高性能，其弥补了图挖掘应用中高级抽象和高性能之间的“沟壑”。AutoMine为用户提供了一个高级API，不需要用户挖掘算法或系统的优化细节；同时，AutoMine能够以很低的算法复杂度和最小的内存开销将用户编写的代码编译成高效的C++代码。
AutoMine系统的工作流包括一个编译阶段和一个执行阶段。编译阶段通过调用三个模块来将用户通过高级API编写的代码编译成高效的C++程序。第一个模块是模式枚举器，模式枚举器能够理解所有的高级API语义，并枚举出所有非同构的子图模式；第二个组件是调度生成器，调度生成器会生成一个优化的调度（算法）来识别每一个子图模式，每一个调度用一个带有有向边的染色图表示；最后一个模块是代码生成器，代码生成器会生成最终的C++挖掘程序代码。在执行阶段，挖掘程序会处理输入图并返回最终结果。
Maiter
由于BSP并行模型可能存在性能瓶颈，而AP并行模型会浪费计算和通信资源并且某些算法在AP模型下不一定能够收敛，因此，Zhang[15]等提出了delta-based accumulative iterative computation（DAIC）的异步计算模型，并从理论上证明了，在满足特定条件下，基于DAIC的实现的异步图算法能够保证正确性和收敛性。Maiter是基于DAIC模型实现的异步并行分布式图计算系统，其保留了异步计算的高效性，同时保证了算法的正确性。
图表示学习与图神经网络
将机器学习和深度学习方法应用到图数据上也是当前的一大研究热点，由此催生了图表示学习和图神经网络[19]。图数据的复杂性对现有的机器学习算法提出了重大挑战。由于图具有复杂的结构，没有固定的节点顺序，并且图可能是动态的，因此一些重要的操作，例如卷积，在图像中易于计算，但是应用到图数据上却非常困难。此外，现有机器学习算法的核心假设是实例彼此独立，但是该假设不再适用于图数据。为了能够将传统的机器学习方法应用到图数据上，我们需要将图数据表示成欧几里得空间的数据，而这正是图表示学习所研究的内容。
一些比较著名的节点表示学习方法包括DeepWalk[16]、LINE[17]和Node2Vec[18]等。这些节点表示学习方法能够将网络中的节点表示为特征向量，使得该向量能够自带节点信息，例如在特征空间上，相似的节点会离得特别近，从而后续的一些图分析任务比如分类、集群和推荐等能够使用一些机器学习算法来解决。图神经网络同样需要学习节点或图的编码。比如，循环图神经网络旨在通过循环神经网络架构来学习节点表示，该网络假设图中的节点能够持续地与邻居节点交换信息，直到达到稳定平衡点；而卷积图神经网络将卷积操作从网络数据泛化到了图数据上，其主要思想是通过汇总节点自身的特征和邻居节点的特征来学习节点的表示。但与节点表示学习不同的是，图神经网络强调以端到端的方式解决图相关的问题，图神经网络是一组为各种任务设计的神经网络模型，而节点表示学习则是多种方法针对同一任务。
总结
大规模图数据分析是当前大数据研究领域的一大研究热点。本文中，我们首先介绍了当前大规模图分析分析系统中常见的系统架构、编程（计算）模型和并行模型，进一步对当前一些具有代表性的图分析系统进行了介绍和总结。
大规模图数据分析系统的发展目前还较为不成熟，如何高效地处理大图仍然面临着巨大的挑战。此外，将机器学习和深度学习方法应用到图数据分析上来也是当前的一大研究热点，即图表示学习和图神经网络。
Slides
报告分享的slides：Introduction to Graph Systems
参考文献
[1] Grzegorz Malewicz, Matthew H. Austern, Aart J. C. Bik, James C. Dehnert, Ilan Horn, Naty Leiser, and Grzegorz Czajkowski, Pregel: A System for Large-Scale Graph Processing, SIGMOD’10, June 6–11,2010, Indianapolis, Indiana, USA.
[2] Amitabha Roy, Ivo Mihailovic, Willy Zwaenepoel, X-Stream: Edge-centric Graph Processing using Streaming Partitions, SOSP ’13, Nov 03-06 2013, Farmington, PA, USA
[3] Julian Shun,Guy E. Blelloch, Ligra: A Lightweight Graph Processing Framework for Shared Memory, PPoPP’13, February 23–27, 2013, Shenzhen.
[4] Carlos H. C. Teixeira ∗ , Alexandre J. Fonseca, Marco Serafini,Georgos Siganos, Mohammed J. Zaki, Ashraf Aboulnaga, Arabesque: A System for Distributed Graph Mining, SOSP’15, October 4–7, 2015, Monterey, CA, USA.
[5] Joseph E. Gonzalez,Yucheng Low,Haijie Gu,Danny Bickson,Carlos Guestrin, PowerGraph: Distributed Graph-Parallel Computation on Natural Graphs, OSDI ’12
[6] Xiaowei Zhu, Wenguang Chen, Weimin Zheng, and Xiaosong Ma, Gemini: A Computation-Centric Distributed Graph Processing System, OSDI’16
[7] Aapo Kyrola, Guy Blelloch, Guy Blelloch, GraphChi: Large-Scale Graph Computation on Just a PC, OSDI’12
[8] Xiaowei Zhu, Wentao Han, and Wenguang Chen, GridGraph: Large-Scale Graph Processing on a Single Machine Using 2-Level Hierarchical Partitioning, USENIX ATC ’15
[9] Narayanan Sundaram, Nadathur Satish, Md Mostofa Ali Patwary, Subramanya R Dulloor,Michael J. Anderson, Satya Gautam Vadlamudi, Dipankar Das and Pradeep Dubey, GraphMat: High performance graph analytics madeproductive, Proceedings of the VLDB Endowment, Vol. 8, No. 11
[10] Da Zheng, Disa Mhembere, Randal Burns,Joshua Vogelstein,Carey E. Priebe,Alexander S. Szalay, FlashGraph: Processing Billion-Node Graphs on an Array of Commodity SSDs, FAST ’15
[11] Hang Liu,H. Howie Huang, Graphene: Fine-Grained IO Management for Graph Computing, FAST’17
[12] Keval Vora, L UMOS : Dependency-Driven Disk-based Graph Processing, ATC2019
[13] Kai Wang,Zhiqiang Zuo,John Thorpe,Tien Quang Nguyen,Guoqing Harry Xu, RStream: Marrying Relational Algebra with Streaming for Efficient Graph Mining on A Single Machine, OSDI’18
[14] Daniel Mawhirter,Bo Wu, AutoMine: Harmonizing High-Level Abstraction and High Performance for Graph Mining, SOSP ’19, October 27–30, 2019, Huntsville, ON, Canada
[15] Yanfeng Zhang, Qixin Gao, Lixin Gao, Cuirong Wang, Maiter: An Asynchronous Graph Processing Framework for Delta-based Accumulative Iterative Computation,
[16] B. Perozzi, R. Al-Rfou, and S. Skiena, “Deepwalk: Online learning of social representations,” in Proceedings of the 20th ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2014, pp. 701–710.
[17] J. Tang, M. Qu, M. Wang, M. Zhang, J. Yan, and Q. Mei, “Line: Large-scale information network embedding,” in Proceedings of the 24th international conference on world wide web. International World Wide Web Conferences Steering Committee, 2015, pp. 1067–1077.
[18] A. Grover and J. Leskovec, “node2vec: Scalable feature learning for networks,” in Proceedings of the 22nd ACM SIGKDD international conference on Knowledge discovery and data mining. ACM, 2016, pp. 855–864.
[19] Z. Wu, S. Pan, F. Chen, G. Long, C. Zhang, and P. S. Yu, “A comprehensive survey on graph neural networks,” arXiv preprint arXiv:1901.00596, 2019.