🤖 machine learning

Hierarchical Multi-Scale Graph Neural Networks: Scalable Heterophilous Learning with Oversmoothing and Oversquashing Mitigation

Este artículo introduce HAAR multivista jerárquico (HMH), un marco escalable de aprendizaje espectral de grafos que mitiga el sobrealisamiento y el sobreaplastamiento en grafos heterofílicos mediante la construcción de una jerarquía suave con bases de Haar ortonormales y filtros espectrales aprendibles, superando así a las líneas base más avanzadas en tareas de clasificación de nodos y de grafos.

Autores originales: Md Sazzad Hossen, Avimanyu Sahoo

Publicado 2026-05-13

📖 5 min de lectura🧠 Análisis profundo

CC BY 4.0

Autores originales: Md Sazzad Hossen, Avimanyu Sahoo

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

Imagina que estás tratando de entender una ciudad masiva y caótica caminando por sus barrios. En el mundo de la ciencia de datos, esta ciudad es un grafo (una red de puntos conectados), y las personas que viven allí son nodos.

Por lo general, cuando enseñamos a las computadoras a entender estas ciudades, nos encontramos con tres grandes problemas:

El problema del "Vecino Rico" (Dominancia de los Nodos Centrales o Hubs): Si un barrio tiene una celebridad súper popular (un "hub" con miles de amigos), su opinión ahoga las voces silenciosas de los barrios más pequeños y menos conectados. La computadora solo escucha a la celebridad.
El problema de la "Foto Borrosa" (Suavizado Excesivo): Si sigues preguntando a los vecinos qué piensan, y ellos siguen preguntando a sus vecinos, eventualmente todos empiezan a sonar exactamente igual. Los detalles únicos se diluyen y la imagen se convierte en una mancha gris borrosa.
El problema del "Juego del Teléfono" (Aplastamiento Excesivo): Si intentas enviar un mensaje de un lado de la ciudad al otro, el mensaje se comprime tanto al pasar por calles abarrotadas que llega como un galimatías.

El artículo presenta una nueva solución llamada HMH (Aproximación de Haar Jerárquica Multivista). Imagina a HMH no como una sola persona caminando por las calles, sino como un sistema inteligente de planificación urbana multinivel que utiliza un tipo especial de "lente de zoom".

Así es como funciona, paso a paso:

1. El Traductor Inteligente (El Codificador Heterófilo)

En muchas ciudades, los vecinos son similares (les gusta la misma música). En otras, los vecinos son opuestos (uno ama el jazz, el otro ama el heavy metal). Esto se llama heterofilia.

La vieja forma: Las computadoras a menudo asumen que todos son similares y simplemente promedian sus opiniones. Esto falla cuando los vecinos son opuestos.
La forma HMH: Actúa como un traductor que escucha atentamente. Si dos vecinos son similares, les da un "pulgar arriba" (peso positivo). Si son opuestos, les da un "pulgar abajo" (peso negativo). Esto asegura que la computadora aprenda a detectar diferencias tan bien como similitudes, sin confundirse por el cambio de signo que va y viene.

2. La Lente de Zoom (Agrupamiento Jerárquico)

En lugar de intentar analizar a cada persona de la ciudad a la vez, HMH construye una pirámide de barrios.

Nivel 1: Agrupa a personas similares en pequeños "montones" o clústeres.
Nivel 2: Trata esos montones como "superpersonas" individuales y los agrupa en distritos más grandes.
Nivel 3: Sigue alejando el zoom hasta ver toda la ciudad como unas pocas regiones principales.

Esto es como mirar un mapa: primero ves las casas, luego las manzanas, luego los barrios y finalmente toda la ciudad. Esto ayuda a la computadora a manejar el problema del "Vecino Rico" porque los barrios pequeños y silenciosos obtienen su propia voz en los clústeres más pequeños antes de ser fusionados en la imagen general.

3. El Filtro Especial (Base de Haar)

Este es el ingrediente secreto. La mayoría de las computadoras usan un "filtro global" que intenta suavizar toda la ciudad a la vez, lo que causa el problema de la "foto borrosa".
HMH utiliza algo llamado Base de Haar. Imagina esto como un conjunto de linternas especializadas:

Algunas linternas brillan solo sobre una sola casa (detalles locales).
Algunas brillan sobre toda una manzana (detalles medios).
Algunas brillan sobre toda la ciudad (tendencias grandes).

Como estas linternas son ortogonales (no se superponen ni interfieren entre sí), HMH puede encender la linterna de "detalle local" sin desenfocar accidentalmente la linterna de "tendencia grande". Mantiene los detalles de alta frecuencia (las diferencias entre vecinos) nítidos mientras aún entiende el panorama general.

4. El Ascensor (Desagrupamiento con Conexiones de Salto)

Después de analizar la ciudad en cada nivel de zoom, HMH no se detiene solo en la cima. Utiliza un ascensor para traer toda esa información de vuelta al nivel original de la calle.

Toma las ideas de "panorama general" de la cima de la pirámide.
Las mezcla con los "detalles locales" de la base.
Cada persona individual (nodo) recibe un informe final que incluye tanto el chisme de su vecindario inmediato como el contexto de toda la ciudad.

¿Por qué es esto algo importante?

El artículo afirma que al usar este sistema de "Lente de Zoom + Linternas Especiales + Ascensor", HMH resuelve los tres grandes problemas:

Sin más Dominancia de los Nodos Centrales: Los barrios pequeños no son ahogados por las celebridades porque se analizan primero en sus propios clústeres.
Sin más Fotos Borrosas: Las linternas especiales mantienen los detalles únicos nítidos, incluso en capas muy profundas.
Sin más Mensajes Aplastados: Como la ciudad está organizada en una jerarquía (como un árbol), los mensajes no tienen que comprimirse por calles abarrotadas; viajan hacia arriba y hacia abajo por el árbol, lo cual es mucho más rápido y claro.

El Resultado:
Los autores probaron esto en muchos tipos diferentes de "ciudades" (conjuntos de datos), desde redes sociales hasta estructuras moleculares. Descubrieron que HMH era más rápido (escalando casi linealmente, lo que significa que no se atasca a medida que la ciudad crece) y más preciso que los métodos anteriores, especialmente en lugares donde los vecinos son muy diferentes entre sí. Logró mejores puntuaciones al identificar a quién pertenece a qué grupo (clasificación) sin perder la identidad única de los individuos.

Resumen Técnico: Redes Neuronales Gráficas Jerárquicas Multiescala (HMH)

1. Enunciado del Problema

Los grafos del mundo real a menudo exhiben heterofilia, donde los nodos adyacentes poseen etiquetas o características diferentes. Aunque las Redes Neuronales Gráficas (GNN) existentes han avanzado en el manejo de tales datos, sufren de tres patologías críticas, particularmente en grafos con desequilibrio de grados (dominados por hubs):

Dominio de Hubs: En grafos con nodos "hubs" de alto grado, los mecanismos convencionales de paso de mensajes permiten que estos hubs dominen el proceso de agregación. Esto abrumba las señales de los nodos "rayos" de bajo grado (pequeños clústeres), causando que los embeddings de clústeres distintos converjan hacia una representación común inducida por el hub, borrando así las fronteras de decisión.
Sobresuavizado: A medida que aumenta la profundidad de las GNN, los embeddings de los nodos tienden a converger hacia una distribución estacionaria (medias de clase), haciendo que las características sean indistinguibles. Esto se ve exacerbado por filtros polinomiales subóptimos que mezclan señales de regiones semánticamente no relacionadas.
Sobrecuadrado: La información de nodos distantes decae exponencialmente con la distancia en el grafo, creando cuellos de botella que impiden el flujo de información a larga distancia.

Los enfoques espectrales existentes (por ejemplo, ChebNet, BernNet) a menudo dependen de bases polinomiales globales (Chebyshev, Jacobi) que asumen ortogonalidad continua. Sin embargo, los grafos reales poseen medidas espectrales discretas, lo que conduce a fugas de frecuencia, expresividad reducida y una incapacidad para adaptarse a la heterofilia estructural local. Por el contrario, los enfoques espaciales (por ejemplo, Paso de Mensajes Firmado) a menudo sufren cancelación de signos a través de las capas o requieren costosos pasos de agregación global que mezclan señales entre regiones.

