图是由点和边构成的一种古老的数据结构，已有上百年历史。由于其优秀的表达能力和坚实的数学基础，图已经在物理、生物、计算机科学等众多领域得到了广泛应用。仅以计算机科学领域为例，图被用来表示通信网络、数据组织、计算流和数据流等。当前广泛应用的分布式计算框架如Dryad、TensorFlow等均根据有向无环图（DirectedAcyclicGraph，DAG）作为基本的作业模型。而对互联网和社交网络拓扑结构的分析则揭示了其小世界（smallworld）和无尺度（scale-free）特性。随着信息技术的持续进步以及数据量的不断增长，图上的运算面临越来越多的挑战，基于图的数据处理和分析已经形成了“图计算”这一专门的研究方向，吸引着越来越多的研究者投身其中。
与其他应用相比，图计算应用具有以下几个主要特点：
1.具有很高的访存计算比。即应用的很大一部分时间都花费在了数据读写（访存）方面，而真正用于计算的时间并不多。对于这类应用而言，其性能的瓶颈在于内存和I/O带宽，优化的关键在于提升数据加载速度，尽可能减少Cache-内存-外存之间的数据交换。此外，重叠计算和通信也会有所帮助。2.数据局部性差。数据局部性是为了应对处理器Cache、内存和外存的读写性能差异而引入的提升性能的重要举措，其核心是提升Cache利用率。然而，由于计算模式的多样性以及图顶点之间关联关系的复杂性，尽管已经有了不少优化数据局部性的措施，但现有的图计算应用对系统Cache的利用率通常都不高。3.类型与操作多样。图有很多种类型，从边的连接关系来看，分为有向图、无向图和混合图等；从图本身的特性来看，分为正则图、完全图、二分图、连通图等。图上的操作也是多种多样的，从最简单的度（degree）数统计、邻接点查找、遍历，到复杂的路径查找、着色、流分析（如最大流最小切割）、子图匹配、种子集扩充（seedsetexpansion），在应用中均有所涉及。二者耦合，产生了丰富的应用场景。4.规模巨大，结构不规则。随着社交网络的发展，现实生活中规模达数千万乃至上亿条边的图已经变得十分普遍。更为重要的是，这些图往往遵循幂律（powerlaw）分布，即顶点的度数非常不均匀，一小部分顶点拥有大量的连接，而大量的点只有有限的几条边与之相连，给数据的高效处理带来了巨大的困扰。上述应用特点并不是孤立的，而是相互交织在一起的。类型与操作多样表明，我们很难找到满足所有应用场景的最优计算方式，甚至连次优方式都很难做到，这也是有大量相关工作存在的最根本的原因。从体系结构的角度来说，由于数据访问速度的差异，高的访存计算比意味着系统Cache的利用率十分重要，然而，图数据本身局部性差使得其对Cache的利用率先天不足。图的巨大规模超出了单台物理机的处理能力，必须扩展到分布式环境中去计算，而局部性差意味着系统需要耗费更多的时间进行大量数据的跨节点传输，而这进一步降低了数据处理的效率；在分布式环境中，由于作业的结束时间就是最后一个任务的结束时间，各个节点之间的负载不均衡会极大影响应用的效率，而结构的不规则如果不加以精心处理，不可避免地会引起负载不均衡。综上，图计算的效率优化是一个非常复杂的问题，充满了挑战。
图计算的一般模型：
计算的基本目标是描述清楚应用需求，在应用需求和硬件环境之间架起桥梁，使得需求中所指定的各种运算能够高效地在给定的硬件上完成，图计算也是如此。应用需求是通过编程模型来描述的，编程模型的易用性和表达能力在很大程度上直接决定了框架的生命力，同时也影响到执行优化的空间；而运算的完成则是由执行框架负责的，它在编程模型所描述的应用需求的指导下，结合硬件环境的特点，自动完成数据的划分、任务到硬件环境的映射（即任务调度）、数据传输和任务执行管理。现有的执行框架通常都支持负载的自动扩展和容错等功能，通过屏蔽底层硬件环境的细节，使得用户能够