MINING AND SEARCHING GRAPHS AND STRUCTURES (TUTORIAL) 


The 12th ACM Conference on Knowledge Discovery and Data Mining (SIGKDD'2006) Philadelphia, PA, August 20  23, 2006 by Jiawei Han*, Xifeng Yan*, and Philip S. Yu^ *Univ. of Illinois at UrbanaChampaign ^IBM T. J. Watson Research Center 

TUTORIAL SLIDES
[pdf] 

INTRODUCTION 

Scalable methods for mining, indexing, and
similarity search in graphs and other complex structures, such
as sequences, trees, and networks, have become increasingly
important in data mining and database management with broad
applications in social science, the Web, computer vision,
software engineering, cheminformatics, bioinformatics, etc. Graph mining algorithms
such as mining network motif, structural pattern with
constraints and contrast graph pattern, graph clustering, and
graph classification, have been studied extensively in recent
years. The applications built on these algorithms, such as graph
indexing and similarity search, are evolving into new components
of data management system for handling complex structured data.
The motivation for this tutorial is to present to the data
engineering community a comprehensive overview of this growing
area and discuss its potential research and application topics. In this tutorial, we will present a survey on the state of the art in graph and structural pattern mining, indexing and similarity search, and their applications. It will cover the following major themes: scalable methods for mining trees [Zak02, CXYM05], graphs [HCD94, IWM00, KK01, BB02, YH02,YH03], coherent graph patterns [HWB+04], network patterns with constraints [YZH05, PJZ05], graph indexing methods [WZJS94, PF97, GW97, CSF+01, SWG02, CLO03, SK03, YYH04], similarity search in tree and graph databases [WBD98, RGW02, KSBG02, KKSS04, YKT05, YYH05], mining networks in bioinformatics [HWB+04, KGS04, YZH05], mining social networks and the Web [KKR+99, LKF05], and other applications. 

OUTLINE 

1. Why mining, indexing, and similarity search in
graphs and structured databases? 2. From database systems to data mining and information management systems that handle complex structured data: A road map 3. Mining complex structural patterns: sequences, trees, and graphs (a) Aprioribased method (b) Patterngrowth method (c) Relational graph mining 4. Constrained graph pattern mining (a) Density constraints (b) Connectivity constraints (c) The framework of constraintbased graph mining 5. Indexing complex structures: graph indexing (a) Pathbased indexing (b) Frequent discriminative patternbased indexing 6. Similarity search in tree and graph databases (a) Featurebased distance (b) Tree/Graph edit distance (c) Maximum common subgraph 7. Graph classification (a) Pathbased classification (b) Frequent graphbased classification (c) Kernel method 8. Graph clustering and pattern summarization 9. Applications (a) Structural motifs in biological networks (b) Graph classification using structural patterns: (1) chemical compounds, and (2) protein structures 

REFERENCES (mainly Data
Mining and Database) (somehow out of date, I'll try to update it
later) 

[BB02] 
C. Borgelt and M. R. Berthold. Mining molecular
fragments: Finding relevant substructures of molecules. In Proc.
2002 Int. Conf. on Data Mining (ICDM’02), pages 211–218,
Maebashi, Japan, Dec. 2002. 
[CDK+99] 
S. Chakrabarti, B. E. Dom, S. R. Kumar, P.
Raghavan, S. Rajagopalan, A. Tomkins, D. Gibson, and J. M.
Kleinberg. Mining the web’s link structure. COMPUTER, 32:60–67,
1999. 
[CLO03] 
Q. Chen, A. Lim, and K. Ong. D(k)Index: An
adaptive structural summary for graphstructured data. In Proc.
2003 ACMSIGMOD Int. Conf. Management of Data (SIGMOD’03), pages
134–144, 2003. 
[CSF+01] 
B. Cooper, N. Sample, M. Franklin, G. Hjaltason,
and M. Shadmon. A fast index for semistructured data. In Proc.
2001 Int. Conf. Very Large Data Bases (VLDB’01), pages 341–350,
2001. 
[CXYM05] 
Y. Chi, Y. Xia, Y. Yang, and R.Muntz. Mining
closed and maximal frequent subtrees from databases of labeled
rooted trees. IEEE Trans. on Knowledge and Data Engineering,
17:190–202, 2005. 
[FFF99] 
M. Faloutsos, P. Faloutsos, and C.
Faloutsos. On powerlaw relationships of the internet topology.
In Proc. ACM SIGCOMM’99 Conf. Applications, Technologies,
Architectures, and Protocols for Computer Communication, pages
251–262, Cambridge, MA, Aug. 1999. 
[FMT04] 
C. Faloutsos, K. McCurley, and A. Tomkins.
Fast discovery of connection subgraphs. In Proc. 2004 Int. Conf.
on Knowledge Discovery and Data Mining (KDD’04), pages 118–127,
2004. 
[GW97] 
R. Goldman and J.Widom. DataGuides:
Enabling query formulation and optimization in semistructured
databases. In Proc. 1997 Int. Conf. Very Large Data Bases
(VLDB’97), pages 436–445, 1997. 
[HCD94] 
L. Holder, D. Cook, and S. Djoko.
Substructure discovery in the subdue system. In Proc. AAAI’94
Workshop on Knowledge Discovery in Databases (KDD’94), pages 169
– 180, 1994. 
[HK05] 
J. Han and M. Kamber. Data Mining:
Concepts and Techniques, 2ed. Morgan Kaufmann, 2006. 
[HWB+04] 
J. Huan, W.Wang, D. Bandyopadhyay, J.
Snoeyink, J. Prins, and A. Tropsha. Mining spatial motifs from
protein structure graphs. In Proc. of the 8th Annual Int. Conf.
on Research in Computational Molecular Biology (RECOMB’04),
pages 308–315, 2004. 
[IWM00] 
A. Inokuchi, T. Washio, and H. Motoda. An
aprioribased algorithm for mining frequent substructures from
graph data. In Proc. 2000 European Symp. Principle of Data
Mining and Knowledge Discovery (PKDD’00), pages 13–23, Lyon,
France, Sept. 2000. 
[KGS04] 
M. Koyuturk, A. Grama, and W. Szpankowski.
An efficient algorithm for detecting frequent subgraphs in
biological networks. In Proc. of the 12th International
Conference on Intelligent Systems for Molecular Biology
(ISMB’04), pages 200–207, 2004. 
[KK01] 
M. Kuramochi and G. Karypis. Frequent
subgraph discovery. In Proc. 2001 Int. Conf. on Data Mining
(ICDM’01), pages 313–320, 2001. 
[KKR+99] 
J. M. Kleinberg, R. Kumar, P. Raghavan,
S. Rajagopalan, and A. Tomkins. The web as a graph:
Measurements, models, and methods. In Proc. Int. Conf.
Combinatorics and Computing, pages 1–17, 1999. 
[KKSS04] 
K. Kailing, H. Kriegel, S. Schnauer, and
T. Seidl. Efficient similarity search for hierarchical data in
large databases. In Proc. 9th Int. Conf. on Extending Database
Technology (EDBT’04), pages 676–693, 2004. 
[KKT03] 
D. Kempe, J. Kleinberg, and E. Tardos.
Maximizing the spread of influence through a social network. In
Proc. 2003 ACM SIGKDD Int. Conf. on Knowledge Discovery and Data
Mining (KDD’03), pages 137–146, Washington, DC, Aug 2003. 
[Kle01] 
J. M. Kleinberg. Small world phenomena
and the dynamics of information. In Advances in Neural
Information Processing Systems 14 (NIPS’01), pages 431–438,
Vancouver, BC, Dec. 2001. 
[KSBG02] 
R. Kaushik, P. Shenoy, P. Bohannon, and
E. Gudes. Exploiting local similarity for efficient indexing of paths in graph structured data. In Proc. 2002 Int. Conf. Data Engineering (ICDE’02), pages 129–140, 2002. 
[LKF05] 
J. Leskovec, J. Kleinberg, and C.
Faloutsos. Graphs over time: Densification laws, shrinking diam eters and possible explanations. In Proc. 2005 ACM SIGKDD Int. Conf. on Knowledge Discovery and Data Mining (KDD’05), 2005. 
[PF97] 
E. Petrakis and C. Faloutsos. Similarity
searching in medical image databases. Knowledge and Data Engineering, 9(3):435–447, 1997. 
[PJZ05] 
J. Pei, D. Jiang, and A. Zhang. On mining
crossgraph quasicliques. In Proc. 2005 Int. Conf. Knowledge Discovery and Data Mining (KDD’05), Chicago, IL, Aug. 2005. 
[RGW02] 
J. Raymond, E. Gardiner, and P. Willett.
Rascal: Calculation of graph similarity using maximum common edge subgraphs. The Computer Journal, 45:631–644, 2002. 
[SK03] 
S. Srinivasa and S. Kumar. A platform
based on the multidimensional data model for analysis of biomolecular structures. In Proc. 2003 Int. Conf. on Very Large Data Bases (VLDB’03), pages 975–986, 2003. 
[SWG02] 
D. Shasha, J. Wang, and R. Giugno.
Algorithmics and applications of tree and graph searching. In Proc. 21th ACM Symp. on Principles of Database Systems (PODS’02), pages 39–52, 2002. 
[WBD98] 
P. Willett, J. Barnard, and G. Downs.
Chemical similarity searching. J. Chem. Inf. Comput. Sci., 38:983–996, 1998. 
[WZJS94] 
J. Wang, K. Zhang, K. Jeong, and D.
Shasha. A system for approximate tree matching. IEEE Trans. on Knowledge and Data Engineering, 6:559 – 571, 1994. 
[XHYC05] 
D. Xin, J. Han, X. Yan, and H. Cheng.
Mining compressed frequentpattern sets. In Proc. 2005 Int. Conf. Very Large Data Bases (VLDB’05), Trondheim, Norway,, Aug. 2005. 
[YCHX05] 
X. Yan, H. Cheng, J. Han, and D. Xin.
Summarizing itemset patterns: A profilebased approach. In Proc. 2005 Int. Conf. Knowledge Discovery and Data Mining (KDD’05), Chicago, IL, Aug. 2005. 
[YH02] 
X. Yan and J. Han. gSpan: Graphbased
substructure pattern mining. In Proc. 2002 Int. Conf. on Data Mining (ICDM’02), pages 721–724, Maebashi, Japan, Dec. 2002. 
[YH03] 
X. Yan and J. Han. CloseGraph: Mining
closed frequent graph patterns. In Proc. 2003 Int. Conf. Knowledge Discovery and Data Mining (KDD’03), pages 286–295, Washington, D.C., Aug. 2003. 
[YKT05] 
R. Yang, P. Kalnis, and A. Tung.
Similarity evaluation on treestructured data. In Proc. of 2005 Int. Conf. on Management of Data (SIGMOD’05), pages 754 – 765, 2005. 
[YYH04] 
X. Yan, P. Yu, and J. Han. Graph
indexing: A frequent structurebased approach. In Proc. of 2004 Int. Conf. on Management of Data (SIGMOD’04), pages 335 – 346, Paris, France, 2004. 
[YYH05] 
X. Yan, P. Yu, and J. Han. Substructure
similarity search in graph databases. In Proc. of 2005 Int. Conf. on Management of Data (SIGMOD’05), pages 766 – 777, Baltimore, MD, 2005. 
[YZH05] 
X. Yan, X. Zhou, and J. Han. Mining
closed relational graphs with connectivity constraints. In Proc. 2005 Int. Conf. Knowledge Discovery and Data Mining (KDD’05), Chicago, IL, Aug. 2005. 
[Zak02] 
M. Zaki. Efficiently mining frequent
trees in a forest. In Proc. 2002 ACM SIGKDD Int. Conf. Knowledge Discovery in Databases (KDD’02), pages 71–80, Edmonton, Canada, 2002. 