Fractal Graph Contrastive Learning

Resumen Técnico: Aprendizaje Contrastivo de Grafos Fractales (FractalGCL)

Enunciado del Problema
El Aprendizaje Contrastivo de Grafos (GCL) depende de la generación de aumentaciones de grafos semánticamente consistentes para crear pares positivos destinados al aprendizaje auto-supervisado. Sin embargo, los métodos existentes utilizan predominantemente perturbaciones locales (por ejemplo, eliminación aleatoria de nodos/bordes, enmascaramiento de atributos) o restricciones topológicas fijas. Los autores argumentan que estos enfoques ofrecen un control limitado sobre la consistencia estructural global, a menudo fallando en garantizar que las vistas aumentadas retengan las propiedades globales intrínsecas del grafo original. Esta falta de un mecanismo principista para imponer similitud global crea un cuello de botella en el aprendizaje de representaciones de grafos de alta calidad, particularmente para grafos que exhiben estructuras complejas y multi-escala.

Metodología
El artículo propone FractalGCL, un marco fundamentado en la geometría fractal para abordar el desafío de la consistencia global. La metodología consta de tres componentes centrales:

1. Aumentación Basada en Renormalización:
   En lugar de perturbaciones locales aleatorias, FractalGCL genera vistas positivas mediante renormalización de grafos. Este proceso implica particionar los vértices del grafo en "cajas" (supervértices) disjuntas y conectadas basadas en una restricción de radio. Cada caja se colapsa en un único supervértice, y se forman bordes entre supervértices si existía un borde entre sus vértices constituyentes en el grafo original.

   • Base Teórica: Los autores invocan el Teorema 3.2, estableciendo que la renormalización acotada preserva la dimensión de conteo de cajas (dimensión fractal) en el límite de diámetro infinito. Esto asegura que la vista aumentada $R(G)$ mantenga una similitud estructural con el grafo original $G$ a una escala gruesa.
   • Construcción de la Entrada: La vista aumentada alimentada al codificador es la unión disjunta $A(G) = G \sqcup R(G)$, permitiendo que el modelo procese simultáneamente estructuras locales de grano fino y estructuras renormalizadas de grano grueso.

2. Función de Pérdida Contrastiva Consciente de la Dimensión Fractal:
   El marco introduce una función de pérdida novedosa que penaliza explícitamente las discrepancias en la dimensión de conteo de cajas a escala finita entre el grafo ancla y su vista aumentada.

   • La pérdida modifica los logits contrastivos estándar añadiendo un término proporcional a $|\hat{d}_{B}(G_i) - \hat{d}_{B}(R(G_i))|$, donde $\hat{d}_{B}$ es la dimensión de caja estimada.
   • Pares Positivos: La puntuación de similitud se penaliza si la vista renormalizada se desvía significativamente en dimensión del ancla, desalentando aumentaciones poco fiables.
   • Pares Negativos: La fuerza de repulsión entre pares negativos se repondera basándose en la discrepancia de conteo de cajas entre el ancla y la vista renormalizada de la muestra negativa. Los grafos con geometrías a escala finita significativamente diferentes reciben una repulsión más fuerte.

3. Sustituto Gaussiano para Eficiencia:
   Calcular la dimensión de conteo de cajas para cada grafo renormalizado es computacionalmente costoso ($O(|V|^3)$ en escenarios del peor caso). Para hacer el método práctico, los autores derivan un sustituto gaussiano controlado por diámetro.

   • Demuestran (Proposición 3.5) que la discrepancia de renormalización $\Delta(G) = \hat{d}_{B}(G) - \hat{d}_{B}(R(G))$ puede aproximarse mediante una distribución gaussiana $N(0, \sigma^2)$ controlada por el diámetro del grafo y la incertidumbre de regresión.
   • Este sustituto evita regresiones repetidas de conteo de cajas durante el entrenamiento, reduciendo el tiempo de ejecución en aproximadamente 61%.
   • Respuesta Segura: Un mecanismo de puerta desactiva la corrección fractal (estableciendo el peso $\alpha=0$) si el diámetro del grafo es pequeño ($\le 9$) o si el ajuste de conteo de cajas es débil ($R^2 < 0.9$), asegurando que el modelo recurra al comportamiento estándar de GCL cuando las suposiciones fractales no se cumplen.

Contribuciones Clave

• Geometría Fractal en GCL: El artículo se encuentra entre los primeros en inyectar una perspectiva fractal matemáticamente rigurosa en el aprendizaje de representaciones de grafos, demostrando que las propiedades estructurales globales y libres de escala son una señal potente para el aprendizaje contrastivo.
• Arquitectura Impulsada por la Teoría: La integración de aumentaciones basadas en renormalización y una función de pérdida consciente de la dimensión proporciona una alternativa principista a las perturbaciones locales heurísticas.
• Implementación Eficiente: La derivación del sustituto gaussiano transforma un método teóricamente sólido pero computacionalmente prohibitivo en una herramienta práctica, logrando una aceleración significativa sin sacrificar el rendimiento.
• Mecanismo de Robustez: La respuesta a nivel de objetivo asegura que el método no degrade el rendimiento en grafos que carecen de una escala fractal clara o son demasiado pequeños para una estimación de dimensión fiable.

Resultados Experimentales
Los autores evalúan FractalGCL en tres configuraciones distintas:

1. Pre-entrenamiento Congelado (MalNet-Tiny): FractalGCL sirve como una herramienta de pre-entrenamiento congelado efectiva. Cuando se combina con clasificadores aguas abajo (por ejemplo, SAGE, JK-SAGE), mejora la precisión sobre las líneas base, siendo la mayor ganancia de 1.20 puntos porcentuales en el modelo SAGE-pequeño.
2. Benchmarks Estándar (TUDataset): En cinco conjuntos de datos (NCI1, MUTAG, PROTEINS, D&D, REDDIT-M5K), FractalGCL logra la mayor precisión promedio (76.93%), superando al siguiente mejor método (GradGCL) por 1.29 puntos porcentuales. Ocupa el primer lugar en los cinco conjuntos de datos individuales. El margen de rendimiento es notablemente mayor en el conjunto de datos D&D, que exhibe características fractales fuertes.
3. Aplicación del Mundo Real (Tráfico Urbano): Evaluado en tareas de clasificación de seguridad vial utilizando redes viales de Chicago, San Francisco y Nueva York, FractalGCL logra una precisión promedio de 61.76%, superando a la siguiente mejor línea base por 4.51 puntos porcentuales.

Significado y Afirmaciones
El artículo afirma que FractalGCL demuestra que la consistencia estructural global, formalizada a través de la geometría fractal, es un factor crítico pero a menudo pasado por alto en el aprendizaje de representaciones de grafos. Al ir más allá de las perturbaciones locales para imponer autosimilitud multi-escala, el método mejora la calidad de los incrustamientos aprendidos.

Los autores notan modestamente que la eficacia del método depende de la presencia de una estructura fractal significativa a escala finita. Reconocen que para grafos con una escala fractal débil o diámetros muy pequeños, la corrección fractal puede ser menos informativa, razón por la cual el mecanismo de respuesta propuesto es esencial. La obra posiciona la geometría fractal no solo como una curiosidad teórica, sino como un prior práctico y escalable para diseñar objetivos de aprendizaje contrastivo de grafos robustos.