Mesurer la similarité de graphes

National audienceMesurer la similarité d'images est un problème qui se pose dans de nombreuses applications, que ce soit pour rechercher des images, les classifier ou encore les confronter à des modèles pour les "reconnaître". Quand les images sont représentées par des graphes, on peut mesurer la similarité de deux images en appariant les sommets des graphes associés aux images de façon à retrouver leurs caractéristiques communes. Différentes sortes d'appariements de graphes, impliquant différentes mesures de similarité, ont été proposées, e.g., l'isomorphisme de (sous-)graphes pour mesurer l'équivalence ou l'inclusion de deux graphes, et la distance d'édition de graphes pour mesurer le coût de transformation d'un graphe en un autre. Ces différents appariements sont "univoques" dans le sens où un sommet d'un graphe ne peut être apparié qu'à au plus un sommet de l'autre graphe. Nous proposons ici une nouvelle mesure de similarité de graphes basée sur un appariement multivoque des sommets des graphes, chaque sommet pouvant être apparié à un ensemble de sommets de l'autre graphe. Cet aspect nous permet notamment de comparer des graphes décrivant des images à différents niveaux de granularité, et de prendre en compte les problèmes de sur- et de sous-segmentation des images. Notre mesure de similarité est générique dans le sens où elle est paramétrée par des fonctions de similarité qui permettent d'exprimer des connaissances de similarité propres à l'application considérée. En particulier, nous montrons que toutes les mesures de similarité proposées jusqu'alors peuvent être vues comme un cas particulier de notre mesure. Nous nous intéressons également au problème du calcul de cette similarité, et nous proposons et comparons trois algorithmes : un algorithme glouton, un algorithme basé sur une recherche locale Taboue réactive et un algorithme basé sur l'optimisation par colonies de fourmis