When Should Graph Attention Be Sparse? Learning a Per-Edge Tsallis Index

Planteamiento del Problema

Las Redes de Atención de Grafos (GAT) normalizan las puntuaciones de relevancia de la vecindad utilizando softmax, lo que corresponde a la solución de máxima entropía bajo la estadística de Shannon. Este diseño asume implícitamente que los pesos de atención deben distribuirse de acuerdo con estadísticas extensivas (Boltzmann–Gibbs). Sin embargo, los grafos del mundo real a menudo violan estos supuestos:

• Grafos homofílicos (p. ej., redes de citas) a menudo se benefician de centrarse en unos pocos vecinos altamente relevantes, ignorando la "cola larga" de aquellos débilmente relacionados.
• Grafos heterofílicos (p. ej., grafos de la web) a menudo se benefician de agregar pequeñas cantidades de evidencia de muchos vecinos disímiles.

El softmax estándar es subóptimo para ambos regímenes porque no puede representar ceros exactos (forzando una atención densa) e impone un comportamiento de cola fijo. Aunque existen alternativas dispersas como Sparsemax y $\alpha$-entmax, estas suelen depender de hiperparámetros fijos o están restringidas a regímenes específicos (por ejemplo, $\alpha$-entmax solo está definida para $\alpha \ge 1$, perdiendo el régimen de cola pesada). Además, los métodos existentes a menudo tratan el índice de dispersión como un hiperparámetro congelado que requiere una búsqueda de cuadrícula (grid search) por tarea.

Metodología: LTGA

Los autores proponen LTGA (Learnable Tsallis Graph Attention), una capa de atención de grafos que reemplaza la normalización softmax estándar con una $q$-softmax basada en la estadística de Tsallis. El índice entrópico $q$ se aprende de extremo a extremo (end-to-end), lo que permite al modelo interpolar continuamente entre tres regímenes:

1. Cola pesada ($q < 1$): Soporte ilimitado, reteniendo peso en los vecinos con puntuaciones bajas.
2. Shannon/Softmax ($q = 1$): La línea base estándar de GAT.
3. Soporte compacto ($q > 1$): Produce ceros exactos para puntuaciones por debajo de un umbral, podando eficazmente a los vecinos no informativos.

Componentes Técnicos Clave:

• Reparametrización: Para asegurar la estabilidad numérica y evitar que el índice derive hacia regímenes degenerados, $q$ se parametriza como $q(\alpha) = 1 + \delta \tanh(\alpha)$, donde $\alpha$ es un escalar sin restricciones. Esto fija la inicialización en la línea base de Shannon ($q=1$) cuando $\alpha=0$.
• Granularidades: El índice $q$ puede vincularse en cuatro niveles de granularidad, intercambiando expresividad por recuento de parámetros:
  • Global-q: Un único escalar compartido en todas las capas y cabezales.
  • Layer-q: Un escalar por capa.
  • Head-q: Un escalar por cabezal de atención.
  • Edge-q (LTGA-Edge): Un índice por arista generado por un pequeño MLP que mapea las incrustaciones (embeddings) de los puntos finales a un escalar de puerta (gate). Esto permite que diferentes aristas dentro de la misma vecindad adopten diferentes regímenes de atención.
• Estabilidad Numérica: Se utiliza una rama de expansión de Taylor cerca de $q=1$ para manejar la singularidad eliminable en la función $q$-exponencial, asegurando valores y gradientes continuos.
• Estabilizadores de Entrenamiento:
  • Optimizador Desacoplado: Un optimizador Adam separado para los parámetros $\alpha$ con un esquema de calentamiento (warm-up) que congela $\alpha=0$ durante las primeras $T_w$ épocas, permitiendo que los pesos de las características converjan antes de que la geometría de la atención cambie.
  • Regularizador de Prior de Shannon: Una penalización cuadrática en $(q-1)^2$ actúa como la navaja de Occam, penalizando las desviaciones de la línea base de softmax a menos que mejoren la pérdida de la tarea.

Contribuciones Clave

