Aprendizaje Imparcial de GNN mediante Difusión de Subgrafos Consciente de Equidad

Información Básica

• ID del Artículo: 2501.00595
• Título: Unbiased GNN Learning via Fairness-Aware Subgraph Diffusion
• Autores: Abdullah Alchihabi, Yuhong Guo (Carleton University)
• Clasificación: cs.LG cs.AI
• Fecha de Publicación: 31 de diciembre de 2024 (preimpresión arXiv)
• Enlace del Artículo: https://arxiv.org/abs/2501.00595

Resumen

Las redes neuronales de grafos (GNNs) demuestran un desempeño excepcional en diversas tareas relacionadas con grafos, pero enfrentan un desafío importante: la generación de predicciones sesgadas cuando se involucran atributos de nodos sensibles (como edad, género). Debido a que el mecanismo de paso de mensajes causa que los nodos se influyan mutuamente, el sesgo en GNNs es más grave que en los modelos tradicionales de aprendizaje automático. Este artículo propone un novedoso método generativo de difusión de subgrafos consciente de equidad (FASD) para lograr aprendizaje imparcial de GNN. El método primero realiza un muestreo estratégico de pequeños subgrafos del grafo grande original, luego dessesgua los subgrafos mediante un proceso generativo de difusión de grafos consciente de equidad basado en ecuaciones diferenciales estocásticas (SDEs). Al introducir perturbaciones de sesgo adversarial en el proceso de difusión hacia adelante, se entrena un modelo basado en puntuaciones para predecir estas perturbaciones, aprendiendo así la dinámica latente del sesgo en los datos. Posteriormente, se utiliza el modelo de puntuaciones entrenado para dessesguar muestras de subgrafos originales mediante el proceso de difusión inversa. Finalmente, se ejecuta aprendizaje estándar de GNN en los subgrafos dessesgados para producir predicciones de nodos justas.

Antecedentes de Investigación y Motivación

Definición del Problema

1. Problema Central: Las GNNs tienden a producir predicciones sesgadas basadas en atributos sensibles (edad, género, raza, etc.) en tareas de clasificación de nodos
2. Mecanismo de Amplificación del Sesgo: El mecanismo de paso de mensajes de las GNNs causa que el sesgo se propague y amplifique en el grafo, siendo más grave que en modelos de ML tradicionales
3. Importancia de Aplicación: En campos críticos como atención médica y evaluación de candidatos laborales, la equidad del modelo es fundamental

Limitaciones de Métodos Existentes

1. Métodos Tradicionales de Aprendizaje Justo: No consideran la estructura del grafo ni las interacciones del paso de mensajes entre nodos
2. Métodos Existentes de GNN Justo:
   • Los métodos de preprocesamiento carecen de robustez y están diseñados para formas específicas de sesgo
   • Los métodos de procesamiento requieren un equilibrio cuidadoso entre equidad y precisión, con pobre estabilidad
   • Los métodos de postprocesamiento solo modifican los resultados de predicción
3. Métodos de Difusión de Grafos: Los métodos existentes tienden a heredar el sesgo presente en los datos de entrada

Motivación de la Investigación

Desarrollar métodos de aprendizaje y aumento de grafos conscientes de equidad y adaptativos a los datos, que sean ampliamente aplicables a diversos dominios de aplicación de GNNs.

Contribuciones Principales

1. Método Pionero: Propone el primer método de difusión de grafos consciente de equidad FASD, que utiliza procesos de difusión para dessesguar instancias de subgrafos y promover equidad en tareas posteriores
2. Innovación Técnica: Integra perturbaciones de sesgo adversarial en el proceso de difusión hacia adelante basado en SDE, aprendiendo dinámicas de sesgo mediante modelos de puntuaciones
3. Verificación Experimental: Demuestra desempeño superior en comparación con líneas base de GNN justo de última generación en múltiples conjuntos de datos de referencia
4. Contribución Teórica: Proporciona un marco teórico e implementación para difusión de grafos consciente de equidad

Explicación Detallada del Método

Definición de la Tarea

• Entrada: Grafo G=(V,E), matriz de características de nodos X∈R^(N×D), vector de atributos sensibles S, matriz de etiquetas Y^ℓ
• Objetivo: Aprender un modelo GNN que pueda predecir etiquetas de nodos de manera precisa y justa
• Criterio de Equidad: Equidad grupal, evaluada mediante paridad estadística e igualdad de oportunidades

Arquitectura del Modelo

1. Muestreo de Instancias a Nivel de Subgrafo

G^(i) = Subgraph_Sampling(G, u, d, k)

• Comenzando desde el nodo inicial u, profundidad d, muestreo de k vecinos por salto
• Generación del conjunto de subgrafos G = {G^(i)}_^M

2. Difusión Hacia Adelante Consciente de Equidad

Modelado SDE:

dG_t^(i) = f_t(G_t^(i))dt + g_t(G_t^(i))dw

