🤖 machine learning

SLeDGe: Semi-Supervised Learning on Data Streams with Graph Structure Learning

Le document propose SLeDGe, une méthode d'apprentissage semi-supervisé pour les flux de données qui apprend conjointement un modèle prédictif et une structure de graphe adaptative sous des contraintes strictes de mémoire et d'étiquetage, capturant efficacement l'évolution des relations entre les échantillons et surpassant les concurrents de pointe sur 12 jeux de données.

Auteurs originaux : Heechan Moon, Kijung Shin

Publié 2026-06-23

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Heechan Moon, Kijung Shin

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez une salle de rédaction en pleine effervescence où l'information (les données) arrive sans interruption, comme un jet d'eau à pleine puissance. Votre travail consiste à trier ces actualités par catégories (comme « Sports », « Politique » ou « Divertissement »). Cependant, vous avez deux problèmes majeurs :

Vous manquez cruellement de temps et d'espace : Vous ne pouvez pas conserver chaque article qui est entré, car votre classeur est minuscule.
Vous avez très peu d'experts : Seule une infime fraction des articles arrive avec une étiquette indiquant leur catégorie. La plupart ne sont que des feuilles de papier vierges.

C'est le défi de l'apprentissage semi-supervisé sur des flux de données. La publication présente une nouvelle méthode appelée SLeDGe pour résoudre ce problème.

Voici comment fonctionne SLeDGe, expliqué à travers de simples analogies :

1. Les deux classeurs spéciaux (Mémoire)

La plupart des anciennes méthodes tentent de conserver une liste statique d'éléments « similaires » ou traitent chaque nouvel article comme un étranger. SLeDGe est plus intelligent. Il maintient deux petits classeurs spéciaux dans sa mémoire :

Le « Classeur des Experts » (Mémoire étiquetée) : Il contient quelques articles qui ont des étiquettes. SLeDGe les traite comme des prototypes d'experts. Si un nouvel article ressemble beaucoup à un expert existant, SLeDGe met à jour le dossier de cet expert pour refléter la nouvelle information rapidement. C'est comme un enseignant qui met à jour son plan de cours en se basant sur un nouvel exemple clair.
Le « Classeur des Étudiants » (Mémoire non étiquetée) : Il contient des articles sans étiquettes. SLeDGe est plus prudent ici. Il met à jour ces fichiers lentement, en mélangeant la nouvelle information avec ce qui était déjà là. C'est comme un étudiant qui prend des notes ; il n'efface pas tout son cahier simplement parce qu'il vient d'entendre un nouveau fait ; il ajoute progressivement sa compréhension.

Pourquoi c'est important : Cet équilibre permet au système d'apprendre de nouvelles choses rapidement (plasticité) sans oublier les modèles anciens et fiables (stabilité).

2. La carte dynamique (Apprentissage de la structure du graphe)

Les méthodes traditionnelles utilisent une carte fixe pour connecter des éléments similaires. Imaginez une carte où les « Pommes » sont toujours connectées aux « Oranges » parce qu'elles sont toutes deux des fruits, même si le contexte change. C'est rigide et souvent erroné.

SLeDGe dessine une carte vivante et respirante.

À mesure que les nouvelles données arrivent, SLeDGe redessine constamment les lignes reliant les articles dans ses classeurs.
Il se demande : « Qui est réellement lié à qui en ce moment même ? »
Il ne conserve que les connexions les plus fortes et les plus importantes et supprime les plus faibles ou les plus bruyantes (comme on retirerait un pont instable).

C'est ce qu'on appelle l'Apprentissage de la structure du graphe (Graph Structure Learning). Au lieu de deviner les relations, il les apprend au fur et à mesure que les données défilent.

3. Le relais des étiquettes (Propagation)

Une fois la carte dessinée, SLeDGe utilise cette carte pour faire passer le témoin de l'« étiquette ».

Imaginez que vous avez un article étiqueté « Sports ».
Comme la carte vivante de SLeDGe montre que cet article « Sports » est fortement connecté à un article non étiqueté situé à proximité, il devine avec confiance que l'article non étiqueté est aussi « Sports ».
Il utilise ensuite cette supposition pour aider à étiqueter d'autres articles connectés à celui-ci.
Cela crée une réaction en chaîne, permettant au système d'apprendre de milliers d'articles non étiquetés en utilisant seulement une poignée d'articles étiquetés.

4. La version légère (SLeDGe-L)

La méthode SLeDGe principale est puissante mais peut devenir lourde si les classeurs deviennent trop pleins (car dessiner une carte pour tout le monde prend du temps).