1. Índice Entrópico Aprendible: LTGA introduce un $q$ aprendible a la atención de grafos, cubriendo toda la familia Tsallis de dos lados ($q<1$ y $q>1$), a diferencia del trabajo previo restringido a $\alpha \ge 1$.
2. Formulación Estable: El artículo proporciona una formulación de $q$-softmax numéricamente estable con una rama de Taylor alrededor del límite de Shannon, junto con estrategias de reparametrización y regularización para permitir un entrenamiento estable de extremo a extremo.
3. Evaluación Exhaustiva: El método se evalúa en ocho benchmarks que abarcan un amplio espectro de homofilia ($h \in [0.05, 0.81]$), comparándolo contra softmax, cuadrículas de $q$ congelado, $\alpha$-entmax ajustado, sparsemax y arquitecturas específicas de heterofilia.
4. Análisis de Interpretabilidad: Los autores analizan el comportamiento del índice aprendido, vinculando $q>1$ con la poda de vecindad dependiente de los datos y verificando que las aristas podadas son, de hecho, "ruido" (baja concordancia de etiquetas y similitud de características).

Resultados

• Rendimiento: En 10 semillas y 8 conjuntos de datos, LTGA-Edge logra el mejor rango de Friedman promedio (2.75), superando a GAT (3.19) y GATv2 (4.06). Sin embargo, la prueba ómnibus no rechaza la hipótesis nula ($p=0.199$), lo que indica que la diferencia de rendimiento agregada no es estadísticamente significativa entre todos los métodos.
• Ganancias Específicas: Las principales ganancias se observan en los benchmarks heterofílicos:
  • Roman-Empire ($h=0.05$): LTGA-Edge mejora la precisión en un +16.3% sobre GAT y un +1.4% sobre GATv2.
  • Amazon-Ratings ($h=0.38$): LTGA-Edge mejora la precisión en un +0.8% sobre GAT y un +1.1% sobre GATv2.
  • En grafos homofílicos (Cora, CiteSeer, PubMed), $q$ converge a 1, y LTGA se comporta de manera comparable a GATv2.
• Aprendizaje vs. Ajuste: Aprender $q$ no supera estrictamente a la búsqueda del $q$ congelado óptimo. Una cuadrícula congelada ajustada por validación logra 61.4%, un $\alpha$-entmax ajustado logra 62.2%, y un control de capacidad igualada logra 62.0%, frente al 61.7% de LTGA-Edge. El artículo concluye que el valor de aprender $q$ es la conveniencia (una sola ejecución en lugar de una búsqueda de cuadrícula) y la adaptabilidad, más que un techo de precisión bruta.
• Validación del Mecanismo:
  • En Roman-Empire, el índice aprendido poda aproximadamente el 42% de los coeficientes de atención a cero exacto.
  • Selectividad: Las aristas podadas tienen significativamente menor concordancia de etiquetas (9.3% frente a 43.5% para las mantenidas) y similitud de características.
  • Contrafácticos: Restaurar las aristas podadas durante la inferencia reduce la precisión en 7.1 puntos. Podar aleatoriamente el mismo número de aristas reduce la precisión 13.0 puntos más que la poda aprendida, confirmando que la dispersión es selectiva y beneficiosa.
• Granularidad: Aunque LTGA-Edge obtiene el mejor rango promedio, las granularidades escalares (Global, Capa, Cabezal) se comportan de manera similar en los conjuntos de datos donde $q$ se mueve, lo que sugiere que la capacidad por arista es el principal motor del rendimiento en grafos heterofílicos.

Significado y Reivindicaciones

El artículo afirma modestamente que LTGA proporciona un marco unificado y aprendible para la normalización de la atención de grafos que se adapta a las necesidades estadísticas específicas de un grafo sin el ajuste manual de hiperparámetros.

• Interpretabilidad: Donde $q$ se desvía de la línea base de Shannon, lo hace de forma interpretable: $q>1$ corresponde a la poda selectiva de vecinos no informativos (soporte compacto), mientras que $q<1$ corresponde a la difusión de cola pesada.
• Limitaciones: Los autores declaran explícitamente que el régimen de cola pesada ($q<1$) no mostró beneficios empíricos en los benchmarks probados. También señalan que, en conjuntos de datos pequeños y de alta varianza (WebKB), el método no ofrece ventaja sobre GATv2.
• Posicionamiento: No se pretende que LTGA sea complementario a las arquitecturas específicas de heterofilia (como H2GCN o GPR-GNN) porque esos modelos no normalizan la atención de la misma manera. En cambio, LTGA compite directamente con los modelos basados en atención y ofrece un mecanismo para reemplazar la normalización softmax fija con una alternativa adaptativa y basada en datos.

En resumen, LTGA demuestra que aprender el índice entrópico permite a una red de atención de grafos descubrir automáticamente si debe ser densa, dispersa o de cola pesada basándose en la homofilia del grafo, ofreciando una alternativa robusta y de una sola ejecución frente a los mecanismos de atención dispersa de búsqueda de cuadrícula.