The Polynomial Counting Capabilities of Message Passing Neural Networks

Resumen Técnico: Las Capacidades de Conteo Polinómico de las Redes Neuronales de Paso de Mensajes

Enunciado del Problema
Investigaciones recientes han establecido que las Redes Neuronales de Paso de Mensajes (MPNN) pueden expresar propiedades lógicas que involucran conteo hasta un umbral o el cumplimiento de restricciones aritméticas lineales, a menudo caracterizadas mediante fragmentos de lógica de primer orden con conteo (FOC2) o extensiones con aritmética entera lineal. Sin embargo, persiste una brecha en la comprensión del poder expresivo de las MPNN en lo referente a restricciones de conteo polinómico (aritmética no lineal), las cuales son relevantes para técnicas avanzadas de clasificación de grafos como los kernels polinómicos. Este artículo investiga las condiciones bajo las cuales las MPNN, específicamente aquellas que utilizan agregación media, pueden reconocer propiedades definidas por la Lógica Modal Peano (PML). La PML extiende la Lógica Modal Graduada permitiendo restricciones polinómicas (por ejemplo, $x_1^2 \cdot x_2 \leq x_3$) en lugar de solo lineales.

Metodología
Los autores emplean un marco formal para analizar las capacidades expresivas de las MPNN comparándolas con fragmentos de PML.

• Definición del Modelo: El estudio se centra en MPNN ($M_{mean}$) que utilizan agregación media tanto para información local (vecindad) como global (grafo completo). Los autores también consideran variantes ($M_{mean, x}$) que permiten agregaciones adicionales de suma o máximo.
• Definición de la Lógica: Definen la PML, donde las fórmulas modales $\langle \pi_1, \dots, \pi_m \rangle \psi(x_1, \dots, x_m)(\phi_1, \dots, \phi_m)$ cuentan nodos que satisfacen subfórmulas $\phi_i$ dentro de vecindades específicas (definidas por modalidades $\pi \in \{id, E_{in}, E_{out}, \top\}$) y verifican si los conteos satisfacen una restricción de aritmética Peano $\psi$.
• Marco de Reconocimiento: Se dice que una MPNN "reconoce" una fórmula $\phi$ sobre una clase de grafos puntuados si el estado de salida de la red para el nodo foco $v$ es no nulo (específicamente $\geq c(|V|)$) si el grafo satisface $\phi$, y cero en caso contrario. La certeza $c(|V|)$ puede depender del tamaño del grafo.
• Estrategia de Construcción: Las pruebas implican la construcción de arquitecturas específicas de MPNN capa por capa. Estas construcciones utilizan "dispositivos" (combinaciones de neuronas ReLU) para realizar operaciones aritméticas (multiplicación, suma, comparación) sobre valores agregados. Un desafío técnico clave abordado es el manejo de los denominadores introducidos por la agregación media (por ejemplo, $1/|V|$ o $1/|neigh(v)|$) al evaluar términos polinómicos de grados variables.

Contribuciones y Resultados Clave
El artículo identifica supuestos estructurales específicos en los grafos de entrada que permiten a las MPNN de media capturar propiedades de conteo polinómico. Los resultados se categorizan según la profundidad de las modalidades (superficial vs. anidada) y el tipo de modalidades utilizadas (global vs. local).

1. Modalidades Globales (Profundidad Superficial):

   • Restricciones Homogéneas: Para fórmulas que utilizan solo modalidad global ($\top$) y términos Peano homogéneos (sin términos constantes, mismo grado para todos los monomios), las MPNN de media pueden reconocer la lógica sin supuestos adicionales sobre el grafo (Lema 1).
   • Restricciones Polinómicas Generales: Para reconocer restricciones polinómicas globales arbitrarias (incluyendo términos no homogéneos y constantes), los grafos de entrada deben contener un nodo marcado (un nodo con un color único). Bajo este supuesto, las MPNN de media pueden alinear los denominadores a $|V|^k$ y reconocer la lógica (Teorema 1).

