——最近在做图论相关加速器的研究，对近期的GPM软件优化算法做了调研，现在整理后顺便写成一篇小文章。

图组件挖掘（Graph Pattern Mining，后面统一简称GPM）指的是根据给定查询Q和数据图G，输出embedding函数集F。F表示所有能够从Q映射到G的embedding函数f的集合。典型的应用有三角形计数、k-clique计数、子图匹配和k-motif计数等等。

input: query Q, data graph G
output: embedding function set F

GPM问题建模思路是将GPM的过程视为搜索树，树的深度为Q中节点数量，树中level i 的节点具有i+1个匹配节点。

后面会提到的算法有Graphflow、EmptyHeaded、GpSM、CECI、Clasgow、STwig、GSI、CFL、DAF，后面只会进行简单的介绍，想深入了解的朋友可以搜索相关论文查看。

按照搜索树的搜索顺序，GPM算法可分为sequential型和parallel型，sequential型的搜索顺序和DFS相同，占用内存空间小；parallel型的搜索顺序类似BFS，消耗大量内存，天然适合分布式计算。

sequential型算法有：Graphflow、EmptyHeaded、GpSM等
parallel型算法有：CECI、Clasgow、STwig等

现在不存在一个能吊打一切的GPM算法，在不同的情况下（大规模/小规模图，稀疏/稠密图，不同规模的查询）存在不同的最快算法。
现有算法存在拓展性不足，时间开销高等问题。初步结论是有做GPM加速器的潜力。

在GPM专用加速器领域，近期有FlexMiner(2021)、Gramer(2020)、TireJax(2019)。（其中Gramer宣称自己是第一个graph mining accelerator）
后面会对这几个专用加速器做一个调查。