Resumen Técnico: Poder de Separación de las Redes Neuronales Equivariantes

Declaración del Problema

La expresividad de los modelos de aprendizaje automático se cuantifica a menudo mediante su universalidad: la capacidad de aproximar cualquier función dentro de una clase específica. Sin embargo, para las redes neuronales equivariantes (aquellas que respetan simetrías como permutaciones o rotaciones), la universalidad está limitada por la incapacidad inherente de la red para distinguir entre entradas que son equivalentes bajo el grupo de simetría. Esta limitación crea una interacción compleja entre la capacidad de una red para discriminar entradas distintas y las estructuras invariantes/equivariantes que debe preservar.

Si bien la comunidad de aprendizaje de grafos ha estudiado extensamente el poder de separación de las Redes Neuronales de Grafos (GNN) utilizando la prueba de Weisfeiler-Leman (WL) y el conteo de homomorfismos, estas herramientas combinatorias tienen limitaciones severas cuando se aplican a clases más amplias de modelos equivariantes, particularmente aquellos que procesan datos geométricos o utilizan convoluciones regulares. Existe una falta de herramientas analíticas finas para caracterizar el conjunto de entradas indistinguibles (la relación de identificación) para redes neuronales equivariantes generales con activaciones no polinómicas, representaciones de dimensión finita y equivariancia de permutación.

Metodología

El artículo introduce un marco teórico para caracterizar el poder de separación $\rho(\mathcal{N})$ de una familia de redes neuronales equivariantes $\mathcal{N}$. El poder de separación se define como la relación de equivalencia que identifica pares de entradas $(\alpha, \beta)$ tales que $f(\alpha) = f(\beta)$ para todo $f \in \mathcal{N}$.

La contribución metodológica central es el "Truco de la Red Gemela" (Twin Network Trick), que transforma el problema de identificar entradas indistinguibles en un problema de lugar cero (zero locus problem). Al construir una red gemela $\hat{\eta}(\alpha, \beta) = \eta(\alpha) - \eta(\beta)$, los autores reformulan la relación de identificación como la búsqueda del conjunto de puntos mapeados al cero por el espacio de la red gemela.

Esta reducción permite a los autores aplicar técnicas recursivas derivadas de la teoría de ecuaciones funcionales. Específicamente, aprovechan resultados relativos a ecuaciones funcionales lineales que involucran funciones continuas no polinómicas (por ejemplo, ReLU, sigmoid) para derivar una fórmula explícita y recursiva para el lugar cero. Esta fórmula relaciona el lugar cero de una red de profundidad $d$ con los lugares cero de redes de profundidad $d-1$, involucrando uniones e intersecciones de subespacios específicos definidos por la arquitectura de la red y los términos de sesgo (bias).

El análisis asume:

1. Representaciones de Permutación: Las redes actúan sobre espacios de funciones de valores reales sobre conjuntos finitos, equivariantes bajo grupos finitos que actúan como permutaciones.
2. Activaciones No Polinómicas: Las funciones de activación son continuas y no polinómicas.
3. Sesgo Completo (Complete Bias): Las capas afines incluyen términos de sesgo subordinados a la partición de la órbita del espacio de representación.

Contribuciones Clave y Resultados

1. Caracterización Completa de Entradas Indistinguibles

El artículo proporciona una caracterización completa del conjunto de pares de entrada identificados por redes con una arquitectura fija.

• Teorema 1 (Teorema de Caracterización): Establece una fórmula recursiva para el lugar cero de un espacio de red. Esta fórmula descompone la relación de identificación basándose en la profundidad de la red, las propiedades de activación y la partición del espacio de representación inducida por los términos de sesgo.

2. Equivalencia de Activaciones No Polinómicas

• Teorema 2: Demuestra que, para una arquitectura fija, cualquier función de activación continua, real, elemento a elemento y no polinómica produce el mismo poder de separación. En consecuencia, las activaciones comunes como ReLU, sigmoid y tanh son equivalentes en su capacidad para distinguir entradas y todas alcanzan el máximo poder de separación posible para esa arquitectura. Las activaciones polinómicas quedan excluidas de esta equivalencia.

