图数据压缩技术综述*

李凤英，杨恩乙，董荣胜

(桂林电子科技大学可信软件重点实验室,广西 桂林 541004)

1 引言

随着大数据时代的到来，数据规模以前所未有的方式不断增长，数据结构也呈现出复杂性和多样性。如何对其有效地描述、存储和分析已成为当前的研究热点和难点。图通常被看成是一系列节点和节点关系的集合[1]，节点对应于实体，边对应于实体关系，非常适合描述关联性数据及内部有一定结构的数据，如社交网络[2]、知识图谱[3]等。

研究表明，大多数领域的问题都可以通过图的相关理论来解决。在Web网络分析[4]中，实体和它们的关系可以表示成有向无权图，节点表示网页，边表示网页之间的链接，节点标识表示不同的域名。在这种表示形式下，查询给定的实体关系和侦测特定的团体，可以转化为图的邻居查询和子图匹配[5 - 7]问题。在化学数据分析中，从给定的化合物集中挖掘常见的原子团，可以转化为频繁子图查询[8]问题。在蛋白质交互网络分析中，衡量给定的某2个蛋白质发生作用的概率时，可以用不确定图[9,10]建模得以解决。可见，图在众多领域都有着重要的研究价值。

随着图在各个领域的广泛应用，传统的图存储结构已经不能支持超大规模图数据的管理和分析。比如具有一百万个节点的社交网络，邻接矩阵的大小(2个节点之间的1条边存储空间为1 bit)大约为116 GB，大多数计算机不会有如此大的主存储器来加载图并执行社交网络分析。中国互联网络中心2018年发布的《第41次中国互联网络发展状况报告》[11]中提到，网页的数量约为2 600亿。若采用图模型存储上述网页节点及节点关系，至少需要42 TB的存储空间。并且随着因特网的不断发展，需要的存储开销也越来越大。如何存储和操作上亿万个节点的图数据，国内外研究人员主要从以下3个方向做了大量的研究：

(1)外部存储技术[12,13]：针对大规模图数据无法一次装入内存问题，研究人员一方面将图数据存储到价格低廉、容量大的外部存储器(硬盘或软盘)，另一方面设计更加高效的I/O算法来避免更多的I/O开销。

(2)分布式存储技术[14]：将图数据分割为多个部分，存储到不同的分布式计算机中，但这会带来更多的通信开销和CPU资源消耗。

(3)图数据压缩技术[15 - 17]：主要思想是消除图数据中的冗余信息，将图数据以压缩的形式存储到内存中。

相对前2种技术，第(3)种技术时间开销相对降低，而且可以适用于任何类型的图数据。

本文主要从3个方面讨论图数据压缩技术:

(1)基于邻接矩阵的压缩技术，主要思想是尽可能地压缩邻接矩阵中的“0”元素。

(2)基于邻接表的压缩技术，主要思想是利用节点的邻居节点集的相似性和局部引用性来进行压缩。

(3)基于形式化方法的压缩技术，主要思想是对所给的图进行编码，使其转化为布尔代数，再利用决策图对布尔代数进行表示和化简。

本文的结构如下：首先介绍3类压缩技术，分别为基于邻接矩阵的压缩技术、基于形式化方法的压缩技术和基于邻接表的压缩技术。在此基础上，为了充分说明形式化方法对于图数据压缩的优势，我们给出了相关的实验数据对比，并预测了未来图数据压缩发展方向。

2 基于邻接矩阵的压缩技术

Broder等人[18]和Raghavan等人[19]的研究表明，大量的图特征函数服从幂律分布，其邻接矩阵往往具有一定的稀疏性和聚类性。Brisaboa等人[20]利用邻接矩阵的特征提出了k2-tree，取得了较好的时间/空间均衡。k2-tree的构造过程主要包括以下2个步骤：

步骤1对于1个给定的n×n邻接矩阵，首先判断n是否为k的幂。若满足条件，转到步骤2；若n不是k的幂，增加矩阵中的行和列使得n=ks(s为正整数)，其中增加的行和列的元素用“0”填充，然后再转到步骤2进行递归划分。

步骤2进行递归划分：根据MXQuntree规则[21]把矩阵划分为k2个大小一致的子矩阵。如果子矩阵中的元素至少有1个为1，那么把这种矩阵标记为1,否则标记为0,自上而下，自左而右排列这些值，它们将作为根节点的4个儿子节点，树的第1层节点构造完毕。将标记为1的矩阵再进行递归处理，它们的值将作为树的第2层节点，如此重复直到划分后的矩阵全部为0或者已经划分到原始矩阵中的某个元素，递归停止。

