Adaptation et apprentissage distribués pour les signaux sur graphe – DARLING

Le projet DARLING s'attaque à trois verrous méthodologiques.

Le premier verrou concerne la modélisation des données. Les graphes constituent des représentations polyvalentes pour capturer la géométrie d’un jeu de données nativement structurées. Les échantillons, éventuellement multidimensionnels supportés par leurs nœuds, sont collectivement nommés signal sur graphe. Les exemples de signaux sur graphe abondent. En imagerie cérébrale fonctionnelle, ils permettent de caractériser la connectivité anatomique de régions fonctionnelles distinctes du cortex. En radioastronomie, ils permettent de représenter les données interférométriques acquises par des antennes disséminées à l’échelle d’un continent en vue de la reconstruction d’images du ciel.

Le deuxième verrou concerne la taille des graphes. Elle peut en effet être un obstacle majeur au traitement centralisé des données. Wikipedia constitue par exemple une excellente source d’information en raison de son échelle exceptionnelle et des dizaines de millions d’usagers qui y laissent quotidiennement leur empreinte, créant un vaste graphe dynamique de pages visitées interconnectées. L’apparition d’anomalies dans l’activité d’édition et de visite de pages Wikipedia révèle des faits intéressants sur la manière dont les utilisateurs réagissent en réponse à une actualité. Ce graphe de près de 6 millions de nœuds échappe toujours à une surveillance exhaustive et nécessite de se limiter à des sujets d’intérêt particuliers. L’exemple du radiotélescope SKA est plus emblématique encore puisqu’il devrait totaliser 2.5 millions d’antennes réparties sur une zone de 5000 kilomètres de diamètre. Pleinement opérationnel en 2025, il devrait générer 1 exaoctet de données par jour et mobiliser 1000 fois le trafic internet actuel.

Le troisième verrou concerne la temporalité des données. Outre leur volume, les analystes sont confrontés à des difficultés nouvelles dues à la temporalité des données sur graphe. D’une part, alors que les interactions sur les graphes pouvaient déjà être analysées sous de multiples perspectives grâce à la théorie des graphes, une nouveauté réside dans la présence d’agents interagissant dynamiquement les uns avec les autres, et influençant leurs comportements respectifs. D’autre part, certains flux de données structurées nécessitent une analyse en ligne et/ou en temps réel afin de s’adapter à des dynamiques variant dans le temps et de répondre aux contraintes de processus chrono-sensibles.

L’équipe projet a mené des travaux et obtenus des résultats significatifs dans le développement de nouvelles méthodes d’apprentissage adaptatives, distribuées et collaboratives sur graphes.
Principalement, elle s'est intéressée jusqu'ici à l'inférence en ligne de topologie de graphes, à la détection de changement sur graphe, à la classification et au clustering sur graphe, et à l'apprentissage pour des données attribuées sur graphe.

Au cours des prochains mois, des efforts seront portés dans la mesure du possible sur les applications afin de compléter le volet méthodologique déjà bien avancé.

Large Dimensional Analysis and Improvement of Multi Task Learning. M. Tiomoko, et al. Journal of Machine Learning Research, 2020.
A unified framework for spectral clustering in sparse graphs. L. Dall'Amico, et al. Journal of Machine Learning Research, vol. 22, no. 187, pp. 1-56, 2022.
Nishimori meets Bethe: a spectral method for node classification in sparse weighted graphs. L. Dall'Amico, et al. Journal of Statistical Mechanics: theory and experiment, 2021.
Consistent Semi-Supervised Graph Regularization for High Dimensional Data. X. Mai et al. Journal of Machine Learning Research, vol. 22, no. 84, pp. 1-48, 2021.
Emergence of ß and ? networks following multisensory training. D. La Rocca, et al. Neuroimage. 2020 Feb 1;206:116313.
Transient performance analysis of the L1-RLS algorithm. W. Gao, et al. Signal Processing Letters, IEEE. 2021. Early Access
From time-frequency to vertex-frequency and back. L. Stankovic, et al. Mathematics, 9(12). 2021.
Graph topology inference with derivative-reproducing property in RKHS: algorithm and convergence analysis.
Transient theoretical analysis of diffusion RLS algorithm for cyclostationary colored inputs. W. Gao, et al. Signal Processing Letters, IEEE, 28: 1160-1164. 2021.
Convex combination of diffusion strategies over networks. D. Jin, et al. Information Processing over Networks, IEEE Transactions on, 6: 714-731. 2020.
Online proximal learning over multitask networks over jointly sparse multitask networks with L(infty,1) regularization. D. Jin, et al. Signal Processing, IEEE Transactions on, 68: 2087-2104. 2020.
Diffusion LMS with communication delays: Stability and performance analysis. F. Hua, et al. Signal Processing Letters, IEEE, 27: 730-734. 2020.
Learning over multitask graphs – Part I: Stability analysis. R. Nassif, et al. Signal Processing, IEEE Open Journal on, 1: 28-45. 2020.
Learning over multitask graphs – Part II: Performance analysis. R. Nassif, et al. Signal Processing, IEEE Open Journal on, 1(46-63). 2020.
Online distributed learning over graphs with multitask graph-filter models. F. Hua, et al. Signal and Information Processing over Networks, IEEE Transactions on, 6(1): 63-77. 2020.
Multitask learning over graphs: an approach for distributed, streaming machine learning. R. Nassif, et al. Signal Processing Magazine, IEEE, 37(3): 14-25. 2020.
Affine combination of diffusion strategies over networks. D. Jin, et al. Signal Processing, IEEE Transactions on, 68(1): 2087-2104. 2020.
Semi-automatic extraction of functional dynamic networks describing patient's epileptic seizures. G Frusque, et al. Frontiers in Neurology 11. 2020
Multiplex network inference with sparse tensor decomposition for functional connectivity. G Frusque, et al. IEEE transactions on Signal and Information Processing over Networks 6, 316-328, 2020.
Variational Graph Autoencoders for Multiview Canonical Correlation Analysis. Y Kaloga, et al. Signal Processing, 108182, 2021.

