Efficient techniques for subgraph mining and query processing
Wenqing Lin · 2015
Graph data has been so prevalent that efficiently obtaining useful information from them is highly demanded.Given massive amounts of graph data, people are often interested in a small portion, namely their subgraphs, by the processes of mining and querying.Due to the enormous number of subgraphs in the massive graph data, these processes are highly costly.In this thesis, we study three important problems on subgraph mining and query processing, i.e., frequent subgraph mining, network motif discovery, and generalized subgraph query processing.These problems find numerous applications in real world, whereas they are extremely challenging.First, mining frequent subgraphs from a large collection of graph objects is an important problem in several application domains such as bio-informatics, social networks, computer vision, etc.The main challenge in subgraph mining is efficiency, as (i) testing for graph isomorphisms is computationally intensive, and (ii) the cardinality of the graph collection to be mined may be very large.We propose a two-step filter-and-refinement approach that is suitable to massive parallelization within the scalable MapReduce computing model.We partition the collection of graphs among worker nodes, and each worker applies the filter step to determine a set of candidate subgraphs that are locally frequent in its partition.The union of all such graphs is the input to the refinement step, where each candidate is checked against all partitions and only the globally frequent graphs are retained.We devise a statistical threshold mechanism that allows us to predict which subgraphs have a high chance to become globally frequent, and thus reduce the computational overhead in the refinement step.We also propose effective strategies to avoid redundant computation in each round when searching for candidate graphs, as well as a lightweight graph compression mechanism to reduce the communication cost between machines.Extensive experimental evaluation results on several real-world large graph datasets show that the proposed approach clearly outperforms the existing stateof-the-art and provides a practical solution to the problem of frequent subgraph mining for massive collections of graphs.Second, the identification of network motifs has essential applications in numerous domains, such as pattern detection in biological networks and graph analysis in digital circuits.However, mining network motifs is computationally challenging, as it requires to enumerate subgraphs from a real-life graph, and compute the frequency of each subgraph in a large number of random graphs.In particular, existing solutions often require days i First, I want to express my most sincere appreciation to my supervisor, Prof. Xiaokui Xiao, for his patience in guiding me towards the wonderland of research, his continuous support in my PhD study, and his enthusiasm about and profound knowledge in research that always inspire me a lot.Without his great guidance, this thesis would not have been finished.