如图1所示是1个具有4个节点的网页图所对应的邻接矩阵以及k2-tree(n是k的幂)。图2所示是1个具有11个节点的网页图所对应的邻接矩阵以及k2-tree(n不是k的幂)，矩阵中的深色部分是为满足条件所增加的行和列。

Figure 1 k2-tree corresponding to 4*4 adjacency matrix(k=2)图1 4×4 邻接矩阵所对应的k2-tree(k=2)

Figure 2 Extension of matrix and construction of k2-tree when k=2图2 k=2 时矩阵的拓展和k2-tree 构建

如图2所示，若用邻接矩阵来存储节点数为11的网页图，需要的存储空间为121 bit。若采用k2-tree存储，存储空间为72 bit。可见k2-tree比邻接矩阵具有更好的空间利用率，并且随着图节点数目的不断增加，k2-tree节省的存储空间会越来越多。不仅如此，k2-tree还支持在常数时间范围内查询节点的直接邻居和反向邻居。

k2-tree能够紧凑地表示图数据，但传统的k2-tree对于图的邻接矩阵的压缩还存在不足：(1)网页图中的节点和链接分布严重依赖于URL排序。若采用传统的k2-tree思想机械地划分网页图，会导致稠密区域和稀疏区域划分到同1个子矩阵中，这会使得空间利用率降低。(2)k2-tree的邻居查询时间与k2-tree的高度成正比，面对上亿个节点的图数据，若不对其进行处理，邻居查询时间会大大增加。

为了更加有效、紧凑地压缩表示网页图，Claude等人[22]利用网页图中域特有的规律，提出了k2-partition。他们沿着对角线把图划分成不同的域，对不同的域用传统的k2-tree表示，实现了较好的时间/空间均衡。以下用实例来说明如何对图数据进行k2-partition表示。

采用传统的k2-tree表示图2中的矩阵需要72 bit的存储空间，而采用k2-partition表示图3和图4中的矩阵，需要的存储空间为64 bit，存储空间需求有所改善，并且随着图节点的增加，效果会越来越明显。在传统的k2-tree中查询给定节点的邻居信息的时间与树的高度成正比，在k2-partition中由于降低了树的高度，因此能获得更好的查询时间。

Figure 3 Dividing the graph into domains图3 对图进行分域处理

Figure 4 k2-tree representation of different domains图4 不同域的k2-tree表示

出于对多维数据如时序图(节点关系随时间改变的动态图)、社交网络图和引文网络图紧凑表示的需要，Caro等人[23]利用k2-tree的构造思想提出了kd-tree。kd-tree是k2-tree的一般化形式，通常用来表示d维的二元矩阵，对于1个规模为n1×n2×…×nd的d维矩阵，将其递归地划分为kd个子矩阵，为了简化分析，假设对于每一个i(d≥i≥1)都有ni=n，其中每1个树中的节点都拥有kd个儿子节点来表示对应的子矩阵。对于每1个子矩阵，按照从高维到低维的次序来确定kd-tree中的第1层至最后1层的值，如果子矩阵存在“1”值的元素，使用“1”来表示，如果为“0”，使用“0”来表示。图5表示了不同维度下kd-tree(k=2)表示方法。

3 基于形式化方法的压缩技术

Figure 5 Construction of kd -tree in different dimensions(d is the dimension of data,k=2)图5 不同维度的kd-tree的构建(d为数据的维度，k=2)

二叉决策图BDD(Binary Decision Diagram)作为一种新型的数据结构，不仅是解决布尔代数表示与计算的最为有效的工具[24 - 26],还是符号模型检验技术[27,28]的核心。2007年,杨志飞等人[29]将符号计算运用到大规模图数据的压缩表示中，核心思想是将图中的节点进行二进制编码，把图中的链接关系转化为布尔代数，进一步布尔代数可以通过有序二叉决策图OBDD(Ordered Binary Decision Diagram)求解。利用布尔代数中节点取值的冗余，衍生出OBDD的化简规则和删除规则，以此来共享子图，提高存储效率。在这种表示形式下，查询图中节点的度数、判断2个节点是否存在链接关系、向图中增加或者删除边和图的同构问题分别可以转化为OBDD的可满足性问题、OBDD的求值操作、OBDD的apply操作和OBDD的等价性判定[30]。将图转化为OBDD的具体思想为：对于1个具有n个节点的有向图，利用布尔变量对节点和边进行编码，将其转化为布尔表达式。如图6a中具有4个节点，故需要2个布尔变量。对于图6a中的有向边，则需要2组布尔变量来分别表示有向边的起点和终点，设有向边的起点用x=x1x2表示，终点用y=y1y2表示，其中x1，x2，y1，y2∈{0,1}，由于节点0和节点1存在有向边，设节点0的编码为x′1x′2(表示x1取1，x2取1)，节点1的编码为y′1y2(表示y1取1，y2取1)，则有向边可表示为x′1x′2y′1y2。基于上述方法，编码每1条边，便可得到该图对应的OBDD，如图6b所示是图6a有向图所对应的OBDD。由于OBDD的终节点只能为0或1,所以它只能表示无权图。Bahar等人[31]提出了代数决策图ADD(Algebraic Decision Diagram)，进一步把布尔代数拓展到伪布尔代数，将无权图拓展到带权图，进一步丰富了图的布尔代数表示方法。将图转化为ADD的思想和OBDD类似，其中的区别在于ADD的终节点不再是0或1，而是图中存在的每1条边的权重值。如图7所示是4个节点的带权有向图所对应的邻接矩阵MG以及代数决策图。

