Algorithme de mise en correspondance de chemins

Dans le chapitre précédent, nous avons présenté des fonctions noyaux comme fonc- tions de similarité entre graphes. Bien que ces fonctions possèdent des propriétés in- téressantes, leur évaluation est coûteuse en temps de calcul. Nous allons présenter dans ce chapitre un cadre permettant de limiter le temps de calcul de ces fonctions.Le temps de calcul de ces fonctions est lié au temps nécessaire pour apparier deux chemins de deux graphes et calculer leur similarité. Par exemple, la fonction noyau de Kashima utilise la somme des similarités de tous les appariements possibles. Pour résoudre ce problème, on recense diérentes méthodes dans la littérature pour :

fortement réduit ce nombre en n’utilisant que les chemins représentant des plus courts chemins entre 2 sommets donnés. Outre une réduction, ce choix permet l’utilisation d’algorithmes performants pour la génération des chemins. De plus, la formule du noyau considéré reste inchangée en utilisant une méthode de réduction du nombre de chemins. Néanmoins ce genre de réduction peut poser des problèmes quant à la conservation des propriétés mathématiques de la fonction noyau sur graphe. Enn, il impose un choix qui peut se révéler important selon la morphologie structurelle du graphe.La méthode d’approximation est le plus souvent utilisée lorsque le nombre de cheminsest inni ou très grand. Il s’agit d’approximer les valeurs des fonctions en eectuant soit des calculs de fonctions proches mais plus simples, soit en supprimant certains calculs ayant une faible contribution sur la valeur nale, soit en arrêtant, avant terminaison, le calcul en utilisant des propriétés de convergence. Kashima l’utilise pour pallier unepossibilité de temps de calcul inni (si le nombre de chemins est inni, le nombre d’ap- pariements le sera. Par conséquent, le calcul de la somme sur toutes les similarités des appariements ne se nit jamais) . Néanmoins, celle-ci pose des problèmes de non conser- vation des propriétés mathématiques des fonctions noyaux utilisées dans la similarité.

Le stockage d’éléments s’arrête le plus souvent au stockage des similarités sur les arêtes et les sommets. La similarité des chemins peut s’écrire le plus souvent comme une combinaison de la similarité de ses sous-éléments arêtes et sommets. La similarité des graphes peut elle-même combiner la similarité de nombreux chemins. Ainsi ces similarités d’arêtes et de sommets interviennent de nombreuses fois dans le calcul des similarités de chemins et de graphes.Notre méthode exploite la redondance et la récursivité de l’expression des appariements de chemins dans une représentation sous forme d’arbre. Dans cette représentation, un chemin entre la racine et la feuille de l’arbre est une solution d’appariement de chemins. Cette représentation permet de se placer dans le cadre d’exploration d’un arbre de recherche. Par conséquent des algorithmes de type A, par exemple le « branch andNous présentons la mise en représentation sous forme d’arbre d’appariements pour une catégorie de fonctions de mise en correspondance de graphe. Puis nous montrons l’application de cette représentation d’arbre avec des ensembles de chemins pour con- struire un arbre de recherche parcourant l’ensemble des possibilités. Enn nous présen- tons l’utilisation algorithmique de ces représentations pour calculer les similarités noy- aux sur graphes.

Représentation arborescente du calcul de sim- ilarité de chemins

Les chemins ainsi que leur fonctions de similarité basées sur la similarité entre som- mets et arêtes sont calculables ou constructibles récursivement. Les éléments possé- dant cette propriété récursive peuvent facilement se représenter sous forme d’arbre en regroupant les parties communes. La littérature a détaillé l’utilisation d’arbres de recherche sur des appariements de chemins entre deux graphes. Ce qui nous intéresse est d’obtenir un arbre de recherche dans le cadre d’ensemble de chemins particuliers. Et de plus, il faut que la fonction de similarité entre les chemins soit calculable lors de l’ex- ploration de l’arbre. Pour cela il faut vérier que le calcul peut lui aussi se représenter sous forme d’arbre. Nous allons dans un premier temps montrer au travers d’exemples comment on peut eectuer cette représentation arborescente puis dans un deuxième temps, formaliser l’écriture de ces similarités au travers de l’arbre. Enn nous mettrons en place une structure arborescente qui permettra la mise en place dans la prochaine).La représentation de la gure 4.1(c) se rapproche plus d’un arbre représentant les ap- pariements. La gure 4.1(b) montre une représentation de ces similarités sous forme d’arbre : la similarité commune est encore plus visible (premier n÷ud). La valeur de similarité portée par le premier n÷ud de l’arbre de la gure 4.1(b) est égale à la somme des similarités portées par les deux premiers n÷uds de l’arbre de la gure 4.1(c).