Vous êtes ici : Accueil » Kiosque » Annonce

Identification

Identifiant: 
Mot de passe : 

Mot de passe oublié ?
Détails d'identification oubliés ?

Annonce

8 janvier 2017

Distance d'édition entre graphes : une nouvelle approche


Catégorie : Stagiaire


Définition d’une distance d’édition entre graphes
Stage de Master/3e année d’ingénieur

Luc Brun, Benoit Gaüzère, Sébastien Bougleux
8 janvier 2017


Résumé :

  • Lieu du stage : Laboratoire LITIS (Rouen) ou GREYC (Caen) à discuter avec le candidat,
  • Compétences attendues :
    — Programmation : C/C++, bonnes bases en Matlab/Octave
    — Des bases en théorie des graphes et/ou optimisation seraient un plus.
  • Contact : Luc Brun (luc.brun@ensicaen.fr)
  • Mots clés : distance d’édition, algorithmes, optimisation, GPU.
  • Suite : Le stage peut éventuellement se poursuivre par une thèse sur la conception de réseaux profonds de graphes (voir sujet également sur le site du GdR).

Contexte du stage

L’étude de masses de graphes pour des problèmes de régression ou de classification est un problème classique en informatique. On peut par exemple, vouloir prédire la propriété d’une molécule (codée par un graphe) ou indexer des images en tenant compte des relations spatiales de leurs points d’intérêt (via un graphe des k plus proches voisins des points d’intérêt). Dans ces différentes applications, il est nécessaire d’établir une métrique entre les graphes pour reconnaître les graphes similaires et dissimilaires. La distance d’édition entre graphes est une de ces métrique, sans doute la plus connue et la plus utilisée. La distance d’édition de deux graphes, disons G 1 et G 2 , est le coût minimal de la série d’opérations permettant de transformer G 1 en G 2 . Généralement ces opérations incluent les suppression/ insertion ou substitution de sommets et/ou d’arêtes. Chaque opération élémentaire est affectée d’un coût et le coût de la séquence d’opérations permettant de passer de G 1 à G 2 est simplement définie comme la somme des coûts des opérations élémentaires. Si on note Γ, l’ensemble des séquence d’opérations (également appelés chemins d’édition) la distance d’édition est définie par :

GED(G 1 , G 2 ) = min_(P ∈Γ) \sum_(e∈P) c(e) (1)

où P est un chemin d’édition, e une opération élémentaire du chemin et c(e) le coût associé à cette opération. L’équipe qui encadrera le stagiaire a démontré [2, 3, 4, 5] l’équivalence, sous certaines conditions, entre le calcul de la distance d’édition (équation 1) et la minimisation d’une fonction quadratique :

GED(G 1 , G 2 ) = min_x x^t ∆_(12) x (2)

où x est un vecteur codant un appariement partiel entre les sommets de G 1 et G 2 . La matrice ∆_12 code les coûts élémentaires de suppression, insertion ou substitution de sommets et d’arêtes.

Cette formulation transforme le problème initialement purement combinatoire en la minimisation d’une fonctionnelle quadratique. Le problème n’en est pas simplifié pour autant mais l’équation 2 ouvre la voie à la résolution du calcul de la distance d’édition par des méthodes de minimisation. Ce qui ouvre de très nombreuses possibilités.

Travail à réaliser

Le stagiaire devra dans un premier temps se familiariser avec les travaux et le code développé par l’équipe. Pour cela après une petite étude bibliographique, il sera chargé de reprendre le code actuel qui combine C++ et matlab pour le porter uniquement en C++. Il faudra dans ce cadre, concevoir des structures de données adaptées aux opérations à effectuer. L’idée est d’obtenir un code suffisamment fini pour pouvoir être distribué à l’ensemble de la communauté scientifique via internet.

Le stagiaire devra ensuite développer un algorithme à partir d’un pseudo code permettant de trouver l’ensemble des solutions minimisant un problème d’affectation linéaire. Il conviendra ensuite d’intégrer cette solution à la minimisation du problème quadratique définit par l’équation 2.

Enfin, la résolution du problème quadratique (équation 2) passe par la résolution de nombreuses approximations linéaires de ce problème. Une version parallèle de l’algorithme de résolution de ce problème est connue sous le nom d’algorithme des enchères [1]. L’étudiant devra étudier l’implémentation sous GPU de l’algorithme des enchères et étendre son application à la distance d’édition. Nous espérons ainsi passer une échelle, i.e. augmenter significativement la taille des graphes pour lesquels on peut obtenir une bonne approximation de la distance d’édition.

Références

[1] Dimitri P Bertsekas. The auction algorithm : A distributed relaxation method for the assignment problem. Annals of operations research, 14(1):105–123, 1988.

[2] Sébastien Bougleux and Luc Brun. Linear Sum Assignment with Edition. Research report, Normandie Université ; GREYC CNRS UMR 6072, March 2016.

[3] Sébastien Bougleux, Luc Brun, Vincenzo Carletti, Pasquale Foggia, Benoit Gaüzère, and Mario Vento. A Quadratic Assignment Formulation of the Graph Edit Distance. Research report,Normandie Université ; GREYC CNRS UMR 6072 ; LITIS, December 2015.

[4] Vincenzo Carletti, Benoit Gauzere, Luc Brun, and Mario Vento. Approximate graph edit distance computation combining bipartite matching and exact neighborhood substructure distance. In Cheng-Lin Liu, Bin Luo, Walter G. Kropatsch, and Jian Cheng, editors, Proceedings of the 10 th IAPR-TC15 Workshop on Graph-based Representations (GbR) in Pattern Recognition, volume 9069 of LNCS, pages 188–197, Bejing, China, May 2015. IAPR TC15, Springer International Publishing. aceptance rate :67.9

[5] Benoit Gaüzère, Sébastien Bougleux, Kaspar Riesen, and Luc Brun. Approximate graph edit distance guided by bipartite matching of bags of walks. In Structural, Syntactic, and Statistical Pattern Recognition - JointIAPR International Workshop, S+SSPR 2014. Proceedings, pages 73–82, Joensuu, Finland, August 20-22 2014.

 

Dans cette rubrique

(c) GdR 720 ISIS - CNRS - 2011-2015.