Résumé Technique : Modèle de Signal Graphe-Dictionnaire pour la Représentation Creuse de Données Multivariées

1. Énoncé du Problème

Les signaux multivariés, tels que l'activité cérébrale, les marchés financiers ou les flux de trafic, présentent souvent des dynamiques instantanées complexes qui varient selon les échantillons de données. Bien que ces systèmes soient régis par des structures relationnelles sous-jacentes (graphes), ces structures sont généralement cachées et doivent être inférées à partir des signaux des nœuds observés. Les approches existantes se heurtent à plusieurs limites :

• Apprentissage de la Structure de Graphe : De nombreuses méthodes supposent un graphe statique unique ou nécessitent des observations de graphes alignées, échouant ainsi à capturer les relations variant selon l'échantillon.
• Apprentissage de Dictionnaire : L'apprentissage de dictionnaire traditionnel opère sur des espaces vectoriels, et non sur des topologies de graphes.
• Clustering : Des méthodes comme K-means ou les Mélanges Gaussiens imposent des assignations strictes ou souples à des clusters statiques, peinant à modéliser les changements continus ou les systèmes où plusieurs structures sous-jacentes se superposent pour générer une seule observation.

Le défi central consiste à développer un modèle capable d'apprendre conjointement un ensemble fini de structures de graphes élémentaires (atomes) et leurs coefficients de mélange creux et variables dans le temps pour expliquer les distributions de signaux multivariés, sans connaissance préalable de la topologie du graphe.

2. Méthodologie

A. Le Modèle de Signal Graphe-Dictionnaire (GraphDict)

Les auteurs proposent GraphDict, un cadre probabiliste où un signal multivarié $x_t \in \mathbb{R}^N$ à l'instant $t$ est généré par un graphe instantané $G_t$. Ce graphe n'est pas appris de manière isolée, mais est défini comme une combinaison linéaire de $K$ atomes de graphes $\{G_1, \dots, G_K\}$ issus d'un dictionnaire.

• Processus Génératif :

  1. Atomes : Un dictionnaire de $K$ atomes de graphes est représenté par des matrices de poids d'arêtes $W = [w_1, \dots, w_K]$.
  2. Coefficients : Pour chaque échantillon $t$, un vecteur de coefficients $\delta_t \in [0, 1]^K$ détermine la contribution de chaque atome.
  3. Graphe Instantané : Le Laplacien du graphe instantané $L_t$ est une forme bilinéaire : $L_t = \sum_{k} \delta_{tk} L_{w_k}$.
  4. Génération du Signal : Le signal est modélisé comme la sortie d'un filtre de graphe $k(L_t)$ appliqué à un vecteur aléatoire $\eta_t$. Plus précisément, les auteurs utilisent un champ aléatoire de Markov gaussien contraint par le Laplacien (LGMRF), où $x_t \sim \mathcal{N}(0, k^2(L_t))$.

• Objectif d'Apprentissage :
  Le problème est formulé comme une estimation du Maximum A Posteriori (MAP) pour trouver le dictionnaire de poids $W$ et la matrice de coefficients $\Delta$. L'objectif minimise la log-vraisemblance négative, en incorporant des priors pour :

  • La Parcimonie (Sparsity) : Régularisation $L_1$ sur les poids des atomes et les coefficients de mélange.
  • L'Orthogonalité : Une pénalité sur les produits scalaires entre les poids des atomes pour encourager des rôles structurels distincts.
  • Contraintes de Domaine : Non-négativité des poids et des coefficients.

B. Optimisation : Décomposition Primal-Dual Bilinéaire (BiPDS)

Les algorithmes de Décomposition Primal-Dual (PDS) standards supposent un opérateur linéaire $A$ dans le terme $h(Ax)$. Cependant, dans GraphDict, l'opérateur faisant correspondre les coefficients et les poids au Laplacien est bilinéaire.

Pour résoudre cela, les auteurs introduisent BiPDS, une généralisation de l'algorithme PDS :

• Opérateur Bilinéaire : L'opérateur $L(\Delta, W)$ fait correspondre le produit des coefficients et des poids à l'espace des Laplaciens.
• Dérivation de l'Adjoint : Les auteurs dérivent les opérateurs adjoints partiels $L^*$ et $L^{**}$ nécessaires pour les mises à jour des variables duales. Ces adjoints projettent la variable duale (liée au tenseur Laplacien) vers les espaces des poids et des coefficients, respectivement.
• Algorithme : L'algorithme met à jour de manière itérative les variables primales ($W, \Delta$) et la variable duale ($Y$) en utilisant des opérateurs proximaux et les adjoints dérivés, gérant ainsi la non-séparabilité du terme bilinéaire.

C. Variantes Pratiques

Le papier détaille deux instanciations spécifiques du modèle :

