Nous adressons le problème de découverte de motifs dans les graphes attribués. Cette structure de données correspond à un graphe qui est augmenté par des attributs associés aux sommets. Elle permet de modéliser efficacement et intuitivement une large variété de bases de données réelles. L'analyse de ce type de graphes peut offrir une grande opportunité pour extraire des informations utiles et actionnables, par exemple, l'analyse des réseaux sociaux, réseaux biologiques, réseaux internet, etc. 

La fouille de graphes attribués nécessite des méthodes qui prennent en compte au même temps la structure du graphe et les attributs décrivant les sommets, et cela génère deux défis. Premièrement, il est important de définir un langage de motifs intuitif sur lequel on peut appliquer des stratégies de recherche efficaces. Un motif étant intuitif signifie qu'il peut être facilement interprété et compris par l'utilisateur. Sachant qu'un motif est généralement défini sur un sous-graphe, il peut donc être immense en nombre de sommets, ce qui le rend difficile à comprendre. Le coût d'assimilation du motif est donc une question importante qui doit être adressée. Le deuxième défi est la formalisation de la mesure de qualité (pertinence) des motifs. Un motif local est généralement pertinent s'il décrit des propriétés locales distinctives, autrement, ce motif serait déjà attendu en regardant les propriétés globales du graphe. Par ailleurs, la qualité d'un motif est subjective, i.e., elle dépend significativement de l'utilisateur final, de ses connaissances antérieurs sur les données et de ses préférences. Généralement, un utilisateur considère qu'un motif est utile s'il lui fournit de nouvelles connaissances, particulièrement si ce motif lui informe sur des caractéristiques ou des sujets qui intéressent habituellement l'utilisateur. Un autre problème lié à la qualité des motifs est la redondance. En d'autres termes, une méthode de fouille de données peut retourner un ensemble de motifs qui donnent des informations redondantes, par exemple, des motifs peuvent couvrir des parties significativement superposées de sommets et d'attributs. La redondance d'information peut être aussi due aux relations sémantiques entre les attributs, comme les hiérarchies d'attributs. Par exemple, dans un réseau social, si on sait déjà qu'une communauté est caractérisée par un grand intérêt lié à la "musique du rock", caractériser cette communauté encore par  "musique" serait redondant, car "musique du rock" est un sous-type de "musique". 

Dans cette thèse, nous adressons ces différents défis pour le problème de la fouille de graphes attribués. Premièrement, on introduit une méthode de découverte de sous-graphes exceptionnelles, en s'appuyant sur le cadre générale de découverte de sous-groupes. L'objectif est d'identifier des sous-graphes connexes dont le sommets partagent des caractéristiques qui les distinguent du reste du graphe. Ensuite, nous proposons des méthodes qui visent à prendre en compte l'utilisateur lors de l'évaluation de la qualité des motifs. Nous proposons une méthode qui intègre les connaissances apriori de l'utilisateur sur le graphe, ainsi que le coût d'assimilation des motifs. Cette méthode est capable de déterminer les motifs qui sont à la fois surprenants (donc informatifs) et faciles à interpréter. Pour faciliter l'assimilation, des descriptions alternatives des sous-graphes exceptionnels identifiés sont fournies. Par ailleurs, nous proposons une autre approche qui intègre les préférences de l'utilisateur. Cette méthode utilise un processus interactif avec l'utilisateur pour biaiser la qualité (le score) du motif. Nous l'exploitons particulièrement pour adresser le problème de détection d'évènements géolocalisés dans les réseaux sociaux. Ensuite, nous définissons une méthode qui considère explicitement les dépendances liées aux hiérarchies d'attributs lors de l'évaluation de la qualité des motifs, ce qui permet d'éviter la redondance due aux relations sémantiques entre les attributs. En d'autres termes, quand les attributs sont organisés hiérarchiquement, cette méthode est capable d'inférer les informations que l'utilisateur peut avoir sur quelques attributs quand il est informé sur d'autres attributs. Finalement, nous donnons la conclusion de la thèse et nous discutons les futures directions possibles.