The aim of this paper is to investigate the Graph Based Anomaly Detection (GBAD) systems to find anomalies or features in a graph that are inconsistent with the general or maximal substructures of the graph. A substructure miner approach was implemented. The Frequent Substructure Miner (FSM) was adopted to find the optimal substructure, which was then used to compare the normal GBAD and Minimum Description Length (MDL) approach that has been in use. The FSM approach uses graphs of size 10, 100 and 1000 nodes to determine the resulting efficiency and hence the runtime as well. The runtime determines how long the two systems require to find anomalies in each type of graph.