Programmes de recherche

DC-GNN : Deep Clustering with Graph Neural Networks for real world data

Contexte

L'apprentissage non supervisé ou clustering est un sujet de recherche primordial en sciences des données et en apprentissage automatique. Grâce aux progrès technologiques, une énorme quantité d'images, de textes, de réseaux, et tout autre type de données sont désormais disponibles. Cependant, leur étiquetage est souvent coûteux, fastidieux et nécessite l’intervention des experts. Il existe donc un réel besoin d'analyser les données non étiquetées et de révéler leur structure sous-jacente. L'apprentissage non supervisé peut aboutir à des outils très puissants capables de découvrir des groupes et des structures particulières dans des bases de données non étiquetées. L'une des principales raisons du succès de ce type d’apprentissage vient du fait qu'il peut être utilisé pour n'importe quel domaine ou ensemble de données où les annotations ne sont pas disponibles (données commerciales et socio-économiques, données énergétiques, assurance, transport/mobilité, applications environnementales, santé, surveillance et sécurité, agriculture, etc.). Par exemple, la communauté médicale s'intéresse de plus en plus à l'utilisation de techniques d’apprentissage non supervisées dans le diagnostic des troubles (cancer du sein [1], maladies de Parkinson et d'Alzheimer, maladies cardiaques et diabétiques, épilepsie [2]).

A son tour, le clustering profond a réalisé des avancées dans une variété de tâches d’apprentissage automatique au cours des dernières années, particulièrement lorsque les données sont structurées en une dimension, comme pour les signaux médicaux, le texte, la parole, etc. ou en deux dimensions, comme pour la reconnaissance des formes dans les images. Cependant, peu d’études ont été réalisées pour explorer l’applicabilité du clustering profond sur les graphes, un concept puissant pour la représentation des relations entre des paires d’entités. Vue que les données ayant une structure de graphes inhérentes peuvent être trouvées dans de nombreuses disciplines, le clustering profond sur graphe va certainement impliquer un changement de paradigme sociétal dans de nombreux domaines. A titre d’illustration, les graphes peuvent décrire des composés chimiques et moléculaires, ou des surfaces des modèles tridimensionnels, ou des interactions sociales ou des bases de connaissance, ou des systèmes de recommandation, ou des connections des réseaux urbains, pour n’en nommer que quelques-uns.

Problématique

Le clustering profond est un outil important qui contribue à une meilleure compréhension, récupération, visualisation et organisation des données massives, en plus d'être un élément important des systèmes décisionnels complexes. Les méthodes de clustering traditionnelles, par exemple, k-moyennes (k-Means) [3] et les modèles de mélanges gaussiens (Gaussian Mixture Models) [4], reposent entièrement sur les représentations de données d'origine et peuvent alors être inefficaces lorsqu'elles se trouvent dans un espace de grande dimension - un problème communément appelé la malédiction de la dimensionnalité. Une solution intuitive largement étudiée consistait à projeter les données d'un espace de grande dimension en un espace de dimension inférieure dans lequel le clustering peut être plus facile [5]. De telles techniques, basées sur des mesures statistiques, s’avèrent non optimales en vue de l'objectif principal du clustering qui est de découvrir la structure sous-jacente des clusters. Une autre solution consistait à utiliser les réseaux de neurones profonds (Deep Neural Network DNN) pour effectuer le clustering.