Les auteurs ont créé une version SLeDGe-L (Light/Légère).
Considérez cela comme un mode « speedrun ». Au lieu de vérifier les connexions entre tout le monde, elle ne vérifie les connexions qu'entre les « Experts » (articles étiquetés) et le reste.
Cela la rend beaucoup plus rapide et évolutive, comme un livreur qui ne s'arrête que dans les grands centres de distribution plutôt que dans chaque maison, tout en accomplissant sa mission.

Les résultats : Pourquoi il gagne

Les auteurs ont testé SLeDGe sur 12 jeux de données différents (allant de pages web à des images et des données de capteurs).

Le score : Lorsqu'ils n'avaient que 0,1 % des données étiquetées (soit pratiquement une étiquette pour 1 000 éléments), SLeDGe était 31,7 % plus précis que les meilleures méthodes existantes.
Avec un peu plus d'étiquettes (1 %) : Il était toujours 14,8 % meilleur que la concurrence.

En résumé

SLeDGe est comme un gestionnaire de salle de rédaction hautement efficace qui :

Garde une liste restreinte et sélectionnée d'« Experts » et d'« Étudiants ».
Redessine constamment une carte de qui connaît qui en fonction de l'actualité.
Utilise cette carte pour propager le savoir des quelques experts étiquetés vers les nombreux étudiants non étiquetés.
Fait tout cela sans manquer de mémoire ou de temps, même quand les actualités ne s'arrêtent jamais.

L'article affirme que cette approche est nettement plus efficace pour gérer le chaos des flux de données continus avec très peu d'étiquettes que les méthodes précédentes.

Résumé Technique : SLeDGe – Apprentissage Semi-Supervisé sur des Flux de Données avec Apprentissage de Structure de Graphe

1. Définition du Problème

Le papier traite du défi de l'apprentissage semi-supervisé (SSL) sur les flux de données. Dans ce contexte, les données arrivent séquentiellement ( $D = \{x_t\}_{t=1}^T$ ) en volume élevé, et l'apprenant doit opérer sous deux contraintes strictes :

Contraintes de Mémoire : Le système dispose d'une capacité de mémoire fixe et limitée ( $M$ ) et ne peut pas stocker l'intégralité de l'historique du flux.
Rareté des Étiquettes : Seule une infime fraction des échantillons entrants possède des étiquettes observées ( $y_t$ ), rendant l'apprentissage supervisé traditionnel irréalisable.

Les méthodes de SSL existantes pour les flux échouent souvent car elles traitent soit les échantillons de manière indépendante, soit s'appuient sur des heuristiques de similitude fixes (qui ne peuvent capturer les relations évolutives), ou supposent des jeux de données statiques hors ligne. Le problème central est la manière de propager efficacement la supervision limitée des étiquettes aux échantillons non étiquetés tout en s'adaptant à l'évolution continue des distributions de données et des relations au fil du temps.

2. Méthodologie : SLeDGe

Les auteurs proposent SLeDGe (Semi-supervised Learning on Data Stream with Graph structure learning), un cadre qui apprend conjointement un modèle prédictif et une structure de graphe adaptative. La méthode opère en trois étapes continues pour chaque échantillon entrant $x_t$ :

A. Mécanisme de Mise à Jour à Double Mémoire

Pour équilibrer le besoin d'adaptation rapide (plasticité) et la rétention de la cohérence historique (stabilité), SLeDGe maintient deux tampons de mémoire compacts distincts :

Mémoire Étiquetée ( $M_L$ ) : Optimisée pour la plasticité. Elle stocke des prototypes pour chaque classe. Lorsqu'un nouvel échantillon étiqueté arrive, il remplit soit un emplacement vide, soit met à jour le prototype existant le plus similaire via une combinaison pondérée. Le poids de mise à jour $\alpha$ est dynamique, favorisant la nouvelle entrée pour faciliter l'intégration rapide de nouvelles caractéristiques.
Mémoire Non Étiquetée ( $M_U$ ) : Optimisée pour la stabilité. Elle stocke des prototypes non étiquetés représentatifs. Les mises à jour ici utilisent un poids $\beta$ qui favorise le prototype existant, reflétant l'incertitude des données non étiquetées et assurant une accumulation graduelle d'informations.

B. Apprentissage de Structure de Graphe Dynamique (GSL)

Au lieu d'utiliser un graphe fixe ou des métriques de similitude statiques, SLeDGe construit un graphe dynamiquement à chaque étape sur la mémoire combinée ( $M_L \cup M_U$ ) et l'échantillon actuel $x_t$ .

Plongement (Embedding - $f_E$ ) : Un perceptron multicouche (MLP) projette les caractéristiques d'entrée dans un espace latent.
Scoring ( $f_S$ ) : Une fonction de score (similitude cosinus) calcule les poids relationnels par paires entre tous les nœuds de la mémoire et l'échantillon actuel, générant une matrice d'adjacence dense.
Élagage (Pruning - $f_P$ ) : Pour garantir l'efficacité, la matrice dense est élaguée pour ne conserver que les $k$ meilleures connexions par nœud, résultant en une matrice d'adjacence creuse $A_t$ .
Classification ( $f_B$ ) : Un fond de structure de type Réseau de Neurones Convolutifs sur Graphes (GCN) propage la supervision à travers la structure de graphe apprise $A_t$ pour générer des prédictions.

