A Graphop Analysis of Graph Neural Networks on Sparse Graphs: Generalization and Universal Approximation

Resumen Técnico: Un Análisis de Graphop de las Redes Neuronales de Grafos sobre Grafos Dispersos

Planteamiento del Problema
El análisis teórico de las Redes Neuronales de Grafos de Paso de Mensajes (MPNN) con respecto a la generalización y la aproximación universal ha enfrentado históricamente una dicotomía. Los enfoques existentes dependen de la definición de un espacio métrico compacto de grafos bajo el cual las MPNN son equicontinuas. Sin embargo, estos enfoques sufren de un compromiso fundamental:

1. Grafos Densos: Las métricas que permiten grafos de tamaños ilimitados (necesarias para los límites de generalización) se basan típicamente en la teoría de los graphons. Estas métricas son apropiadas solo para grafos densos; fallan para grafos dispersos porque la agregación de suma normalizada (requerida para la convergencia en los límites de graphon) produce salidas casi nulas para estructuras dispersas.
2. Grafos Dispersos: Los enfoques que manejan grafos dispersos (usando agregación de suma) típicamente restringen el espacio métrico a grafos de tamaño uniformemente acotado. Esto impide la derivación de límites de generalización para tamaños de grafo ilimitados y limita el alcance de los teoremas de aproximación universal.

Consecuentemente, no existe un marco unificado que proporcione límites de generalización potentes y teoremas de aproximación universal para las MPNN que actúan sobre grafos tanto dispersos como densos.

Metodología
Los autores proponen un enfoque unificado basado en el Análisis de Graphop, una teoría de límites de grafos adecuada para grafos dispersos, extendiéndola para manejar características de nodos y MPNN. La metodología procede a través de los siguientes pasos:

1. Operadores de Fibra Acotados (Bofops): El artículo introduce una subclase de graphops llamada operadores de fibra acotados (bofops). A diferencia de los graphops generales, los bofops poseen una estructura de conectividad específica caracterizada por una familia de medidas (fibras) que representan los vecindarios de los nodos. Esta estructura codifica naturalmente patrones de conectividad tanto dispersos como densos. Los autores extienden la teoría de graphops para incluir características de nodos, definiendo las señales de bofop como pares de un bofop y una señal (mapeo de características).
2. Métrica de Acción y Perfiles: Para analizar las MPNN, los autores utilizan la métrica de acción, definida mediante la distancia de Hausdorff entre "perfiles" (histogramas de valores de salida sobre funciones de entrada). Demuestran que el espacio de señales de bofop es compacto bajo esta métrica y que las MPNN son Lipschitz continuas con respecto a ella.
3. Distancia de Mover de DIDM: La métrica de acción es demasiado fina para servir como base para la aproximación universal porque distintas señales de bofop pueden producir salidas de MPNN idénticas. Para abordar esto, los autores introducen la distancia de Mover de DIDM (Distribución de Medidas de Grado Iteradas). Esta métrica es más gruesa que la métrica de acción y está construida basada en los árboles computacionales subyacentes al algoritmo 1-Weisfeiler-Leman (1-WL).
4. Conmutación y Continuidad: Los autores demuestran que las MPNN conmutan con el algoritmo 1-WL sobre las señales de bofop. Prueban que las MPNN son uniformemente equicontinuas con respecto a la distancia de Mover de DIDM y poseen el mismo poder de separación que esta métrica (es decir, distinguen exactamente aquellas señales de bofop que tienen una distancia de Mover de DIDM no nula).
5. Densidad y Completitud: El artículo establece que el espacio de señales de grafos finitos (tanto dispersos como densos) es denso dentro del espacio de bofop-DIDMs bajo la distancia de Mover de DIDM. Por lo tanto, los bofop-DIDMs sirven como la completación del espacio de todos los grafos finitos.

Contribuciones Clave

• Espacio Métrico Unificado: La definición de un espacio métrico compacto (señales de bofop) que incluye grafos de todos los tamaños, tanto dispersos como densos.
• Extensión de la Teoría de Graphop: La introducción de bofops y señales de bofop, que generalizan a los graphons y permiten el modelado natural de las agregaciones de suma, suma normalizada y promedio simétrico dentro de un mismo marco.
• Garantías Teóricas:
  • Aproximación Universal: Un teorema que establece que cualquier función continua sobre el espacio de bofop-DIDMs (con respecto a la distancia de Mover de DIDM) puede ser aproximada uniformemente por una MPNN. Dado que los grafos finitos son densos en este espacio, esto se aplica a funciones continuas sobre grafos.
  • Límites de Generalización: Una prueba de que las MPNN admiten límites de generalización (donde el error entre el riesgo de entrenamiento y de prueba decae a cero a medida que el tamaño de la muestra aumenta) debido al número de cobertura finito del espacio compacto de bofop-DIDMs y la equicontinuidad uniforme de las MPNN.
• Jerarquía de Espacios de DIDM: El establecimiento de una jerarquía estricta donde los DIDMs de grafos densos (basados en graphons) forman un subconjunto propio de los bofop-DIDMs, los cuales a su vez forman un subconjunto propio del espacio de todos los DIDMs formales.

Resultos
El artículo proporciona pruebas rigurosas para lo siguiente:

• El espacio de señales de bofop es compacto bajo la métrica de acción y la distancia de Mover de DIDM.
• Las MPNN son Lipschitz continuas con respecto a la métrica de acción y uniformemente equicontinuas con respecto a la distancia de Mover de DIDM.
• Las MPNN separan puntos en el espacio de señales de bofop con respecto a la distancia de Mover de DIDM.
• El espacio de señales de grafos finitos es denso en el espacio de señales de bofop bajo la distancia de Mover de DIDM.
• Consecuentemente, el teorema de Stone-Weierstrass se aplica a las MPNN sobre señales de bofop, garantizando la aproximación universal.
• Los argumentos de número de cobertura garantizan límites de generalización para las MPNN entrenadas en distribuciones de datos sobre grafos dispersos o densos.

Significancia y Reivindicaciones
El artículo afirma resolver la limitación de larga data donde los análisis teóricos de las GNN estaban restringidos ya sea a grafos densos (vía graphons) o a grafos dispersos de tamaño acotado. Al utilizar el análisis de graphop y la subclase específica de bofops, los autores proporcionan un marco teórico unificado que:

1. Trata a los grafos dispersos y densos de tamaños ilimitados en igualdad de condiciones.
2. Proporciona teoremas de aproximación universal y límites de generalización más fuertes que trabajos previos.
3. Clarifica la relación entre el poder computacional de las MPNN (poder de separación) y la estructura topológica del espacio de entrada a través de la distancia de Mover de DIDM.

Los autores señalan que su construcción de MPNN sobre perfiles es actualmente teórica, ya que los perfiles se definen como conjuntos de medidas sin una estructura computacional directa. Identifican la obtención de límites explícitos sobre el número de cobertura de los espacios de bofop como una dirección futura para hacer que los límites de generalización sean más concretos.