Récemment, plusieurs algorithmes de clustering profond ont été développés, et ces algorithmes peuvent être divisés en deux types : (i) les algorithmes à deux étapes, qui utilisent l’apprentissage profond afin d’apprendre les caractéristiques pertinentes des données massives puis appliquent les algorithmes de clustering classiques sur ces nouvelles représentations réduites, et (ii) les approches qui apprennent conjointement les caractéristiques pertinentes des données ainsi que les clusters. Le premier type d'algorithmes s'appuie sur des cadres et des techniques d'apprentissage profond non supervisés existants. Par exemple, dans [6] les auteurs proposent un modèle de fusion basé sur le réseau de neurones profond à convolution (CNN) et les autoencondeurs (AE) pour extraire les caractéristiques non supervisées des signaux d'électroencéphalogramme, puis l’utilisation des algorithmes de clustering traditionnels pour détecter les anomalies (crises d'épilepsie). Etant donné que l'apprentissage des caractéristiques est découplé du clustering, les algorithmes en deux étapes sont moins performants que ceux qui apprennent conjointement les caractéristiques et les clusters en une seule étape. Ces derniers algorithmes définissent explicitement une fonction objective propre au clustering. Dans [7] les auteurs proposent un algorithme de clustering d’image qui intègre l’apprentissage des caractéristiques et des clusters, avec une fonction coût multiobjective.

Malgré la grande efficacité qu’a pu démontrer ces algorithmes dans des domaines divers, ces méthodes héritent des inconvénients inhérents au clustering traditionnel, comme le besoin de fixer a priori le nombre de clusters, l’utilisation des procédures d'optimisation discrètes, etc.

D'autres algorithmes de clustering profond ont été spécifiquement conçus pour le clustering d'images [8, 9, 10]. Ces travaux exploitent les réseaux de neurones convolutifs (CNN), qui ont largement contribué aux principales avancées de la vision par ordinateur. Il convient de mentionner que la capacité de généralisation de ces algorithmes spécifiques à l'image à d'autres types de données (texte, réseaux, etc.) n'est pas garantie.

De nos jours, l'apprentissage avec des données de graphes a attiré une attention croissante car les graphes sont de plus en plus présents dans de nombreuses applications [11], telles que l'analyse des réseaux sociaux [12, 13], l'analyse des réseaux de citations [14], le système de recommandation de produits [15, 16], les trafics des villes [17], les réseaux d’énergie, etc. Les graphes sont des données non structurées, complexes, parcimonieuses, et de grande dimension. Ceci rend difficile l’apprentissage des graphes.

De nombreux algorithmes de clustering profond des graphes, basés principalement sur les réseaux de neurones graphiques (GNN) [18], ont été proposés au cours de la dernière décennie. Toutefois, le clustering profond reste un domaine ouvert et difficile pour plusieurs raisons. En effet, ces méthodes optimisent des fonctions objectives qui ne sont pas inhérentes au clustering, ce qui ne permet pas de garantir de bonnes capacités pour la séparation de différents groupes. De plus, ces algorithmes n'intègrent que les informations de voisinage et ne peuvent pas capturer adéquatement la structure globale du cluster.

La problématique consistera alors à répondre à la question de recherche suivante :  “comment réaliser, d’une manière efficace, un clustering profond sur les graphes ?”.

Objectifs

L’objectif principal consiste à proposer des algorithmes de clustering profond sur graphes et les valider sur des données réelles. Pour atteindre cet objectif nous allons nous baser sur des études de cas sur des données déjà publiées [11]. Notre travail devra prendre en compte d’une manière originale des aspects importants :

  • Nous cherchons à apprendre une architecture permettant d’intégrer les interactions aussi bien entre les nœuds voisins que ceux éloignés. A chaque fois, les caractéristiques extraites des graphes deviennent plus générales et plus complexes, ce qui fait que les relations entre nœuds deviennent plus complètes. Ceci est réalisé à travers un certain nombre de couches du réseau, où chaque couche est constituée d’un « bloc Graph Convolutional Networks » (GCN) qui effectue l'agrégation/propagation de l’information vers les couches voisines. Ainsi, les premières couches permettent de représenter des aspects simples du graphe et les couches éloignées quant à elles représentent des aspects beaucoup plus complexes du graphe. La couche GCN finale est constituée de deux couches denses de perceptron multicouche (Multi Layer Perceptron MLP).
  • Nous allons aussi proposer des fonctions coûts permettant d'apprendre des architectures GNN qui permettent d’extraire les caractéristiques des graphes en utilisant un opérateur de convolution approprié à ceux-ci.
  • Nous envisageons l'utilisation d'une architecture multi-têtes. Celle-là est basée sur un processus développé par plusieurs couches apprenant conjointement différentes représentations à partir de différentes positions. Nous allons utiliser une tête fournissant la représentation spectrale non linéaire du graphe et une autre tête fournissant la matrice d'indice de cluster.
  • Validation des méthodes proposées sur deux ou trois bases benchmark en libre accès (Voir la liste des bases disponibles Page 8 de la référence [11]) à choisir dans les domaines :
  • Des réseaux routiers : les villes intelligentes améliorent la gestion et l’organisation de leur quotidien en prévoyant le flux de leur trafic.
  • De l’analyse de réseaux : L’analyse de réseaux peut aussi bien englober les réseaux sociaux que les citations dans les papiers de recherche (un papier est un nœud et une citation est un lien entre le papier qui cite et le papier cité). On peut avoir besoin, à l’intérieur d’un réseau, de chercher les « communautés », un ensemble de nœuds qui interagissent plus souvent ensemble qu’avec les autres, pour par exemple trouver les cercles d’amis, les groupes d’intérêt…
  • Des systèmes de recommandation : Recommander des films sur Netflix ou des pages Facebook aux utilisateurs fait usage de ce que l’on appelle les systèmes de recommandation. Ces problèmes consistent en un remplissage de matrices dont les lignes sont les utilisateurs, les colonnes les produits et les valeurs à l’intérieur représentent un score qui indique à quel point un utilisateur a aimé un film par exemple. La difficulté réside dans le fait que chaque utilisateur a vu une très faible minorité de films parmi le catalogue entier. Les matrices sont donc extrêmement peu remplies. En 2009, Netflix avait offert 1 million de dollars à qui pourrait améliorer son système de recommandation, dont les matrices étaient remplies à seulement 0.011% !
  • De la vision par ordinateur : De plus en plus, les algorithmes traitent des données en 3 dimensions, pour lesquelles on ne peut plus appliquer les méthodes traditionnelles.
  • Validation des méthodes sur les données médicales du CHU d’Angers et de l’ICO d’Angers.
  •  

    Références

    [1] Chen, C.-H. (2014). A hybrid intelligent model of analyzing clinical breast cancer data using clustering techniques with feature selection. Appl. Soft. Comput. 20, 4–14. doi: 10.1016/j.asoc.2013.10.024

    [2] Wen T and Zhang Z 2018 Deep convolution neural network and autoencoders-based unsupervised feature learning of EEG signals IEEE Access 6 25399–410

    [3] J. MacQueen. Some Methods for Classification and Analysis of Multivariate Observations. In Proceedings of Berkeley Symposium on Mathematical Statistics and Probability, pages 281–297, 1967.

    [4] C. M. Bishop. Pattern Recognition and Machine Learning. Springer, 2006.

    [5] G. E. Hinton and R. R. Salakhutdinov. Reducing the Dimensionality of Data with Neural Networks. Science, 313(5786):504–507, 2006.

    [6] T. Wen and Z. Zhang, "Deep Convolution Neural Network and Autoencoders-Based Unsupervised Feature Learning of EEG Signals," in IEEE Access, vol. 6, pp. 25399-25410, 2018.

    [7] Jianwei Yang, Devi Parikh, and Dhruv Batra. Joint unsupervised learning of deep representations and image clusters. In IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pages 5147–5156, 2016.

    [8] K. G. Dizaji, A. Herandi, C. Deng, W. Cai, and H. Huang. Deep Clustering via Joint Convolutional Autoencoder Embedding and Relative Entropy Minimization. In Proceedings of ICCV, ICCV ’17, pages 5736–5745, 2017.

    [9] C.-C. Hsu and C.-W. Lin. CNN-Based Joint Clustering and Representation Learning with Feature Drift Compensation for Large-Scale Image Data. IEEE Transactions on Multimedia, 20(2):421–429, 2018.

    [10] W. Hu, T. Miyato, S. Tokui, E. Matsumoto, and M. Sugiyama. Learning Discrete Representations via Information Maximizing Self-Augmented Training. In Proceedings of ICML, ICML ’17, pages 1558–1567, 2017.

    [11] L. Waikhom & R. Patgiri, Graph Neural Networks: Methods, Applications, and Opportunities. arXiv preprint arXiv:2108.10733, 2021.

    [12] J. Tang, Computational models for social network analysis: A brief survey, in: Proceedings of the 26th International Conference on World Wide Web Companion, pp. 921-925, 2017.

    [13] F. Liu, S. Xue, J. Wu, C. Zhou, W. Hu, C. Paris, S. Nepal, J. Yang, P. S. Yu, Deep learning for community detection: Progress, challenges and opportunities, in: The 29th International Joint Conference 380 on Artificial Intelligence, 2020, pp. 4981-4987.

    [14] J. Yang, J. 381 Leskovec, Defining and evaluating network communities based on ground-truth, Knowledge and Information Systems 42 (1) (2015) 181-213.

    [15] Z. Du, X. Wang, H. Yang, J. Zhou, J. Tang, Sequential scenario-specific meta learner for online recommendation, in: Proceedings of the 25th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining, 2019, pp. 2895-2904.

    [16] Y. Cen, J. Zhang, X. Zou, C. Zhou, H. Yang, J. Tang, Controllable multi-interest framework for recommendation, in: Proceedings of the 26th ACMSIGKDD International Conference on Knowledge Discovery and Data Mining, 2020, pp. 2942-2951.

    [17] B. Wang, X. Luo, F. Zhang, B. Yuan, A. L. Bertozzi & P.J. Brantingham, Graph-based deep modeling and real time forecasting of sparse spatio-temporal data. arXiv preprint arXiv:1804.00684, 2018.

    [18] J. Zhou, G. Cui, Z. Zhang, C. Yang, Z. Liu, M. Sun, Graph neural networks: A review of methods and applications, AI Open, vol. 1, p. 57-81, 2020.

     

    Porteur(s) du projet
    Voir le profil des chercheurs UCO participant au projet
    Voir le profil des doctorants participant au projet
    Equipes concernées
    Durée du programme
    01/12/2022 - 30/11/2025