Graph classification is an important data mining task that has attracted considerable attention recently. This paper presents a probabilistic substructure-based approach for classifying graph-based data. More specifically, we use a frequent subgraph mining algorithm to extract substructure based descriptors and apply the maximum entropy principle to build a classification model from the frequent subgraphs. We perform extensive experiments to compare the performance of the proposed approach against existing feature vector methods using AdaBoost and Support Vector Machine. Keywords: Graph classification, Maximum entropy, frequent subgraph mining .