【论文笔记】PVLDB14 GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph_综合

论文地址
代码 JAVA
作者后序改进的并行版本 SC16 -ScaleMiner笔记

overview

问题定义：对于给定的图G，和给定的支持度 $τ\tau$ ，找出图中所有的子图，这些子图s都满足 $sup(s)>τsup(s)>\tau$ ，其中sup()是支持度计算函数，往往是与图同构相关的函数。

GRAMI是针对单个大图的频繁子图挖掘的算法。针对原来“增长存储”算法受到内存限制而无法处理大规模图的情况，提出用CSP计算子图同构来代替存储实例。并且根据问题的定义，在计算支持度时，并不计算子图的精确的支持度，而是只证明子图的支持度大于阈值就停止（即摘要中提及的miniaml set）。

本文核心是针对问题中的“漏洞”（支持度大于阈值，而不需求精确值）和CSP中利用错误信息进行剪枝。

输入是单个标签图和指定的支持度，输出是频繁子图。

该算法是目前看到的 单线程 精确算法中的SOAT。但在大规模图上的时间依然难以接受，但不会导致内存爆炸。如果对时间没有限制，且有足够耐心，可以试试。作者后续还有一篇基于本文改进的并行版本，效果有明显的提升。

是否为精确算法

子图生成过程中采用了GSAPN中的最右路扩展，从而保证了搜索空间是完备的。在计算图的支持度时，理论上也是精确的。但算法也提供了支持度的近似算法，近似算法保证了挖掘的子图一定是频繁的，但不是所有频繁的子图都能获得，即存在false negatives,不存在false positives。

增长存储到增长计算

原文中应该时没有增长计算这概念的，这里使用该概念方便进行描述。需要注意的是，本方法在后续依然是进行了一定的存储，但存储代价较小。

频繁子图挖掘算法可以简单的描述如下：

1.对于已获得的频繁子图进行扩展，获得新的候选子图。
2.验证新产生的候选子图是否满足要求（支持度要求）
3.若满足，则返回1继续扩展，否则停止。

其主要的步骤即：模式扩展（候选子图生成）和支持度计算。从增长存储到增长计算主要的改进在支持度的计算上。

先简单介绍增长存储模式，其代表为GSAPN，详细可见GSPAN详解。频繁子图挖掘最初有两种模式，其中效率较高的是“模式增长”，即从已知的模式上继续扩展来获得新的模式。在每一步扩展时，都将模式对应的实例保存下来，方便进行支持度计算和接下来的扩展，这种边扩展边存储实例的方法称为增长存储模式。这样支持度计算较快，但对内存的需求较大，无法处理大图。

增长计算模式是针对与增长存储的缺点改进的，即计算模式后，并不保存对应的实例，而是每次通过计算的方式来获得同构数用于计算支持度。这里并没有用典型的图同构算法，而是将图同构问题转为CSP问题。

需要解决如下的问题

子图同构是NP hard问题，如何计算
模式是通过模式扩展得到的，存在一定的关联性，如何利用

存储是模式对应的实例，扩展后的实例必来自这。对于不存在的点，无需考虑。包含不频繁的边的图一定不频繁。

CSP

CSP 全称为Constraint Satisfaction Problem，约束满足问题。其包括三部分，变量、每个变量对应的域、变量上的约束条件。CSP是求解满足约束条件下，变量对应的解。CSP求解常用的是回溯，所以解是完备的。~~CSP详细的介绍见（已弃坑）~~ 。

在文中，是将子图同构问题转为CSP问题进行计算。定义如下。关于域D，简单处理即取图中全部节点。
请添加图片描述

支持度本来使用与计算子图出现的次数，即子图同构数量，但在单个图中，存在同构图之间的overlap，以及要保证支持度的单调性，所以最终的支持度是一个关于子图同构的一个函数。在计算支持度时，采用MNI（minimum image based suppor）支持度，文中有给出定义，这里借用作者另一篇论文中的图进行解释。