1. GraphDictLog : Impose des degrés de nœuds positifs en utilisant une barrière logarithmique sur la diagonale du Laplacien. Cette méthode est efficace sur le plan computationnel et évite les problèmes numériques associés aux pseudo-déterminants.
2. GraphDictSpectral : Suppose que tous les graphes instantanés partagent les mêmes vecteurs propres (base spectrale fixe), optimisant uniquement les valeurs propres et les coefficients. Cela réduit la complexité en évitant les décompositions spectrales répétées.

3. Contributions Clés

1. Nouveau Modèle de Signal : Introduction de GraphDict, un modèle probabiliste qui définit les distributions de signaux multivariés via un dictionnaire de graphes, permettant la décomposition de relations complexes variant selon l'échantillon en combinaisons creuses d'atomes de graphes élémentaires.
2. Algorithme d'Optimisation : Développement de l'algorithme de Décomposition Primal-Dual Bilinéaire (BiPDS), une nouvelle généralisation de PDS capable d'apprendre conjointement les atomes du dictionnaire de graphes et leurs coefficients de mélange.
3. Implémentation Pratique : Dérivation de fonctions de perte et d'opérateurs proximaux spécifiques qui intègrent des hypothèses courantes de l'apprentissage de structure de graphe (ex: parcimonie, orthogonalité, lissage).
4. Évaluation des Performances : Démonstration de l'efficacité du modèle pour reconstruire des graphes instantanés à partir de signaux et de son utilité dans des tâches de classification en aval.

4. Résultats Expérimentaux

A. Données Synthétiques : Graphes Superposés

• Configuration : Les signaux ont été générés à partir d'un dictionnaire de 5 graphes d'Erdős-Rényi avec des niveaux variables de "superposition" (de 1 à 5 atomes actifs par échantillon).
• Baselines : Comparaison avec les Mélanges Gaussiens, KGraphs et GLMM.
• Résultats : GraphDictLog a systématiquement surpassé les baselines en termes de récupération d'arêtes (mesurée par le coefficient de corrélation de Matthews - MCC), particulièrement lorsque le niveau de superposition augmentait. Alors que les autres méthodes peinaient face à des structures multiples et chevauchantes, GraphDict a réussi à les désentrelacer.

B. Données Synthétiques : Graphes Variant dans le Temps

• Configuration : Données séquentielles générées à partir de graphes évolutifs de type Edge-Markovian Evolving Graphs (EMEG) et de Switching Behavior Graphs (SBG).
• Baselines : Comparaison avec WindowLogModel, TGFA et un modèle hiérarchique (GraphDictHier).
• Résultats : GraphDictLog a atteint la précision la plus élevée dans la récupération d'arêtes dans tous les contextes. Il a capturé efficacement tant l'évolution graduelle (EMEG) que les états récurrents (SBG). Les auteurs attribuent ce succès à la flexibilité du modèle pour apprendre quand les atomes contribuent, plutôt que de s'appuyer sur des structures hiérarchiques fixes.

C. Application au Monde Réel : Décodage de l'Imaginerie Motrice

• Configuration : Classification de l'imaginerie motrice de la main gauche vs main droite à l'aide de données EEG (15 sujets). La tâche consistait à apprendre des "états cérébraux" (atomes de graphes) et à utiliser leurs coefficients comme caractéristiques pour un classificateur Random Forest.
• Baselines : KMeans, Mélanges Gaussiens et GLMM.
• Résultats :
  • Performance : GraphDictLog avec seulement 3 atomes (9 caractéristiques) a obtenu l'aire sous la courbe ROC (AUROC) la plus élevée, surpassant KMeans avec 16 clusters (48 caractéristiques).
  • Interprétabilité : Les atomes appris ont révélé des motifs de connectivité fonctionnelle (ex: activité du lobe frontal, connectivité occipitale) cohérents avec la littérature en neurosciences.
  • Efficacité : Le modèle a démontré que des représentations de dictionnaire de graphes creuses et explicables peuvent surpasser les méthodes standards utilisant beaucoup moins de caractéristiques.

5. Signification et Revendications

Le papier affirme que GraphDict comble le fossé entre la représentation creuse de données multivariées et la décomposition structurée de relations variant selon l'échantillon. Sa principale importance réside dans :

• L'Explicabilité : Contrairement au deep learning "boîte noire" ou au clustering statique, les coefficients dans GraphDict décrivent explicitement l'influence de certains atomes de graphe sur le processus de génération des données.
• La Flexibilité : Le cadre permet d'incorporer des priors spécifiques au domaine (ex: parcimonie, orthogonalité) directement dans l'objectif d'apprentissage.
• L'Utilité en Aval : Les coefficients creux servent de caractéristiques efficaces et de faible dimension pour les tâches de classification, comme démontré dans la tâche de décodage de l'imaginerie motrice.

Les auteurs reconnaissent des limites, notamment la complexité computationnelle de l'implémentation actuelle et la nécessité d'un réglage heuristique des hyperparamètres. Ils notent que bien que l'algorithme BiPDS soit performant empiriquement, une preuve formelle de convergence reste une question théorique ouverte. Des travaux futurs sont suggérés pour explorer des régularisations plus efficaces et des extensions vers des ensembles de nœuds non alignés via le transport optimal.