Modelo de Predicción de Atributos Sensibles:

Ŝ^(i) = g_sen(X^(i), A^(i))

Perturbación Consciente de Equidad:

X_t^(i) = μ_t(X_0^(i)) + σ_t(X_0^(i)) × ε_X - γ_X∇_X L_sen(X_0^(i), A_0^(i))
A_t^(i) = μ_t(A_0^(i)) + σ_t(A_0^(i)) × ε_A - γ_A∇_A L_sen(X_0^(i), A_0^(i))

3. Estimación de Perturbaciones Basada en Puntuaciones

Modelo de Puntuaciones de Características de Nodos:

s_{θ,t}(G_t^(i)) = MLP_X([{H_j}_{j=0}^L])
H_{j+1} = GNN_X(H_j, A_t^(i)), H_0 = X_t^(i)

Modelo de Puntuaciones de Estructura de Grafos:

s_{φ,t}(G_t^(i)) = MLP_A([{GMH(H_j, (A_t^(i))^p)}_{j=0,p=1}^{K,P}])

Función de Pérdida:

L_θ = E_t{E_{G_0^(i)} E_{G_t^(i)|G_0^(i)} ||s_{θ,t}(G_t^(i)) - ε_X + (γ_X/σ_t(X_0^(i)))∇_X L_sen||_2^2}

4. Dessesgamiento mediante Difusión Inversa

SDE Inversa:

dX_t^(i) = [f_{1,t}(X_t^(i)) - g_{1,t}^2 s_{θ,t}(G_t^(i))]dt̄ + g_{1,t}dw̄_1
dA_t^(i) = [f_{2,t}(A_t^(i)) - g_{2,t}^2 s_{φ,t}(G_t^(i))]dt̄ + g_{2,t}dw̄_2

Resolución aproximada mediante muestreador Predictor-Corrector.

5. Clasificación Justa de Nodos

Entrenamiento de GNN estándar en subgrafos dessesgados G̃:

P^(i) = f(X̃^(i), Ã^(i))
L = Σ_{G̃^(i)∈G̃} Σ_{u∈V_ℓ^(i)} ℓ_ce(P_u^(i), Y_u^ℓ)

Puntos de Innovación Técnica

1. Diseño de Perturbación Consciente de Equidad: Utiliza el gradiente de la pérdida de predicción de atributos sensibles como perturbación adversarial, modelando directamente el sesgo
2. Modelo Dual de Puntuaciones: Modela perturbaciones de características de nodos y estructura de grafos por separado, capturando patrones de sesgo complejos
3. Procesamiento a Nivel de Subgrafo: Resuelve la complejidad computacional de grafos grandes mediante muestreo de subgrafos
4. Dessesgamiento Generativo: Aprovecha la capacidad generativa de modelos de difusión para lograr dessesgamiento a nivel de datos

Configuración Experimental

Conjuntos de Datos

1. NBA: Datos de jugadores de NBA, atributo sensible es nacionalidad, etiqueta es si el salario supera la mediana
2. Pokec-z/Pokec-n: Datos de red social eslovaca, atributo sensible es región, etiqueta es campo de trabajo
3. División de Datos: NBA(20%/35%/45%), Pokec-z(10%/10%/80%), Pokec-n(10%/10%/80%)

Métricas de Evaluación

1. Precisión (Acc.): Precisión de clasificación
2. Paridad Estadística (ΔDP): |P(Ŷ=1|S=0) - P(Ŷ=1|S=1)|
3. Igualdad de Oportunidades (ΔEO): |P(Ŷ=1|S=0,Y=1) - P(Ŷ=1|S=1,Y=1)|

Nota: Valores menores de ΔDP y ΔEO indican mejor equidad

Métodos de Comparación

• Métodos de GNN Justo: FairWalk, FairDrop, NIFTY, FairAug, Graphair
• Métodos de Aprendizaje Contrastivo de Grafos: GRACE, GCA

Detalles de Implementación

• Muestreo de Subgrafos: d=2(NBA), d=3(Pokec), k=10
• Predictor de Atributos Sensibles: 2 capas GCN + 2 capas completamente conectadas, dimensión oculta(64,32,16)
• Modelo de Puntuaciones: Dimensión oculta 32, entrenamiento 1000 épocas
• Pasos de Difusión Inversa: N_steps=5(NBA), 4(Pokec-z), 2(Pokec-n)

Resultados Experimentales

Resultados Principales

Hallazgos Clave:

1. Mejora Significativa en Equidad: En igualdad de oportunidades, se logran mejoras del 29% en Pokec-z y 43% en Pokec-n respectivamente
2. Liderazgo en Paridad Estadística: Supera al segundo lugar en 64% en NBA y 60% en Pokec-n
3. Mantenimiento de Precisión: Mientras se mejora significativamente la equidad, la disminución en precisión es mínima