C. Optimisation du Modèle

Le modèle est mis à jour à l'aide d'une fonction de perte composite :

Perte Supervisée ( $L_L$ ) : Perte d'entropie croisée calculée sur la mémoire étiquetée, pondérée par un facteur de décroissance temporelle pour donner la priorité aux échantillons récents.
Régularisation Structurelle ( $L_{reg}$ ) : Un terme qui encourage la cohérence entre les similitudes par paires dans l'espace d'entrée et l'espace latent. Cela stabilise l'inférence du graphe dynamique, empêchant la structure du graphe de devenir erratique.

D. Variante Légère : SLeDGe-L

Pour répondre à la complexité temporelle quadratique ( $O(M^2)$ ) de la construction complète du graphe lorsque la taille de la mémoire $M$ est grande, les auteurs proposent SLeDGe-L. Cette variante restreint le scoring du graphe à une approche centrée sur les classes, calculant les similitudes uniquement entre les prototypes étiquetés et tous les échantillons de la mémoire. Cela réduit la complexité à une croissance linéaire en $M$ ( $O(c \cdot M)$ ), où $c$ est le nombre de classes.

3. Contributions Clés

Structure de Graphe Adaptative : Contrairement aux méthodes de SSL de flux antérieures qui reposent sur des graphes fixes, SLeDGe apprend une topologie de graphe dynamique qui évolue avec le flux de données, capturant les dépendances inter-échantillons variables dans le temps.
Gestion de Mémoire à Double Stratégie : L'introduction de stratégies de mise à jour distinctes pour les mémoires étiquetées (axées sur la plasticité) et non étiquetées (axées sur la stabilité) permet au modèle d'équilibrer l'adaptation aux nouvelles caractéristiques et la préservation des connaissances historiques.
Efficacité sous Contraintes : Le cadre est conçu pour opérer sous des budgets de mémoire stricts et une rareté extrême des étiquette (jusqu'à 0,1 % d'étiquettes) tout en maintenant l'efficacité computationnelle grâce à l'élagage de graphe creux et une variante légère (SLeDGe-L).
Régularisation Structurelle : L'inclusion d'un terme de régularisation de cohérence garantit que la structure de graphe apprise reste stable et significative durant le processus de flux.

4. Résultats Expérimentaux

Les auteurs ont évalué SLeDGe sur 12 jeux de données couvrant les domaines du web, de l'image et des données tabulaires.

Performance : SLeDGe a surpassé les concurrents de pointe (TLP, ReSSL, HDSSL) sur tous les jeux de données.
- Avec 0,1 % d'étiquettes, il a obtenu un gain de précision relative moyen de 31,7 % par rapport à la base de référence la plus forte.
- Avec 1,0 % d'étiquettes, il a obtenu un gain de précision relative moyen de 14,8 %.
Études d'Ablation : Les expériences ont confirmé que le module de mémoire et la structure de graphe dynamique sont tous deux critiques. Supprimer le graphe dynamique (revenir à un graphe k-NN statique) a entraîné des performances nettement inférieures, validant la nécessité d'apprendre des relations évolutives.
Scalabilité : La méthode démontre une mise à l'échelle linéaire par rapport à la taille du flux de données (temps constant par échantillon). SLeDGe-L a montré une scalabilité supérieure par rapport à la taille du tampon de mémoire comparée à la version complète, confirmant l'analyse de complexité théorique.
Vitesse : Malgré l'utilisation d'un modèle de deep learning, SLeDGe est compétitif en temps d'exécution face aux méthodes basées sur le clustering, particulièrement sur les données de haute dimension où il tire parti des calculs au niveau de l'embedding.

5. Signification et Revendications

Le papier affirme que SLeDGe comble une lacune critique dans la littérature en permettant l'Apprentissage de Structure de Graphe (GSL) dans des contextes de flux où la mémoire et les étiquettes sont sévèrement contraintes. Les auteurs soutiennent que les méthodes existantes échouent car elles ne peuvent pas modéliser la façon dont les relations entre les échantillons évoluent au fil du temps. En apprenant conjointement le modèle prédictif et la structure du graphe, SLeDGe propage efficacement la supervision limitée aux données non étiquetées, atteignant des améliorations de précision substantielles sans nécessiter le stockage de l'intégralité de l'historique des données. Le travail souligne que l'inférence de graphe dynamique est supérieure aux mesures de similitude statiques dans les environnements de flux de données non stationnaires.