🤖 machine learning

Universality and Approximation Rates of Graph Neural Networks with Random Features

Este artículo establece que las redes neuronales de grafos de paso de mensajes con características de nodos parcialmente aleatorias poseen capacidades de aproximación universal para funciones permutación-invariantes y permutación-equivariantes en grafos dirigidos de tamaño fijo, al tiempo que deriva límites superiores teóricos sobre sus tasas de aproximación basados en la complejidad de la red.

Autores originales: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Publicado 2026-07-30

📖 6 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Lukas Gonon, Thilo Meyer-Brandis, Niklas Weber

Artículo original bajo licencia CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Esta es una explicación generada por IA del artículo a continuación. No ha sido escrita ni avalada por los autores. Para mayor precisión técnica, consulte el artículo original. Leer descargo de responsabilidad completo

El enigma de la multitud cambiante de formas

Imagina que estás intentando enseñar a una computadora a entender el mundo no como una cuadrícula de píxeles o una lista de palabras, sino como una red de conexiones. Este es el reino de las Redes Neuronales de Grafos (GNN, por sus siglas en inglés), una rama de la inteligencia artificial diseñada para manejar datos que parecen un mapa de amigos, moléculas o rutas de tráfico. En estos mapas, lo más importante no es solo qué es un elemento individual, sino cómo se conecta con sus vecinos.

Sin embargo, hay una regla truculenta que estas computadoras deben seguir: la simetría. Si tienes un grupo de amigos y cambias sus nombres, el grupo sigue siendo el mismo grupo. Una buena IA de grafos no debería importarle quién está sentado en la silla A o en la silla B; solo debería importarle el patrón de quién está hablando con quién. Esto se llama invariancia de permutación (para el grupo completo) o equivariancia de permutación (para los individuos). El problema es que los modelos de IA estándar son terribles en esto. A menudo se confunden por el orden en que llegan los datos, fallando al reconocer que dos listas de nombres diferentes describen en realidad el mismo círculo social.

Para solucionar esto, los científicos han intentado dar a la IA "ruido aleatorio" o "IDs aleatorios" para ayudarla a distinguir los nodos, de forma muy similar a dar a cada persona en una multitud una pegatina única y temporal. Pero hasta ahora, no sabíamos plenamente si este truco podría hacer que la IA fuera lo suficientemente inteligente como para aprender cualquier patrón posible, o si había límites en cuanto a qué tan bien podía aprender reglas complejas. Este artículo profundiza en esa pregunta, planteando: "Si le damos a estas computadoras que leen grafos pegatinas aleatorias, ¿pueden aprender a ser perfectas al entender cualquier estructura de grafo?".

La magia de las pegatinas aleatorias

Los autores de este artículo, Lukas Gonon, Thilo Meyer-Brandis y Niklas Weber, se propusieron demostrar que un tipo específico de IA de grafos, llamada Red Neuronal de Permutación Equivariante (PENN), se vuelve increíblemente poderosa cuando le proporcionas características de nodo aleatorias. Piensa en una PENN como un equipo de detectives tratando de resolver un misterio en un mapa. Normalmente, si dos sospechosos lucen idénticos y tienen los mismos amigos, los detectives no pueden distinguirlos. Pero si le das a cada sospechoso una pegatina aleatoria y única (una característica aleatoria), los detectives finalmente pueden distinguirlos y resolver el caso.

El principal descubrimiento del artículo es una garantía "universal". Los autores demostraron matemáticamente que, si alimentas estas PENNs con pegatinas aleatorias, pueden aproximar cualquier función medible en un grafo de un tamaño fijo con una probabilidad arbitrariamente alta. En lenguaje sencillo: si quieres que la IA aprenda una regla específica sobre una red (como predecir si una molécula es tóxica o si una red financiera está en riesgo), y le proporcionas suficientes pegatinas aleatorias, existe una arquitectura PENN que puede aprender esa regla casi perfectamente. Esto se mantiene cierto incluso si la regla es desordenada o compleja, e incluso si los datos tienen muchos tipos diferentes de características adjuntas a los nodos y bordes.

