FOGGER: an algorithm for graph generator discovery

ABSTRACT

To our best knowledge, all existing graph pattern mining algorithms can only mine either closed, maximal or the complete set of frequent subgraphs instead of graph generators which are preferable to the closed subgraphs according to the Minimum Description Length principle in some applications. In this paper, we study a new problem of frequent subgraph mining, called frequent connected graph generator mining, which poses significant challenges due to the underlying complexity associated with frequent subgraph mining as well as the absence of Apriori property for graph generators. Whereas, we still present an efficient solution FOGGER for this new problem. By exploring some properties of graph generators, two effective pruning techniques, backward edge pruning and forward edge pruning, are proposed to prune the branches of the well-known DFS code enumeration tree that do not contain graph generators. To further improve the efficiency, an effective index structure, ADI++, is also devised to facilitate the subgraph isomorphism checking. We experimentally evaluate various aspects of FOGGER using both real and synthetic datasets. Our results demonstrate that the two pruning techniques are effective in pruning the unpromising parts of search space, and FOGGER is efficient and scalable in terms of the base size of input databases. Meanwhile, the performance study for graph generator-based classification model shows that generator-based model is much simpler and can achieve almost the same accuracy for classifying chemical compounds in comparison with closed subgraph-based model.

REFERENCES

• 1: Yves Bastide , Nicolas Pasquier , Rafik Taouil , Gerd Stumme , Lotfi Lakhal, Mining Minimal Non-redundant Association Rules Using Frequent Closed Itemsets, Proceedings of the First International Conference on Computational Logic, p.972-986, July 01, 2000
• 2: Jean-Francois Boulicaut , Artur Bykowski , Christophe Rigotti, Approximation of Frequency Queris by Means of Free-Sets, Proceedings of the 4th European Conference on Principles of Data Mining and Knowledge Discovery, p.75-85, September 13-16, 2000
• 3: James Cheng , Yiping Ke , Wilfred Ng , An Lu, Fg-index: towards verification-free query processing on graph databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247574]
• 4: Bernhard Ganter , C. Franzke , Rudolf Wille, Formal Concept Analysis: Mathematical Foundations, Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 5: Qiong Gao , Ming Li , Paul Vitányi, Applying MDL to learn best model granularity, Artificial Intelligence, v.121 n.1-2, p.1-29, Aug. 2000 [doi>10.1016/S0004-3702(00)00034-5]
• 6: Peter D. Grnwald , In Jae Myung , Mark A. Pitt, Advances in Minimum Description Length: Theory and Applications (Neural Information Processing), The MIT Press, 2005
• 7: P. Grünwald. A tutorial introduction to the minimum description length principle. The Computing Research Repository, math.ST/0406077, 2004.
• 8: Haiyan Hu , Xifeng Yan , Yu Huang , Jiawei Han , Xianghong Jasmine Zhou, Mining coherent dense subgraphs across massive biological networks for functional discovery, Bioinformatics, v.21 n.1, p.213-221, January 2005 [doi>10.1093/bioinformatics/bti1049]
• 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: Jun Huan , Wei Wang , Jan Prins , Jiong Yang, SPIN: mining maximal frequent subgraphs from graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014123]
• 11: 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
• 12: 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
• 13: Michihiro Kuramochi , George Karypis, Finding Frequent Patterns in a Large Sparse Graph*, Data Mining and Knowledge Discovery, v.11 n.3, p.243-271, November 2005 [doi>10.1007/s10618-005-0003-9]
• 14: J. Li, H. Li, L. Wong, J. Pei, and G. Dong. Minimum description length principle: Generators are preferable to closed patterns. In AAAI '06, Proceedings of the Twenty-First National Conference on Artificial Intelligence and the Eighteenth Innovative Application of Artificial Intelligence. AAAI Press, 2006.
• 15: Ming Li , Paul Vitányi, An introduction to Kolmogorov complexity and its applications (2nd ed.), Springer-Verlag New York, Inc., Secaucus, NJ, 1997
• 16: J. Rissanen. Modelling by the shortest data description. Automatica, 14:465--471, 1978.
• 17: Kelvin Sim , Jinyan Li , Vivekanand Gopalkrishnan , Guimei Liu, Mining Maximal Quasi-Bicliques to Co-Cluster Stocks and Financial Ratios for Value Investment, Proceedings of the Sixth International Conference on Data Mining, p.1059-1063, December 18-22, 2006 [doi>10.1109/ICDM.2006.111]
• 18: Jimeng Sun , Christos Faloutsos , Spiros Papadimitriou , Philip S. Yu, GraphScope: parameter-free mining of large time-evolving graphs, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281266]
• 19: Lini T. Thomas , Satyanarayana R. Valluri , Kamalakar Karlapalem, MARGIN: Maximal Frequent Subgraph Mining, Proceedings of the Sixth International Conference on Data Mining, p.1097-1101, December 18-22, 2006 [doi>10.1109/ICDM.2006.102]
• 20: R. M. H. Ting and J. Bailey. Mining minimal contrast subgraph patterns. In SDM'06: Proceedings of the Sixth SIAM International Conference on Data Mining, Bethesda, MD, USA, 2006. SIAM.
• 21: Hanghang Tong , Christos Faloutsos , Yehuda Koren, Fast direction-aware proximity for graph mining, Proceedings of the 13th ACM SIGKDD international conference on Knowledge discovery and data mining, August 12-15, 2007, San Jose, California, USA [doi>10.1145/1281192.1281272]
• 22: Chen Wang , Wei Wang , Jian Pei , Yongtai Zhu , Baile Shi, Scalable mining of large disk-based graph databases, Proceedings of the tenth ACM SIGKDD international conference on Knowledge discovery and data mining, August 22-25, 2004, Seattle, WA, USA [doi>10.1145/1014052.1014088]
• 23: Junmei Wang , Wynne Hsu , Mong Li Lee , Chang Sheng, A Partition-Based Approach to Graph Mining, Proceedings of the 22nd International Conference on Data Engineering, p.74, April 03-07, 2006 [doi>10.1109/ICDE.2006.7]
• 24: Jianyong Wang , Zhiping Zeng , Lizhu Zhou, CLAN: An Algorithm for Mining Closed Cliques from Large Dense Graph Databases, Proceedings of the 22nd International Conference on Data Engineering, p.73, April 03-07, 2006 [doi>10.1109/ICDE.2006.34]
• 25: D. Williams, J. Huan, and W. Wang. Graph database indexing using structured graph decomposition. In ICDE '07, IEEE 23rd International Conference on Data Engineering, pages 976--985, Istanbul, Turkey, 2007.
• 26: 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]
• 27: Xifeng Yan , Jiawei Han, gSpan: Graph-Based Substructure Pattern Mining, Proceedings of the 2002 IEEE International Conference on Data Mining, p.721, December 09-12, 2002
• 28: 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]
• 29: Xifeng Yan , X. Jasmine Zhou , Jiawei Han, Mining closed relational graphs with connectivity constraints, Proceedings of the eleventh ACM SIGKDD international conference on Knowledge discovery in data mining, August 21-24, 2005, Chicago, Illinois, USA [doi>10.1145/1081870.1081908]
• 30: 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]
• 31: Zhiping Zeng , Jianyong Wang , Lizhu Zhou , George Karypis, Coherent closed quasi-clique discovery from large dense graph databases, Proceedings of the 12th ACM SIGKDD international conference on Knowledge discovery and data mining, August 20-23, 2006, Philadelphia, PA, USA [doi>10.1145/1150402.1150506]
• 32: S. Zhang, J. Yang, and V. Cheedella. Monkey: Approximate graph mining based on spanning trees. In ICDE '07, IEEE 23rd International Conference on Data Engineering, pages 1247--1249, Istanbul, Turkey, 2007.
• 33: Peixiang Zhao , Jeffrey Xu Yu , Philip S. Yu, Graph indexing: tree + delta <= graph, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria

INDEX TERMS

Keywords:
graph classification, graph generator, graph mining