Large-scale graph mining using backbone refinement classes

ABSTRACT

We present a new approach to large-scale graph mining based on so-called backbone refinement classes. The method efficiently mines tree-shaped subgraph descriptors under minimum frequency and significance constraints, using classes of fragments to reduce feature set size and running times. The classes are defined in terms of fragments sharing a common backbone. The method is able to optimize structural inter-feature entropy as opposed to occurrences, which is characteristic for open or closed fragment mining. In the experiments, the proposed method reduces feature set sizes by >90 % and >30 % compared to complete tree mining and open tree mining, respectively. Evaluation using crossvalidation runs shows that their classification accuracy is similar to the complete set of trees but significantly better than that of open trees. Compared to open or closed fragment mining, a large part of the search space can be pruned due to an improved statistical constraint (dynamic upper bound adjustment), which is also confirmed in the experiments in lower running times compared to ordinary (static) upper bound pruning. Further analysis using large-scale datasets yields insight into important properties of the proposed descriptors, such as the dataset coverage and the class size represented by each descriptor. A final cross-validation run confirms that the novel descriptors render large training sets feasible which previously might have been intractable.

REFERENCES

• 1: Mohammad Al Hasan , Vineet Chaoji , Saeed Salem , Jeremy Besson , Mohammed J. Zaki, ORIGAMI: Mining Representative Orthogonal Graph Patterns, Proceedings of the 2007 Seventh IEEE International Conference on Data Mining, p.153-162, October 28-31, 2007 [doi>10.1109/ICDM.2007.45]
• 2: B. Bringmann, A. Zimmermann, L. de Raedt, and S. Nijssen. Don't Be Afraid of Simpler Patterns. In Proceedings 10th PKDD, pages 55--66. Springer-Verlag, 2006.
• 3: C. Helma. Lazy Structure-Activity Relationships (lazar) for the Prediction of Rodent Carcinogenicity and Salmonella Mutagenicity. Molecular Diversity, pages 147--158, 2006.
• 4: Tamás Horváth , Jan Ramon , Stefan Wrobel, Frequent subgraph mining in outerplanar graphs, 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.1150427]
• 5: K. Jahn and S. Kramer. Optimizing gSpan for Molecular Datasets. In Proceedings of the Third International Workshop on Mining Graphs, Trees and Sequences (MGTS-2005), 2005.
• 6: Stefan Kramer , Luc De Raedt , Christoph Helma, Molecular feature mining in HIV data, Proceedings of the seventh ACM SIGKDD international conference on Knowledge discovery and data mining, p.136-143, August 26-29, 2001, San Francisco, California [doi>10.1145/502512.502533]
• 7: Shinichi Morishita , Jun Sese, Transversing itemset lattices with statistical metric pruning, Proceedings of the nineteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.226-236, May 15-18, 2000, Dallas, Texas, United States [doi>10.1145/335168.335226]
• 8: Siegfried Nijssen , Joost N. Kok, A quickstart in frequent structure mining can make a difference, 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.1014134]
• 9: S. Nijssen and J. N. Kok. Frequent Subgraph Miners: Runtimes Don't Say Everything. In Proceedings of the International Workshop on Mining and Learning with Graphs (MLG 2006, pages 173--180, 2006.
• 10: Ulrich Rückert , Stefan Kramer, Optimizing Feature Sets for Structured Data, Proceedings of the 18th European conference on Machine Learning, September 17-21, 2007, Warsaw, Poland [doi>10.1007/978-3-540-74958-5_72]
• 11: F. Wilcoxon. Individual comparisons by ranking methods. Biometrics Bulletin, 1(6):80--83, 1945.
• 12: M. Worlein, T. Meinl, I. Fischer, and M. Philippsen. A Quantitative Comparison of the Subgraph Miners MoFa, gSpan, FFSM, and Gaston. In Proceedings of PKDD, pages 392--403, 2005.
• 13: 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
• 14: 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]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Trees

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.8 Database applications
          Subjects: Data mining; Scientific databases

  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.5 Implementation

General Terms:
Experimentation, Performance, Theory

Keywords:
classification, graph-mining, pruning