A Survey of Frequent Subgraph Mining Algorithms

  • Authors

    • Chandra Prakash Dixit
    • Nilay Khare
    2018-07-07
    https://doi.org/10.14419/ijet.v7i3.8.15218
  • Data Mining, Frequent Subgraph Mining, Graph Algorithms, Indexing, Knowledge Data Discovery, Pattern Mining,

  • Graphs are broadly used data structure. Graphs are very useful in representing/analyzing and processing real world data. Evolving graphs are graphs which are frequently changing in nature. There is either increase or decrease in their size i.e. change in number of edges or/and vertices.  Mining is the process done for knowledge discovery in graphs. Detecting specific patterns with their number of repetition more than a predefined threshold in graph is known as frequent subgraph mining or FSM. Real Timed data representing graphs are high volumetric or of very large in size, handling such graphs require processing them with special mechanisms and algorithms. Our review paper discovers present FSM techniques and tries to give their comparative study.

     

  • References

    1. [1] L. Dehaspe, H. Toivonen, and R. D. King. Finding Frequent Substructures in Chemical Compounds. Pages 30-36. AAAI Press, 1998.

      [2] A. Inokuchi, T. Washio, and H. Motoda, “An apriori-based algorithm for mining frequent substructures from graph data,†Proc. Fourth European Conf. Principles of Data Mining and Knowledge Discovery (PKDD), pp. 13-23, 2000.

      [3] S. Nijssen and J. N. Kok, "Faster association rules for multiple relations," IJCAI, pp. 891–896, 2001.

      [4] Borgelt and M. R. Berhold, "Mining molecular fragments: finding relevant substructures of molecules," Proc. 2nd IEEE Int’l Conf. Data Mining (ICDM ’02), pp. 51-58, 2002.

      [5] X. Yan, J. Han, "gSpan: graph-based substructure pattern mining," Proc. 2nd IEEE Int'1 Conf, 2002.

      [6] X. Yan, J. Han, "CloseGraph: mining closed frequent graph patterns," Proc. Ninth ACM SIGKDD Int’l Conf. Knowledge Discovery and Data Mining (KDD), pp. 286-295, 2003.

      [7] M. Kuramochi and G. Karypis,"GREW—a scalable frequent subgraph discovery algorithm," 2004.

      [8] K. M. Borgwardt, H. P. Kriegel, P. Wackersreuther,"Pattern mining in frequent dynamic subgraphs," ICDM 2006.

      [9] M. Kuramochi and G. Karypis, “Frequent Subgraph Discovery,†Proc. IEEE Int’l Conf. Data Mining (ICDM), pp. 313-320, 2004.

      [10] N. S. Ketkar, L. B. Holder, D. J. Cook,"Subdue: compressionbased frequent pattern discovery in graph data," 2005.

      [11] M. Kuramochi, G. Karypis, “Discovering frequent geometric subgraphsâ€, Information Systems, Volume 32, Issue 8, 2007, Pages 1101-1120

      [12] Y. Li, Q. Lin, G. Zhong, D. Duan, Y. Jin and W. Bi, "A Directed Labeled Graph Frequent Pattern Mining Algorithm Based on Minimum Code," 2009 Third International Conference on Multimedia and Ubiquitous Engineering, Qingdao, 2009, pp. 353-359.

      [13] Y. Liu, J. Li, H. Gao, "JPMiner: Mining Frequent Jump Patterns From Graph Databases," In the proceedings of Sixth International Conference on Fuzzy Systems and Knowledge Discovery 2009.

      [14] H. Hsieh,C. Li, "Mining Temporal Subgraph Patterns in Heterogeneous Information Networks," IEEE International Conference on Social Computing / IEEE International Conference on Privacy, Security, Risk and Trust, 2010.

      [15] J. Li, Y. Liu, and H. Gao, "Efficient Algorithms for Summarizing Graph Patterns," IEEE Transactions On Knowledge And Data Engineering, Vol. 23, No. 9, September 2011.

      [16] P. Shelokar, A. Quirin, Ó. Cordón, Three-objective subgraph mining using multiobjective evolutionary programming, Journal of Computer and System Sciences, Volume 80, Issue 1, 2014, Pages 16-26.

      [17] S. Aridhi, L. d'Orazio, M. Maddouri, E. M. Nguifo, “Density-based data partitioning strategy to approximate large-scale subgraph mining,†Information Systems, Volume 48, 2015, Pages 213-223.

      [18] M. Riondato, J.A. DeBrabant, R. Fonseca, E. Upfal, PARMA: a parallel randomized algorithm for approximate association rules mining in MapReduce, in: Proceedings of the 21st ACM International Conference on Information and Knowledge Management, CIKM’12, ACM, New York, NY, USA, 2012, pp. 85–94.

      [19] U. Kang, C.E. Tsourakakis, C. Faloutsos, PEGASUS: a peta-scale graph mining system implementation and observations, in: Proceedings of the 2009 Ninth IEEE International Conference on Data Mining, ICDM’09, IEEE Computer Society, Washington, DC, USA, 2009, pp. 229–238.

      [20] S. Aridhi, E. M. Nguifo, "Big Graph Mining: Frameworks and Techniques," In Big Data Research, Volume 6, 2016, Pages 1-10, ISSN 2214-5796.

      [21] E. Abdelhamid, M. Canim, M. Sadoghi, B. Bhattacharjee, Y. C. Chang and P. Kalnis, "Incremental Frequent Subgraph Mining on Large Evolving Graphs," in IEEE Transactions on Knowledge and Data Engineering, vol. 29, no. 12, pp. 2710-2723, Dec. 1 2017.

      [22] G. Malewicz , M. H. Austern , A. J. C. Bik , J. C. Dehnert , I. Horn, N. Leiser, "Pregel : A system for large-scale graph processing," In The pro-ceedings of the ACM SIGMOD international conference on management of data (pp. 135–145), 2010.

      [23] V. Bhatia, R. Rani, Ap-FSM: A parallel algorithm for approximate frequent subgraph mining using Pregel, Expert Systems with Applications, Volume 106, Pages 217-232. 2018

      [24] V. Ingalalli, D. Ienco, P. Poncelet, Mining frequent subgraphs in multigraphs, Information Sciences, Volumes 451–452, Pages 50-66, 2018.

  • Downloads

  • How to Cite

    Prakash Dixit, C., & Khare, N. (2018). A Survey of Frequent Subgraph Mining Algorithms. International Journal of Engineering & Technology, 7(3.8), 58-62. https://doi.org/10.14419/ijet.v7i3.8.15218