Graph-based Learning Using A Naive Bayesian Classifier

Abstract

Graph-based data representation is becoming increasingly more commonplace, as graphs can represent some kinds of data more efficiently than relational tables. As such, interesting patterns in the form of subgraphs can be discovered by mining these graph-based datasets. Because the learned patterns can be used to predict future occurrences, it is necessary to learn graphical concepts that can optimally classify the data in the presence of uncertainty. This work explores the construction and learning of optimal naïve Bayesian graph classifiers to distinguish between positive and negative graphs given a set of graphs as examples. Whereas most previous work in graph-based data mining has been restricted to exact graph matching algorithms, the classifiers discovered using this approach are not similarly restricted, and thus are able to classify graphs in the presence of missing data.