Network data is ubiquitous in a variety of domains such as mobile computing, telecommunications, and social networks. In order to analyze these networks of data for valuable structural information, it is sometimes useful to represent the data as graphs or graph streams. However, these underlying network graph streams are massive in size, which can be challenging to mine in terms of both memory and computational complexity. To address these challenges, we propose an approach that samples a large and dynamic graph stream and then uses the sampled graph to detect anomalous structures with minimal loss in accuracy and precision over analyzing the graph stream in its entirety. In our experiments, we use datasets from different domains to evaluate the performance of our proposed system. We also compare the performance of our system against others where the entire original graph is processed. Finally, we demonstrate the effectiveness of applying this approach to detect potential suspicious activities.