图数据在生产和生活中无处不在，图挖掘旨在发现图中特定的子图结构模式。随着图规模的日益剧增，提供一个高性能可扩展的通用框架来支持图挖掘应用是一个亟待解决的问题。现有工作将图挖掘应用转换为一系列图模式匹配问题以提高性能，然而深入分析可以发现同一个中间子图的相关计算会在运行时大量重复出现，随着图模式数量和大小的增长，这些冗余计算对性能的影响会急剧增大。针对现有图挖掘系统在并行匹配图模式中的性能瓶颈，我们详细地分析了图模式的计算冗余问题，发现冗余计算和图模式结构相似性紧密相关，并根据这种相似性设计了基于图模式抽象的高效图挖掘系统SumPA，能够同时对图模式内部和模式之间的相似结构进行合并，通过有效的重用计算结果极大地提高系统的性能。

该成果“SumPA: Efficient Pattern-Centric Graph Mining with Pattern Abstraction”发表于PACT 2021（The 30th International Conference on Parallel Architectures and Compilation Techniques），是实验室系统软件研究小组在图计算领域的系列研究成果之一。PACT是并行体系结构领域的顶级国际会议，2021年共收到96篇投稿，共录用25篇论文，录用率约为26.04%。

• 论文原文：
• https://doi.org/10.1109/PACT52795.2021.00030

摘要

以图模式为中心的系统通常将一个通用的图挖掘问题转化为一系列的子图匹配问题，并聚焦探索高度优化的节点匹配顺序，以减少单个图模式的搜索空间。然而，这些匹配顺序本身固有的计算冗余难以解决，导致显著的性能下降。我们观察发现图模式结构的相似性是冗余计算的根源，并提出利用图模式共享子结构来对冗余计算进行刻画，同时对模式内部和外部的计算冗余进行归并。围绕该思想本文实现了一个高性能的图模式为中心的图挖掘系统SumPA，以消除图挖掘应用中的计算冗余。SumPA包含三个关键设计：高效的图模式抽象技术，将众多复杂的图模式融合为少数简单的图模式抽象，减少计算任务量；图模式抽象引导的匹配方法，高效重用计算结果；运行时调度优化，以最大限度地提高存储和计算效率。面向多种真实图数据进行测试表明，SumPA相比领域前沿系统最高取得61.89倍性能提升。

图1 现有图挖掘系统按照匹配顺序计算示例

背景与动机

“以图模式为中心”的图挖掘框架以潜在图模式作为引导搜索相应子图结构，节省内存空间的同时取得优异性能。这些系统通常遵循一个匹配顺序，将数据图顶点映射到图模式顶点。不同匹配顺序下的搜索空间大小不同，现有系统或通过调整匹配顺序减小搜索空间（如图1(b)所示，例如AutoMine系统），或通过对称性约束过滤无法导致最终结果的任务分支（如图1(a)所示，例如GraphPi系统）。然而即便是最优的匹配顺序中仍存在严重的冗余计算问题。具体而言，找到一个匹配的顶点往往需要对一些共同的顶点集进行大量的交集，以计算它们的重叠邻居，如图1(a)中匹配u2节点的时候，0和2号节点的邻居集合被重复求交两次。随着问题规模增大，冗余计算对性能的影响将会更加严重，如图2所示。以统计LiveJournal图中所有5节点图模式出现次数为例，冗余计算的比率达到70.3%且占整体运行时间的61.8%。

图2 Peregrine系统运行Motif Counting应用的冗余计算开销

针对这一问题，研究将冗余计算细分为两类，一类是单个图模式内部不同节点计算之间的冗余，一类是多个图模式之间的计算冗余，该分类为接下来的冗余计算合并提供依据。如图3中，两个原始模式按照匹配顺序进行计算，模式Pa在匹配u3和u4节点的时候所需的计算相同，模式Pb在计算u3的时候也需要重复进行和Pa相同的计算。通过对图模式结构进行分析，可以观察到大多数模式内和模式间冗余都集中在该模式的少数顶点的密集计算上。基于此提出共享子结构概念（Shared-Connected-Subpattern, SCS）对两类冗余计算进行系统描述，共享子结构由图模式中特定顶点形成的连通子图构成，图模式所有的边均可与之直接相连。与同一子结构存在相同连接方式的节点之间的计算具有潜在的冗余性，如图3中冗余计算均与（u0, u1, u2）形成的子结构有关，从而可以将复杂的冗余计算合并问题简化为相同子结构合并问题，使得冗余计算的预判成为可能。在实际匹配过程中先匹配共享子结构，然后将相同计算结果共享给原始的图模式。

图3 图模式抽象示意图

设计与实现

如何提取合适的共享子结构获得全局最优性能，以及如何高效重用计算结果，成为系统设计的关键挑战。首先，每个模式通常有不同的SCS。为每个模式选择一个合适的SCS是非常困难的。对单个模式而言最佳SCS可能会导致与其他不同模式间合并机会减少。其次，现有的图挖掘匹配引擎会将不同模式的中间计算结果隔离开来，使得中间结果重用变得十分困难。一个直观的解决方案是存储SCS的所有相关计算结果，然后在不同模式需要的时候进行访问。但这种方案需要消耗巨大的内存空间以及导致大量的I/O开销。最后，重用计算结果过程中如何在保持正确性的同时也保持高效性存在挑战。虽然在计算模式顶点候选集的时候会得到相同的计算结果，但是最后将计算结果映射到原始模式顶点上的时候有所差别。

图4 SumPA系统框架示意图

本工作设计并实现了基于图模式抽象的高效图挖掘系统SumPA，图4展示了系统执行过程。对于第一个挑战，研究提出了基于共享子结构的图模式抽象方法，将多个模式之间存在潜在冗余计算的节点进行合并，并使用一个抽象模式来表示，如图3所示。这样一来，多个模式的多次冗余计算可以通过计算一次抽象模式进行缩减。为了实现全局最优，本文提出了一种轻量准确的开销预测模型来预估不同抽象模式的潜在计算量。对于第二个挑战，研究设计了基于图抽象引导的匹配引擎，以实现高效并行和结果共享，采用DFS执行方式，在保证并行性的前提下极大的节省了内存消耗。对于单个抽象模式而言，共享子结构的计算结果可以通过抽象节点进行不同模式之间的重用。通过抽象节点将结果映射到原始模式节点的过程中，系统通过一个映射表来记录不同节点的实际结果在候选集数组中的范围，采用二分查找的方式快速对结果进行定位，同时保障了正确性和高效性。大量实验表明，SumPA能够有效消除不同类型图挖掘应用中的冗余计算，相比领域前沿系统Peregrine和GraphPi分别获得最高61.89倍和8.94倍性能提升。

图5 多模式匹配性能对比

详细内容请参见：

Chuangyi Gui, Xiaofei Liao, Long Zheng, Pengcheng Yao, Qinggang Wang, Hai Jin. "SumPA: Efficient Pattern-Centric Graph Mining with Pattern Abstraction". In Proceedings of the 30th International Conference on Parallel Architectures and Compilation Techniques (PACT), 2021, pp. 318-330, doi: 10.1109/PACT52795.2021.00030.

往期 · 回顾