Figure 6 An OBDD representation of a digraph图6 有向图的OBDD表示

Figure 7 An ADD representation of a weighted graph图7 带权图的ADD表示

随着图数据规模的不断增长，如何更加有效地紧凑表示图数据，成为当前的一个研究重点。文献[20]提到k2-tree能很好地压缩邻接矩阵，实现较好的时间/空间均衡，但k2-tree还面临以下问题：(1)k2-tree中还存在大量的同构子树。(2)k2-tree只能对稀疏图进行压缩。(3)k2-tree只能表示静态图，不能向其中增加或者删除边。

针对上述问题，董荣胜等人[32]把多值决策图MDD(Multi-value Decision Diagram)[33]和k2-tree进行结合,提出了k2-MDD，利用MDD的删除规则和化简规则以及多变量取值性质进行相同子图的合并，构造过程主要包括3步：

步骤1将所给的邻接矩阵用传统的k2-tree表示。

步骤2删除k2-tree中所有的0节点，合并k2-tree叶子节点中为1的节点。

步骤3对k2-tree每个分支进行二进制编码(k=2)，节点值相等且儿子节点相同的节点合并(共享子图)。

图8所示是11个顶点的邻接矩阵的k2-tree表示。图9所示是传统的k2-tree中的同构子树的分布，相同的子树用大小相等的方框注明。图10表示k2-tree的MDD。

Figure 8 k2-tree representation of an adjacency matrix图8 邻接矩阵的k2-tree表示

Figure 9 Isomorphic subtree distribution of k2-tree图9 k2-tree的同构子树分布

Figure 10 MDD representation of a k2-tree图10 k2-tree的MDD表示

4 基于邻接表的压缩技术

根据研究表明，如果所有网页图的URLs按照字典序排序，大多数的网页图具有以下2种特性[34,35]:

(1)局部性：对于某个页面来说，它的直接邻居集合彼此之间挨得很近。

(2)相似性：位置上靠得很近的一些网页集，它们的后继集很相似。

利用网页的局部性，Boldi等人[36]提出了空隙编码,其思想为用2个连续的节点标签值来替代原始节点标签值，设A(x)=(a1,a2,a3,…,an)，x为第x个节点的标签值，a1,a2,a3,…,an为x的直接邻居，则x对应的空隙编码为B(x)=(c(a1-x),a2-a1-1,a3-a2-1,…,an-an-1-1)。式(1)为计算A(x)中a1的空隙编码标签值。

(1)

表1是网页图中截取的小部分邻接表，表2是邻接表对应的空隙编码。

Table 1 Traditional adjacency table representation表1 传统的邻接表表示

Table 2 Void coding representation表2 空隙编码表示

图数据规模的不断增长使得节点标签值的位数不断增加，空隙编码的本质为压缩节点的标签值，减少所需要的存储空间。

利用网页的相似性，Suel等人[37]提出了参考压缩，其思想是用1个节点的邻接表来表示其余的邻接表，设s(x),s(y)分别为2个节点的出度表，s(x)称为参考表，s(y)称为复制表，y-x称为参考系数，用r表示。若s(x)的后继在s(y)中也存在，那么复制表中对应位置为1，否则为0。进一步若s(y)的后继在s(x)中不存在，记这些节点为额外节点。表3是邻接表的参考压缩。

上述2种技术都要求节点的直接邻居集合是有序的，如果网页图需要保存最原始的链接顺序，上面的方法并不适用。

Adler和Faust等人[38,39]2010年发现，

Table 3 Reference compressed of adjacency table表3 邻接表的参考压缩

邻接表的节点之间的后继有许多相似的信息，这意味着数据还存在一定的冗余[38,39]，Repair算法[40]应运而生。其算法思想是把所有节点的后继看成1个序列T，每1次在序列中用s(s为从来没有在T中出现的符号)替换T中最频繁的符号对，直到序列T不再出现频繁模式。假设图G=(V,E)，T(G)=v1v1.1v1.2v1.3…v1.nv2v2.1v2.2v2.3…v2.n…vnvn.1vn.2vn.3…vn.n，其中v1为第1个节点的标签值，v1.n为第1个节点的后继。Ptrs[m]为1个指针数组，记录每1个节点在序列T中的起始位置。图11是给定图的邻接表的Repair压缩。

