图数据库 | 4、图数据库三大组件之一 ——图计算 （上）
图数据库 | 4、图数据库三大组件之一 ——图计算 （上）
图数据库是当前大数据和人工智能领域的重要技术，其中图计算组件更是至关重要的部分。本文将详细介绍图计算的基础概念、查询模式、数据结构以及计算效率等方面的内容，帮助读者深入理解图数据库的核心技术。
在图数据库中有三大组件——图计算、图存储以及图查询语言。接下来，将分别进行介绍。
先从图计算开始。图计算组件是至关重要的。传统数据库架构以存储为中心，计算通常是依附存储引擎而存在的；而在图数据库中，因为要解决高性能计算、复杂遍历查询计算的效率问题，所以图计算的重要性不言而喻！
一般情况下，图计算可以等同于图数据库，毕竟图数据库最重要的工作就是图计算。然而，从图论以及数据库的发展历程来看，在相当长的一段时间内，图计算框架基本是独立发展的，而图数据库是近20年内才开始形成的。最早的图计算的内容是研究一些基于图论的算法，例如1959年发表的Dijkstra算法（一种在道路网络中寻找最短路径的算法） 。在图数据库的语境下，图计算关注的是如何高效地完成数据库的查询、计算、分析，以及对数据的动态调整。（了解更多图计算与图数据库的异同点，可点击链接——图计算与图数据库差异简析）
一、图计算的基础概念
了解图计算的基础概念之前，需要先了解图论的基础概念，它是欧拉于18世纪上半叶（1736年）开创的。
图论研究的对象就是图——若干顶点及连接顶点的边所构成的空间拓扑结构（图形） ，这种图形用来描述事物（顶点）之间的某种关系（边） 。显然，我们所说的图形就是网络，而图计算的本质就是面向复杂网络的计算，或者是面向关联数据与关联关系的计算。
很多我们日常生活中接触的数据类型在本质上都是图论的研究对象，如集合、树、列表、堆栈、队列、数组或向量。
细心的读者一定会问：数组是离散的数据，为什么也会是图论的研究对象？因为虽然图论研究的是复杂网络，但是在极端的情况下，网络中只存在一组顶点而没有边，这些离散的点就是一组数组。同样的逻辑，基于表结构的关系型数据库可以看作一种二维数据库，而图数据库本质上是一种高维的数据库，高维可以向下兼容低维，反之则非常困难。
图计算中最关注的有如下几点：
·基础的计算与查询模式；
·常见的数据结构；
·关于计算效率的讨论。
1.查询模式
我们先来看看图计算中有哪些基础的查询模式，从不同角度看有不同的分类方式。
1）从关联还是离散的角度看，可以分为离散查询（discreted query）和关联查询（connected query） 。
最典型的离散查询是面向元数据的查询，在图计算、图数据库的语境下，元数据（meta-data）指顶点或边，这两者是最小颗粒度的数据，通常用唯一的ID来标识，不需要再作细分。所有仅面向顶点或边的操作，都是典型的离散类型操作。
有的读者对边是否算作元数据表示困惑，认为边并非独立存在，它因为关联顶点而看起来像是一个复合数据结构。需要指出的是，元数据的定义一方面是最小颗粒度、不可再分，另一方面是有唯一匹配的ID来定位它。而在图数据库中，只有顶点和边符合这两点。但是，边的表达的确更为复杂，因为边上面除了ID外，还会关联起点与终点、方向以及其他属性。有一些图计算系统中会对边进行切割，也就是说关联一条边的两个顶点可能会被切分存储在不同的分片中，但是这种切边设计的系统比较少见，且计算效率很低（相比于切点而言的分片逻辑） 。
关联查询是图数据库相比于其他数据库而言最有特色的图计算操作。例如，路径查询、K邻查询、子图查询、组网查询、各类图算法等都属于典型的关联查询。关联查询通常是从某个顶点（或多个顶点）出发，通过对边、点以及它们各自的属性进行过滤，来返回相关联的数据集。从关系型数据库的视角看，这种关联查询类似于表连接的操作，然而，图计算所能带来的灵活性与高性能是关系型数据库无法比拟的。
2）从图上的查询（遍历操作）方式来看，可以分为广度优先（BFS）和深度优先（DFS） 。广度优先的遍历最为典型的是K邻（K-Hop）和最短路径查询。以K邻为例，它的原始定义是，从某个顶点出发，查找和该顶点最短路径距离为K跳（步、层）的所有不重复的顶点集合。
K邻计算的逻辑是如果想知道某个顶点第K层的全部邻居，需要先知道它的全部K-1层邻居，依此类推。换个角度描述为：从该顶点出发，先要找到它的第一层的全部邻居，再到第二层，直到找到第K层所有的邻居为止。
K邻操作在数据量巨大且高度联通的数据集上的计算复杂度可能非常大，因为从任何一个节点出发，只要K值够大，就可以联通到所有的节点上去。在金融场景中，以信用卡交易数据的图计算为例，所有的信用卡和它们的交易对手POS机之间形成的交易网络几乎是完全联通的（这个假设的前提是，每一张卡只要消费，就会至少和某个POS机关联，而这个POS机还会与其他卡交易，其他卡还会与更多的POS机关联，这样的网络是高度联通的，甚至是不存在孤点的。在实际操作中，孤点可能会被直接剔除，因为它们对于关联查询是没有意义的） ，见图2-1。
图2-1 信用卡和POS机之间形成的交易网络
图2-2演示了2种不同类型的K邻操作：
·仅返回第K跳邻居；
·返回从第1跳到第K跳的全部邻居。
图2-2 K邻操作示意图
其中第K跳邻居指的是距离原点最短路径为K的全部邻居数量。以上两种操作的区别仅仅在于到底第K跳邻居是只包含当前层的邻居，还是包含前面所有层的邻居。
例如K=3时，仅返回第3层邻居，但当K是一个范围值[1,3]时，该操作的返回值显然大于前者，因为它还额外包含了K=1和K=2情况下的最短路径邻居的数量。
如果把K=[1,2]和K=3的K邻返回数值相加，总和应等于K=[1,3]的K邻值。这也是通过K邻计算来验证一个图数据库或图计算系统准确性的一种典型手段。笔者注意到，由于图计算的复杂性而造成的系统性的图计算准确性问题是普遍存在的，例如第K-1层的顶点重复出现在第K层，或者第K层中出现同一个顶点多次，这都属于典型的图计算的广度优先遍历算法实现存在Bug的情况。
图2-3展示的是典型的BFS与DFS在遍历一张有向图时经过节点的顺序差异。
图2-3 BFS与DFS示意图
深度优先算法常见于按照某种特定的过滤规则从图中某个顶点出发寻找另一个或多个顶点之间的联通路径。例如，在银行的交易网络数据中，寻找两个账户之间全部单一方向的按时序降序或升序排列的转账路径。
理论上，广度优先和深度优先算法都可以完成同样的查询需求，区别在于算法的综合复杂度与效率，以及对计算资源的消耗。另外，图2-3中的遍历算法是典型的单线程遍历逻辑，在多线程并发遍历的情况下，每个顶点被遍历时的途径顺序会产生变化，这在后面的章节中再详细剖析。
2.数据结构与计算效率
可以用来进行图计算的数据结构有很多种，前面已经提到过一部分，这里将梳理得更为清晰。我们通常把数据结构分为原始数据结构和非原始数据结构，如图2-4所示。
图2-4 数据结构分类示意图
原始数据结构是构造用户定义数据结构的基础，在不同的编程语言中对原始数据结构的定义各不相同，例如，短整型（short） 、整数（int） 、无符号整数（unsigned int） 、浮点数（float、double） 、指针（pointer） 、字符（char） 、字符串（string） 、布尔类型（boolean）等，这里不再赘述，有兴趣的读者可以查询相关的工具书和资料，本书关注更多的是用户系统（图计算框架或图数据库）定义的线性（linear）或非线性（nonliniear）数据结构。在不考虑效率的前提下，几乎任何原始数据结构都可以被用来组合和完成任何计算，然而它们之间的效率差距是指数级的。如图2-4所示，图数据结构被认为是一种复合型、非线性、高维的数据结构，用来构造图数据结构的原始或非原始数据结构有很多种，例如常见的数组（array） 、栈（stack） 、队列（queue） 、链表（linked list） 、向量（vector） 、矩阵（matrix） 、哈希表（hash table） 、Map、HashMap、树（tree） 、图（graph）等。
在具体的图计算场景中，到底使用哪些数据结构需要具体分析，主要考虑以下两个维度：
·效率及算法复杂度；
·读写需求差异。
以上两个维度经常是交织在一起的，例如只读的条件下意味着数据是静态的，那么显而易见连续的内存存储可以实现更高效的数据吞吐及处理效率；如果数据是动态的，数据结构就需要支持增删改查操作，那么就需要更复杂的存储逻辑，也意味着计算效率就会降低，我们通常说的用空间换时间就是这种情况。这里再次重申，在不同的上下文中，图计算的涵义可能大相径庭，图数据库的图计算引擎组件毫无疑问需要支持动态、不断变化的数据；学术界实现的图计算框架则大多只考虑静态数据。这两种图计算所适用的场景和各自能完成的工作差异巨大，笔者所写所谈所涉及的内容属于前者——图数据库，对于后者，有兴趣深入了解的读者可以参考GAP Benchmark及其他图计算实现。
很多现实世界中的应用场景都用图数据结构来表达，尤其是这些应用可以被表达为网络化的模式时，如交通道路网络、电话交换网络、电网、社交网络、金融交易网络。业界范围内很多赫赫有名的公司（例如谷歌、脸书、高盛、黑石）都是基于图技术而构建的。
图2-5展示了一个典型的社交图网络的局部。它实际上是在一张大图上进行的实时路径查询所生成的一张子图。A节点为初始顶点，B节点为终止顶点，两者有15层间隔，并有100条关联路径，每条路径上有不同类型的边连接着两两相邻的顶点，其中不同类型（属性）的边以不同的色彩来渲染，以表达不同类型的社交关系（帮助、喜欢、爱情、合作、竞争等） 。
图2-5 典型的社交网络图谱（实时生成的子图）
图的数据结构大体包含以下3种类型的数据：
1）顶点，也被称作点、节点。顶点可以有多个属性，下面的边也一样，有鉴于此，某个类型顶点的集合可以看作传统数据库中的一张表，而顶点间基于路径或属性的关联操作则可看作传统关系型数据库中的表连接操作，区别在于图上的连接操作效率指数级高于传统数据库。
2）边，也被称作关系。一般情况下，一条边会连接2个顶点，2个顶点的排列顺序可以表明边的方向，而无向边通常通过双向边来表达，所以A-B=A←→B=A→B+B→A。而那种特殊类型的关联多个（≥3）顶点的边，一般都被拆解为两两顶点相连的多条边来表达。
3）路径，表达的是一组相连的顶点与边的组合，多条路径可以构成一张网络，也称作子图，多张子图的全集合则构成了一张完整的图数据集，我们称之为“全图” 。很显然，点和边两大基础数据类型的排列、组合就可以表达图上的全部数据模型。
在图中，数据类型的表达如下。
·顶点：u、v、w、a、b、c……
·边：(u,v)……
·路径：(u,v)、(v,w)、(w,a)、(a,b)……
注意，边的表达形式(u,v)通常代表有向边，也就是说边是存在方向的，即括号中的u和v指代不同的涵义，方向是从u指向v，我们也称u为out-node（出点） ，v为in-node（入点） 。如果是无向图，则括号中的出点、入点顺序并不重要。在实际的数据结构设计中，也可以使用额外的字段来表明边的方向，例如(u,v，1)和(v,u，-1)表达了u→v这条边的正向与反向边，即从u出发到v是正向边，而从v到u存在一条反向边。之所以要表达反向边是因为如果不存在从v到u的边，那么在图上（路径）查询或遍历的时候，将不会找到从v出发可以直接到达u的任何边，也就意味着图的连通度受到了破坏，或者说数据结构的设计和表达没有100%反映出真实的顶点间的路网连接情况。
传统意义上，用来表达图的数据结构有3类：相邻链表（adjacency list） 、相邻矩阵（adjacency matrix） 、关联矩阵（incidence matrix） 。
相邻链表以链表为基础数据结构来表达图数据的关联关系，如图2-6所示，左侧的有向图（注意带权重的边）用右侧的相邻链表表达，它包含了第一层的“数组或向量” ，其中每个元素对应图中的一个顶点，第二层的数据结构则是每个顶点的出边所直接关联的顶点构成的链表。
注意，图2-6中右侧的相邻链表中只表达了有向图中的单边，如果从顶点4出发，只能抵达顶点5，却无从知道顶点3可以抵达顶点4，除非用全图遍历的方式搜索，但那样的话效率会相当低下。当然，解决这一问题的另一种方式是在链表中也插入反向边和顶点，类似于上面提及的用额外的字段来表达边的方向，进而来表达反向边。
图2-6 用相邻链表（右）来表达单边有向图（左）
相邻矩阵是一个二维的矩阵，我们可以用一个二维数组的数据结构来表达，其中每个元素都代表了图中两个顶点之间存在一条边。有向图用相邻矩阵AM来表达，如表2-1所示，每条边需要用矩阵中的一个元素来对应行、列中的一个顶点，矩阵是6×6的，并且其中只有7个元素（7条边）是被赋值的。很显然，这是一个相当稀疏的矩阵，占满率只有(7/36)<20%，它所需要的最小存储空间则为36B（假设每个字节可以表达其所对应的一条边的权重） 。如果是一张有100万顶点的图，其所需的存储空间至少为100GB（1M×1MB） ，而在工业界中动辄亿万量级的图中，这还只是属于占比仅1%的小图。
也许读者会质疑以上相邻矩阵的存储空间估算被夸大了，那么我们来探讨一下。如果每个矩阵中的元素可以用1个比特位来表达，那么100万顶点的全图存储空间可以降低到12.5GB。然而，我们是假设用1B来表达边的权重，如果这个权重的数值范围超过256，我们或许需要2B、4B甚至8B，如果边还有其他多个属性，那么对于存储空间就会有更大的甚至不可想象的需求。现代GPU是以善于处理矩阵运算而闻名的，不过通常二维矩阵的大小被限定在小于32K（32 768）个顶点。这是可以理解的，因为32K顶点矩阵的内存存储空间已经达到1GB以上了，而这已经占到了GPU内存的25%～50%。换句话说，GPU并不适合用于大图上面的运算，除非使用极其复杂的图上的Map-Reduce方式来对大图进行切割、分片来实现分而治之、串行的或并发的处理方式。但是这种处理方式的效率会很高吗？
关联矩阵是一种典型的逻辑矩阵，它可以把两种不同的图中的元数据类型顶点和边关联在一起。例如每一行的行首对应顶点，每一列的列首对应边。仍以上面的有向图为例，我们可以设计一个6×7=42元素的二维带权重的关联矩阵，如表2-2所示。
表2-2的二维矩阵仅能表达无向图或有向图中的单向图，如果要表达反向边或者属性，这种数据结构显然是有缺陷的。
事实上，工业界的图数据库极少用以上三种数据结构，原因如下：
·无法表达点、边的属性；
·无法高效利用存储空间（降低存储量） ；
·无法进行高性能（低延迟）的计算；
·无法支持动态的增删改查；
·无法支持复杂查询的高并发。
综合以上几点原因，我们可以对上面提及的相邻链表数据结构进行改造，或许就可以更好地支持真实世界的图计算场景。今天先写这么多，结合计算效率来评估与设计图计算所需的数据结构，在下期内容继续。