Rademacher Meets Colors: More Expressivity, but at What Cost?

Información Básica

• ID del Artículo: 2510.10101
• Título: Rademacher Meets Colors: More Expressivity, but at What Cost?
• Autores: Martin Carrasco, Caio Deberaldini Netto, Vahan A. Martirosyan, Aneeqa Mehrab, Ehimare Okoyomon, Caterina Graziani
• Clasificación: cs.LG (Aprendizaje Automático)
• Fecha de Publicación: 11 de octubre de 2025 (preimpresión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2510.10101

Resumen

La capacidad expresiva de las redes neuronales de grafos (GNNs) se comprende típicamente a través de su correspondencia con pruebas de isomorfismo de grafos (como la jerarquía de Weisfeiler-Leman). Aunque las GNNs más expresivas pueden distinguir conjuntos de grafos más ricos, también exhiben errores de generalización más altos. Este trabajo vincula la expresividad con la capacidad de generalización a través de la perspectiva de algoritmos de coloración, proporcionando una explicación teórica para este compromiso. Específicamente, los autores demuestran que el número de clases de equivalencia inducidas por la coloración WL delimita directamente la complejidad de Rademacher de la GNN, una medida crítica de generalización dependiente de los datos. El análisis revela que una expresividad más fuerte conduce a una complejidad mayor, resultando en garantías de generalización más débiles. Además, los autores demuestran la estabilidad de la complejidad de Rademacher bajo perturbaciones de conteo de colores entre muestras. Importantemente, el marco no se limita a GNNs de paso de mensajes o 1-WL, sino que se extiende a arquitecturas GNN arbitrarias y medidas de expresividad que particionan grafos en clases de equivalencia.

Contexto de Investigación y Motivación

Problema Central

Esta investigación aborda una cuestión teórica fundamental en el campo de GNNs: el compromiso entre expresividad y capacidad de generalización. Aunque las observaciones empíricas sugieren que las GNNs más expresivas tienden a tener un desempeño de generalización deficiente, existe una falta de explicación teórica rigurosa.

Importancia del Problema

1. Ausencia de Fundamentos Teóricos: La investigación existente se enfoca principalmente en el análisis de expresividad de GNNs, pero carece de comprensión teórica suficiente sobre su relación con la capacidad de generalización
2. Valor de Orientación Práctica: Comprender este compromiso es crucial para diseñar arquitecturas GNN que posean tanto expresividad adecuada como buen desempeño de generalización
3. Necesidad de Marco Unificado: Se requiere un marco teórico unificado para explicar el comportamiento de generalización de diferentes arquitecturas GNN

Limitaciones de Métodos Existentes

1. Análisis de Dimensión VC de Morris et al.: Solo aplicable a funciones de activación específicas y grafos acotados, dependiendo de la cantidad de parámetros en lugar de características estructurales
2. Complejidad de Rademacher de Garg et al.: Aunque proporciona límites más ajustados, no explora la conexión con la distribución de coloración WL
3. Falta de Generalidad: Los análisis existentes se limitan principalmente a arquitecturas GNN específicas o pruebas 1-WL

Contribuciones Principales

1. Establecer Conexión Teórica Expresividad-Generalización: Primera conexión directa entre la expresividad de GNN y la complejidad de Rademacher a través de algoritmos de coloración
2. Proporcionar Límites de Complejidad Precisos: Demostrar que el límite superior de complejidad de Rademacher es $\sqrt{p/m}$, donde $p$ es el número de clases de equivalencia
3. Probar Garantías de Estabilidad: Establecer continuidad de Lipschitz de la complejidad de Rademacher bajo perturbaciones de conteo de colores
4. Diseño de Marco Genérico: Extensión a arquitecturas GNN arbitrarias y algoritmos de coloración correspondientes, sin limitarse a GNNs de paso de mensajes o 1-WL
5. Mejorar Límites de Integral de Dudley: Utilizar la estructura $p$-dimensional para proporcionar límites de número de cobertura más ajustados

Explicación Detallada del Método

Definición de la Tarea

Se estudia la tarea de clasificación binaria a nivel de grafo, donde:

• Entrada: Conjunto de datos de grafos $S = \{(G_i, y_i)\}_{i=1}^m$, $G_i \in \mathcal{G}$, $y_i \in \{-1, +1\}$
• Salida: Límites de complejidad de Rademacher para la clase de funciones $\mathcal{F} = \{f: \mathcal{G} \to [-1,1]\}$
• Objetivo: Establecer relación cuantitativa entre medidas de expresividad y capacidad de generalización

Marco Teórico

Idea Central

El algoritmo de coloración particiona la muestra $S$ en $p$ conjuntos disjuntos $I_1, \ldots, I_p$, donde cada $I_j$ contiene todos los grafos con el mismo color $c_j$. Esta partición impone restricciones estructurales en la clase de funciones: cualquier función implementable por la arquitectura debe mantener constancia en clases de equivalencia.

Resultados Teóricos Principales

Proposición 3.1 (Límite Central): Para la clase de funciones $\mathcal{F}$, si para cada $f \in \mathcal{F}$, los grafos con el mismo color 1-WL tienen la misma salida, entonces el límite de complejidad de Rademacher empírica es:

$R_S(\mathcal{F}) \leq \frac{\sup_\Theta L(\Theta)\sqrt{p}}{\sqrt{m}}$

donde $L(\Theta) = \sqrt{\sum_{i=1}^m f(G_i;\Theta)^2}$ es la norma $\ell_2$ de las salidas de función.

Corolario 3.2 (Caso de Salida Acotada): Cuando $f: \mathcal{G} \to [-1,1]$:

$R_S(\mathcal{F}) \leq \sqrt{\frac{p}{m}}$

Núcleo de la Estrategia de Prueba

1. Reorganización de Sumas: Reorganizar la suma en la definición de complejidad de Rademacher por color de grafo
2. Desigualdad de Cauchy-Schwarz: Separar normas relacionadas con funciones de variables de Rademacher
3. Desigualdad de Jensen: Utilizar la concavidad de la función raíz cuadrada
4. Cálculo de Expectativas: Aprovechar la independencia y propiedad de media cero de variables de Rademacher

Análisis de Estabilidad

Proposición 3.4 (Garantía de Estabilidad): Para dos muestras $S$ y $S'$ de tamaño $m$, si la diferencia de conteo para cada color $c_j$ en ambas muestras es como máximo $\epsilon_j$:

$|R_S(\mathcal{F}) - R_{S'}(\mathcal{F})| \leq \frac{\sum_{c_j \in GC} \epsilon_j}{m}$

Esto asegura robustez del límite bajo variabilidad de muestreo.

Extensión Genérica

El marco se extiende a pares arbitrarios $(A, T)$, donde $A$ es una arquitectura GNN y $T$ es un algoritmo de coloración que delimita su expresividad. Si $T \sqsubseteq S$ (la expresividad de $T$ no excede la de $S$), entonces $p_T \leq p_S$, lo que significa que arquitecturas más expresivas tienen límites de complejidad de Rademacher más grandes.

Configuración Experimental

Verificación Teórica

Este trabajo es principalmente teórico, verificando los límites propuestos a través de pruebas matemáticas. Los autores proporcionan ejemplos visualizados en la Figura 1, mostrando cómo clases de funciones de diferente expresividad inducen diferentes particiones de muestras.

Alcance de Aplicabilidad

• Arquitecturas GNN: GNNs de paso de mensajes, k-GNN, redes CW, GNNs de subgrafos, GNNs de caminos, etc.
• Algoritmos de Coloración: 1-WL, k-WL, WL celular, etc.
• Funciones de Pérdida: Pérdida logística, pérdida de entropía cruzada, pérdida de margen (deben satisfacer condiciones de Lipschitz)

Resultados Experimentales

Verificación de Resultados Teóricos

Todos los resultados teóricos se verifican mediante pruebas matemáticas rigurosas:

1. Límite Principal: Se demuestra que $R_S(\mathcal{F}) \leq \sqrt{p/m}$ se cumple para funciones con salida acotada
2. Límite de Dudley Mejorado: Se mejora el término clásico $4\alpha/\sqrt{m}$ a $4\alpha\sqrt{p}/\sqrt{m}$
3. Estabilidad: Se demuestra la estabilidad lineal de la complejidad de Rademacher

Perspectivas Clave

1. Costo de Expresividad: Mayor expresividad conduce directamente a valores más grandes de $p$, aumentando el límite superior del error de generalización
2. Restricciones Estructurales: Las clases de equivalencia inducidas por coloración limitan la capacidad de sobreajuste de la función
3. Comparación de Arquitecturas: Proporciona herramientas teóricas para comparar la capacidad de generalización de diferentes arquitecturas GNN

Trabajo Relacionado

Investigación de Expresividad

• Xu et al. y Morris et al.: Establecen correspondencia entre MPGNN y 1-WL
• Trabajos Posteriores: Extensión a variantes GNN más expresivas (k-GNN, redes CW, etc.)

Teoría de Generalización

• Morris et al. (Dimensión VC): Primera conexión entre expresividad de GNN y dimensión VC, pero limitada a configuraciones específicas
• D'Inverno et al.: Extensión al análisis de dimensión VC para funciones de activación Pfaffianas
• Garg et al.: Proporcionan primer límite de complejidad de Rademacher para MPGNN

Ventajas de Este Trabajo

1. Conexión Directa: Primera conexión directa entre medida de expresividad (número de colores) y medida de generalización
2. Generalidad: Aplicable a arquitecturas GNN arbitrarias y algoritmos de coloración
3. Dependencia de Datos: Proporciona límites más refinados dependientes de datos

Conclusiones y Discusión

Conclusiones Principales

1. Cuantificación del Compromiso: Primera cuantificación de la relación de compromiso entre expresividad de GNN y capacidad de generalización
2. Unificación Teórica: Unificación de investigación de expresividad y generalización a través de algoritmos de coloración
3. Orientación Práctica: Proporciona principios teóricos de orientación para el diseño de arquitecturas GNN

Limitaciones

1. Restricción de Tarea: El análisis actual se limita a tareas de clasificación binaria a nivel de grafo
2. Partición Discreta: Utiliza clases de equivalencia discretas en lugar de medidas de similitud continua
3. Supuestos de Distribución: No considera el comportamiento bajo distribuciones de grafos específicas

Direcciones Futuras

1. Extensión de Tareas: Extensión a clasificación multiclase, regresión y tareas a nivel de nodo
2. Método de Pseudométrica: Reemplazar particiones discretas con similitud estructural basada en pseudométricas
3. Modelos Probabilísticos: Investigar comportamiento asintótico bajo modelos de grafos aleatorios y graphons
4. Verificación Empírica: Investigación empírica sistemática para verificar la practicidad de los límites teóricos

Evaluación Profunda

Fortalezas

1. Innovación Teórica: Primera conexión teórica directa entre expresividad y generalización, llenando una brecha teórica importante
2. Rigor Matemático: Pruebas completas y rigurosas con resultados de generalidad
3. Valor Práctico: Proporciona orientación cuantitativa para la selección de arquitecturas GNN
4. Marco Genérico: Aplicable a amplio rango de arquitecturas GNN y medidas de expresividad
5. Garantías de Estabilidad: Demuestra robustez del límite

Deficiencias

1. Ausencia de Verificación Empírica: Falta de validación experimental sobre la solidez de los límites teóricos
2. Limitación de Tareas: Solo considera clasificación binaria, limitando el rango de aplicabilidad
3. Solidez de Límites Desconocida: No analiza qué tan ajustados son los límites proporcionados
4. Complejidad Computacional: No discute la complejidad de cálculo del número de colores

Impacto

1. Contribución Teórica: Proporciona base importante para teoría de GNN, se espera que genere investigación posterior
2. Diseño de Arquitecturas: Guía la selección y diseño de arquitecturas GNN en la práctica
3. Dirección de Investigación: Abre nueva dirección de investigación en compromiso expresividad-generalización

Escenarios de Aplicabilidad

1. Investigación Teórica: Análisis de teoría de expresividad y generalización de GNN
2. Diseño de Arquitecturas: Escenarios de aplicación que requieren equilibrar expresividad y generalización
3. Selección de Modelos: Seleccionar arquitecturas GNN con expresividad apropiada para tareas específicas

Referencias

Este artículo cita 28 referencias relacionadas, cubriendo trabajos importantes en expresividad de GNN, teoría de generalización, complejidad de Rademacher y otros campos centrales, proporcionando una base sólida para el análisis teórico.

Resumen: Este trabajo establece por primera vez una conexión teórica cuantitativa entre la expresividad de GNN y la capacidad de generalización a través de la perspectiva de algoritmos de coloración, proporcionando herramientas teóricas importantes para comprender y diseñar GNNs. Aunque existen algunas limitaciones, su contribución teórica posee valor importante y se espera que impulse el desarrollo de la investigación teórica de GNNs.