Resumen Técnico: Las Características de Agregación Fija Pueden Rivalizar con las GNN

Planteamiento del Problema

Las Redes Neuronales de Grafos (GNN) se han convertido en el estándar para el aprendizaje a partir de datos estructurados en grafos, particularmente para la clasificación de nodos. Estos modelos dependen típicamente del paradigma de paso de mensajes, donde las representaciones de los nodos se actualizan a través de múltiples capas de agregaciones de vecindad entrenables (por ejemplo, combinaciones lineales aprendidas, mecanismos de atención). Aunque son efectivas, este enfoque introduce una alta complejidad de modelo, desafíos en la interpretabilidad y costos computacionales significativos.

Evidencia reciente sugiere que las GNN clásicas (GCN, GAT, GraphSAGE) siguen siendo competitivas con los Graph Transformers de vanguardia y los modelos conscientes de la heterofilia cuando se dotan de un riguroso ajuste de hiperparámetros. Esto plantea una pregunta fundamental: ¿Es realmente necesaria la alta complejidad de aprender funciones de agregación? Específicamente, ¿qué tan relevante es el aprendizaje de la agregación en sí mismo en comparación con la tarea de clasificación descendente?

Metodología: Características de Agregación Fija (FAFs)

Los autores introducen las Características de Agregación Fija (FAFs), un enfoque libre de entrenamiento que transforma las tareas de aprendizaje en grafos en problemas tabulares estándar. La idea central es desacoplar el aprendizaje de representaciones de la optimización mediante el uso de operadores de agregación fijos y no entrenables.

El Pipeline de FAF

1. Agregación Fija: Para un nodo $v$ dado, el método computa recursivamente características de sus vecindades de $k$-saltos utilizando un conjunto de reductores fijos $\mathcal{R}$ (por ejemplo, media, suma, máximo, mínimo, desviación estándar).
   • $h^{(0,r)}_v = x_v$ (características originales)
   • $h^{(k,r)}_v = r(\{h^{(k-1,r)}_u : u \in \mathcal{N}(v)\})$
2. Concatenación de Características: Las características de todos los saltos ($k \in \{1, \dots, K\}$) y todos los reductores ($r \in \mathcal{R}$) se concatenan con las características originales del nodo para formar un vector tabular de alta dimensión $z_v$.
   • $z_v = x_v \oplus \bigoplus_{r \in \mathcal{R}} \bigoplus_{k=1}^K h^{(k,r)}_v$
3. Clasificación Descendente: Se entrena un Perceptrón Multicapa (MLP) estándar y bien ajustado sobre estas características fijas $z_v$. No se retropropagan gradientes a través de los pasos de agregación; la agregación es un paso de preprocesamiento.

Fundamento Teórico

El artículo conecta las FAFs con el teorema de representación de Kolmogorov–Arnold, que establece que cualquier función continua multivariante puede representarse como una composición de funciones univariantes.

• Posibilidad Teórica: Los autores construyen una función de agregación inyectiva fija $\Phi$ (basada en expansiones ternarias y el conjunto de Cantor) que teóricamente permite una codificación sin pérdida de multisets de vecindad. Esto implica que, en teoría, no es necesario aprender nada durante la agregación para preservar la expresividad.
• Realidad Práctica: Aunque $\Phi$ es teóricamente sin pérdida, es numéricamente frágil y produce embeddings "rugosos" no aptos para clasificadores estándar. En contraste, los reductores simples y no inyectivos (como la media y la suma) son empíricamente más propensos a la optimización. Los autores argumentan que para la mayoría de los benchmarks, la señal relevante se concentra en vecindades de pocos saltos (1–2 saltos), donde las agregaciones simples preservan suficiente información.

Contribuciones Clave

