Technische Samenvatting: SLeDGe – Semi-Supervised Learning op Datastromen met Graph Structure Learning

1. Probleemdefinitie

Het artikel behandelt de uitdaging van Semi-Supervised Learning (SSL) op datastromen. In deze setting arriveert data sequentieel ($D = \{x_t\}_{t=1}^T$ in hoge volumes, en de leerder moet opereren onder twee strikte beperkingen:

1. Geheugenbeperkingen: Het systeem heeft een vaste, beperkte geheugencapaciteit ($M$) en kan niet de volledige geschiedenis van de stroom opslaan.
2. Labelschaarste: Slechts een fractie van de binnenkomende monsters heeft geobserveerde labels ($y_t$), wat traditioneel gesuperviseerd leren onhaalbaar maakt.

Bestaande SSL-methoden voor stromen falen vaak omdat ze monsters ofwel onafhankelijk behandelen, vertrouwen op vaste heuristieken voor gelijkenis (die evoluerende relaties niet kunnen vastleggen), of uitgaan van statische offline datasets. Het kernprobleem is hoe beperkte label-supervisie effectief gepropageerd kan worden naar ongelabelde monsters, terwijl men zich tegelijkertijd aanpast aan de continue evolutie van datadistributies en relaties in de tijd.

2. Methodologie: SLeDGe

De auteurs stellen SLeDGe voor (Semi-supervised Learning on Data Stream with Graph structure learning), een framework dat gezamenlijk een predictief model en een adaptieve graafstructuur leert. De methode werkt in drie continue stadia voor elk binnenkomend monster $x_t$:

A. Dual-Memory Update Mechanisme

Om de balans te vinden tussen de noodzaak van snelle adaptatie (plasticiteit) en het behoud van historische consistentie (stabiliteit), onderhoudt SLeDGe twee afzonderlijke compacte geheugenbuffers:

• Gelabelde Geheugen ($M_L$): Geoptimaliseerd voor plasticiteit. Het slaat prototypes op voor elke klasse. Wanneer een nieuw gelabeld monster arriveert, vult het ofwel een lege plek in, of werkt het het meest gelijkaardige bestaande prototype bij via een gewogen combinatie. Het updategewicht $\alpha$ is dynamisch en geeft de voorkeur aan de nieuwe input om de snelle integratie van nieuwe kenmerken te faciliteren.
• Ongelabelde Geheugen ($M_U$): Geoptimaliseerd voor stabiliteit. Het slaat representatieve ongelabelde prototypes op. Updates hier gebruiken een gewicht $\beta$ dat de voorkeur geeft aan het bestaande prototype, wat de onzekerheid van ongelabelde data reflecteert en graduele informatieaccumulatie waarborgt.

B. Dynamische Graph Structure Learning (GSL)

In plaats van een vaste graaf of statische gelijkenis-heuristieken te gebruiken, construeert SLeDGe dynamisch een graaf op elk tijdstip over het gecombineerde geheugen ($M_L \cup M_U$) en het huidige monster $x_t$.

1. Embedding ($f_E$): Een Multi-Layer Perceptron (MLP) brengt inputkenmerken naar een latente ruimte.
2. Scoring ($f_S$): Een scorefunctie (cosine similarity) berekent paargewijze relationele gewichten tussen alle knopen in het geheugen en het huidige monster, wat een dichte adjacency matrix genereert.
3. Pruning ($f_P$): Om efficiëntie te garanderen, wordt de dichte matrix gepruned om alleen de top-$k$ verbindingen per knoop te behouden, wat resulteert in een ijle (sparse) adjacency matrix $A_t$.
4. Classificatie ($f_B$): Een Graph Convolutional Network (GCN)-achtige backbone propageert supervisie door de geleerde graafstructuur $A_t$ om voorspellingen te genereren.

C. Model Optimalisatie

Het model wordt bijgewerkt met een samengestelde verliesfunctie:

• Gesuperviseerde Loss ($L_L$): Cross-entropy loss berekend op het gelabelde geheugen, gewogen door een temporele vervalfactor om recente monsters prioriteit te geven.
• Structurele Regularisatie ($L_{reg}$): Een term die consistentie stimuleert tussen de paargewijze gelijkenissen in de inputruimte en de latente ruimte. Dit stabiliseert de dynamische graafinferentie en voorkomt dat de graafstructuur erratisch wordt.

D. Lichtgewicht Variant: SLeDGe-L

Om de kwadratische tijdscomplexiteit ($O(M^2)$) van de volledige graafconstructie aan te pakken wanneer de geheugengrootte $M$ groot is, stellen de auteurs SLeDGe-L voor. Deze variant beperkt de graafscoring tot een klasse-centrische aanpak, waarbij gelijkenissen alleen worden berekend tussen gelabelde prototypes en alle geheugensamples. Dit reduceert de complexiteit tot lineair in $M$ ($O(c \cdot M)$), waarbij $c$ het aantal klassen is.

3. Belangrijkste Bijdragen

1. Adaptieve Graafstructuur: In tegenstelling tot eerdere SSL-methoden voor stromen die vertrouwen op vaste grafen, leert SLeDGe een dynamische graaftopologie die evolueert met de datastroom, waardoor tijdvariërende interacties tussen monsters worden gevangen.
2. Dual-Strategy Geheugenbeheer: De introductie van onderscheidende update-strategieën voor gelabelde (plasticiteitsgerichte) en ongelabelde (stabiliteitsgerichte) geheugens maakt het model in staat om de balans te vinden tussen adaptatie aan nieuwe kenmerken en het behoud van historische kennis.
3. Efficiëntie onder Beperkingen: Het framework is ontworpen om te opereren onder strikte geheugenbudgetten en extreme label-schaarste (zo laag als 0,1% labels) terwijl het computationele efficiëntie behoudt door ijle graaf-pruning en een lichtgewicht variant (SLeDGe-L).
4. Structurele Regularisatie: De inclusie van een consistentie-regularisatieterm zorgt ervoor dat de geleerde graafstructuur stabiel en betekenisvol blijft tijdens het streamingproces.

4. Experimentele Resultaten

De auteurs evalueerden SLeDGe op 12 datasets verspreid over web-, beeld- en tabelvormige domeinen.

• Prestaties: SLeDGe presteerde beter dan state-of-the-art concurrenten (TLP, ReSSL, HDSSL) over alle datasets.
  • Met 0,1% labels behaalde het een gemiddelde relatieve nauwkeurigheidswinst van 31,7% ten opzichte van de sterkste baseline.
  • Met 1,0% labels behaalde het een gemiddelde relatieve nauwkeurigheidswinst van 14,8%.
• Ablatie-studies: Experimenten bevestigden dat zowel de geheugenmodule als de dynamische graafstructuur cruciaal zijn. Het verwijderen van de dynamische graaf (terugvallen op een statische k-NN graaf) resulteerde in aanzienlijk lagere prestaties, wat de noodzaak van het leren van evoluerende relaties valideert.
• Schaalbaarheid: De methode vertoont een lineaire schaalbaarheid ten opzichte van de omvang van de datastroom (constante tijd per monster). SLeDGe-L toonde een superieure schaalbaarheid ten opzichte van de geheugenbuffer grootte vergeleken met de volledige versie, wat de theoretische complexiteitsanalyse bevestigt.
• Snelheid: Ondanks dat het een deep learning model is, was SLeDGe competitief in uitvoeringstijd tegenover cluster-gebaseerde methoden, vooral op hoog-dimensionale data waar het profiteerde van berekeningen op embedding-niveau.

5. Betekenis en Claims

Het artikel claimt dat SLeDGe een kritiek gat in de literatuur vult door Graph Structure Learning (GSL) in streaming settings mogelijk te maken waar geheugen en labels ernstig beperkt zijn. De auteurs stellen dat bestaande methoden falen omdat ze niet kunnen modelleren hoe de relaties tussen monsters in de loop van de tijd evolueren. Door gezamenlijk zowel het predictieve model als de graafstructuur te leren, propageert SLeDGe effectief beperkte supervisie naar ongelabelde data, waarbij een aanzienlijke verbetering in nauwkeurigheid wordt bereikt zonder de volledige geschiedenis van de data op te slaan. Het werk benadrukt dat dynamische graafinferentie superieur is aan statische gelijkenis-maten in niet-stationaire datastroomomgevingen.