Mining Graph Data

by Cook, Diane J.; Holder, Lawrence B.

• ISBN13: 9780471731900
• ISBN10: 0471731900
• Edition: 1st
• Format: Hardcover
• Copyright: 2006-11-28
• Publisher: Wiley-Interscience

Summary

This text takes a focused and comprehensive look at mining data represented as a graph, with the latest findings and applications in both theory and practice provided. Even if you have minimal background in analyzing graph data, with this book you'll be able to represent data as graphs, extract patterns and concepts from the data, and apply the methodologies presented in the text to real datasets. There is a misprint with the link to the accompanying Web page for this book. For those readers who would like to experiment with the techniques found in this book or test their own ideas on graph data, the Web page for the book should be http://www.eecs.wsu.edu/MGD.

Author Biography

DIANE J. COOK, PhD, is the Huie-Rogers Chair Professor in the School of Electrical Engineering and Computer Science at Washington State University. Her extensive research in artificial intelligence and data mining has been supported by grants from the National Science Foundation, NASA, DARPA, and Texas Instruments. Dr. Cook is the coauthor of Smart Environments: Technology, Protocols, and Applications (Wiley).

LAWRENCE B. HOLDER, PhD, is Professor in the School of Electrical Engineering and Computer Science at Washington State University, where he teaches and conducts research in artificial intelligence, machine learning, data mining, graph theory, parallel and distributed processing, and cognitive architectures.

Table of Contents

