Journal of East China Normal University(Natural Sc ›› 2019, Vol. 2019 ›› Issue (6): 73-87.doi: 10.3969/j.issn.1000-5641.2019.06.008

• Computer Science • Previous Articles     Next Articles

Algorithm for mining approximate frequent subgraphs in a single graph

DOU Jian-kai1, LIN Xin1, HU Wen-xin2   

  1. 1. Department of Computer Science and Technology, East China Normal University, Shanghai 200062, China;
    2. Computer Center, East China Normal University, Shanghai 200062, China
  • Received:2018-12-21 Online:2019-11-25 Published:2019-11-26

Abstract: Graph mining is an important part of data mining, and significant research has been dedicated to the field. Due to the inevitability of noise during data acquisition, it is crucial to address the issue of approximation in mining frequent subgraphs. Previous work has only considered the absolute value of the graph edit distance (GED); however, the relative value between the GED and the size of the subgraph should also be considered. Hence, in this paper, we propose a novel algorithm to mine approximate frequent subgraphs in a single graph; this algortihm takes into account the size of current subgraphs for the calculation of approximations. We increase the efficiency of this algorithm by estimating the upper bound of frequent subgraphs, and pruning according to local anti-monotonicity. Experimental results show that this algorithm can find subgraphs that are missed by traditional mining algorithms, and our proposed approach is relatively efficent compared to other algorithms.

Key words: approximate, graph, frequent subgraph mining, pruning

CLC Number: