Discovering frequent topological structures from graph datasets

ABSTRACT

The problem of finding frequent patterns from graph-based datasets is an important one that finds applications in drug discovery, protein structure analysis, XML querying, and social network analysis among others. In this paper we propose a framework to mine frequent large-scale structures, formally defined as frequent topological structures, from graph datasets. Key elements of our framework include, fast algorithms for discovering frequent topological patterns based on the well known notion of a topological minor, algorithms for specifying and pushing constraints deep into the mining process for discovering constrained topological patterns, and mechanisms for specifying approximate matches when discovering frequent topological patterns in noisy datasets. We demonstrate the viability and scalability of the proposed algorithms on real and synthetic datasets and also discuss the use of the framework to discover meaningful topological structures from protein structure data.

REFERENCES

• 1: Reinhard Diestel. Graph Theory. Springer-Verlag, 2000.
• 2: H. Hofer, C. Borgelt, and M. R. Berthold. Large scale mining of molecular fragments with wildcards. In Advances in Intelligent Data Analysis V, pages 380--389, 2003.
• 3: 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]
• 4: Akihiro Inokuchi , Takashi Washio , Hiroshi Motoda, Complete Mining of Frequent Patterns from Graphs: Mining Graph Data, Machine Learning, v.50 n.3, p.321-354, March 2003 [doi>10.1023/A:1021726221443 ]
• 5: Ruoming Jin, Chao Wang, Dimitrii Polshakov, Srinivasan Parthasarathy, and Gagan Agrawal. Discovering frequent topological structures from graph datasets. Technical report, CSE, Ohio State University.
• 6: 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
• 7: Thorsen Meinl, Christian Borgelt, Michael R. Berthold, and Michael Philippsen. Mining fragments with fuzzy chains in molecular databases. In Second International Workshop on Mining Graphs, Trees and Sequences (MGTS2004), 2004.
• 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: H. Palsdottir and C. Hunte. Lipids in membrane protein structures. BBA, 1666:2--18, 2004.
• 10: Srinivasan Parthasarathy , Matt Coatney, Efficient Discovery of Common Substructures in Macromolecules, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.362, December 09-12, 2002
• 11: D. Polshakov, K. Marsolo, and S. Parthasarathy. Mining 3d-motifs using phisical-chemical constraints: application to cardiolipin binding sites. In ISMB, 2005.
• 12: A. Srinivasan, R.D. King, S.H. Muggleton, and M. Sternberg. The predictive toxicology evaluation challenge. In IJCAI, pages 1--6, 1997.
• 13: 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

INDEX TERMS

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

General Terms:
Algorithms

Keywords:
frequent graph pattern, graph mining, topological minor