Querying and mining graph databases

Graphs have become popular for modeling complex data in a variety of domains: chemical compounds, protein structures, protein interaction networks, database schemas, social networks, Web, XML, multimedia, etc. As a result, graph querying and mining has become important for information retrieval and analysis. However, many challenges arise in efficient processing of graph querying and mining. How to address the subgraph isomorphism problem which is NP-hard? How to measure the similarity between graphs? How to index a large collection of graphs for fast retrieval? How to optimize query processing over large-scale graphs? How to define and discover significant graph patterns in a graph database? In this dissertation, I demonstrate that the above questions can be well addressed with both theoretical soundness and practical efficiency. I first consider queries over a large collection of small graphs. For subgraph queries, I develop an approximation algorithm for the subgraph isomorphism problem. For similarity queries, I measure graph similarity through edit distance using heuristic graph mapping methods. Our index structure, called Closure-tree, organizes graphs hierarchically where each node summarizes its descendants by a generalized graph called a graph closure. Then, I propose GraphQL, a graph query language where graphs are the basic units of information and each query manipulates collections of graphs. The core of GraphQL is a graph algebra extended from the relational algebra where the selection operator is generalized to graph pattern matching and a composition operator is introduced for rewriting matched graphs. I then present efficient graph pattern matching over large graphs. In graph mining, I focus on finding significant graph patterns. For the case of a large collection of graphs, I present GraphRank, a technique that evaluates and ranks frequent subgraphs by their statistical significance. I also address feature vector mining that generalizes frequent itemset mining. In the case of mining a large weighted graph, I consider local maximal substructures around a given node. A scalable algorithm is developed for the k-MST problem (minimum spanning tree over k vertices) with approximation guarantees. All the presented techniques have been validated through extensive experiments on real and synthetic graphs.