Experimentos de Ablación

Conclusiones de Experimentos de Ablación:

1. Necesidad del Proceso de Difusión: La eliminación del proceso de difusión resulta en una disminución significativa de la equidad
2. Importancia de Perturbación Consciente de Equidad: El uso solo de perturbaciones aleatorias produce resultados deficientes

Análisis de Sensibilidad de Hiperparámetros

1. Pasos de Difusión Inversa: El valor óptimo es 2-5 pasos, demasiados pasos disminuyen el desempeño
2. Peso de Perturbación de Equidad: λX, λA funcionan mejor en el rango 0.1, 10.0

Trabajo Relacionado

Aprendizaje Justo de GNN

1. Métodos de Preprocesamiento: FairWalk, FairDrop, Graphair, etc., pero carecen de robustez
2. Métodos de Procesamiento: NIFTY, FairAug, etc., requieren equilibrio cuidadoso entre equidad y precisión
3. Métodos de Postprocesamiento: Modifican directamente los resultados de predicción de GNN

Métodos de Difusión de Grafos

1. Difusión Continua: GDSS y otros basados en modelado SDE
2. Difusión Discreta: DiGress y otros usando procesos de ruido de Markov
3. Limitaciones: Los métodos existentes tienden a heredar sesgos de los datos de entrada

Conclusiones y Discusión

Conclusiones Principales

1. FASD aplica exitosamente modelos de difusión al aprendizaje justo de GNN, logrando dessesgamiento a nivel de datos
2. Mediante perturbaciones conscientes de equidad y modelos de puntuaciones, aprende y elimina efectivamente patrones de sesgo
3. Logra el mejor desempeño de equidad en múltiples conjuntos de datos de referencia mientras mantiene precisión competitiva

Limitaciones

1. Complejidad Computacional: Requiere entrenar múltiples modelos (predictor de atributos sensibles, modelo de puntuaciones, clasificador)
2. Sensibilidad de Hiperparámetros: Requiere ajuste cuidadoso de hiperparámetros como λX, λA
3. Atributos Sensibles Binarios: Actualmente solo maneja atributos sensibles binarios, la extensión a múltiples clases requiere investigación adicional
4. Representación de Subgrafos: El muestreo de subgrafos puede perder información global

Direcciones Futuras

1. Extensión a atributos sensibles multiclase y clasificación multietiqueta
2. Mejora de eficiencia computacional, reducción de complejidad de entrenamiento
3. Exploración de aplicabilidad de otros criterios de equidad
4. Análisis teórico de convergencia y garantías de equidad del método

Evaluación Profunda

Fortalezas

1. Fuerte Innovación del Método: Primera aplicación de modelos de difusión al aprendizaje justo de GNN, enfoque novedoso
2. Diseño Técnico Razonable: El diseño de perturbación consciente de equidad es intuitivo y efectivo, la arquitectura del modelo de puntuaciones es adecuada para datos de grafos
3. Experimentación Completa: Verificación en múltiples conjuntos de datos, experimentos de ablación y análisis de hiperparámetros completos
4. Resultados Convincentes: Mejoras significativas en métricas de equidad, significancia estadística clara

Deficiencias

1. Falta de Análisis Teórico: No proporciona pruebas de convergencia ni garantías teóricas de equidad
2. Problemas de Eficiencia Computacional: El entrenamiento multietapa aumenta el costo computacional, falta análisis de eficiencia
3. Limitaciones de Aplicabilidad: Solo verificado en grafos de escala relativamente pequeña, escalabilidad en grafos grandes desconocida
4. Comparación Incompleta: Falta comparación con métodos de aprendizaje justo más recientes

Impacto

1. Contribución Académica: Proporciona una nueva ruta técnica para aprendizaje justo de GNN
2. Valor Práctico: Tiene importancia significativa en campos de aplicación crítica
3. Reproducibilidad: Detalles de implementación exhaustivos, facilita reproducción y extensión

Escenarios Aplicables

1. Grafos de Escala Pequeña a Mediana: El método actual es adecuado para grafos con decenas de miles de nodos
2. Dominios con Altos Requisitos de Equidad: Aplicaciones sensibles como medicina, contratación, crédito
3. Tareas de Clasificación Binaria: Especialmente escenarios que involucran atributos sensibles binarios

Referencias

El artículo cita 61 referencias relacionadas, cubriendo múltiples campos incluyendo aprendizaje justo, redes neuronales de grafos, modelos de difusión y otros trabajos importantes, proporcionando una base teórica sólida para la investigación.

Evaluación General: Este es un trabajo innovador en el campo del aprendizaje justo de GNN, siendo el primero en aplicar modelos de difusión al dessesgamiento de datos de grafos. El diseño del método es razonable y los resultados experimentales son convincentes. Aunque requiere mejora en análisis teórico y eficiencia computacional, proporciona una ruta técnica valiosa y novedosa para el campo.