2. Modalidades Locales (Profundidad Superficial):

   • Requisito de Regularidad: Para fórmulas que utilizan solo modalidades locales ($E_{in}, E_{out}$), las MPNN de media requieren que los grafos de entrada sean regulares (todos los nodos tienen el mismo grado de entrada/salida) y que el nodo foco esté marcado fuertemente (marcado y con un bucle propio). Esto permite a la red normalizar los tamaños de las vecindades locales (Teorema 2).
   • Relajación de la Regularidad: Si se permite que la MPNN utilice agregación de suma o máximo además de la media, el supuesto de regularidad puede omitirse. La red puede entonces reconocer restricciones polinómicas locales en cualquier grafo donde el foco esté marcado fuertemente (Teorema 3).

3. Modalidades Mixtas (Profundidad Superficial):

   • Al combinar modalidades globales y locales, los resultados de las secciones anteriores pueden combinarse. Las MPNN de media reconocen estas fórmulas en grafos regulares y fuertemente marcados (Teorema 4).
   • Con la adición de agregaciones de suma/máximo, el supuesto de regularidad es nuevamente eliminable (Teorema 5).

4. Modalidades Anidadas (Profundidad Arbitraria):

   • Anidamiento Global: Anidar modalidades globales no aumenta el poder expresivo más allá de la profundidad 1; pueden aplanarse (Proposición 1).
   • Anidamiento Local: Para fórmulas con modalidades locales anidadas, el artículo introduce una clase de grafos llamada $(T \circlearrowleft_\phi)^p_\bullet$. Estas son estructuras "tipo árbol" donde el foco está marcado y la estructura del grafo garantiza trazas únicas para nodos a distancias específicas (evitando ambigüedad en los conteos de vecindad).
   • Resultados: Las MPNN de media pueden reconocer PML local anidado en estos grafos tipo árbol, regulares y fuertemente marcados (Teorema 6). Si se permiten agregaciones de suma/máximo, la restricción de regularidad se elimina, permitiendo el reconocimiento en grafos generales tipo árbol y fuertemente marcados (Teorema 7).

Significado y Afirmaciones
El artículo afirma identificar las condiciones mínimas requeridas para que las MPNN generalicen más allá de la aritmética lineal hacia el conteo polinómico.

• Generalización Teórica: Los resultados sugieren que las MPNN con agregación media pueden generalizar técnicas utilizadas en clasificación de grafos que dependen de kernels polinómicos (por ejemplo, SVMs con kernels polinómicos), siempre que los datos de entrada satisfagan propiedades estructurales específicas (nodos marcados, regularidad o tipo árbol).
• Rol de la Agregación: El estudio destaca que, aunque la agregación media es suficiente para el conteo polinómico bajo supuestos estructurales estrictos, la inclusión de agregaciones de suma o máximo relaja significativamente estos requisitos (específicamente eliminando la necesidad de regularidad del grafo).
• Limitaciones: Los autores declaran explícitamente que, sin estos supuestos estructurales (nodos marcados, regularidad o estructuras tipo árbol), las MPNN de media no pueden expresar todas las restricciones polinómicas. Por ejemplo, el Lema 2 demuestra que las MPNN de media no pueden distinguir entre ciertos grafos no regulares que satisfacen una restricción polinómica simple.

El artículo concluye que, si bien las MPNN poseen capacidades de conteo polinómico, su realización requiere ya sea elecciones arquitectónicas específicas (añadir suma/máximo) o supuestos específicos de preprocesamiento de datos/estructurales (marcar nodos, garantizar regularidad o estructuras tipo árbol). Se sugiere trabajo futuro para explorar combinaciones booleanas arbitrarias de modalidades y comparar conteos a diferentes distancias, aspectos que no están cubiertos actualmente por el marco PML utilizado.