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

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


Catégorie : Doctorant


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

  • Lieu: la thèse se déroulera à Caen au sein du laboratoire GREYC UMR CNRS 6072.
  • Contact:

Objectifs

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.

 

Dans cette rubrique

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