Un grand nombre d'applications nécessitent d'analyser un unique graphe attribué évoluant dans le temps. Cette tâche est particulièrement complexe car la structure du graphe et les attributs associés à chacun de ses noeuds ne sont pas figés. Dans ce travail, nous nous focalisons sur la découverte de motifs récurrents dans un tel graphe. Ces motifs, des séquences de sous-graphes connexes, représentent les évolutions récurrentes de sous-ensembles de noeuds et de leurs attributs. Différentes contraintes ont été définies (e.g. fréquence, volume, connectivité, non redondance, continuité) et un algorithme original a été proposé. Les expérimentations réalisées sur des jeux de données synthétiques et réelles démontrent l'intérêt de l'approche proposée et son passage à l'échelle.