大图数据管理与分析技术

2018 年 11 月 9 日 中国计算机学会

CCF于2018年10月出版了新一期《中国计算机科学技术发展报告》，对AI与系统软件的深度融合等10个方向的研究进展做了详细的介绍和讨论。我们将分期分享报告中的精彩内容。请加入CCF，登录CCF数字图书馆下载和浏览。

1 引言

随着社交网络等新型应用的兴起和云计算等新技术的快速发展，人类获取数据的规模正以前所未有的速度爆炸式的增长，与大数据相关的技术变革成为了当今世界的热点话题。大数据在信息科学、物理学、生物学、环境生态学等领域以及军事、金融、通讯等行业普遍存在，并引起人们的极大关注。在这些领域或行业中，数据通常具有关联性，从而产生了大图数据。图是表示对象与对象之间关系的方法，一个图由若干顶点和连接它们的边组成。图是计算机科学中最常用的一类抽象数据结构，在结构和语义方面比线性表和树更为复杂，更具有一般性表示能力。现实世界中的许多应用场景都需要用图结构表示，与图相关的处理和应用几乎无所不在。比如，传统应用中的最优运输路线的确定、疾病爆发路径的预测、科技文献的引用关系、生物信息网络分析等；新兴应用中的社交网络分析、知识图谱、数据万维网、人脑网络等都可以看作大图数据的应用。

传统的图数据管理与分析技术通常针对彼此独立的“小图”分别进行处理，尽管图的数目可能较多，但通常不需要复杂的迭代过程，也不会产生大量的消息，算法的时间和空间开销一般较低。但是，真实世界中实体规模的扩张，导致相应图模型的数据规模迅速增长，动辄有数十亿个顶点和上万亿条边，而这些庞大的顶点和边数目构成的结构信息只是大图数据规模惊人的冰山一角。复杂应用中的图数据为了表达复杂的语义，在顶点和边上往往会附带各类属性信息，这些属性信息内容丰富，需要大量的空间开销。而且，相比于基于属性的简单查询和搜索，大图上的统计分析算法往往需要基于图的结构进行循环和递归操作，直至达到收敛的条件，因此需要频繁的处理并行迭代过程中由于通信交互产生的消息数据等中间结果。此外，除了静态的结构和属性信息，很多情况下大图是动态变化的，如时序图、动态图等，这种动态变化随着某种特定的属性，不断改变着大图的规模和结构，因此需要对这些变化过程进行详细的记录。面对如此大规模的静态和动态数据，其存储、索引、查找和分析等处理的时间开销和空间开销远远超出了传统集中式图数据管理的承受能力，因此如何解决大图数据的分布式存储技术、查询处理与优化技术、挖掘和分析技术、系统的执行保证技术，已经成为数据库领域急需解决的问题，也是一项极具挑战性的工作。而且，随着研究的不断深入，研究者们已经不满足于仅通过传统的方法探讨基本的图管理与分析问题，一些新兴的研究热点也在不断涌现，如图查询语言、基于硬件的图处理等。对于这些研究方向，虽然早期也有一些相关的探讨，但随着计算机软硬件的不断发展，如何提出更准确高效的方法来解决这些问题，为图管理与分析工作带来了新的机遇与挑战。

2 国内研究进展

2.1 大图数据查询处理与优化

对于大规模图上的路径问题，东北大学Cheng等人提出的DistR[101]是通过分布式策略解决大规模图数据上可达性查询问题的方法。DistR具体分2步：分布式图缩减和分布式合并。在分布式图缩减步骤中，找到原始图的所有最大子图，其可达性概率可以在多项式时间内计算，计算它们并相应地减少图。完成此步骤后，只剩下一个小图。在分布式合并步骤中，本文将问题转换为关系连接过程，并Dist-2hop构建索引，提供可达性查询的近似答案。DistR可以在多项式时间内计算图的大部分可达性关系，将较大的问题分解为易处理的子问题，以产生对最终解决方案的估计。