MNI是找到节点映射数量的最小值。左边为整个图G，右边是待匹配的子图S，首先在图G中找到S的全部同构子图数量，同构图已经在图中被红圈标记，子图S和每个同构图之间存在一个节点映射关系，子图S中的每个节点会被映射到图G中的不同节点，如 $v_2$ 会映射到 $u_2,u_{19},u_{16},u_{12},u_9$ ，映射关系被整理在MNI table中，每一列的数量代表了模式中的一个节点在图中映射的数量，所有节点的映射集合大小的最小值即位MNI值，图中MNI的值为5。
请添加图片描述
MNI支持度大于阈值，等价于每个节点在图中的映射数量都大于阈值。将MNI和CSP相结合后，可以把问题转为，对于每个变量（节点），在域D中找到至少 $τ\tau$ 个值， $τ\tau$ 为阈值。

显然，当某个节点对应的 域D的大小 小于阈值 $τ\tau$ ，那么该子图的MNI一定小于阈值，无需进一步进行计算。这是本文中很重要的剪枝。

关于CSP的讨论

related work中，作者简单的阐述了使用CSP的原因。目前子图同构都是针对全局优化，且是针对全部实例，所以不如CSP。理由不是很有说服力，但没看过子图同构的算法，而且作者后续还发了一篇子图同构的论文，可能是真的的吧。

论文中后续进行了一定的实验。实验设计的较为合理，利用CSP代替子图同构应该进行对比。但就实验结果而言，CSP可能存在一定的优势，但并不明显。GGQL是用子图同构来计算支持度的。在Mico数据集上，支持的较大，相对而言计算量较小。在Aiation数据上，由于纵坐标是log后的，看起来有较大的差距。并且在论文中简单解释为对CSP进行了一定的优化（见下）。
请添加图片描述

一些优化

本文的主要贡献在提出利用CSP计算支持度，并对其进行了一定的优化。下面为基于启发式的CSP求解图同构的baseline。优化后的伪码见后。

node consistency 和arc consistency 是CSP求解过程中的“剪枝”，node consistency 对域中节点进行 label 、度等约束（如节点label应该是一致的），arc consistency 没看懂。第5行之所以要进行重新约束，是因为在12行上对域D进行了修改，可能会导致不一致。
请添加图片描述

push-down pruning

这里是利用了模式增长的特点。

CSP在求解过程中，会记录错误值，从而加速求解。这里利用错误值，进行剪枝。以下图为例。

模式之间的关系如左所示，从S1扩展得到S2和S3，S2扩展得到S4。假设在S1中淘汰了一组分配，即v1取a3，v2取b1 ，V3取a3，那么在S2，S3，S4中这组取值都是错误的，在后面的计算中，也直接忽略这组取值。按照这种方法，在S4计算时，只有2234种取值可能，如果不忽略的话，则存在5356种可能。对于不合理的取值，使用了hash map进行了存储，key是子图对应的DFS code（可能是 min DFS code ，文中没有确定描述），使得子图匹配转为了字符串匹配。
请添加图片描述

unique label

这是针对一种特殊情况进行的优化。

当子图是树（无环），且节点的label都不相同时，在施加CSP中的一致性约束后，对应的域即为最后的取值集合。MNI的值就是当前所有变量对应的域的最小值。

lazy search

用CSP求同构时候，不用将所有的同构实例求出来，只需要求一部分，使得子图满足支持度就可以停止了。

对于一些较难求解的，可以保存状态，暂时不求，去求解简单的。把所有简单的求解完，如果支持度沟，则不需要计算复杂的。如果有需要，再去求解这些难求的实例。

文中的近似也可以认为是这方法的一种变种。对于求解时间超过阈值的，则直接认为其是不频繁的，停止求解。

decomposition pruning

对于lazy search中难求的实例，在不得不计算时，对其进行分解。

如下图，新增C-K的边得到图S，则将图分解成若干包含C-K的子图，计算每个子图的取值，每个子图可能都会删去一部分取值，那么这部分取值最终在图S上也不会取，有效的减少了搜索空间。
请添加图片描述

automorphisms

由于对称性，存在的一些子同构现象。同一个子图，由于节点映射的方式不同，同一个图对应了多个同构实例。用CSP求解确实会会出现这种问题。只能说时CSP求解时的bug，说成优化可还行。但文中也说这种数量较少。

完整的优化后的伪码

请添加图片描述

【论文笔记】PVLDB14 GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph