Resumen Técnico: SLeDGe – Aprendizaje Semi-Supervisado en Flujos de Datos con Aprendizaje de Estructura de Grafos

1. Definición del Problema

El artículo aborda el desafío del Aprendizaje Semi-Supervisado (SSL) en flujos de datos. En este entorno, los datos llegan secuencialmente ($D = \{x_t\}_{t=1}^T$) en alto volumen, y el aprendiz debe operar bajo dos restricciones estrictas:

1. Restricciones de Memoria: El sistema posee una capacidad de memoria fija y limitada ($M$) y no puede almacenar todo el historial del flujo.
2. Escasez de Etiquetas: Solo una mínima fracción de las muestras entrantes tiene etiquetas observadas ($y_t$), lo que hace que el aprendizaje supervisado tradicional sea inviable.

Los métodos de SSL existentes para flujos de datos suelen fallar porque tratan las muestras de forma independiente, dependen de heurísticas de similitud fijas (que no pueden capturar relaciones evolutivas) o asumen conjuntos de datos estáticos fuera de línea (offline). El problema central es cómo propagar eficazmente la supervisión de etiquetas limitadas a las muestras no etiquetadas mientras se adapta a la evolución continua de las distribuciones de datos y sus relaciones a lo largo del tiempo.

2. Metodología: SLeDGe

Los autores proponen SLeDGe (Semi-supervised Learning on Data Stream with Graph structure learning), un marco que aprende conjuntamente un modelo predictivo y una estructura de grafo adaptativa. El método opera en tres etapas continuas para cada muestra entrante $x_t$:

A. Mecanismo de Actualización de Memoria Dual

Para equilibrar la necesidad de una rápida adaptación (plasticidad) con la retención de la consistencia histórica (estabilidad), SLeDGe mantiene dos buffers de memoria compactos y distintos:

• Memoria Etiquetada ($M_L$): Optimizada para la plasticidad. Almacena prototipos para cada clase. Cuando llega una nueva muestra etiquetada, esta llena un espacio vacío o actualiza el prototipo existente más similar mediante una combinación ponderada. El peso de actualización $\alpha$ es dinámico, favoreciendo la nueva entrada para facilitar la integración rápida de nuevas características.
• Memoria No Etiquetada ($M_U$): Optimizada para la estabilidad. Almacena prototipos no etiquetados representativos. Las actualizaciones aquí utilizan un peso $\beta$ que favorece al prototipo existente, reflejando la incertidumbre de los datos no etiquetados y asegurando una acumulación gradual de información.

B. Aprendizaje de Estructura de Grafo Dinámico (GSL)

En lugar de utilizar un grafo fijo o métricas de similitud estáticas, SLeDGe construye un grafo dinámicamente en cada paso de tiempo sobre la memoria combinada ($M_L \cup M_U$) y la muestra actual $x_t$.

1. Embedding ($f_E$): Un Perceptrón Multicapa (MLP) mapea las características de entrada a un espacio latente.
2. Puntuación ($f_S$): Una función de puntuación (similitud de coseno) calcula los pesos relacionales por pares entre todos los nodos en la memoria y la muestra actual, generando una matriz de adyacencia densa.
   3.Poda ($f_P$): Para garantizar la eficiencia, la matriz densa se poda para retener solo las $k$ conexiones superiores por nodo, resultando en una matriz de adyacencia dispersa $A_t$.
3. Clasificación ($f_B$): Un núcleo de tipo Red Neuronal Convolucional de Grafos (GCN) propaga la supervisión a través de la estructura de grafo aprendida $A_t$ para generar predicciones.

C. Optimización del Modelo

El modelo se actualiza utilizando una función de pérdida compuesta:

• Pérdida Supervisada ($L_L$): Pérdida de entropía cruzada calculada sobre la memoria etiquetada, ponderada por un factor de decaimiento temporal para priorizar las muestras más recientes.
• Regularización Estructural ($L_{reg}$): Un término que fomenta la consistencia entre las similitudes por pares en el espacio de entrada y el espacio latente. Esto estabiliza la inferencia del grafo dinámico, evitando que la estructura del grafo se vuelva errática.