¿Qué es "suficiente bueno"?

Pero el artículo no solo dice "funciona"; te dice qué tan grande debe ser la IA para lograr el trabajo. Los autores analizaron funciones que son suaves y bien comportadas (matemáticamente hablando, " $k$ -veces continuamente diferenciables", donde $k \ge 2$ ). Derivaron una fórmula para las tasas de aproximación, que es básicamente un límite de velocidad sobre qué tan rápido puede aprender la IA a medida que se hace más grande.

Descubrieron que la profundidad de la red (el número de capas) solo necesita crecer de forma logarítmica a medida que exiges más precisión. Esto es una excelente noticia: si quieres ser el doble de preciso, no necesitas duplicar el tamaño del cerebro; solo necesitas un poco más de profundidad. Sin embargo, el número de conexiones (pesos no nulos) crece polinómicamente a medida que exiges más precisión. Específicamente, la complejidad escala con una potencia de $1/\epsilon$ , donde $\epsilon$ es tu margen de error deseado. El artículo señala que este exponente depende de la "suavidad" de la regla que intentas aprender ( $k$ ) y del tamaño del grafo ( $N$ ). Esencialmente, para reglas muy complejas y dentadas o grafos muy grandes, necesitas muchas más conexiones, pero para reglas suaves, la IA sigue siendo eficiente.

El truco del "promedio" para la seguridad

Uno de los aspectos más lúdicos y prácticos del artículo aborda un efecto secundario del uso de pegatinas aleatorias. Debido a que las pegatinas son aleatorias, si ejecutas la IA una vez, podría dar una respuesta ligeramente diferente de la que daría si la ejecutaras de nuevo con diferentes pegatinas. Esto rompe la regla de simetría: la IA podría tratar a un mismo grupo de amigos de manera diferente solo porque las pegatinas cambiaron.

Los autores sugieren un arreglo ingenioso: el promedio. Si ejecutas la IA muchas veces con diferentes pegatinas aleatorias y tomas el promedio de los resultados, la aleatoriedad se cancela y la IA vuelve a ser perfectamente simétrica. Demostraron que esta versión "promediada" aún conserva el superpoder de ser capaz de aprender cualquier regla. Es como pedirle a una multitud de personas que adivinen el peso de una calabaza; una persona puede estar muy errada, pero si promedias las suposiciones de cien personas, obtienes una respuesta muy precisa. El artículo muestra que puedes obtener esta simetría perfecta y la capacidad de aprendizaje perfecto simultáneamente mediante el simple hecho de promediar algunas ejecuciones.

Lo que esto significa para el futuro

Los autores aclaran cuidadosamente que esto es una prueba teórica, no una simulación de un conjunto de datos específico. Han demostrado matemáticamente que el potencial existe para que estos modelos sean aproximadores universales. Excluyen explícitamente la idea de que necesites arquitecturas personalizadas y complejas para lograr esto; la estructura estándar de una PENN, cuando se aumenta con características aleatorias, es suficiente.

También aclaran que, si bien las características aleatorias rompen la "simetría perfecta" de una sola ejecución, no rompen la "simetría en la expectativa" (el comportamiento promedio). Esto sugiere que, en la práctica, usar características aleatorias es una estrategia robusta. El artículo concluye que las PENN con características aleatorias deberían considerarse una base sólida para las tareas de aprendizaje de grafos. No son solo una curiosidad teórica; ofrecen un plano concreto y matemáticamente respaldado para construir IAs de grafos que sean tanto poderosas como flexibles, capaces de aprender patrones complejos en redes que van desde moléculas químicas hasta sistemas financieros.

Resumen Técnico: Universalidad y Tasas de Aproximación de Redes Neuronales de Grafos con Características Aleatorias

