Models and Algorithms for Mining Subgraph Coverage Patterns and Graph Transactional Coverage Patterns

Abstract

The process of data mining discovers interesting knowledge from large amounts of data. Given a newlinelarge amount of data, we have several data mining software systems for summarizing/characterizing, newlineextracting frequent patterns and association rules, classification, and clustering tasks. The data mining newlinebased systems are employed to improve the performance of e-commerce systems, marketing, search newlinesystems, banking, healthcare, etc. Investigating data mining approaches to extract new knowledge from newlinethe given data is one of the active research areas. Graph model is widely employed to model the real newlineworld. For example, a chemical compound, a protein-ligand complex, and an XML document can be newlinemodeled as a graph or a graph transaction. In the literature, the topic of extracting the knowledge of newlinefrequent subgraphs from the given Graph Transactional Dataset (GTD) has been extensively studied. It newlinehas been shown that such knowledge could help in the drug discovery process. So far, in the literature, newlinethe issue of extracting coverage-related knowledge from GTD has not yet been explored. In this thesis, newlinewe propose new data mining models and approaches to extract two types of knowledge patterns from newlineGTDs. newlineMotivated by the issues in the process of drug discovery, as the first contribution, we propose the newlinemodel and approach to extract the coverage-related knowledge of potential subgraph patterns from the newlinegiven GTD. A subgraph pattern is a set of subgraphs. We consider that a subgraph covers the graph newlinetransaction if it belongs to that graph transaction. A subgraph pattern is considered as Subgraph Cov- newlineerage Pattern (SCP) if the ratio of the union of the graph transactions covered by the subgraphs of the newlinesubgraph pattern to the size of GTD is not less than a user-given threshold value. We have defined newlinethree metrics to characterize an SCP. First, the relative frequency metric ensures that each subgraph of newlinean SCP should appear in the threshold number of graph transactions. Second, the coverage support newlinemetric ensures that the union of gr