Diagonally Subgraphs Pattern Mining

ABSTRACT

In this paper we present an efficient algorithm, called DSPM, for mining all frequent subgraphs in large set of graphs. The algorithm explores the search space in a DFS fashion, while generating candidates in advance to each mining phase just like the Apriori algorithm does. It combines the candidate generation and anti monotone pruning into one efficient operation thanks to the unique mode of exploration. DSPM efficiently enumerates all frequent patterns by using diagonal search, which is a general scheme for designing effective algorithms for hard enumeration problems. Our experiments show that DSPM has better performance, from several aspects, than the current state of the art - gSpan algorithm.

REFERENCES

• 1: 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
• 2: Michihiro Kuramochi and George Karypis. An efficient algorithm for discovering frequent subgraphs. Technical report, 2002. http://www.cs.umn.edu/~kuram/papers/fsg-long.pdf.
• 3: 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
• 4: 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
• 5: 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
• 6: 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
• 7: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 8: 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]
• 9: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 10: Rakesh Agrawal , Ramakrishnan Srikant, Fast Algorithms for Mining Association Rules in Large Databases, Proceedings of the 20th International Conference on Very Large Data Bases, p.487-499, September 12-15, 1994
• 11: 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
• 12: M. Kuramochi and G. Karypis, Finding Frequent Patterns in a Large Sparse Graph, SIAM International Conference on Data Mining, 2004.
• 13: Jiawei Han , Micheline Kamber, Data mining: concepts and techniques, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 14: 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

INDEX TERMS

Keywords:
frequent subgraphs, graph mining, pattern discovery