Mining tree queries in a graph

ABSTRACT

We present an algorithm for mining tree-shaped patterns in a large graph. Novel about our class of patterns is that they can contain constants, and can contain existential nodes which are not counted when determining the number of occurrences of the pattern in the graph. Our algorithm has a number of provable optimality properties, which are based on the theory of conjunctive database queries. We propose a database-oriented implementation in SQL, and report upon some initial experimental results obtained with our implementation on graph data about food webs, about protein interactions, and about citation analysis.

REFERENCES

• 1: Luc Dehaspe , Hannu Toivonen, Discovery of frequent DATALOG patterns, Data Mining and Knowledge Discovery, v.3 n.1, p.7-36, March 1999 [doi>10.1023/A:1009863704807 ]
• 2: 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
• 3: 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
• 4: 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]
• 5: 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
• 6: 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
• 7: 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.
• 8: N. Vanetik , E. Gudes , S. E. Shimony, Computing Frequent Graph Patterns from Semistructured Data, Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM'02), p.458, December 09-12, 2002
• 9: Shayan Ghazizadeh , Sudarshan S. Chawathe, SEuS: Structure Extraction Using Summaries, Proceedings of the 5th International Conference on Discovery Science, p.71-85, November 24-26, 2002
• 10: M. Kuramochi and G. Karypis. Finding frequent patterns in a large sparse graph. In M.W. Berry, U.Dayal, C.Kamath, and D.B. Skillicorn, editors, Proceedings of the Fourth SIAM International Conference on Data Mining. SIAM, 2004.
• 11: Glen Jeh , Jennifer Widom, Mining the space of graph properties, 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.1014075]
• 12: Ashok K. Chandra , Philip M. Merlin, Optimal implementation of conjunctive queries in relational data bases, Proceedings of the ninth annual ACM symposium on Theory of computing, p.77-90, May 04-04, 1977, Boulder, Colorado, United States [doi>10.1145/800105.803397]
• 13: Serge Abiteboul , Richard Hull , Victor Vianu, Foundations of Databases: The Logical Level, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 14: 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]
• 15: H.I. Scions. Placing trees in lexicographic order. In D. Michie, editor, Machine Intelligence 3, pages 43--62. Edinburgh University Press, 1968.
• 16: Gang Li , Frank Ruskey, The advantages of forward thinking in generating rooted and free trees, Proceedings of the tenth annual ACM-SIAM symposium on Discrete algorithms, p.939-940, January 17-19, 1999, Baltimore, Maryland, United States
• 17: Heikki Mannila , Hannu Toivonen, Levelwise Search and Borders of Theories in KnowledgeDiscovery, Data Mining and Knowledge Discovery, v.1 n.3, p.241-258, 1997 [doi>10.1023/A:1009796218281 ]
• 18: Dick Tsur , Jeffrey D. Ullman , Serge Abiteboul , Chris Clifton , Rajeev Motwani , Svetlozar Nestorov , Arnon Rosenthal, Query flocks: a generalization of association-rule mining, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.1-12, June 01-04, 1998, Seattle, Washington, United States
• 19: Sunita Sarawagi , Shiby Thomas , Rakesh Agrawal, Integrating Association Rule Mining with Relational Database Systems: Alternatives and Implications, Data Mining and Knowledge Discovery, v.4 n.2-3, p.89-125, July 2000
• 20: S. Chakravarthy, R. Beera, and R. Balachandran. DB-Subdue: Database approach to graph mining. In H. Dai, R. Srikant, and C. Zhang, editors, Advances in Knowledge Discovery and Data Mining, Proceedings 8th PAKDD Conference, volume 3056 of Lecture Notes in Computer Science, pages 341--350. Springer, 2004.
• 21: Rakesh Agrawal , Hiekki 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
• 22: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 23: J. Memmott, N.D. Martinez, and J.E. Cohen. Predators, parasites and pathogens: species richness, trophic generality, and body sizes in a natural food web. Journal of Animal Ecology, 69:1--15, 2000.
• 24: H. Jeong, S.P. Mason, et al. Lethality and centrality in protein networks. Nature, 411(3 May 2001).
• 25: M. Newman. The structure and function of complex networks. SIAM Review, 45(2):167--256, 2003.
• 26: R. Kumar , P. Raghavan , S. Rajagopalan , D. Sivakumar , A. Tomkins , E. Upfal, Stochastic models for the Web graph, Proceedings of the 41st Annual Symposium on Foundations of Computer Science, p.57, November 12-14, 2000
• 27: Krishna Bharat , Bay-Wei Chang , Monika Rauch Henzinger , Matthias Ruhl, Who Links to Whom: Mining Linkage between Web Sites, Proceedings of the 2001 IEEE International Conference on Data Mining, p.51-58, November 29-December 02, 2001
• 28: Proceedings of the 2002 IEEE International Conference on Data Mining (ICDM 2002), 9-12 December 2002, Maebashi City, Japan. IEEE Computer Society Press, 2002.
• 29: Nick Cercone , Tsau Y. Lin , Xindong Wu, Proceedings: 2001 IEEE International Conference on Data Mining, 29 November - 2 December 2001, San Jose, California, IEEE Computer Society Press, Los Alamitos, CA, 2001

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
SQL, canonical form, conjunctive query, equivalence checking, graph, levelwise, redundancy checking, tree query