Planteamiento del Problema

Las Redes Neuronales de Grafos (GNNs), particularmente las arquitecturas de paso de mensajes, han logrado un éxito empírico significativo pero enfrentan limitaciones teóricas respecto a su poder expresivo. Las GNNs de paso de mensajes estándar están limitadas por la prueba 1-Weisfeiler–Leman (1-WL), lo que significa que no pueden distinguir ciertas estructuras de grafos no isomórficos. Aunque existen estrategias para superar esto —como arquitecturas de orden superior o el enriquecimiento de las características de los nodos—, existe una falta de resultados teóricos rigurosos que establezcan las capacidades de aproximación universal de arquitecturas de GNN específicas y prácticas cuando se aumentan con características aleatorias. Además, los resultados de universalidad existentes suelen depender de supuestos restrictivos, como requerir que las funciones objetivo sean continuas, que los dominios sean compactos o que las características sean de dimensión finita, y a menudo no abordan las tasas de aproximación (límites de complejidad) para estos modelos.

Metodología

Los autores investigan las Redes Neuronales de Permutación-Equivariantes (PENNs), una clase de GNNs que generaliza muchas arquitecturas populares de paso de mensajes (por ejemplo, GCN, GIN, GraphSAGE, GAT). La innovación metodológica central es el aumento de las características estándar de los nodos con características de nodo aleatorias.

Definición de la Arquitectura: El artículo define las PENNs como funciones compuestas de componentes de redes neuronales de alimentación hacia adelante (FNN) ( $\rho, \phi, \alpha, \psi$ ) que agregan información de vecindarios y atributos globales del grafo. Esta estructura subsume el marco de Agregación-Combinación-Lectura (ACR).
Características Aleatorias: Los autores introducen características de nodo aleatorias $R$ que proporcionan "características de nodo únicas finitas". Esto significa que, con alta probabilidad (o casi con seguridad), las características aleatorias asignan identificadores distintos a nodos distintos, rompiendo efectivamente la simetría que limita a las GNNs estándar. El marco acomoda tanto características aleatorias independientes e idénticamente distribuidas (i.i.d.) como identificadores únicos deterministas (o sus permutaciones aleatorias).
Marco de Aproximación: El estudio aprovecha los teoremas clásicos de aproximación universal para FNNs (por ejemplo, Leshno et al., 1993), pero los adapta al dominio de los grafos. La idea clave es que si las características de los nodos son únicas, cualquier función de permutación-equivariante puede representarse como una composición de FNNs actuando sobre estas características únicas.
Equivarianza Basada en la Esperanza: Reconociendo que la permutación-equivarianza por trayectoria se rompe con las características aleatorias fijas, los autores analizan la permutación-equivarianza en la esperanza. Proponen promediar las PENNs sobre múltiples muestras de características aleatorias re-muestreadas para recuperar las propiedades de equivariancia mientras se retiene una alta expresividad.

Contribuciones Clave

1. Teoremas de Aproximación Universal

El artículo establece que las PENNs aumentadas con características aleatorias son aproximadores universales para funciones de permutación-invariantes y de permutación-equivariantes medibles en grafos dirigidos con tamaño fijo y características de nodo/arista multidimensionales.

Generalidad: A diferencia de trabajos previos (por ejemplo, Abboud et al., 2020; Puny et al., 2020), este resultado no requiere que la función objetivo sea continua, ni asume la compacidad o la finitud del espacio de características. Se aplica a funciones medibles en dominios no acotados.
Arquitectura Concreta: Los autores especifican una arquitectura concreta (PENNs) para la cual la universalidad se mantiene, en lugar de simplemente afirmar la existencia de alguna arquitectura abstracta.
Probabilidad: La aproximación se cumple con una probabilidad arbitrariamente alta, siempre que las características aleatorias induzcan identificadores de nodos únicos.

2. Tasas de Aproximación y Límites de Complejidad

