Resumen Técnico: GRAPHLCP

Enunciado del Problema

Las Redes Neuronales de Grafos (GNN) se despliegan cada vez más en dominios de alto riesgo, como el descubrimiento de fármacos, la predicción meteorológica y la detección de fraudes, lo que hace necesaria una cuantificación fiable de la incertidumbre (UQ). La Predicción Conformal (CP) ofrece un marco libre de distribuciones para construir predicciones de tipo conjunto con garantías en muestras finitas. Sin embargo, aplicar CP a las GNN presenta desafíos únicos:

1. Dependencias Estructurales: Los nodos en los grafos son naturalmente dependientes, lo que viola los supuestos estándar de independencia e identidad de distribución (i.i.d.) requeridos para la CP clásica.
2. Limitaciones de las Representaciones (Embeddings): Los métodos de CP localizados existentes para grafos a menudo dependen de la proximidad en el espacio de representaciones (por ejemplo, estimación de densidad de kernel en las representaciones de GNN) para definir vecindarios locales. Este enfoque es frecuentemente poco fiable debido a:
   • Suavizado excesivo (Over-smoothing): El paso de mensajes profundo reduce la varianza de las medidas de similitud, haciendo que las representaciones sean indiscriminadas.
   • Aplastamiento excesivo (Over-squashing): Las cuellos de botella topológicos restringen el flujo de información global, particularmente bajo heterofilia.
   • Falta de confianza (Under-confidence): Las GNN a menudo exhiben una separabilidad insuficiente en las representaciones aprendidas.
3. Ineficiencia de las Soluciones Existentes: Los métodos de CP específicos para grafos actuales dependen o bien de entrenar modelos auxiliares (aumentando la sobrecarga computacional) o de particiones estructurales rígidas (por ejemplo, agrupamiento duro) que no logran capturar la heterofilia local de alta granularidad. En consecuencia, los métodos existentes a menudo producen conjuntos de predicción excesivamente conservadores o mal localizados en topologías complejas.

Metodología: GRAPHLCP

Los autores proponen GRAPHLCP, un marco de Predicción Conformal localizado basado en proximidad diseñado para incorporar explícitamente la topología del grafo y las dependencias inter-nodo en los pasos de localización y ponderación. El método opera en un entorno transductivo donde la GNN está pre-entrenada y congelada. El marco consta de cuatro etapas clave:

1. Densificación Consciente de las Características

Para mitigar el sesgo de localidad en grafos dispersos y capturar dependencias semánticas de largo alcance, los autores introducen un paso de densificación previo al cálculo del kernel.

• Proyección PCA: Las representaciones de los nodos se proyectan primero mediante Análisis de Componentes Principales (PCA) para desacoplar las dimensiones de características correlacionadas y condensar el espacio, abordando el ruido y la redundancia causados por el suavizado excesivo.
• Kernel Anisotrópico Adaptativo: Se construye un kernel gaussiano anisotrópico utilizando las representaciones transformadas por PCA. El ancho de banda se adapta basándose en los valores propios de la matriz de covarianza para tener en cuenta las escalas variables entre dimensiones.
• Aumento de Aristas: Se añaden nuevas aristas a la matriz de adyacencia del grafo si la similitud entre nodos no conectados (calculada mediante el kernel gaussiano) supera un umbral dinámico $\tau_d$. Este umbral se ajusta automáticamente basándose en la razón de homofilia del grafo para equilibrar la adición de aristas informativas frente a la introducción de ruido.

2. Kernel de PageRank Personalizado (PPR)

En lugar de depender únicamente de las distancias de las representaciones, GRAPHLCP utiliza PPR para modelar la proximidad estructural.

• Localización: PPR captura la influencia de múltiples saltos manteniendo la localidad mediante una probabilidad de reinicio ($\beta$). Proporciona una noción suave y probabilística de proximidad que se alinea naturalmente con la CP ponderada.
• Muestreo: Para un nodo de prueba, se muestrea un nodo ancla de la distribución inducida por PPR centrada en el nodo de prueba. Esto asegura que los nodos cercanos ejerzan una mayor influencia en la estimación del cuantil.
• Ponderación: Los nodos de calibración y de prueba se ponderan según su proximidad estructural al ancla muestreada. Los autores explotan la simetría normalizada por grado de PPR ($d_i H(u_i, u_j) = d_j H(u_j, u_i)$) para calcular las ponderaciones de manera eficiente, incluso cuando el número de muestras de calibración supera el número de muestras de prueba.

3. Integración de Predicción Conformal Localizada Aleatorizada (RLCP)

