Annonce en lien avec l’Action/le Réseau : aucun

Laboratoire/Entreprise : Laboratoire GREYC UMR CNRS 6072
Durée : 3 ans
Contact : olivier.lezoray@unicaen.fr
Date limite de publication : 2017-05-01

Contexte :
Réseaux de convolution de graphes sans a priori de structure

Sujet :
De nombreux problèmes mettent en jeu des données dont la structure sous-jacente est non-
Euclidienne, mais qui peuvent être représentées sous la forme de graphes (souvent attribués). La complexité
de telles données, combinée avec le Big Data, requiert l’usage de techniques efficaces d’apprentissage pour
les traiter. Récemment, les techniques d’apprentissage profond se sont révélées êtres des outils très puissants
pour des problèmes mettant en jeu des données Euclidiennes disponibles en très grand nombre. En
particulier, les Réseaux de Neurones à Convolution (RNC) [1] permettent d’extraire des motifs statistiquement
significatifs de grands jeux de données et cela leur a permis d’améliorer considérablement les tâches
de reconnaissance en image, son et vidéo [2].
Récemment il y a eu un fort intérêt des communautés du traitement du signal et de l’apprentissage
automatique afin de généraliser les RNC à des graphes [3]. Ceci est un problème délicat puisque les
opérations de convolution, de descente en résolution et de mise en commun entre plusieurs couches, ne
sont bien définies que pour des grilles régulières. Ceci rend l’extension des RNC aux graphes relativement
difficile. On peut distinguer deux courants parmi ces approches d’extension des RNC aux graphes car elles
considèrent deux types de problèmes différents.
Le premier courant cherche à analyser des signaux sur des graphes de structure fixée. La majorité des
méthodes récentes proposées concernent ce premier type de problème [4, 5, 6]. Le défaut de ces approches
est qu’elles reposent sur une formulation spectrale de la convolution qui est dépendante de la transformée de
Fourier sur graphe [7] et qui n’est valide que pour le graphe en cours d’étude. Le modèle spectral appris sur
un graphe ne peut alors pas être aisément appliqué sur un autre graphe ayant une base de Fourier différente,
ce qui est relativement problématique.
Le second courant cherche à caractériser directement la structure des graphes et donc à définir des
RNC sur graphes, sans apriori de structure. Un tel problème est habituellement considéré à l’aide de
méthodes de manifold learning [8] ou bien par la caractérisation des motifs composant le graphe [9]. Par
exemple, étant donné une collection de graphes, nous désirons apprendre une fonction de classification sur
ces graphes (pour les catégoriser par exemple) et qui puisse être en mesure de considérer des graphes non
connus et de topologies éventuellement très différentes (les noeuds des graphes ne sont pas nécessairement
en correspondance). Très peu d’approches ont considéré ce problème à l’aide de RNC sur graphes et la
majorité d’entre elles utilise une étape de normalisation afin de se ramener à une grille régulière 1D ou 2D
[10, 11], ce qui ne préserve pas toute l’information du graphe initial. D’autres approches reposent sur des
patchs géométriques locaux lorsqu’une variété sous-jacente existe [12], ce qui n’est pas toujours vrai.
Dans cette thèse, nous considérons ce second type de problème et nous chercherons à nous affranchir
de tout apriori sur la structure du graphe qui puisse être présenté à un RNC. Pour cela, nous considérerons
des développements exploitant conjointement les notions de noyaux sur graphes [13], de calcul du
super-graphe d’une base de graphes [14], de coarsening et pooling par agrégation pondérée [15]. Les domaines
d’applications privilégiés seront la prédiction de propriétés de graphes moléculaires pour les graphes
symboliques et la catégorisation d’images pour les graphes à attributs réels.

