Anomaly detection is a very active research area addressed by several scientific communities such as: computer security, medicine, industry and finance. In general, this problem consists of detecting data that are significantly different from benign or normal data. However, nowadays data is increasingly represented by graphs, as graphs have the ability to model complex interactions in a simple and intuitive way. The problem of detection in this case is to identify graphs that are different from the graphs corresponding to the normal objects observed by the system. In this work, we are interested in the problem of detecting anomalies in a Graph Stream.