1. Perspectiva Teórica: El artículo establece que la agregación de vecindad sin pérdida es teóricamente posible mediante funciones inyectivas fijas derivadas de representaciones de Kolmogorov–Arnold. Sin embargo, destaca una brecha crucial entre expresividad y capacidad de aprendizaje: los reductores simples y no inyectivos suelen ofrecer un mejor rendimiento práctico porque producen embeddings más suaves que los clasificadores descendentes pueden optimizar con mayor eficacia.
2. Propuesta Metodológica: La introducción de las FAFs, que convierte los datos de grafos en un formato tabular mediante la apilamiento de agregaciones de múltiples saltos fijas. Esto proporciona un marco interpretable para estudiar la interacción entre la estructura del grafo, las características y la tarea sin sesgo arquitectónico.
3. Evidencia Empírica: Experimentos extensos en 14 benchmarks estándar de clasificación de nodos muestran que las FAFs, combinadas con MLPs bien ajustados, rivalizan o superan a las GNN de vanguardia y a los Graph Transformers en 12 de los 14 casos.
   • Rendimiento: Las FAFs igualan o exceden a las GNN clásicas (GCN, GAT, SAGE) y arquitecturas complejas en redes de citas (Cora, Citeseer, PubMed), grafos de coautoría y grafos de productos de Amazon.
   • Excepciones: Las FAFs rinden por debajo únicamente en los conjuntos de datos Roman Empire y Minesweeper. Los autores atribuyen esto a que estos conjuntos de datos requieren dependencias de largo alcance o conexiones residuales lineales específicas que las FAFs estándar (usando 2–4 saltos) no capturan, alineándose con los hallazgos de que estas tareas se benefician de GNN profundas con residuales parametrizados.
4. Implicaciones para el Benchmarking: Los resultados desafían la necesidad de la agregación aprendida en los benchmarks actuales. Los autores argumentan que muchos conjuntos de datos pueden resolverse mediante predictores tabulares potentes alimentados con características fijas y transparentes, lo que sugiere que los benchmarks actuales podrían no estar probando adecuadamente la capacidad de los modelos para aprender dinámicas de agregación complejas.

Resultados y Análisis

• Estudios de Ablación:
  • Complejidad del Clasificador: Un MLP bien ajustado supera significativamente a una sola capa lineal cuando se aplica a las características FAF, lo que indica que la no linealidad y la capacidad son cruciales para aprovechar la información de múltiples saltos.
  • Concatenación de Saltos: Concatenar características de todos los saltos produce un mejor rendimiento que usar solo el último salto, confirmando que la información se pierde durante las agregaciones repetidas y que los saltos tempranos (0–2) contienen la señal más predictiva.
  • Elección del Reductor: Aunque la concatenación de múltiples reductores (por ejemplo, media, suma, máximo, mínimo) es generalmente beneficiosa, un único reductor (frecuentemente la media) suele ser suficiente y a veces supera a las combinaciones complejas, probablemente debido a la reducción del sobreajuste en espacios de alta dimensión.
• Interpretabilidad: Al tratar el problema como tabular, los autores utilizan valores SHAP para analizar la importancia de las características. Por ejemplo, en el conjunto de datos Minesweeper, identifican que la media del salto-1 de características específicas es la señal primaria, aclarando dónde tiene éxito o falla el modelo.
• Eficiencia: Precomputar las agregaciones y entrenar un MLP es generalmente más escalable y eficiente que entrenar GNN profundas, aunque la dimensionalidad de la entrada aumenta con el número de saltos y reductores.

Significado y Reivindicaciones

El artículo postula que el campo del aprendizaje en grafos puede estar excesivamente dependiente de mecanismos de agregación complejos y entrenables para tareas donde estadísticas simples y fijas son suficientes. Los autores afirman que:

1. Baselines Fuertes: Las FAFs deberían servir como un baseline obligatorio y fuerte para la futura investigación en aprendizaje de grafos. Si una nueva GNN no puede superar a una FAF bien ajustada, su complejidad añadida puede no estar justificada.
2. Reevaluación de Benchmarks: Los benchmarks actuales (ej. Cora, Citeseer) pueden no requerir genuinamente una agregación aprendida, ya que la señal predictiva suele concentrarse en vecindades de bajo orden. Los autores piden "benchmarks más ricos" que prueben específicamente las dependencias de largo alcance y las dinámicas complejas entre saltos.
3. Optimización vs. Expresividad: El éxito de las FAFs sugiere que la optimizabilidad y la entrenabilidad son tan críticas como la expresividad teórica. Las GNN complejas pueden tener dificultades para aprender agregaciones útiles debido a problemas de optimización (ej. desvanecimiento de gradientes, sobre-suavizado) más que por una falta de capacidad teórica.
4. Perspectiva Tabular: Convertir problemas de grafos a problemas tabulares permite a los investigadores aprovechar el conjunto de herramientas maduras del aprendizaje tabular (selección de características, interpretabilidad, manejo de desequilibrio de clases) e aislar la contribución de la estructura del grafo de los artefactos de optimización.

En conclusión, los autores abogan por un cambio de enfoque: en lugar de asumir que los parámetros adicionales o una mayor expresividad extraen automáticamente una señal más relevante, la comunidad debe priorizar modelos más simples e interpretables y diseñar benchmarks que realmente necesiten el aprendizaje de funciones de agregación complejas.