References
————–
[1] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner, “Gradient-based learning applied to document recognition,”
Proceedings of the IEEE, vol. 86, no. 11, pp. 2278–2324, November 1998.
[2] Yann LeCun, Yoshua Bengio, and Geoffrey Hinton, “Deep learning,” Nature, vol. 521, no. 7553, pp. 436–444,
05 2015.
[3] Michael M. Bronstein, Joan Bruna, Yann LeCun, Arthur Szlam, and Pierre Vandergheynst, “Geometric deep
learning: going beyond euclidean data,” CoRR, vol. abs/1611.08097, 2016.
[4] Mikael Henaff, Joan Bruna, and Yann LeCun, “Deep convolutional networks on graph-structured data,” CoRR,
vol. abs/1506.05163, 2015.
[5] Michaël Defferrard, Xavier Bresson, and Pierre Vandergheynst, “Convolutional neural networks on graphs with
fast localized spectral filtering,” CoRR, vol. abs/1606.09375, 2016.
[6] Michael Edwards and Xianghua Xie, “Graph based convolutional neural network,” CoRR, vol. abs/1609.08965,
2016.
[7] D. I. Shuman, S. K. Narang, P. Frossard, A. Ortega, and P. Vandergheynst, “The emerging field of signal
processing on graphs: Extending high-dimensional data analysis to networks and other irregular domains,”
IEEE Signal Process. Mag., vol. 30, no. 3, pp. 83–98, 2013.
[8] Mikhail Belkin and Partha Niyogi, “Laplacian eigenmaps for dimensionality reduction and data representation,”
Neural Computation, vol. 15, no. 6, pp. 1373–1396, 2003.
[9] Nino Shervashidze, S. V. N. Vishwanathan, Tobias Petri, Kurt Mehlhorn, and Karsten M. Borgwardt, “Efficient
graphlet kernels for large graph comparison,” in AISTATS, 2009, pp. 488–495.
[10] Mathias Niepert, Mohamed Ahmed, and Konstantin Kutzkov, “Learning convolutional neural networks for
graphs,” in Proceedings of the 33nd International Conference on Machine Learning, ICML 2016, New York
City, NY, USA, June 19-24, 2016, 2016, pp. 2014–2023.
[11] Shaosheng Cao, Wei Lu, and Qiongkai Xu, “Deep neural networks for learning graph representations,” in
Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, February 12-17, 2016, Phoenix, Arizona,
USA., 2016, pp. 1145–1152.
[12] Jonathan Masci, Davide Boscaini, Michael M. Bronstein, and Pierre Vandergheynst, “Geodesic convolutional
neural networks on riemannian manifolds,” in 2015 IEEE International Conference on Computer Vision Workshop,
ICCV Workshops 2015, Santiago, Chile, December 7-13, 2015, 2015, pp. 832–840.
[13] John Shawe-Taylor and Nello Cristianini, Kernel Methods for Pattern Analysis, Cambridge University Press,
2004.
[14] Horst Bunke, P. Foggia, C. Guidobaldi, and M. Vento, Graph Clustering Using the Weighted Minimum Common
Supergraph, pp. 235–246, Springer Berlin Heidelberg, Berlin, Heidelberg, 2003.
[15] Cédric Chevalier and Ilya Safro, “Learning and intelligent optimization,” chapter Comparison of Coarsening
Schemes for Multilevel Graph Partitioning, pp. 191–205. Springer-Verlag, Berlin, Heidelberg, 2009.

Profil du candidat :
Le candidat doit avoir un master ou un diplôme d’ingénieur en Informatique ou en Mathématiques
Appliquées. Des connaissances en théorie des graphes, apprentissage automatique, apprentissage
profond seront très bienvenues. Le candidat effectuera ses développements en C++ et de solides bases de
programmation sont requises.

Formation et compétences requises :
Les candidats intéressés doivent envoyer (par e-mail dans un unique fichier pdf) leurs
Curriculum Vitae, relevés de Notes des deux dernières années d’étude, une lettre de motivation relative au
sujet de thèse. Le financement de la thèse se fera dans le cadre d’une bourse du ministère de l’enseignement
supérieur et de la recherche (une audition en Juin 2017 sera nécessaire).

Adresse d’emploi :
La thèse se déroulera à Caen au sein du laboratoire GREYC UMR CNRS 6072.

Document attaché : proposal_fr.pdf