Proposition de thèse – Apprentissage de métrique sur graphes – Metric Learning on Graphs

Apprentissage de métrique sur graphes  – Metric Learning on Graphs

Sujet de thèse pour septembre 2017

Equipe Apprentissage
Laboratoire LITIS EA 4108
Fédération Norm@stic FR CNRS 3638
Université de Rouen Normandie

Description du sujet

Les graphes sont des structures de données informatiques très souples qui permettent une description très riche et très fine d’une gamme très large d’ob- jets, allant des molécules aux images, en passant par de l’écriture manuscrite ou des réseaux sociaux.

Paradoxalement, malgré l’important pouvoir de représentation des graphes, la communauté de l’apprentissage automatique (Machine Learning), dont les progrès ont été impressionnants ces dernières années, en particulier avec l’apprentissage profond, s’est encore assez peu attaquée au développement d’algo- rithmes performants pour l’analyse de données représentées par des graphes. Au niveau international, on peut d’ailleurs mentionner que la communauté Fran- çaise est probablement l’une des plus dynamiques dans ce domaine. Outre leur dimensionnalité (nombre de nœuds et d’arcs) variable, une autre raison qui explique le peu de travaux relatifs à l’apprentissage à base de graphes est liée au fait que les algorithmes existant en apprentissage automatique s’appuient sur le calcul d’une distance (ou plus généralement d’un produit scalaire) entre les exemples d’apprentissage. Or, si ce calcul est immédiat dans des espaces vec- toriels, il constitue à lui seul un problème scientifique complexe lorsque l’on manipule des données de type graphe.

Les méthodes existantes pour estimer la (di)similarité entre graphes reposent souvent sur le calcul d’une distance d’édition, c’est-à-dire une fonction de coût calculée comme étant la somme de coûts d’édition élémentaire transformant un graphe en un autre. Considérant la complexité exponentielle des algorithmes de calcul exact de telles distances, les travaux récents ont cherché à calculer plus rapidement des fonctions de coût d’appariement de graphe (matching complet, isomorphisme de sous-graphe) soit de façon exacte [4, 5, 7, 6], soit grâce à des approximations [3, 8, 11, 12, 13, 1, 9], permettant de repousser la limite en taille des graphes pouvant être traités. En revanche, dans la plupart des travaux, les fonctions de coût associées aux opérations élémentaires sont considérées données ou sont déterminées en optimisant un très faible nombre de paramètres (rapport du coût lié aux nœuds par rapport à celui lié aux arcs) au regard d’un objectif (optimisation du taux d’erreur sur une tâche de classification) [10]. Peu de travaux [2] ont porté sur l’étude de la fonction de coût des opérations d’édition élémentaire et son impact sur la qualité des résultats et sur le temps de calcul. Il existe donc un réel enjeu à développer des travaux fondamentaux et applica- tifs à l’intersection de la théorie des graphes et de l’apprentissage automatique qui permettent d’apprendre une métrique entre graphes, afin de faire passer un cap aux algorithmes actuels. Les approches permettraient ainsi d’apprendre à comparer des graphes, comme les réseaux profonds apprennent à extraire des caractéristiques pertinentes.

Dans ce contexte, le sujet de thèse proposé visera dans un premier temps à étudier l’impact des fonctions de coût correspondant aux opérations d’édition élémentaire (substitution, insertion, suppression des nœuds et des arcs) sur la qualité des résultats et sur les temps de traitement. Il s’agira notamment de proposer des procédures permettant, étant donné un modèle paramétrique de la fonction de coût, de déterminer les valeurs optimales des paramètres au regard de différents objectifs. Ces objectifs peuvent être de plusieurs natures en fonction de l’information disponible dans les bases d’apprentissage. Il peut s’agir d’optimiser des performances en classification si seule la classe des objets représentés par les graphes est disponible, ou bien de respecter au mieux les appariements nœud à nœud et arc à arc, voire sous-graphe à sous-graphe, si ceux-ci sont connus.

L’étude portera également sur la nature du modèle paramétrique de la fonc- tion de coût pour déterminer si la seule intégration des différentes dimensions des étiquettes est pertinente, par exemple dans un modèle linéaire dont il faudra déterminer les pondérations, ou si la prise en compte des informations de contexte structurel (centralité de nœuds, degré, factorisation de graphe, sous-graphes fréquents…) est de nature à accélérer la mise en correspondance. Enfin, considérant la complexité des algorithmes de mise en correspondance de graphes, on pourra également étudier l’impact de l’usage d’approximations pour la détermination des fonctions de coût optimales.

