Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Planteamiento del Problema
La equidad en la predicción de enlaces busca reducir las disparidades en las probabilidades de enlace predichas entre grupos. En las recomendaciones de redes sociales, los predictores de enlaces determinan la visibilidad y la conectividad, lo que puede inducir bucles de retroalimentación que refuerzan las conexiones dentro del grupo y desfavorecen a los grupos minoritarios. Un problema crítico surge cuando estos modelos se entrenan con datos históricos de grafos, los cuales pueden heredar y amplificar los sesgos estructurales existentes.

La paridad demográfica ($\Delta$DP) es una métrica de equidad común en la predicción de enlaces con ranking, pero agrega los enlaces en categorías gruesas (mismo grupo frente a entre grupos). Mattos et al. (2025) argumentan que esta visión diádica no logra detectar el sesgo de exposición porque ignora la posición específica de los enlaces dentro del ranking. En consecuencia, la paridad agregada puede mantenerse incluso cuando los enlaces de pares de subgrupos específicos (por ejemplo, enlaces femenino-femenino) están sistemáticamente posicionados más bajo que otros, ocultando las disparidades intragrupales.

Metodología
Este estudio es una reproducibilidad y extensión de Mattos et al. (2025). Los autores formalizan la predicción de enlaces como un problema de ranking donde los atributos sensibles definen tipos de pares de subgrupos (por ejemplo, $E_{0-0}, E_{1-1}, E_{0-1}$).

1. Métricas:

   • Paridad Demográfica ($\Delta$DP): Mide la diferencia en las puntuaciones medias predichas entre los enlaces intra-grupo ($E_{intra}$) e inter-grupo ($E_{inter}$). Es invariante a la permutación respecto al orden del ranking.
   • Divergencia KL normalizada (NDKL): Una métrica sensible al rango y no diádica que trata todos los tipos de pares de subgrupos de forma distinta. Acumula la divergencia de Kullback-Leibler entre la distribución de exposición predicha y una distribución objetivo a través de los prefijos del ranking, ponderada por un factor de decaimiento logarítmico para penalizar más fuertemente las desviaciones en los rangos superiores.
   • Utilidad: Medida mediante Precision@1000 y NDCG@1000.

2. MORAL (Multi-Output Ranking Aggregation for Link Fairness):
   Un algoritmo de post-procesamiento que re-clasifica los resultados de predictores de enlaces desacoplados (un modelo entrenado por cada tipo de par de subgrupos). MORAL emplea una estrategia de agregación codiciosa guiada por KL: en cada posición de ranking, selecciona el mejor elemento restante de cada grupo de pares de subgrupos que minimiza la divergencia KL entre la distribución de exposición actualizada y una distribución objetivo $\pi$ (derivada del grafo original).

3. Configuración Experimental:

   • Conjuntos de Datos: Seis conjuntos de datos de redes sociales (Credit, Facebook, German, NBA, Pokec-n, Pokec-z) y dos conjuntos adicionales (Global Airport Routes Network, Chameleon) para la verificación de la topología.
   • Reproducción: Los autores reprodujeron la configuración central utilizando codificadores GCN y decodificadores de producto punto, corrigiendo inconsistencias encontradas en el código original respecto al cálculo de la distribución objetivo y la agregación KL.
   • Extensiones:
     • Prueba de Estrés de Homofilia Asimétrica: Grafos sintéticos generados mediante el modelo de Acoplamiento Preferencial Dirigido con Homofilia (DPAH) para probar el rendimiento bajo diversos grados de conectividad dentro del grupo.
     • Robustez de la Métrica: Evaluación utilizando la Equidad de Rango Ponderada por Atención (AWRF) y NDCG para asegurar que los resultados no sean específicos del mecanismo de agregación NDKL.
     • Atributos Categóricos: Extensión del marco de trabajo a atributos sensibles con cardinalidad $m > 2$.

Contribuciones Clave

