Apprentissage dans les Graphes

Cet axe rassemble les travaux autour de la conception d’algorithmes d’apprentissage dédiés aux graphes. Il regroupe des travaux théoriques, comme la formalisation d’opérateurs de fermeture dans les graphes, et plus appliqués, concernant la famille des réseaux attribués ou les réseaux d’interactions en biologie.

Opérateurs de Fermeture pour la Fouille de Graphes

La fouille de motifs fréquents se base traditionnellement sur les notions d’opérateur de fermeture et de motif fermé. À l’aide de l’opÉrateur de fermeture, l’ensemble des motifs peut être partitionné en classes d’équivalences et les motifs fermés sont les représentants de chacune de ces classes. Ces représentants sont moins nombreux que l’ensemble des motifs fréquents et ils peuvent être énumérés efficacement. Nous avons étendu ces algorithmes aux graphes et à leurs extensions.

Nous nous sommes appuyés sur des travaux récents en fouille de données pour montrer, d’un point de vue théorique, comment préserver l’existence de l’opérateur de fermeture en affaiblissant la structure de treillis en une structure plus faible, appelée une préconfluence [CI-23], qui est en particulier la structure de l’ensemble des sous-graphes (induits) connexes d’un graphe.

Nous avons généralisé la notion de motif fermé pour que le résultat obtenu respecte des contraintes naturelles dans les graphes [ CI-45 ] ; cela permet par exemple d’énumérer les motifs dits locaux, i.e. partagés par les sommets de sous-graphes connexes et ayant d’autres propriétés topologiques désirables.

Fouille de réseaux attribués

Dans un réseau attribué, chaque sommet est pourvu d’une description sous la forme des valeurs prises par un ensemble d’attributs. En pratique, cette description est ramenée à un sous-ensemble d’items, et un motif particulier (un sous-ensemble d’items) est associé au sous-graphe induit par les sommets où ce motif est présent. Dans ce cadre, nous avons exploré les abstractions de graphes [CI-22]. Il s’agit d’une forme particulière de granularité obtenue en considérant la notion de noyau (core) d’un graphe. À un motif donné est d’abord associé le sous-graphe induit par le motif, puis ce sous-graphe est réduit en un sous-graphe noyau dont les sommets satisfont une certaine propriété topologique. Par exemple, dans le cas du noyau le plus classique, le k-core, les sommets du sous-graphe réduit doivent être de degré au moins k. Le motif fermé associé, dit fermé abstrait, est alors le plus spécifique porté par les sommets du sous-graphe noyau. Nous avons ainsi proposé une méthode générale d’énumération des motifs fermés abstraits associés à une notion de noyau.

Dans [CI-43, CL-9*], on décompose de plus ces sous-graphes noyaux en communautés structurales. Dans le cas le plus simple, ces communautés sont les composantes connexes du noyau, mais on peut utiliser des formes plus contraintes, comme les k-communautés proposées par G. Palla et al. [2]. À chaque sous-graphe noyau associé à un motif donné, et à chacune de ses communautés structurales, est alors associé un motif fermé local : le motif le plus spécifique partagé par les sommets de la communauté. Nous avons développé et expérimenté un algorithme qui récolte dans un réseau attribué les motifs locaux fréquents et les implications locales associées, c’est-à-dire valides dans la communauté.

Analyse de graphes de terrain

Nous avons poursuivi nos travaux sur l’analyse de grands graphes de terrain démarrée dès l’année 2007. Trois problématiques ont été abordées.

Détection de communautés locales. Nous avons proposé un algorithme efficace basé sur une approche gloutonne d’optimisation multi-objectif [CI-35, RI-15]. Pour le partitionnement des grands graphes en communautés, nous avons proposé des algorithmes dits centrés-graine où l’idée est de calculer un partitionnement d’un graphe en identifiant des communautés locales d’un ensemble de graines choisies avec des heuristiques adéquates [CI-34] : les graines sont les nœuds d’articulation dans le graphe [CI-33] ou sont des nœuds leader identifiés dans le graphe [RE-3].

La prévision de liens. Nous avons proposé une approche originale de prévision de liens fondée sur des techniques supervisées d’aggrégation de préférences [CI-4, CI-3], approche qui a été étendue aux réseaux hétérogènes [RI-13].

Analyse de graphes multiplexes. Un réseau multiplexe est un réseau multi-couches où chaque couche contient le même ensemble de nœuds reliés par différents ensembles de liens et les nœuds dans les différentes couches sont reliés entre eux par des liens dits de couplage. Ce nouveau modèle permet de prendre en compte, dans un formalisme unifié, différents cas intéressants issus d’applications réelles [RE-6].

Nous avons proposé une extension des travaux de [RE-3] au cas des réseaux multiplexes [RI-16]. Cet algorithme a été utilisé dans le cadre d’un système original de recommandation de tags dans les folksonomies [CO-64, CI-87]. Une bibliothèque d’analyse et de fouille de graphes multiplexes a été développée [CO-55].

Apprentissage de réseaux d’interactions

D’une manière plus appliquée, nous travaillons depuis une dizaine d’années sur des méthodes d’apprentissage et de fouille de données pour la construction de réseaux d’interactions à partir de données génomiques. Nous avons proposé un modèle hybride de réseau de régulation, permettant de prédire de façon robuste l’expression d’un gène cible en fonction de l’expression de ses régulateurs, ainsi que l’algorithme d’apprentissage construisant ce modèle. Des corégulateurs candidats sont d’abord identifiés par une méthode de fouille de données dans des données discrètes, puis un ensemble de modèles de régression linéaire faisant intervenir ces corégulateurs est ensuite appris à partir de donnés perturbées [CI-19, RI-11]. L’algorithme a été validé, en collaboration avec l’Université d’Evry sur des données réelles de l’Institut Curie.