国内在图模式匹配问题上有着很深入的研究，近三年中，国内主要针对图模式匹配的扩展问题进行了研究。北京航空航天大学Ma等人[102]在模式匹配的现有方法基础之上添加了对图结构和容量的约束，从而提出了团队模拟匹配。该问题首先将top-k团队组建问题视为一种新的模式匹配问题。然后，提出批处理算法解决了top-k团队组建问题，批量算法需要判断某一模式是否可以被满足，随后用统一的方法来处理模式和数据图更新的需求，其中包含了一种基于模式碎片的增量策略和一种将模式和数据图更新影响进行本地化的方法，以解决问题固有的不确定性。最后，提出了一种统一的增量算法来处理单独和同时发生的模式和数据更新问题，并提供了一种优化技术，使增量top-k算法具有早期返回属性。北京大学Du等人提出Lmatch[103]来解决基于有限模拟下的个性化图模式匹配问题。其中个性化是指允许图中的每个顶点或边缘具有不同强度的匹配条件，文中为模式图中的每个顶点赋予权重，以表示该点在模式图中的影响强度。有限模拟需满足[104]中提到的k-限制相似条件和边缘标签。文中提出通过有限模拟进行图模式匹配时，存在最大的匹配图，Lmatch算法即是寻找出这一最大的匹配图。Lmatch算法可在多项式时间内高效完成通过有限模拟进行的图模式匹配查询问题，但同NP难的子图双模拟匹配相比，有限模拟最终得出的结果会存在一些冗余的边。东北大学Yuan等人[105]通过过滤-验证框架对大规模不确定图上基于阈值的概率模式匹配进行了研究，在该问题中顶点是确定的，边是不确定的。在过滤阶段，通过PM树建立的切割选择过程获得的匹配切割，并对图进行结构修剪和概率修剪，以此细化候选集。在验证阶段，通过高效的采样算法来验证每个剩余的候选匹配然后确定最终答案集。为了更好的适应大规模图，西北工业大学Suo等人提出的ParMa[106]实现了分布式并行平台上的高效子图模式匹配。该方法将数据图划分为一组平衡的子图，存储在不同的计算顶点上，为了便于分布式子图匹配，该方法将整个图中边界顶点的k跳结构存储在图形分区中。ParMa首先搜索图形分区上k跳图模式的匹配，然后迭代地加入以生成查询图的匹配。对于时序图，国防科技大学Sun等人[107]引入Hasse图来表示查询图的时序关系。然后设计了Hasse缓存结构，提出了一种基于Hasse图的连续时序子图模式匹配算法。该算法利用动态图的概率减少中间结果，同时实现拓扑匹配和时间关系验证。相较于搜索整个查询图，该方法首先搜索查询边的时序关系是否匹配查询边，并通过使用Hasse图同时实现拓扑匹配和时序关系验证，提高了算法的性能。

目前，国内对图查询语言的研究相对较少。微软亚洲研究院提出的G-SQL[108]是利用图引擎提供的快速图探索功能来应对多路连接查询，使用RDBMS提供成熟的数据管理功能。同时提供了一个统一的成本模型来协调底层SQL执行引擎和本地图查询处理引擎。G-SQL利用混合架构，使用本地图计算引擎Trinity来提供快速的图探索，使用RDBMS或SQL引擎来处理关系查询并提供其他功能，如数据持久性、完整性和一致性。借助Trinity将多路连接操作转换为内存图中的子图匹配或图遍历操作，利用快速图遍历来避免在关系表上进行昂贵的多路连接查询。Trinity管理图拓扑，RDBMS管理拓扑以外的数据。

2.2 大图数据挖掘与分析

当前大多数社区检测方法集中在分离的社区，即每个顶点只能属于一个社区。然而，现实世界中社区往往是相互重叠的，即一个顶点可以属于不同的社区。为了解决重叠社区问题，华南理工大学Wen等人提出的MCMOEA[109]是一个基于极大团的多目标演化算法，用来解决重叠社区检测问题。将MOEA应用于重叠社区检测的一个阻碍是个体的表示方案，现有的表示方法大致可以分为2类：1）基于原型的方；2）基于顶点的方法，然而这两种方法都有其缺点。因此本文提出了最大团图的概念，它使用一组最大团作为顶点，并将最大团之间的连接作为边。基于最大团图，本文提出了基于团的表示方案MCMOEA，其中个体的每个基因代表相应的最大团的社区标签，之后将基于团的表示方案和相应的演化算子与MOEA框架相结合，构成基于最大团的MOEA。山西大学Bai等人[110]提出了一种新的基于图聚类的描述模型来解决社区发现问题。社区描述模型可评估某一顶点在某一社区中的重要性即局部重要性，也可评估某一顶点在所有社区中的重要性，以反映某点是否可代表某社区。基于描述模型，文中提出了社区检测的迭代搜索算法ISCD。ISCD通过相似性度量来将每个顶点分配到相应的社区中，若某一顶点的邻居顶点们对某一社区有着较高的代表性，则该顶点很有可能属于这一社区。