D. Variante Ligera: SLeDGe-L

Para abordar la complejidad temporal cuadrática ($O(M^2)$) de la construcción completa del grafo cuando el tamaño de la memoria $M$ es grande, los autores proponen SLeDGe-L. Esta variante restringe la puntuación del grafo a un enfoque centrado en la clase, computando similitudes solo entre los prototipos de clase y todas las muestras de la memoria. Esto reduce la complejidad a lineal respecto a $M$ ($O(c \cdot M)$), donde $c$ es el número de clases.

3. Contribuciones Clave

1. Estructura de Grafo Adaptativa: A diferencia de los métodos previos de SSL para flujos, SLeDGe aprende una topología de grafo dinámica que evoluciona con el flujo de datos, capturando dependencias inter-muestrales variables en el tiempo.
2. Gestión de Memoria de Estrategia Dual: La introducción de estrategias de actualización distintas para las memorias etiquetada (enfocada en la plasticidad) y no etiquetada (enfocada en la estabilidad) permite al modelo equilibrar la adaptación a nuevas características con la preservación del conocimiento histórico.
3. Eficiencia bajo Restricciones: El marco está diseñado para operar bajo presupuestos de memoria estrictos y una escasez extrema de etiquetas (tan baja como el 0.1% de etiquetas) manteniendo la eficiencia computacional mediante la poda de grafos dispersos y una variante ligera (SLeDGe-L).
4. Regularización Estructural: La inclusión de un término de regularización de consistencia asegura que la estructura de grafo aprendida permanezca estable y significativa durante el proceso de streaming.

4. Resultados Experimentales

Los autores evaluaron SLeDGe en 12 conjuntos de datos que abarcan dominios web, de imagen y tabulares.

• Desempeño: SLeDGe superó a competidores del estado del arte (TLP, ReSSL, HDSSL) en todos los conjuntos de datos.
  • Con 0.1% de etiquetas, logró una ganancia de precisión relativa promedio del 31.7% sobre el baseline más fuerte.
  • Con 1.0% de etiquetas, logró una ganancia de precisión relativa promedio del 14.8%.
• Estudios de Ablación: Los experimentos confirmaron que tanto el módulo de memoria como la estructura de grafo dinámico son críticos. Eliminar el grafo dinámico (revirtiendo a un grafo k-NN estático) resultó en un desempeño significativamente menor, validando la necesidad de aprender relaciones evolutivas.
• Escalabilidad: El método demuestra un escalamiento lineal con respecto al tamaño del flujo de datos (tiempo constante por muestra). SLeDGe-L mostró una escalabilidad superior con respecto al tamaño del buffer de memoria en comparación con la versión completa, confirmando el análisis de complejidad teórica.
• Velocidad: A pesar de ser un modelo de aprendizaje profundo, SLeDGe fue competitivo en tiempo de ejecución frente a métodos basados en clusters, particularmente en datos de alta dimensión donde aprovechó los cálculos a nivel de embedding.

5. Significado y Reivindicaciones

El artículo afirma que SLeDGe llena un vacío crítico en la literatura al permitir el Aprendizaje de Estructura de Grafos (GSL) en entornos de streaming donde la memoria y las etiquetas están severamente restringidas. Los autores argumentan que los métodos existentes fallan porque no pueden modelar cómo evolucionan las relaciones entre muestras a lo largo del tiempo. Al aprender conjuntamente el modelo predictivo y la estructura del grafo, SLeDGe propaga eficazmente la supervisión limitada a los datos no etiquetados, logrando mejoras sustanciales en la precisión sin requerir el almacenamiento de todo el historial de datos. El trabajo enfatiza que la inferencia de grafos dinámicos es superior a las medidas de similitud estáticas en entornos de flujos de datos no estacionarios.