3. El Papel de la Profundidad

• Teorema 3: Demuestra que aumentar la profundidad de la red mejora el poder de separación solo hasta un umbral de repetición específico. Más allá de este umbral, añadir más capas del mismo tipo no mejora la capacidad de distinguir entradas; el poder de separación se estabiliza.
  • Para las Redes de Grafos $k$-Invariantes (IGNs), este umbral es proporcional al umbral de la prueba $k$-WL.
  • Para redes con representaciones ocultas regulares, la estabilización ocurre tras la repetición de una sola capa.

4. Independencia del Ancho de Características Ocultas y Características Invariantes

• Teorema 4 y Observación 1: Muestra que el poder de separación es independiente de la multiplicidad de los bloques en las representaciones ocultas. Específicamente, aumentar el ancho de las características ocultas invariantes (por ejemplo, la dimensión del espacio de características en las IGNs) no mejora la capacidad de la red para distinguir entradas. El poder de separación de una red con representación oculta $V \otimes \mathbb{R}^f$ es idéntico al de una red con representación oculta $V$.

5. Jerarquía de Tipos de Representación

• Teorema 5: Establece una jerarquía en el poder de separación basada en el tipo de representación utilizada en las capas. El poder de separación corresponde al orden parcial de los subgrupos del grupo de simetría.
  • Las representaciones inducidas por subgrupos más pequeños (por ejemplo, el subgrupo trivial $\{e\}$, correspondiente a la representación regular) producen un poder de separación máximo.
  • Las representaciones inducidas por subgrupos más grandes (por ejemplo, el propio grupo $G$, correspondiente a los vectores invariantes) producen un poder de separación mínimo.
  • Esto implica que el uso de representaciones regulares ($\mathbb{R}^G$) en las capas ocultas es suficiente para alcanzar el máximo poder de separación permitido por la arquitectura.

Implicaciones para Modelos Prácticos

Los autores aplican estos resultados generales a modelos prácticos específicos:

• Redes de Grafos Invariantes (IGNs): Los resultados refuerzan hallazgos previos al mostrar que las $k$-IGNs igualan el poder de separación de la prueba $k$-WL, independientemente de las dimensiones de las características ocultas. Esto resuelve la necesidad de los resultados previos que requerían anchos de características ocultas "grandes" para alcanzar la universalidad.
• CNNs Circulares: Se demuestra que el poder de separación de las Redes Neuronales Convolucionales Circulares depende del tamaño del filtro. Específicamente, las redes con soportes de filtro más grandes (acercándose al tamaño completo del grupo) tienen un poder de separación estrictamente más fino que aquellas con soportes más pequeños, formando una jerarquía estricta.

Significado y Reivindicaciones

El artículo afirma proporcionar una condición necesaria para comprender la universalidad de las redes neuronales equivariantes. Al caracterizar precisamente la relación de identificación $\rho(\mathcal{N})$, los autores permiten clasificar los hiperparámetros y las elecciones arquitectónicas en dos categorías:

1. Determinantes de la Separación: Elecciones que influyen directamente en el conjunto de entradas distinguibles (por ejemplo, tipo de activación, profundidad hasta un umbral, tipo de representación). Estas impactan significativamente tanto en la capacidad de aproximación como en el costo computacional.
2. Independientes de la Separación: Elecciones que no afectan el conjunto de entradas distinguibles (por ejemplo, ancho de la característica oculta, multiplicidad de bloques). Estas pueden influir en la aproximación dentro de las restricciones del poder de separación, pero no expanden la clase de entradas distinguibles.

Los autores enfatizan que su marco está limitado a representaciones de permutación y activaciones no polinómicas. Reconocen que su enfoque no se extiende actualmente a modelos que utilizan coeficientes de Clebsch-Gordan y enfoques polinómicos, ni aborda completamente los casos donde los términos de sesgo están ausentes (aunque puede proporcionar límites en tales casos). El trabajo sirve como una herramienta teórica fundamental para analizar la expresividad de los modelos equivariantes más allá de las restricciones combinatorias de las pruebas específicas de grafos.