对于频繁子图挖掘问题，北京邮电大学Xu等人设计了基于差分隐私的频繁子图挖掘方法DFG[111]，该方法按照大小增加的顺序识别频繁的子图。DFG首先估计频繁子图的最大尺寸，之后利用频繁的子图识别方法从输入数据库中识别频繁的子图，最后利用基于格的噪声支持推导方法来计算每个识别的频繁子图的噪声支持。在这个过程中，DFG使用二元估计方法来估计频繁的子图的数量，利用条件指数方法对候选子图进行剪枝，来提高私有选择的准确性。DFG算法在满足差分保密性的前提下，可以从一组具有高数据效用的输入图中找到频繁子图。该方法不仅适用于频繁子图的挖掘，而且也适用于其他类型的频繁模式的挖掘。由于算法设计存在特殊约束，频繁子图挖掘很难在分布式系统中实现。因为在分布式平台中，如果输入图形在各个worker上进行分区，则子图的本地支持对于确定子图是否全局频繁没有多大用处。此外，支持计算不能任意延迟，因为候选频繁子图只能根据Apriori原则从频繁的子图中生成。因此上，国防科技大学Zhao等人[112]提出了基于Pregel的大规模单图上频繁子图挖掘分布式方法pegi。pegi算法根据可用的worker采用随机分区方法对图进行分配。然后迭代的进行模式增长和嵌入发现。为了方便评估边支持度，本文采用了增长存储方法，从而将当前子图的嵌入具体化到树结构中，即嵌入树。河北工程大学Wu等人提出了基于邻接矩阵和权重的不确定最大频繁子图挖掘算法UMFGAMW[113]。UMFGAMW设计了一种新的顶点排序策略，并给出了不确定图的标准矩阵编码的定义，用于建立邻接矩阵与不确定图之间的对应关系。该策略可以降低不确定图编码的复杂度，提高不确定子图标准编码的匹配速度。UMFGAMW提出了不确定图权重和不确定边的平均权重的概念，充分考虑了满足图数据集中最小支持阈值的不确定子图的重要性。根据不确定边的权值的限制条件可以有效的减少挖掘结果的数量。

2.3 大图数据系统

国内对于大图数据系统有着一定的研究。清华大学Zhu等人的Gemini[114]将大图进行划分并分布在不同的顶点上，图中的信息和更新通过显示消息传递来共享。Gemini采用master-mirror方式对图中顶点进行存储，每个顶点被分配给一分区，该顶点即是该分区的master顶点，作为维护顶点状态数据的主副本。mirror顶点类似占位符仅用于更新传播，并不包含实际数据。Gemini在每个master-mirror之间会创建一对有向边，其中只有一条边可以使用传播模式。图中的边采取两种模式进行存储，采用位图辅助压缩稀疏行存储稀疏边，采用双压缩稀疏列存储稠密的边。Gemini是一个分布式图形处理系统，其关注计算和通信组件的性能，采用高效的划分，积极压缩计算时间，同时隐藏通信成本，从而达到了在保持高效的同时实现可扩展，弥补了高效共享内存系统可扩展性差和可扩展分布式系统性能差的不足。北京航空航天大学Ju等人提出的iGraph[115]是分布式增量图处理系统，用于连续更新的动态图。其采用基于散列的方法对初始图和更新的数据进行分区，行数据处理器以批处理方式持续分析传入的更新数据，更新数据块将依次保存在缓存图更新信息中，同时，所有变化的顶点以及每个变化频率的信息将被发送到热点检测器上，其中采用标准评分方法来检测图的热点，同时，其定期触发热点重新平衡以均衡所有分区的计算成本，然后对它们执行基于贪心策略的全局优化算法，以计算出所有热点的最佳位置。当获得热点的最佳位置后，将在分区之间进行数据通信，调度器将顶点的ID及其改变的索引发送到原始数据处理器中的图传送表。