Preface	xiii
Acknowledgments	xv
Contributors	xvii
Introduction	1	(14)
Lawrence B. Holder
Diane J. Cook
Terminology	2	(1)
Graph Databases	3	(7)
Book Overview	10	(5)
References	11	(4)
Part I GRAPHS	15	(82)
Graph Matching---Exact and Error-Tolerant Methods and the Automatic Learning of Edit Costs	17	(18)
Horst Bunke
Michel Neuhaus
Introduction	17	(1)
Definitions and Graph Matching Methods	18	(6)
Learning Edit Costs	24	(4)
Experimental Evaluation	28	(3)
Discussion and Conclusions	31	(4)
References	32	(3)
Graph Visualization and Data Mining	35	(30)
Walter Didimo
Giuseppe Liotta
Introduction	35	(3)
Graph Drawing Techniques	38	(10)
Examples of Visualization Systems	48	(7)
Conclusions	55	(10)
References	57	(8)
Graph Patterns and the R-Mat Generator	65	(32)
Deepayan Chakrabarti
Christos Faloutsos
Introduction	65	(2)
Background and Related Work	67	(12)
NetMine and R-MAT	79	(3)
Experiments	82	(4)
Conclusions	86	(11)
References	92	(5)
Part II MINING TECHNIQUES	97	(248)
Discovery of Frequent Substructures	99	(18)
Xifeng Yan
Jiawei Han
Introduction	99	(1)
Preliminary Concepts	100	(1)
Apriori-based Approach	101	(2)
Pattern Growth Approach	103	(4)
Variant Substructure Patterns	107	(2)
Experiments and Performance Study	109	(3)
Conclusions	112	(5)
References	113	(4)
Finding Topological Frequent Patterns from Graph Datasets	117	(42)
Michihiro Kuramochi
George Karypis
Introduction	117	(1)
Background Definitions and Notation	118	(4)
Frequent Pattern Discovery from Graph Datasets---Problem Definitions	122	(5)
FSG for the Graph-Transaction Setting	127	(4)
SiGraM for the Single-Graph Setting	131	(10)
Grew---Scalable Frequent Subgraph Discovery Algorithm	141	(8)
Related Research	149	(2)
Conclusions	151	(8)
References	154	(5)
Unsupervised and Supervised Pattern Learning in Graph Data	159	(24)
Diane J. Cook
Lawrence B. Holder
Nikhil Ketkar
Introduction	159	(1)
Mining Graph Data Using Subdue	160	(5)
Comparison to Other Graph-Based Mining Algorithms	165	(1)
Comparison to Frequent Substructure Mining Approaches	165	(5)
Comparison to ILP Approaches	170	(9)
Conclusions	179	(4)
References	179	(4)
Graph Grammar Learning	183	(20)
Istvan Jonyer
Introduction	183	(1)
Related Work	184	(1)
Graph Grammar Learning	185	(8)
Empirical Evaluation	193	(6)
Conclusion	199	(4)
References	199	(4)
Constructing Decision Tree Based on Chunkingless Graph-Based Induction	203	(24)
Kouzou Ohara
Phu Chien Nguyen
Akira Mogi
Hiroshi Motoda
Takashi Washio
Introduction	203	(2)
Graph-Based Induction Revisited	205	(2)
Problem Caused by Chunking in B-GBI	207	(1)
Chunkingless Graph-Based Induction (CI-GBI)	208	(6)
Decision Tree Chunkingless Graph-Based Induction (DT-ClGBI)	214	(10)
Conclusions	224	(3)
References	224	(3)
Some Links Between Formal Concept Analysis and Graph Mining	227	(26)
Michel Liquiere
Presentation	227	(1)
Basic Concepts and Notation	228	(1)
Formal Concept Analysis	229	(2)
Extension Lattice and Description Lattice Give Concept Lattice	231	(4)
Graph Description and Galois Lattice	235	(5)
Graph Mining and Formal Propositionalization	240	(9)
Conclusion	249	(4)
References	250	(3)
Kernel Methods for Graphs	253	(30)
Thomas Gartner
Tamas Horvath
Quoc V. Le
Alex J. Smola
Stefan Wrobel
Introduction	253	(1)
Graph Classification	254	(12)
Vertex Classification	266	(13)
Conclusions and Future Work	279	(4)
References	280	(3)
Kernels as Link Analysis Measures	283	(28)
Masashi Shimbo
Takahiko Ito
Introduction	283	(1)
Preliminaries	284	(2)
Kernel-based Unified Framework for Importance and Relatedness	286	(4)
Laplacian Kernels as a Relatedness Measure	290	(7)
Practical Issues	297	(2)
Related Work	299	(1)
Evaluation with Bibliographic Citation Data	300	(8)
Summary	308	(3)
References	308	(3)
Entity Resolution in Graphs	311	(34)
Indrajit Bhattacharya
Lise Getoor
Introduction	311	(3)
Related Work	314	(4)
Motivating Example for Graph-Based Entity Resolution	318	(4)
Graph-Based Entity Resolution: Problem Formulation	322	(3)
Similarity Measures for Entity Resolution	325	(5)
Graph-Based Clustering for Entity Resolution	330	(3)
Experimental Evaluation	333	(8)
Conclusion	341	(4)
References	342	(3)
Part III APPLICATIONS	345	(124)
Mining from Chemical Graphs	347	(34)
Takashi Okada
Introduction and Representation of Molecules	347	(8)
Issues for Mining	355	(1)
CASE: A Prototype Mining System in Chemistry	356	(2)
Quantitative Estimation Using Graph Mining	358	(4)
Extension of Linear Fragments to Graphs	362	(4)
Combination of Conditions	366	(9)
Concluding Remarks	375	(6)
References	377	(4)
Unified Approach to Rooted Tree Mining: Algorithms and Applications	381	(30)
Mohammed Zaki
Introduction	381	(1)
Preliminaries	382	(2)
Related Work	384	(1)
Generating Candidate Subtrees	385	(7)
Frequency Computation	392	(5)
Counting Distinct Occurrences	397	(2)
The SLEUTH Algorithm	399	(2)
Experimental Results	401	(4)
Tree Mining Applications in Bioinformatics	405	(4)
Conclusions	409	(2)
References	409	(2)
Dense Subgraph Extraction	411	(32)
Andrew Tomkins
Ravi Kumar
Introduction	411	(3)
Related Work	414	(2)
Finding the densest subgraph	416	(2)
Trawling	418	(3)
Graph Shingling	421	(8)
Connection Subgraphs	429	(9)
Conclusions	438	(5)
References	438	(5)
Social Network Analysis	443	(26)
Sherry E. Marcus
Melanie Moy
Thayne Coffman
Introduction	443	(1)
Social Network Analysis	443	(9)
Group Detection	452	(1)
Terrorist Modus Operandi Detection System	452	(13)
Computational Experiments	465	(2)
Conclusion	467	(2)
References	468	(1)
Index	469