2. Metodología: HAAR Jerárquico Multivista (HMH)

Los autores proponen HMH, un marco de aprendizaje espectral de grafos diseñado para escalar en tiempo casi lineal mientras mitiga las patologías mencionadas anteriormente. El marco opera mediante un análisis jerárquico y multirresolución de señales de grafos.

2.1. Codificador Adaptativo de Heterofilia

El proceso comienza con un codificador consciente de la heterofilia que aprende afinidades firmadas conscientes de características y estructura sin requerir etiquetas de nodos.

Similitud Adaptativa: El codificador calcula una puntuación de similitud que combina la afinidad de características (pesos aprendibles) y la similitud estructural (basada en vecinos compartidos de dos saltos).
Matriz de Adyacencia Firmada: Estas puntuaciones se transforman en una matriz de adyacencia continua y firmada ( $A_{adp}$ ). Una alta similitud produce pesos positivos (comportamiento de paso bajo), mientras que una baja similitud produce pesos negativos (comportamiento de paso alto).
Estabilidad del Signo: A diferencia del Paso de Mensajes Firmado (SMP) fijo, que sufre de inversión periódica de signos ( $S^2 = I$ ), la adyacencia adaptativa de HMH se vuelve a calcular en cada capa basándose en los embeddings actuales, previniendo la oscilación rígida y la cancelación de signos.

2.2. Aproximación Jerárquica de Grafos

Utilizando las puntuaciones de nodos del codificador, HMH construye una jerarquía de grafos suave mediante un proceso de agrupamiento recursivo:

Agrupamiento: Los nodos se agrupan en clústeres (supernodos) utilizando $k$ -means++ sobre los embeddings del codificador.
Asignación Suave: Una matriz de asignación probabilística ( $A_s$ ) mapea nodos finos a clústeres gruesos, controlada por un parámetro de temperatura.
Agregación: Las características y las aristas se agregan para formar el siguiente nivel de la jerarquía. Este proceso se repite hasta alcanzar un umbral, creando una estructura de árbol.

2.3. Bases Haar Conscientes de Clase y Filtrado Espectral

En cada nivel jerárquico, HMH construye una base de Haar ortonormal y dispersa ( $U^{(\ell)}$ ) adaptada a la estructura de clúster específica de ese nivel.

Construcción de la Base: La base consiste en un vector de escalado global (que captura tendencias de baja frecuencia) y wavelets. Las wavelets se dividen en:
- Wavelets inter-clúster: Capturan contrastes entre diferentes supernodos.
- Wavelets intra-clúster: Capturan variaciones localizadas dentro de un clúster.
Filtrado Diagonal: Las señales del grafo se proyectan sobre esta base. Se aplican matrices de ganancia diagonales aprendibles ( $\Lambda^{(\ell)}$ ) para amplificar selectivamente los canales de alta frecuencia (heterofílicos) y atenuar las señales de baja frecuencia (homofílicas) o dominadas por hubs.
Localidad: Dado que la base de Haar está estrictamente localizada (el soporte confinado a pequeñas vecindades), previene la fuga de información entre regiones no relacionadas del grafo, abordando directamente el dominio de hubs.

2.4. Desagrupamiento con Conexiones de Salto

Para recuperar la resolución original, HMH emplea desagrupamiento con conexiones de salto. Las salidas de todos los niveles jerárquicos se agregan de vuelta a los nodos originales. Esto asegura que cada nodo retenga sus características base enriquecidas con contexto multiescala de todos los niveles de la jerarquía, evitando efectivamente el decaimiento exponencial asociado con el sobrecuadrado.

3. Contribuciones Clave

El artículo afirma cuatro contribuciones principales:

