Frequent subgraph mining in outerplanar graphs

ABSTRACT

In recent years there has been an increased interest in algorithms that can perform frequent pattern discovery in large databases of graph structured objects. While the frequent connected subgraph mining problem for tree datasets can be solved in incremental polynomial time, it becomes intractable for arbitrary graph databases. Existing approaches have therefore resorted to various heuristic strategies and restrictions of the search space, but have not identified a practically relevant tractable graph class beyond trees. In this paper, we define the class of so called tenuous outerplanar graphs, a strict generalization of trees, develop a frequent subgraph mining algorithm for tenuous outerplanar graphs that works in incremental polynomial time, and evaluate the algorithm empirically on the NCI molecular graph dataset.

REFERENCES

• 1: Rakesh Agrawal , Heikki Mannila , Ramakrishnan Srikant , Hannu Toivonen , A. Inkeri Verkamo, Fast discovery of association rules, Advances in knowledge discovery and data mining, American Association for Artificial Intelligence, Menlo Park, CA, 1996
• 2: Y. Chi, R. R. Muntz, S. Nijssen, and J. N. Kok. Frequent subtree mining - an overview. Fundamenta Informaticae, 66(1-2):161--198, 2005.
• 3: Yun Chi , Yirong Yang , Richard R. Muntz, Canonical forms for labelled trees and their applications in frequent subtree mining, Knowledge and Information Systems, v.8 n.2, p.203-234, August 2005 [doi>10.1007/s10115-004-0180-7]
• 4: D. J. Cook and L. B. Holder. Substructure discovery using minimum description length and background knowledge. Journal of Artificial Intelligence Research, 1:231--255, 1994.
• 5: 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]
• 6: Tomas Feder , Pavol Hell, List homomorphisms to reflexive graphs, Journal of Combinatorial Theory Series B, v.72 n.2, p.236-250, March 1998 [doi>10.1006/jctb.1997.1812]
• 7: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 8: F. Harary. Graph Theory. Addison--Wesley, Reading, Massachusetts, 1971.
• 9: J. E. Hopcroft , J. K. Wong, Linear time algorithm for isomorphism of planar graphs (Preliminary Report), Proceedings of the sixth annual ACM symposium on Theory of computing, p.172-184, April 30-May 02, 1974, Seattle, Washington, United States [doi>10.1145/800119.803896]
• 10: T. Horváth, B. Bringmann, and L. D. Raedt. Frequent hypergraph mining. Unpublished manuscript, 2004.
• 11: 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]
• 12: David S. Johnson , Christos H. Papadimitriou, On generating all maximal independent sets, Information Processing Letters, v.27 n.3, p.119-123, March 25, 1988 [doi>10.1016/0020-0190(88)90065-8]
• 13: Andrzej Lingas, Subgraph isomorphism for biconnected outerplanar graphs in cubic time, Theoretical Computer Science, v.63 n.3, p.295-302, March 1989 [doi>10.1016/0304-3975(89)90011-X]
• 14: D. W. Matula. Subtree isomorphism in O(n5/2). Annals of Discrete Mathematics, 2:91--106, 1978.
• 15: S. L. Mitchell. Linear algorithms to recognize outerplanar and maximal outerplanar graphs. Information Processing Letters, 9(5):229--232, 1979.
• 16: R. C. Read and R. E. Tarjan. Bounds on backtrack algorithms for listing cycles, paths, and spanning trees. Networks, 5(3):237--252, 1975.
• 17: Ron Shamir , Dekel Tsur, Faster Subtree Isomorphism, Journal of Algorithms, v.33 n.2, p.267-280, Nov. 1999 [doi>10.1006/jagm.1999.1044]
• 18: M. M. Syslo. The subgraph isomorphism problem for outerplanar graphs. Theoretical Computer Science, 17:91--97, 1982.
• 19: R. E. Tarjan. Depth first search and linear graph algorithms. SIAM J. Comput., 1(2):146--160, 1972.
• 20: 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:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Pattern matching

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

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Chemistry

General Terms:
Algorithms, Experimentation

Keywords:
computational chemistry, frequent pattern discovery, graph mining