Applications

Les algorithmes développés seront appliqués prioritairement à des probléma- tiques de chémo-informatique, en collaboration avec des laboratoires de chimie du territoire Normand (COBRA, CERMN, LCMT).

Contexte

Ce travail donnera lieu à des collaborations avec le laboratoire GREYC de Caen et le laboratoire LI de Tours, avec lesquels le LITIS mène des travaux communs depuis longtemps sur les problématiques d’analyse de graphes. Il est également envisagé de collaborer avec le Computer Vision Center de l’Université Autonome de Barcelone.

Financement

Cette thèse fait l’objet d’une demande de financement au sein de l’École doc- torale MIIS de Normandie Université. L’attribution définitive du financement demandé sera connue fin juin 2017.

Équipe d’encadrement :

Les travaux seront encadrés par :

Candidature

Le/la candidat(e) devra avoir une bonne connaissance théorique en appren- tissage statistique et en théorie des graphes. De bonnes aptitudes en programmation sont souhaitées. La sélection des candidats se fera sur dossier (CV, notes à la partie théorique du master 2 + lettre de motivation + lettres de recommandation) puis audition, éventuellement en distanciel. Les dossiers sont à envoyer le plus rapidement possible (et au plus tard le 28 avril) à Sebastien.Adam@univ- rouen.fr, Pierre.Heroux@univ-rouen.fr et Benoit.Gauzere@insa-rouen.fr. Les candidatures seront traitées au fur et à mesure de leur réception et une décision pourra être prise avant la date limite si un candidat donne satisfaction.

Références

  1. [1]  S. Bougleux, L. Brun, V. Carletti, P. Foggia, B. Gaüzère, and M. Vento. Graph edit distance as a quadratic assignment problem. Pattern Recogni- tion Letters, 87 :38–46, 2017.
  2. [2]  Xavier Cortés and Francesc Serratosa. Learning graph-matching edit-costs based on the optimality of the oracle’s node correspondences. Pattern Recogn. Lett., 56 :22–29, 2015.
  3. [3]  Stefan Fankhauser, Kaspar Riesen, and Horst Bunke. Speeding up graph edit distance computation through fast bipartite matching. In Proc. of the 8th IAPR Int. Workshop on Graph-Based Repres. in Pattern Recogn., pages 102–111, 2011.
  4. [4]  Derek Justice and Alfred Hero. A binary linear programming formula- tion of the graph edit distance. IEEE Trans. Pattern Anal. Mach. Intell., 28(8) :1200–1214, 2006.
  5. [5]  Pierre Le Bodic, Pierre HÃ⃝c roux, SÃ⃝c bastien Adam, and Yves Lecour- tier. An integer linear program for substitution-tolerant subgraph isomor- phism and its use for symbol spotting in technical drawings. Pattern Re- cogn., 45(12) :4214 – 4224, 2012.
  6. [6]  Julien Lerouge, Zeina Abu-Aisheh, Romain Raveaux, Pierre Héroux, and Sébastien Adam. Graph edit distance : a new binary linear programming formulation. CoRR, abs/1505.05740, 2015.
  7. [7]  Julien Lerouge, Maroua Hammami, Pierre Héroux, and Sébastien Adam. Minimum cost subgraph matching using a binary linear program. Pattern Recognition Letters, 71 :45–51, 2016.
  8. [8]  Michel Neuhaus, Kaspar Riesen, and Horst Bunke. Fast suboptimal algo- rithms for the computation of graph edit distance. In SSPR/SPR, pages 163–172, 2006.3
  9. [9]  Kaspar Riesen. Structural Pattern Recognition with Graph Edit Distance – Approximation Algorithms and Applications. Advances in Comp. Vis. and Pattern Recogn. Springer, 2015.
  10. [10]  Kaspar Riesen and Horst Bunke. Iam graph database repository for graph based pattern recognition and machine learning. In Structural, Syntac- tic, and Statistical Pattern Recognition, volume 5342 of Lecture Notes in Computer Science, pages 287–297. 2008.
  11. [11]  Kaspar Riesen and Horst Bunke. Approximate graph edit distance com- putation by means of bipartite graph matching. Image Vision Comput., 27(7) :950–959, 2009.
  12. [12]  Francesc Serratosa. Fast computation of bipartite graph matching. Pattern Recogn. Lett., 45 :244–250, 2014.
  13. [13]  Francesc Serratosa. Computation of graph edit distance : Reasoning about optimality and speed-up. Image Vision Comp., 40 :38–48, 2015.

Information Publique