对于图划分问题， Gemini提出了一种轻量级基于块儿的多级分区的划分方法，其基于拓扑结构将相邻的顶点划分为同一分区。采用该种方法划分使得每个块内的顶点拥有连续性的特征，从而简化了顶点数据的表示，减小了内存的消耗。华中科技大学Hao等人提出了一种面向关联的流式图划分方法Assc[116]。该方法为了最小化划分结果之间的相互作用，在将顶点和边进行划分时需要考虑顶点之间的联系。针对大规模图数据连续快速到达的流式情况，Assc使用基于滑动窗口的流模型进行建模，并考虑在滑动窗口中最近到达的图数据之间的联系。Assc首先计算顶点排名，然后根据顶点的排名和顶点之间的联系使用吸引力传播的变体方法对图数据中顶点和边进行聚类，实现对图的划分。在划分过程中主要面临以下2个问题：1)如果顶点排序不够好，可能会导致数据分布严重偏斜；2)过多的合并顶点意味着更少的副本和更高的内部关联，这也会导致数据分布偏差。针对以上2个问题，Assc使用混合近似PageRank方法计算顶点排名。最后，Assc提出了一种保持数据平衡分配的方法，即通过为聚类设置比例阈值来确保数据平衡分配。相比于传统图划分方法，Assc可以处理增量生成的流式数据，并且减少划分结果之间的交互。

2.4 基于硬件的大图处理问题

目前国内对于基于硬件的大图处理问题研究还比较少。东北大学的Li等人[117]研究了基于GPU的具有数据更新的道路网中的KNN查询问题。[117]首先提出了一种新的索引结构G-Grid和索引更新算法，其可以缓存和延迟索引更新，避免了不必要的索引更新。G-Grid索引由三部分组成，其一是表示道路网的图网格，在CPU和GPU的内存中维护两个相同的图网格，并且为了保留GPU上高度并行访问的内存局部性，该图网格基于一维数组进行存储。其二是在CPU的内存中，用哈希表以键值对的形式存储存储索引中对象位置的对象表。其三是缓存对象所更新位置的消息列表，首先将该消息列表存储在主存储器中，并在需要时将他们发送给GPU进行处理。同时查询服务器需要更新G-Grid索引以使对象位置保持更新，当有更新消息到达后，将此消息缓存在消息列表中，并仅在查询其相应的单元格时对其进行处理，而不影响查询答案的更新。对于GPU上高度并行的算法，该算法用于有效处理缓存更新，同时清除缓存的更新，从而实现延迟更新策略。文中进一步提出了GPU-CPU协作解决KNN查询处理的算法，服务器收到查询问题时，首先使用CPU识别查询区域，然后使用GPU处理该区域中的缓存更新，利用GPU计算出候选答案集，再使用CPU计算出最终查询结果。该算法利用了GPU的高并行能力来进行大量数据对象的距离计算，并且利用了CPU在分支操作中的高效率来比较距离并产生最终的查询答案。该算法在查询时间和索引大小方面都优于其他解决KNN查询问题的算法。

3 国内外研究进展比较

从以上分析和总结可以看出，近年来国际学术界对大图数据查询处理与优化、大图数据挖掘与分析以及大图数据系统开展了广泛而深入的研究工作。而国内的研究者们在相关领域也开展了许多深入的研究工作，并取得了一些重要的研究成果。在经典的图查询处理与挖掘问题如图模式匹配、频繁子图挖掘等，国内研究工作的数量与国际研究工作的数量不相上下。但是，对于新兴研究方向如图查询语言、时序图、基于硬件的图处理等，国内的研究工作数量还相对较少，并且对于图系统，国内的研究大多是基于已有系统的进一步研究，几乎没有完整的图系统构建。而且从整体上看，在数据库顶级和会议期刊上发表的论文数量国内研究者的论文数量是要远远小于国际研究者发表的论文数量的。由此可见，国内的研究工作的广度和覆盖度还有所不足，技术的前沿性还有待提高。

