Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

Subgraph patterns are widely used in graph classification, but their effectiveness is often hampered by large number of patterns or lack of discrimination power among individual patterns. We introduce a novel classification method based on pattern co-occurrence to derive graph classification rules. Our method employs a pattern exploration order such that the complementary discriminative patterns are examined first. Patterns are grouped into co-occurrence rules during the pattern exploration, leading to an integrated process of pattern mining and classifier learning. By taking advantage of co-occurrence information, our method can generate strong features by assembling weak features. Unlike previous methods that invoke the pattern mining process repeatedly, our method only performs pattern mining once. In addition, our method produces a more interpretable classifier and shows better or competitive classification effectiveness in terms of accuracy and execution time.

REFERENCES

• 1: Christian Borgelt , Michael R. Berthold, Mining Molecular Fragments: Finding Relevant Substructures of Molecules, Proceedings of the 2002 IEEE International Conference on Data Mining, p.51, December 09-12, 2002
• 2: D. Bandyopadhyay, J. Huan, J. Liu, J. Prins, J. Snoeyink, W.Wang, and A. Tropsha. Structure-based function inference using protein family-specific fingerprints, Protein Science, vol. 15, pp. 1537--1543, 2006.
• 3: Deepak Bandyopadhyay , Jack Snoeyink, Almost-Delaunay simplices: nearest neighbor relations for imprecise points, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 4: Leo Breiman, Random Forests, Machine Learning, v.45 n.1, p.5-32, October 1 2001 [doi>10.1023/A:1010933404324]
• 5: C. Chang and C. Lin. LIBSVM: a library for support vector machines, 2001. Software available at: http://www.csie.ntu.edu.tw/~cjlin/libsvm/
• 6: Chen Chen , Cindy Xide Lin , Xifeng Yan , Jiawei Han, On effective presentation of graph patterns: a structural representative approach, Proceeding of the 17th ACM conference on Information and knowledge management, October 26-30, 2008, Napa Valley, California, USA [doi>10.1145/1458082.1458124]
• 7: Mukund Deshpande , Michihiro Kuramochi , Nikil Wale , George Karypis, Frequent Substructure-Based Approaches for Classifying Chemical Compounds, IEEE Transactions on Knowledge and Data Engineering, v.17 n.8, p.1036-1050, August 2005 [doi>10.1109/TKDE.2005.127]
• 8: 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
• 9: C. Helma, T. Cramer, S. Kramer, and L.D. Raedt. Data mining and machine learning techniques for the identification of mutagenicity inducing substructures and structure activity relationships of noncongeneric compounds. J. Chem. Inf. Comput. Sci., 44:1402--1411, 2004.
• 10: 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]
• 11: 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
• 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: T. Kudo, E. Maeda, and Y. Matsumoto. An application of boosting to graph classification. In Advances in Neural Information Processing Systems 17, pages 729--736. MIT Press, 2005.
• 15: J. Kazius, S. Nijssen, J. Kok, and T. Back A.P. Ijzerman. Substructure mining using elaborate chemical representation. J. Chem. Inf. Model., 46:597--605, 2006.
• 16: S. Nowozin, K. Tsuda, T. Uno, T. Kudo, and G. Bakir. Weighted substructure mining for image analysis. In IEEE Computer Society Conference on Computer Vision and Pattern Recognition (CVPR), IEEE Computer Society, 2007.
• 17: S. Raghavan and H. Garcia-Molina, Representing web graphs. In Proceedings of the IEEE Intl. Conference on Data Engineering, 2003.
• 18: H. Saigo, T. Kadowaki, and K. Tsuda. A linear programming approach for molecular QSAR analysis. In International Workshop on Mining and Learning with Graphs (MLG), pages 85--96, 2006.
• 19: Hiroto Saigo , Nicole Krämer , Koji Tsuda, Partial least squares regression for graph mining, Proceeding of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining, August 24-27, 2008, Las Vegas, Nevada, USA [doi>10.1145/1401890.1401961]
• 20: M. Thoma, H. Cheng, A. Gretton, J. Han, H. Kriegel, A. Smola, L. Song, P. Yu, X. Yan, K. Borgwardt. "Near-optimal supervised feature selection among frequent subgraphs", In SDM 2009, Sparks, Nevada, USA.
• 21: Vladimir N. Vapnik, The nature of statistical learning theory, Springer-Verlag New York, Inc., New York, NY, 1995
• 22: Xifeng Yan , Hong Cheng , Jiawei Han , Philip S. Yu, Mining significant graph patterns by leap search, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376662]
• 23: 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
• 24: F. Zhu, X. Yan, J. Han, and P. S. Yu, gPrune: A Constraint Pushing Framework for Graph Pattern Mining, in Proc. 2007 Pacific-Asia Conf. on Knowledge Discovery and Data Mining (PAKDD'07), Nanjing, China, May 2007.

INDEX TERMS

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

Additional Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Classifier design and evaluation; Feature evaluation and selection

General Terms:
Algorithms, Experimentation, Performance

Keywords:
classification rule, graph classification, graph mining