La recherche de motifs de graphe est l'une des opérations principales de la recherche des correspondances d'une requête dans un graphe donné. Dans ce contexte, trouver des solutions garantissant l'optimalité en termes de précision et de temps de calcul est un problème de recherche difficile et d'actualité. Différents modèles ainsi que leurs algorithmes appropriés ont été proposés pour la recherche de motifs dans les graphes de données. Cependant, l'inconvénient majeur est leur limitation à trouver des réponses significatives entraînant le problème des réponses vides. Dans cet article nous introduisons un nouveau modèle pour la recherche de motifs de graphe permettant un certain type d'assouplissement de requêtes afin d'éviter ce problème. Ensuite nous développons un algorithme efficace basé sur des techniques d'optimisation pour trouver les k-meilleurs réponses selon notre modèle. Nos expérimentations sur quatre ensembles de données réelles démontrent l'efficacité de notre approche.