An Algorithm Based on Dataflow Model for Mining Frequent Patterns from a Large Graph

Big graph data mining has been highly motivated not only by the tremendously increasing size of graphs but also by its large number of applications, such as bioinformatics, chemoinformatics, and social networks. One of the most challenging tasks in big graph mining is pattern mining. These tasks consist on using data mining algorithms to discover interesting, unexpected and useful patterns in large amounts of graph data. Several algorithms exist for frequent pattern mining, but they are mainly used on centralized computing systems and evaluated on relatively small datasets. While modern graphs are growing dramatically, several parallel and distributed solutions have been proposed to solve this problem. However, those methods do not have better performance in scalability and balancing. So that we propose an algorithm based on dataflow model for mining frequent patterns in a large single graph. We construct a dataflow model for Mining frequent patterns, which include three operators: IsFrequent, Expand and Code. At first, the frequent pattern mining method based on dataflow model separates large graph into many micro graphs and has following advantages. These micro graphs can be expanded and calculated simultaneously, because they are independent of each other. At the same time, since each iteration is based on the subgraph instance generated in the previous iteration, only one vertex or one edge needs to be extended, it decreases the generation of redundant subgraph in Expand operator. Secondly, we propose a regular code computing strategy based on invariant relation and an optimization strategy based on coding tree. These two approaches solve the problem that it is difficult to calculate the regular code. The results show that our regular code computing strategy improves performance by 30% over the original approach and our optimization strategy improves performance by 10% over the original strategy. Thirdly, we design operators of checking frequent pattern using micro batch data. After the large batch data is decomposed into multiple micro batch data, each micro batch data can be regarded as a single processing unit, a lot of tasks can be generated concurrently, which reduce data skew. These micro batch data can be iteratively computed more easily in parallel computing. And its iterative approach also satisfies the anti-monotonicity of frequent patterns mining. At last, the algorithm of frequent pattern mining is implemented. The experiments on our cluster show that the algorithm can effectively process a variety of large graphs with millions of vertices and tens of millions of frequent pattern mining, and scales well with the degree of available parallelism. © 2020, Science Press. All right reserved.