GRAPHLCP adapta el marco RLCP. Al muestrear un nodo ancla $\tilde{u}_{n+1}$ de la distribución PPR del nodo de prueba $u_{n+1}$, el método construye un conjunto de predicción basado en un cuantil ponderado de puntuaciones de no conformidad. Las ponderaciones se derivan de las puntuaciones PPR en relación con el ancla muestreada, permitiendo que el método se adapte al contexto local del grafo.

4. Construcción de la Predicción

El conjunto de predicción final $\hat{C}_n(u_{n+1})$ se construye como el conjunto de etiquetas $y$ tales que la puntuación de no conformidad $s(u_{n+1}, y)$ es menor o igual a un cuantil ponderado $\hat{q}_{1-\alpha}$. Este cuantil se calcula utilizando las ponderaciones derivadas del kernel PPR y las puntuaciones de no conformidad del conjunto de calibración.

Contribuciones Clave

1. Localización Consciente de la Estructura: El artículo cierra la brecha entre la localización basada en estructura y la basada en características, reemplazando la proximidad basada únicamente en representaciones con un kernel basado en PPR. Esto incorpora explícitamente la topología del grafo en el proceso de ponderación conformal.
2. Densificación Consciente de las Características: Un paso novedoso de preprocesamiento que aumenta la topología del grafo utilizando la similitud de las representaciones (mediante PCA y kernels anisotrópicos adaptativos) para mitigar la dispersión y capturar dependencias de largo alcance sin depender de la ponderación continua potencialmente ruidosa de las representaciones.
3. Esquema de Ponderación Eficiente: El método proporciona una forma eficiente de calcular ponderaciones basadas en PPR para grafos no dirigidos aprovechando la simetría normalizada por grado, evitando la ineficiencia computacional de calcular vectores PPR completos para grandes conjuntos de calibración.
4. Validez Teórica: El enfoque mantiene las garantías de intercambiabilidad requeridas para la cobertura marginal en entornos transductivos, mientras que busca mejorar la cobertura condicional en pruebas relajada.

Resultados Experimentales

Los autores evaluaron GRAPHLCP en siete conjuntos de datos de regresión de nodos y ocho de clasificación de nodos (incluyendo redes de citas, co-compra de Amazon y conjuntos de datos geográficos).

• Cobertura Marginal: Todos los métodos, incluido GRAPHLCP, satisficieron la tasa de error objetivo ($\alpha = 0.1$), confirmando la validez del enfoque.
• Cobertura Condicional (WSC): En los diagnósticos de la Losa del Peor Caso (WSC), que buscan adversariamente la cobertura mínima a través de direcciones de proyección, GRAPHLCP logró los mejores o segundos mejores resultados en la mayoría de los conjuntos de datos, superando a líneas base como CalLCP, RLCP y SCP.
• Cobertura Basada en Grupos: GRAPHLCP demostró una cobertura superior en particiones basadas en homofilia, agrupamiento de características, coeficiente de agrupamiento y grado de nodo. El método fue particularmente efectivo en regiones heterofílicas donde los métodos estándar tuvieron dificultades.
• Eficiencia de Predicción: Mientras que CalLCP a menudo producía conjuntos de predicción excesivamente grandes (sobre-cobertura), GRAPHLCP logró longitudes de predicción normalizadas favorables, ofreciendo un mejor equilibrio entre cobertura y tamaño del conjunto.
• Estudios de Ablación:
  • Reemplazar el kernel PPR con un kernel gaussiano (GSS) resultó en una cobertura más baja y conjuntos de predicción más grandes, confirmando la importancia de la localización consciente de la estructura.
  • El paso de densificación se identificó como el componente más significativo, particularmente para tareas de regresión.
  • Se demostró que la proyección PCA es crucial para mitigar los efectos negativos de las características de representación correlacionadas.

Significado y Afirmaciones

El artículo afirma que GRAPHLCP aborda con éxito las limitaciones de los métodos de CP para grafos existentes al modelar explícitamente las dependencias estructurales. Al desacoplar las ponderaciones de los codificadores de GNN potencialmente con pérdida y utilizar un kernel basado en PPR, el método crea una "ruta residual de menor ruido" para la cuantificación de la incertidumbre.

Los autores afirman que GRAPHLCP garantiza la cobertura marginal con muestras finitas mientras alcanza eficientemente una cobertura condicional en pruebas favorable en diversos escenarios de condicionamiento. Destacan que el método es particularmente robusto en topologías complejas donde las similitudes basadas en representaciones fallan debido al suavizado excesivo o al aplastamiento excesivo. El trabajo subraya la necesidad de una localización consciente de la estructura para una UQ efectiva en grafos, yendo más allá de la dependencia exclusiva de la proximidad en el espacio de características. Los autores notan modestamente que las direcciones futuras incluyen extender este marco a grafos dinámicos con topologías en evolución.