Resumen Técnico: Una Capa de Tikhonov Generalizada para Redes Neuronales de Grafos Interpretables por Diseño

Declaración del Problema

Las Redes Neuronales de Grafos (GNN) han logrado un éxito significativo en tareas de clasificación de grafos y nodos al aprender a agregar características sobre la topología del grafo. Sin embargo, su interpretabilidad sigue siendo un desafío crítico. A diferencia de las redes neuronales clásicas, las GNN deben explicar no solo cómo se transforman las características de entrada, sino también cómo se explota la propia topología del grafo. Los métodos existentes de interpretabilidad a menudo dependen de aproximaciones post-hoc (por ejemplo, GNNExplainer, saliencia de gradientes) que carecen de garantías de fidelidad, o de arquitecturas de dos módulos donde un extractor de explicaciones está desconectado del clasificador, permitiendo que el clasificador ignore la explicación mientras minimiza la pérdida. Además, las GNN profundas sufren de patologías como el sobrealisamiento (colapso de las representaciones de nodos) y el sobreaplastamiento (decaimiento exponencial de la sensibilidad a largo alcance).

Metodología

Los autores proponen la capa de Tikhonov, una capa de red neuronal de grafos diseñada para ser interpretable por construcción. La innovación central radica en restringir la matriz de propagación del grafo $R$ a una solución de forma cerrada específica derivada de un problema de regularización de Tikhonov generalizado en grafos.

El Operador de Propagación

Para un grafo con laplaciano normalizado $L$, la salida de la capa para las características de entrada $X$ viene dada por:
$$X^{(k+1)} = \sigma \left( R X^{(k)} W \right)$$
donde la matriz de propagación $R$ se define como:
$$R = (p(L) + Q)^{-1} Q$$
Aquí:

• $L$ es el laplaciano normalizado del grafo.
• $Q = \text{diag}(q_1, \dots, q_n)$ es una matriz diagonal aprendible de puntuaciones de importancia de nodos estrictamente positivas.
• $p(\cdot)$ es un polinomio aprendible que satisface $0 < p(\lambda) < 1$ para $\lambda \in [0, 2]$.
• $\sigma$ es una no linealidad punto a punto y $W$ es una matriz de pesos.

Interpretación Variacional

El operador $R$ es el minimizador único de forma cerrada del problema de Tikhonov generalizado:
$$R x = \arg \min_{z \in \mathbb{R}^n} \sum_{i \in V} q_i (x_i - z_i)^2 + z^\top p(L) z$$
Esta formulación intercambia explícitamente la fidelidad de los datos a nivel de nodo (ponderada por $q_i$) contra la regularización impulsada por la topología (gobernada por $p(L)$).

• $q_i$ grande: El nodo $i$ depende fuertemente de sus propias características; la salida $z_i$ permanece cerca de $x_i$.
• $q_i$ pequeño: El nodo $i$ descarta sus propias características en favor de una solución impulsada por la topología del grafo (suavidad o propiedades espectrales específicas definidas por $p$).
• Forma de $p(\lambda)$: Determina la naturaleza de la influencia topológica. Un $p$ creciente penaliza las altas frecuencias (favoreciendo la homofilia/suavidad), mientras que un $p$ decreciente penaliza las bajas frecuencias (favoreciendo la heterofilia).

Arquitectura y Expresividad

Para mantener una alta expresividad sin sacrificar la interpretabilidad, la arquitectura emplea una separación de responsabilidades:

1. La Red Q: Una GNN dedicada, potencialmente profunda (por ejemplo, ChebNet o ARMA), que toma el grafo $(G, X)$ como entrada y produce las puntuaciones de importancia de nodos $Q$. Este componente maneja el aprendizaje representacional complejo y adapta $q_i$ a las estructuras y características locales del grafo.
2. La Capa de Tikhonov: Una sola capa transparente que aplica la propagación $R$. No contiene no linealidades ocultas ni pasos complejos de paso de mensajes; sus parámetros son los coeficientes polinomiales de $p$ y las salidas de la Red Q.
3. Cabeza: Una operación de agrupación global seguida de una MLP para la predicción final.

El modelo admite extensiones multicanal donde se utilizan múltiples redes Q y polinomios independientes, aunque los experimentos se centran en el caso de un solo canal ($J=1$).

Detalles de Implementación

• Cálculo: Calcular $(p(L) + Q)^{-1}QX$ implica resolver sistemas lineales. Los autores utilizan el Método del Gradiente Conjugado Precondicionado (PCG) con un precondicionador diagonal (Jacobi) para evitar el costo $O(n^3)$ de la inversión densa, logrando una escalabilidad $O(dTKm)$ donde $T$ es el número de iteraciones.
• Diferenciación: Para evitar almacenar el grafo computacional del solucionador, los autores utilizan diferenciación implícita, requiriendo solo una solución adicional de PCG en la pasada hacia atrás para calcular los gradientes con respecto a $Q$ y $p$.
• Restricciones: El polinomio $p(\lambda)$ se parametriza utilizando polinomios de Bernstein con activaciones sigmoide para imponer estrictamente $0 < p(\lambda) < 1$. Las puntuaciones $q_i$ se mapean a valores estrictamente positivos mediante una función de limitación en el espacio logarítmico.