4 发展趋势与展望

由于现有的图数据具有规模宏大、结构复杂、动态多变的特征，因此目前图数据研究存在下面这些的问题：

(1)对于大图数据查询处理和优化

大图数据的存储空间将越来越大，严重影响传统的基于内存的图数据查询处理技术。因此当前的工作大都采用分布式环境来处理查询，将大图数据分割为多个部分，分别在不同的计算机内存处理，但是由于图数据的高度耦合性和分布式系统高昂的通信代价，会较大地影响计算速度。另一方面一些工作对原始图数据进行压缩，然后将压缩的图数据放入内存中进行处理，但这种方式经常会产生不精确的查询结果。一些大图的分布式系统也支持图数据的查询处理，但分布式图处理系统存在负载难以均衡、网络开销大、单点故障频发、难以实现和调试等问题，特别是在大规模分布式异构集群环境下，这些因素成为了制约大图查询处理的性能瓶颈。

(2)对于大图数据挖掘与分析

针对大图的挖掘和分析算法都是基于并行迭代模型的，而迭代计算依赖于特定的图类型和算法特点，所有迭代的行为一般是静态的，缺乏对迭代过程状态变化规律的建模、分析和预测方法，也缺乏针对高频迭代计算过程中数据读写和交互的动态调整机制，大大制约了迭代数据分析的执行效率。同时，在分布式环境下，面向动态图的挖掘和分析技术的研究刚刚起步，特别针对高频多态迭代任务，在数据更新驱动的增量数据概要维护技术和增量的迭代计算方法方面，还没有得到充分的重视和研究。

(3)对于大图数据系统

现有针对图数据的模型和存储工作主要支持简单图，尚不能有效地支持复杂图和超图等更为复杂的图模型，因此无法胜任以复杂图、超图为基础的应用环境。在分布式环境下，目前的图处理系统只使用单一模式的图划分，在具有多样性的图操作负载下，单一模式的图划分无法为所有操作提供良好的性能保证，严重制约了分布式图处理系统的可用性。以异构图划分为基础的图处理系统尚未开发，现有工作也缺乏对基于异构图划分的查询和分析操作的性能挖掘。而目前的大图数据系统的执行保障使用检查点技术或者基于单一划分模式的备份技术为系统提供容错性，检查点技术的备份操作I/O开销巨大，严重影响系统的运行性能。而基于单一划分模式的备份技术无法在提供容错性的同时高效地支持多样性的图计算任务。与此同时，基于单一图划分的系统大幅限制系统优化的空间，降低系统潜在的最优性能。在某个划分负载巨大的情况下，单一划分模式可选的后备资源远远少于基于异构图划分的存储模式，因此在负载平衡和任务调度方面降低了系统潜在的最优性能。

由此可以看出现在未来的大图数据研究工作中，需要1)提出效果更好、准确性更高、可扩展性更高的算法来解决现有图管理与分析问题；2)在现有的图管理与分析问题的基础上，提出新的有实际应用价值的问题，并设计合理高效的方法解决这些问题；3)对结构更为复杂、规模更为庞大的图，如超图、时序图、动态图等提出有效的方法解决图上的问题；4)相较于在单一服务器上处理大规模图数据，提出合理的对图进行划分方法并且分布式处理图管理与分析问题；5）对于新的研究热点进行深度的探讨和研究，如图查询语言、基于硬件的图处理等，提出准确高效的方法解决这些问题。

5 结束语

随着网络和数据库技术的飞速发展，语义网络、社交网络、生物信息网络等新兴领域的飞速发展，数据的结构越来越发杂，数据量呈几何状增长，这为大规模图数据上的研究工作带了巨大的挑战。随着图数据的存在性越来越普遍，图数据上的查询处理也得到了越来越多研究者的广泛关注，因此大图数据管理与分析技术的研究与开发不仅具有重要的理论研究意义，而且具有广泛的实际应用价值。国内图数据库的研究正在快速的发展，但是与国外的研究工作相比，在质量和数量上都有一定的差距。希望在未来有更多的研究成果可以为图数据库管理与分析工作打下坚实的基础。

作者简介