On assiste depuis 5 ans à un engouement majeur et persistant pour le traitement des mégadonnées, en écho à une mutation radicale de nos sociétés de l'information. Nombre d'applications impliquant ces mégadonnées sont structurées par un réseau et requièrent des actions en temps réel compte tenu de leur caractère chrono-sensible. La surveillance et la gestion de réseaux de transport, de télécommunication, de production et de distribution d’énergie sont des exemples caractéristiques. Maintes disciplines scientifiques sont également concernées, des Sciences de l’Univers aux Neurosciences. Ces systèmes sont constitués d’un grand nombre d'agents liés par une topologie de connexion. Ces agents peuvent éventuellement interagir, de façon dynamique, afin d’accomplir la tâche qui leur est assignée. Les flux de données sont massifs et leurs propriétés sont susceptibles d'évoluer dans le temps. Les graphes sont eux-mêmes dynamiques.

Le projet DARLING a pour objectif de proposer de nouvelles méthodes d’apprentissage adaptatives, distribuées et collaboratives sur des graphes dynamiques de grande dimension afin d’extraire des informations structurées des flux de données acquis et/ou transitant aux nœuds de ces graphes. Pour atteindre ces objectifs, DARLING doit lever trois verrous méthodologiques. Le premier verrou concerne la modélisation des données. Si le traitement des signaux sur graphe a récemment fourni un ensemble complet d’outils d'analyse, son horizon demeure toutefois restreint à des modèles de signaux généralement statiques dont la dimension temporelle a été négligée au profit de la dimension spatiale. Le deuxième verrou concerne la taille des graphes. L'exemple du radiotélescope SKA est emblématique puisqu'il devrait totaliser 2.5 millions d'antennes réparties sur une zone de 5000 kilomètres de diamètre. Pour de telles situations, il est indispensable de développer des méthodes de traitement et d'apprentissage supportant un passage à l'échelle en étant nativement distribuables sur les nœuds. Le troisième verrou concerne la temporalité des données. Certains flux de données nécessitent une analyse en ligne afin de s'adapter à des dynamiques variant dans le temps et de répondre aux contraintes de processus chrono-sensibles.

A l'issu du projet, l'équipe DARLING prévoit de livrer une famille de méthodes d'apprentissage opérant sur des signaux temporels structurés par des graphes dynamiques. Celles-ci pourront d’être déployées à grande échelle en étant nativement distribuables sur les nœuds des graphes, d'opérer en ligne et d'être dotées de capacités d'adaptation afin de répondre à des contraintes de temporalité. Afin d'obtenir des garanties de performance, ces méthodes seront systématiquement accompagnées d'une étude approfondie par la théorie des matrices aléatoires. Cet outil puissant, jamais exploité dans ce contexte bien que parfaitement indiqué pour l'inférence sur graphe aléatoire, fournira des voies d'amélioration. Enfin, les méthodes seront confrontées à deux techniques d'observation de pointe dans lesquelles deux des partenaires sont impliqués et disposent de données : la radioastronomie avec l'instrument géant SKA (Obs. Côte d'Azur) pour la reconstruction d'images et la calibration, et l'imagerie cérébrale par magnéto-encéphalographie (NeuroSpin, CEA Saclay) pour la caractérisation de la connectivité anatomique de régions fonctionnelles distinctes du cortex. Une partie de ces données accompagnera les routines en Python fournies à l'issu du projet.