Contribuciones Clave y Propiedades Teóricas

1. Interpretabilidad Integrada: El par $\{ \{q_i\}_{i \in V}, p(\cdot) \}$ constituye una explicación directa y fiel. Un $q_i$ grande indica dependencia de características; un $q_i$ pequeño indica dependencia topológica. La forma de $p$ revela el sesgo espectral (homofilia, heterofilia, paso de banda).
2. Acoplamiento Estructural: Los autores demuestran (Proposición 3.6) que el mapa $Q \mapsto R$ es inyectivo. A diferencia de los métodos post-hoc, cambiar la explicación ($Q$) necesariamente cambia el operador de propagación ($R$), asegurando que la explicación sea fiel al cálculo.
3. Expresividad: Se demuestra que la capa es densa en el espacio de filtros espectrales continuos en el caso homogéneo. Con $Q$ heterogénea, extiende estrictamente la expresividad más allá de los filtros espectrales tradicionales al romper la estacionariedad (Proposición 3.3).
4. Mitigación de Patologías de GNN:
   • Sobrealisamiento: Se evita mediante el uso de una sola capa y la invertibilidad de $p(L) + Q$. El colapso de nodos solo ocurre si el modelo impulsa deliberadamente todos los $q_i \to 0$.
   • Sobreaplastamiento: La tasa de decaimiento de la sensibilidad a largo alcance $|R_{ij}|$ está gobernada por el número de condición $\kappa$ del sistema, que depende de la $Q$ aprendida. El modelo puede aprender a reducir $\kappa$ (disminuyendo $q_i$ específicos) para aumentar la sensibilidad a largo alcance donde sea necesario, intercambiando efectivamente la precisión local por el alcance global.

Resultados Experimentales

El modelo fue evaluado en tareas sintéticas controladas y en benchmarks estándar, demostrando tanto rendimiento como interpretabilidad:

• Tareas Sintéticas Controladas:
  • Colors-3: La tarea depende exclusivamente de las características de los nodos. El modelo aprendió $q_i$ grandes en todas partes, ignorando efectivamente la topología y comportándose como una MLP, identificando correctamente que las características impulsan la predicción.
  • Distancia de Clique: Una tarea puramente estructural. El modelo aprendió $q_i$ pequeños para los nodos de camino (confiando en la topología para percibir la distancia) y $q_i$ grandes para los nodos del clique (anclajes), logrando un 100% de precisión.
  • Triángulos: Una tarea estructural para detectar triángulos. El modelo asignó $q_i$ pequeños en general, pero $q_i$ más grandes a los vértices de los triángulos, localizando el motivo sin supervisión.
• CSBM (Modelo de Bloques Estocásticos Contextual): El modelo rastreó con éxito el umbral teórico de transición de fase para la recuperación. Los valores aprendidos de $q_i$ transicionaron suavemente de regímenes dominados por características ($q_i$ grandes) a regímenes dominados por topología ($q_i$ pequeños), identificando correctamente la fuente de la señal en regímenes mixtos.
• ECHO-diam (Propagación a Largo Alcance): En una tarea de regresión del diámetro del grafo, el modelo logró un Error Absoluto Medio (MAE) de 1.17, superando a las GNN profundas de referencia (~1.6) y acercándose al rendimiento de los Transformers (1.05). La explicación reveló que el modelo asignó $q_i$ grandes a los nodos periféricos (extremos) y $q_i$ pequeños a los nodos interiores, utilizando el contraste entre los extremos anclados y el interior suavizado para estimar el diámetro.

Significado y Afirmaciones

El artículo afirma que la capa de Tikhonov ofrece un enfoque novedoso para la interpretabilidad de GNN al diseñar la capa para que sea autoexplicable en lugar de recuperar explicaciones post-hoc.

• Fidelidad: La explicación es el propio modelo; no hay subgrafo desconectado ni aproximación.
• Granularidad: Proporciona una respuesta continua y resuelta espacialmente (valores de $q_i$ graduados) en lugar de una selección binaria de subgrafos.
• Rendimiento: El modelo iguala o supera a las bases opacas (como GIN, GAT y Transformers) en diversas tareas mientras proporciona información sobre cómo se resuelve la tarea (por ejemplo, distinguiendo entre razonamiento basado en características y basado en topología).
• Limitaciones: Los autores reconocen que algunas explicaciones pueden ser complejas de interpretar para los humanos y que el costo computacional del PCG puede ser alto para tareas que requieren interacciones a largo alcance (aunque sugieren el álgebra lineal numérica aleatoria como una dirección futura para la aproximación).

El trabajo establece que es posible restringir las capas de GNN a formas variacionales específicas para ganar interpretabilidad sin sacrificar la capacidad de aprender filtros de grafos complejos y no estacionarios.