Afinidad Firmada Adaptativa Sin Etiquetas: Un mecanismo que asigna pesos positivos/negativos basados en la similitud aprendida de características/estructura, previniendo la patología de cancelación de signos encontrada en modelos SMP fijos.
Construcción de Base Ortonormal Casi Lineal: El primer marco que construye una base espectral ortonormal, dispersa y multiescala (Haar) en tiempo casi lineal, evitando el costo $O(n^3)$ de la descomposición espectral y el costo $O(n^2)$ de las bases polinomiales densas.
Mitigación Teórica de Patologías: Pruebas rigurosas y evidencia empírica que demuestran que HMH supera el dominio de hubs, el sobresuavizado y el sobrecuadrado. Específicamente, la base localizada confina la energía a vecindades de dos saltos, y la estructura jerárquica acorta logarítmicamente las rutas de comunicación.
Rendimiento Estado del Arte: Demostración de una precisión superior en tareas de clasificación de nodos y grafos tanto en conjuntos de datos homofílicos como heterofílicos, incluidos benchmarks a gran escala como OGBN-ArXiv.

4. Resultados Experimentales

Los autores evaluaron HMH en una diversa suite de conjuntos de datos:

Clasificación de Nodos: HMH fue probado en benchmarks homofílicos estándar (Cora, Citeseer) y conjuntos de datos heterofílicos desafiantes (Chameleon, Squirrel, Texas, Roman-empire, Amazon-ratings, etc.).
- Rendimiento: HMH logró hasta un 3% de mejora en tareas de clasificación de nodos en comparación con líneas base espectrales del estado del arte (por ejemplo, ChebNetII, BernNet, UniFilter).
- Análisis de Hubs: En evaluaciones estratificadas por grado (Rayos vs. Hubs), HMH redujo significativamente la brecha de rendimiento. Por ejemplo, en el conjunto de datos Penn94, mejoró la precisión de "Rayos" (bajo grado) en +10.8% en comparación con las líneas base, que típicamente sufren por el dominio de hubs.
- Estabilidad de Profundidad: A diferencia de las GCN que se degradan rápidamente con la profundidad (sobresuavizado), HMH permaneció estable e incluso mejoró con la profundidad (alcanzando un pico de 32–64 capas en Penn94).
- Sobrecuadrado: En el benchmark Tree-NeighborsMatch, HMH mantuvo una precisión >98% a una profundidad de 10, mientras que las líneas base cayeron a adivinanzas aleatorias (50%) a la profundidad 8.
Clasificación de Grafos: Evaluado en conjuntos de datos TU (MUTAG, PROTEINS, etc.).
- Rendimiento: HMH logró una mejora de 7 puntos porcentuales en conjuntos de datos de clasificación de grafos, alcanzando notablemente el 94.5% en MUTAG.
- Escalabilidad: El marco demostró una escalabilidad casi lineal. En el conjunto de datos REDDIT-12K, HMH fue 8.1 veces más rápido por época que las líneas base basadas en descomposición espectral y utilizó 3.9 veces menos memoria.

5. Significado y Afirmaciones

El artículo posiciona a HMH como una solución a las limitaciones fundamentales de las GNN espectrales y espaciales actuales en entornos heterofílicos.

Significado Teórico: Los autores afirman que al utilizar una base de Haar ortonormal y localizada, confinan estrictamente la energía de la señal, previniendo el fenómeno de "aliasing de hubs" donde pequeños clústeres son ahogados por nodos de alto grado. Se afirma que la estructura jerárquica garantiza teóricamente la ausencia de sobrecuadrado al reducir logarítmicamente las longitudes de ruta efectivas.
Significado Práctico: El marco ofrece una alternativa escalable a los métodos espectrales costosos, haciendo viable el aprendizaje heterofílico de alto rendimiento para grafos a gran escala (por ejemplo, OGBN-ArXiv con ~170k nodos).
Modestia: Los autores reconocen las limitaciones actuales, señalando que la formulación asume grafos estáticos y que extender el método a grafos dinámicos o multi-relacionales sigue siendo una dirección para trabajo futuro. Enfatizan que sus mejoras se logran manteniendo la escalabilidad lineal, un factor crucial para el despliegue en el mundo real.