论文地址
code
overview
本文可以认为是GRAMI: Frequent Subgraph and Pattern Mining in a Single Large Graph的改进版本，建议先看GRAMI。ScaleMiner源码阅读部分还未完成（弃坑）。
本文的主要贡献是将GRAMI进行并行化，实现了超大规模的频繁子图挖掘系统，最大可支持千万节点，十亿边的图。
问题
频繁子图挖掘要并行化，主要的难点在负载均衡。基于模式增长的挖掘模式，其搜索空间是包括了所有频繁子图和一层不频繁子图，且是未知的，示意图如下；对于子图同构计算上，不同的子图其计算难度是不同的，会导致即使划分均衡，最终执行时的负载也是不均衡的。
并行的基本思路是，将为了解决这两个问题，论文提出了两个方法。针对域搜索空间的不规则，通过快速估算给出一个近似的搜索空间。为了解决每个子图支持度计算难度不同的问题，对较难算的子图任务进行划分，将任务缩小。
近似搜索的作用：“快速剪枝”，没有真正剪枝，只是记录不频繁的模式中MNI小于域值的点，便于后续快速处理。
1.系统概要
1.1 并行的思路
将每个子图（模式）的支持度计算时为一个task，master节点保持一个task pool，每个worker取一个task并返回master结果。以此作为baseline。
1.2 系统架构
系统是采用一主多从的结构，每个进程都保存一分完整的图结构。进程之间通过MPI进行通信，master将待验证的模式发送给worker，可能会附带一些统计信息，worker返回的是验证的结果。通信代价较小，并且没有需要进行主从同步的。
每个进程可以去fork新的线程来进行辅助，进程不会保存完整的图，对资源的需求较小。
1.3 算法
为了解决两个负载不均衡的问题（1.任务数量不稳定，2. 任务执行的所需的时间差别较大），提出了一个两阶段的算法。首先进行近似挖掘，近似挖掘的目的是为了给精确挖掘提供信息，保证其
近似挖掘阶段
快速构建一个近似的搜索空间。近似搜索和精确挖掘是进行的相同的流程，最大的区别在与支持度的计算上。在近似阶段，支持度计算是通过采样来估计。在该阶段产生的不频繁的模式也会被记录下来，对于其中一些关键信息，包括那些MNI col值较低等将被记录，用来指导精确挖掘。
采样估计MNI。将一个点是否属于某个MNI col视为一种0-1分布，则多个节点与某个MNI col的关系可以视为一种二项分布。那么MNI值即为节点数N和概率p的乘积，也是二项分布的均值。根据中心极限定理，通过多次采样，获得多组平均值，多组平均值的分布是满足正态分布D，正态分布D的均值即为二项分布的均值。
精确挖掘阶段
这阶段没有大动作，主要是借助于近似中的结果，加速判断。