A great number of applications require to analyze a single attributed graph that changes over time. This task is particularly complex because both graph structure and attributes associated with each node can change. In the present work, we focus on the discovery of recurrent patterns in such a graph. These patterns are sequences of subgraphs which represent recurring evolutions of subsets of nodes w.r.t. their attributes. Various constraints have been defined (frequency, volume, connectivity, non-redundancy and temporal continuity) and an original algorithm has been developed. Experiments performed on synthetic and real-world datasets have demonstrated the interest of our approach and its scalability.