1. Reproducción y Corrección: El estudio reproduce con éxito las afirmaciones centrales de Mattos et al. (2025) mientras libera una implementación corregida y reproducible. Identifica y corrige inconsistencias en el código original respecto al cómputo de la distribución objetivo y la normalización de la divergencia KL.
2. Validación de Afirmaciones:
   • C1: Confirma que $\Delta$DP puede indicar paridad agregada incluso cuando existen disparidades de exposición significativas dentro de pares de subgrupos específicos (por ejemplo, dentro de $E_{intra}$).
   • C2: Demuestra que NDKL detecta eficazmente estas disparidades ocultas debido a su naturaleza sensible al rango y no diádica.
   • C3: Muestra que MORAL mitiga consistentemente los sesgos de exposición (bajo NDKL) manteniendo una utilidad competitiva (Precision/NDCG) a través de diversos conjuntos de datos.
3. Análisis de Robustez:
   • El estudio extiende el trabajo original probando la homofilia asimétrica, mostrando que MORAL se desempeña de manera robusta, aunque las disparidades de exposición son más pronunciadas en niveles de homofilia absoluta intermedia.
   • Valida la generalizabilidad del marco a atributos sensibles categóricos (hasta $m=10$) y diferentes topologías de grafos (Core-periphery, Heterophilic).
   • Confirma que las mejoras en la equidad no son meramente un artefacto de la optimización de NDKL, ya que se observan tendencias similares con AWRF.

Resultados

• Equidad vs. Utilidad: MORAL logra un NDKL cercano a cero en todos los conjuntos de datos, superando significativamente a los baselines (FairAdj, FairWalk, DetConstSort). Esta reducción en el sesgo de exposición viene acompañada de una pérdida mínima de utilidad; MORAL mantiene una alta Precision@1000, igualando o incluso superando a los baselines.
• Sensibilidad de la Métrica: $\Delta$DP permanece mayormente invariante a los cambios en la asignación de exposición dentro de los grupos, mientras que NDKL y AWRF son altamente sensibles a estos cambios.
• Homofilia: En entornos sintéticos, las métricas basadas en la exposición alcanzan su pico en la homofilia absoluta intermedia ($\approx 0.6$), donde los bordes intra-grupo son frecuentes pero los rankings siguen siendo diversos. En la homofilia alta, la utilidad cae ligeramente debido a que los predictores desacoplados reciben señales de entrenamiento más débiles.
• Atributos Categóricos: A medida que aumenta el número de tipos de pares de subgrupos ($T$), NDKL y AWRF se degradan monótonamente, indicando que alinear la exposición con la distribución objetivo se vuelve progresivamente más difícil. Sin embargo, la utilidad se mantiene alta, lo que sugiere que los elementos en los primeros rangos siguen siendo precisos incluso cuando los rangos inferiores se vuelven menos estables.
• Ablación: Una comparación de las puntuaciones pre-re-ranking y post-re-ranking muestra que el paso de agregación codiciosa de KL es responsable de una reducción sustancial en el sesgo de exposición (una reducción del 66.9% en NDKL, 92.6% en AWRF).

Significancia y Afirmaciones
El artículo concluye que la paridad demográfica diádica es insuficiente para la predicción de enlaces con ranking porque puede ocultar las disparidades de exposición de los pares de subgrupos. Los autores argumentan que cuando las salidas de la predicción de enlaces se consumen como rankings, la exposición debe ser la moneda relevante de la equidad.

El estudio respalda el uso de métricas sensibles al rango y basadas en la exposición (como NDKL y AWRF) y el método de post-procesamiento MORAL como herramientas efectivas para mitigar el sesgo en las predicciones de enlaces con ranking. Destaca un compromiso práctico: aunque MORAL escala a configuraciones de mayor cardinalidad, el costo computacional y la dificultad de la alineación de la exposición aumentan con el número de tipos de pares de subgrupos. Los autores enfatizan que preservar la distribución original del grafo ($\pi$) es una elección de diseño para prevenir la amplificación algorítmica del sesgo, no una afirmación de que la distribución original sea inherentemente "justa".