HDB-subdue, A Relational Database Approach To Graph Mining And Hierarchical Reduction
Abstract
Data mining aims at discovering interesting and previously unknown patterns
from data sets. Transactional mining (association rules, decision trees etc.) can be
effectively used to find non-trivial patterns in categorical and unstructured data. For
applications that have an inherent structure (e.g., chemical compounds, proteins)
graph mining is appropriate, because mapping the structured data into other representations
would lead to loss of structure. The need for mining structured data has
increased in the past few years. Graph mining uses graph theory principles to perform
mining. Database mining of graphs aims at mining structured graph data stored in
relational database tables using SQL queries. Various kinds of data such as Social
network data, Protein, and other Bioinformatics data can be effectively represented as
graphs. Graph mining has been successful in the areas of counter terrorism analysis,
credit card fraud detection, drug discovery in pharmaceutical industry etc.
The focus of this thesis is to apply relational database techniques to accommodate
all aspects of graph mining. Our primary goal is to address scalability of graph mining to very large data sets, not currently addressed by main memory approaches.
This thesis addressed the most general graph representation including multiple
edges between any two vertices, and cycles. This thesis extends previous work
(EDB-subdue) in a number of ways: improved substructure representation to avoid
false positives during frequency counting, unconstrained substructure expansion with
pseudo duplicate elimination for expanding multiple edges, canonical ordering of substructures
for getting true count, hierarchical reduction for producing abstract pattern
and generalization of DMDL that includes the presence of multiple edges in a subgraph.
We also extend the substructure pruning to include ties when selecting top
beam substructures.