SPIN: mining maximal frequent subgraphs from graph databases

ABSTRACT

One fundamental challenge for mining recurring subgraphs from semi-structured data sets is the overwhelming abundance of such patterns. In large graph databases, the total number of frequent subgraphs can become too large to allow a full enumeration using reasonable computational resources. In this paper, we propose a new algorithm that mines only maximal frequent subgraphs, i.e. subgraphs that are not a part of any other frequent subgraphs. This may exponentially decrease the size of the output set in the best case; in our experiments on practical data sets, mining maximal frequent subgraphs reduces the total number of mined patterns by two to three orders of magnitude.Our method first mines all frequent trees from a general graph database and then reconstructs all maximal subgraphs from the mined trees. Using two chemical structure benchmarks and a set of synthetic graph data sets, we demonstrate that, in addition to decreasing the output size, our algorithm can achieve a five-fold speed up over the current state-of-the-art subgraph mining algorithms.

REFERENCES

• 1: Kenji Abe , Shinji Kawasoe , Tatsuya Asai , Hiroki Arimura , Setsuo Arikawa, Optimized Substructure Discovery for Semi-structured Data, Proceedings of the 6th European Conference on Principles of Data Mining and Knowledge Discovery, p.1-14, August 19-23, 2002
• 2: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.51, December 09-12, 2002
• 3: Douglas Burdick , Manuel Calimlim , Johannes Gehrke, MAFIA: A Maximal Frequent Itemset Algorithm for Transactional Databases, Proceedings of the 17th International Conference on Data Engineering, p.443-452, April 02-06, 2001
• 4: Yun Chi , Yirong Yang , Richard R. Muntz, Indexing and Mining Free Trees, Proceedings of the Third IEEE International Conference on Data Mining, p.509, November 19-22, 2003
• 5: Alin Deutsch , Mary Fernandez , Dan Suciu, Storing semistructured data with STORED, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.431-442, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 6: Karam Gouda , Mohammed Javeed Zaki, Efficiently Mining Maximal Frequent Itemsets, Proceedings of the 2001 IEEE International Conference on Data Mining, p.163-170, November 29-December 02, 2001
• 7: J. Hu, X. Shen, Y. Shao, C. Bystroff, and M. J. Zaki. Mining protein contact maps. 2nd BIOKDD Workshop on Data Mining in Bioinformatics, 2002.
• 8: Jun Huan , Wei Wang , Deepak Bandyopadhyay , Jack Snoeyink , Jan Prins , Alexander Tropsha, Mining protein family specific residue packing patterns from protein structure graphs, Proceedings of the eighth annual international conference on Resaerch in computational molecular biology, p.308-315, March 27-31, 2004, San Diego, California, USA [doi>10.1145/974614.974655]
• 9: Jun Huan , Wei Wang , Jan Prins, Efficient Mining of Frequent Subgraphs in the Presence of Isomorphism, Proceedings of the Third IEEE International Conference on Data Mining, p.549, November 19-22, 2003
• 10: J. Huan, W. Wang, J. Prins, and J. Yang. Spin: Mining maximal frequent subgraphs from graph databases. UNC Technical Report TR04-018, 2004.
• 11: J. Huan, W. Wang, A. Washington, J. Prins, and A. Tropsha. Accurately classify protein family based on coherrent subgraph mining. in Pacific Symposium on Biocomputing, 2004.
• 12: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, An Apriori-Based Algorithm for Mining Frequent Substructures from Graph Data, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.13-23, September 13-16, 2000
• 13: Michihiro Kuramochi , George Karypis, Frequent Subgraph Discovery, Proceedings of the 2001 IEEE International Conference on Data Mining, p.313-320, November 29-December 02, 2001
• 14: M. Kuramochi and G. Karypis. Finding frequent patterns in a large sparse graph. SDM, 2004.
• 15: Jian Pei , Guozhu Dong , Wei Zou , Jiawei Han, On Computing Condensed Frequent Pattern Bases, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.378, December 09-12, 2002
• 16: S. Raghavan and H. Garcia-Molina. Representing web graphs. In Proceedings of the IEEE Intl. Conference on Data Engineering, 2003.
• 17: N. Vanetik , E. Gudes, Mining Frequent Labeled and Partially Labeled Graph Patterns, Proceedings of the 20th International Conference on Data Engineering, p.91, March 30-April 02, 2004
• 18: N. Vanetik , E. Gudes , S. E. Shimony, Computing Frequent Graph Patterns from Semistructured Data, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.458, December 09-12, 2002
• 19: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.721, December 09-12, 2002
• 20: Xifeng Yan , Jiawei Han, CloseGraph: mining closed frequent graph patterns, Proceedings of the ninth ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2003, Washington, D.C. [doi>10.1145/956750.956784]
• 21: Xifeng Yan , Philip S. Yu , Jiawei Han, Graph indexing: a frequent structure-based approach, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007607]
• 22: Mohammed J. Zaki, Efficiently mining frequent trees in a forest, Proceedings of the eighth ACM SIGKDD international conference on Knowledge discovery and data mining, July 23-26, 2002, Edmonton, Alberta, Canada [doi>10.1145/775047.775058]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining

General Terms:
Algorithms

Keywords:
spanning tree, subgraph mining