Para funciones $k$ -veces continuamente diferenciables ( $k \ge 2$ ) definidas en dominios compactos, el artículo deriva límites superiores explícitos sobre la complejidad de los componentes de la PENN necesarios para lograr un error de aproximación deseado $\varepsilon$ .

Profundidad: El número de capas requerido crece logarítmicamente con respecto a $1/\varepsilon$ ( $O(\log(1/\varepsilon))$ ).
Ancho/Pesos: El número de pesos no nulos crece polinómicamente con respecto a $1/\varepsilon$ , específicamente como $O(\varepsilon^{-c/(k-1)})$ , donde $c$ depende de las dimensiones del grafo ( $N, d, d'$ ).
Maldición de la Dimensionalidad: Los límites reflejan una forma de la maldición de la dimensionalidad respecto al dominio del grafo, pero la severidad se mitiga para funciones con mayor regularidad ( $k$ ).

3. Permutación-Equivarianza en la Esperanza

El artículo aborda el compromiso entre expresividad y simetría. Si bien una realización única de una PENN con características aleatorias no es de permutación-equivariante por trayectoria, los autores demuestran que la esperanza de la salida de la PENN (condicionada a la entrada del grafo) es de permutación-equivariante. Además, muestran que el promedio sobre un número finito de muestras de características aleatorias i.i.d. preserva la propiedad de aproximación universal mientras mejora el sesgo hacia la equivariancia.

Resultados

Teorema 9: Establece que para cualquier función de permutación-equivariante medible $f$ y cualquier $\varepsilon, \delta > 0$ , existe una PENN con características aleatorias tal que la probabilidad de que el error de aproximación exceda $\varepsilon$ es a lo sumo $\delta$ .
Teorema 11: Proporciona una versión de la teoría de la medida para el resultado de universalidad, aplicable cuando la distribución del propio grafo induce características de nodo únicas.
Teorema 16: Demuestra que la PENN promediada (usando $M$ copias i.i.d. de características aleatorias) también satisface la propiedad de aproximación universal, con la probabilidad de error acotada por $\delta$ .
Teorema 18: Proporciona las tasas de aproximación cuantitativas. Demuestra que para funciones suficientemente regulares, las PENNs con restricciones arquitectónicas específicas (profundidad y ancho) pueden aproximar uniformemente la función objetivo con alta probabilidad. Los límites de complejidad reflejan aquellos conocidos para las redes neuronales de alimentación hacia adelante estándar.

Significado y Reivindicaciones

Los autores afirman que este trabajo llena vacíos sustanciales en la comprensión teórica de las GNNs:

Puente entre Teoría y Práctica: Al demostrar la universalidad para una arquitectura concreta y eficiente en memoria (PENNs) en lugar de modelos abstractos, los resultados proporcionan una base teórica para el uso de características aleatorias en aplicaciones prácticas de GNN.
Generalización de Resultados Existentes: Los resultados generalizan los teoremas de universalidad previos al relajar los supuestos de continuidad, compacidad y la naturaleza de las funciones objetivo (medibles frente a continuas).
Guía Práctica: Las tasas de aproximación derivadas ofrecen una guía teórica para la selección de hiperparámetros (profundidad y ancho) basados en la precisión deseada y la regularidad de la función objetivo.
Benchmarking: Los autores sugieren que las PENNs con características aleatorias deberían considerarse bases sólidas para tareas de aprendizaje en grafos, ya sea como alternativas competitivas a los modelos de vanguardia o como un punto de referencia para validar las capacidades de otras arquitecturas.

El artículo concluye que, si bien las características aleatorias pueden introducir una pérdida de la equivariancia por trayectoria, los modelos resultantes poseen una capacidad expresiva superior y, al ser promediados, retienen propiedades de simetría deseables, lo que los convierte en una herramienta robusta, tanto teórica como práctica, para el aprendizaje en grafos.