Figure 11 Repair compression of an adjacent table图11 邻接表的Repair压缩

Repair算法将1个邻接表压缩成1个字典规则R的集合，1个指针数组ptrs，1个序列T。每次查询节点的信息时，仅仅需要找到该节点的起始位置和终止位置，然后进行部分解压缩即可。但是，对于大规模图而言，由于每次都要添加新的规则，字典规则R的集合越来越大，Bille等人[41]对该算法进行了改进,取得了很好的时间/空间均衡。

另1种基于邻接表的压缩称为LZ78算法[42]，由Ziv和Lempel提出，其思想为建立1个字典表，每读入1个字符，判断其是否在字典表中，若不存在，则保存字符并建立索引。若存在，则保存索引并加上新的字符作为这个字符串的表示。

具体的算法流程如下[43]：

步骤1建立字典表，并将字典表设置为空。

步骤2依次读取文本中的1个新的字符，设新字符为C。

步骤3在词典中查找当前的前缀和新的字符的组合，也就是P+C：

(1)如果在字典表中找到了这个新组合，那么就把前缀P重新进行改写，需要加上新读取的字符C。

(2)如果字典表中没有这个新组合,就要执行保存新组合的操作：

①输出当前前缀的索引以及字符C。

②把前缀和新读取的字符串保存在字典表中。

③重新改写前缀P，将其设置为空。

(3)重复步骤2和步骤3，直到所有的字符串都完成编码。

LZ78算法和Repair算法在对文本压缩时有1个区别：T(G)=v1.1v1.2v1.3…v1.nv2.1v2.2v2.3…v2.n…vn.1vn.2vn.3…vn.n，表4所示是图11所示的邻接表的LZ78压缩。

Table 4 LZ78 compression表4 LZ78压缩结果

LZ78算法和Repair最大的区别在于在压缩时不用存储和维护字典表，因为字典表以结果形式输出了，因此LZ78算法查询节点信息的速度比Repair算法快，但由于每次解压过程，从结果的最开始开始构造字典R，所以只能对邻接表的边表进行压缩，限制了LZ78算法的性能。

5 图数据压缩技术比较

文献[17]采用真实的网页图数据集和社交网络数据集对其中提到的所有压缩技术进行了对比，其数据集来自于米兰大学LAW[44]，表5给出了网页图数据集的相关属性，表6给出了社交网络数据集的相关属性。通过一系列的实验对比，他们得出k2-tree的压缩率明显低于其他算法(Repair，LZ78等算法)的，能实现较好的时间/空间均衡。为了体现出符号计算对于大规模图数据压缩处理的优势，本文将k2-tree分别与OBDD，k2-MDD 2种压缩技术做了实验对比，实验结果如表7和表8所示。

Table 5 Web graph data set表5 网页图数据集

Table 6 Social network data set表6 社交网络数据集

Table 7 Experimental results of web graph表7 网页图实验结果 bit

Table 8 Experimental results of social network 表8 社交网络实验结果 bit

实验结论：在k2-tree，k2-MDD,OBDD中，用1个位串T来记录除最后1层节点的0值和1值，1个位串L来记录最后1层节点的0值和1值，T和L的总和为需要的存储空间。如表7所示，若采用OBDD来压缩网页图，T和L的总和约为k2-tree的21%，若采用k2-MDD来压缩网页图，T和L的总和约为k2-tree的3%，如表8所示，我们用社交网络数据集来进行实验对比，分别在enron，dblp-1，dblp-2，dewiki数据集上进行实验，得到的T和L的总和分别为k2-tree的4.8%，5.1%，4.7%，3%，对存储空间的需求得到有效的改善。

6 结束语

随着图在各个领域的广泛应用，传统的图存储结构已经不能支持大规模图数据的管理和操作，如何有效地紧凑表示图数据并且支持快速的访问已经成为一项重要的研究任务。本文首先介绍图数据应用概况和相关的图数据压缩表示技术，然后详细阐述了3种图数据压缩技术，并给出了不同压缩技术的优缺点。通过分析发现，基于形式化方法的图压缩技术在处理大规模图数据时，具有很好的压缩效果，这也是我们下一步研究的重点。对于图数据的压缩，未来可能会结合机器学习的聚类算法和形式化方法来更好地解决数据的冗余问题。由于篇幅有限，本文不可能涵盖该领域所有的研究内容，希望这篇综述能对图数据压缩技术的研究起到一定的参考作用。