k-hop Fairness: Addressing Disparities in Graph Link Prediction Beyond First-Order Neighborhoods

Este artículo propone la "justicia k-hop", un nuevo marco estructural para la predicción de enlaces que aborda las disparidades más allá de los vecindarios de primer orden mediante métricas de sesgo y estrategias de mitigación que logran un equilibrio favorable entre rendimiento y equidad.

Lo esencial

Imagina que las redes sociales (como LinkedIn, Facebook o incluso grupos de amigos) son como ciudades gigantes donde cada persona es una casa y cada amistad es un camino que las conecta.

El problema que aborda este paper es que, a veces, los algoritmos que recomiendan "nuevos amigos" o "conexiones laborales" actúan como urbanistas torpes. Tienen una tendencia natural a construir caminos solo entre casas que ya son muy similares (por ejemplo, solo entre personas del mismo barrio, mismo género o misma raza). Esto se llama "homofilia".

Si el algoritmo solo sigue esta regla, crea guetos digitales:

• Si eres de un grupo minoritario, el algoritmo te seguirá conectando solo con gente de tu mismo grupo, ignorando el resto de la ciudad.
• Esto refuerza la desigualdad: los que ya tienen muchos amigos siguen teniendo más, y los que están aislados siguen aislados.

El problema de la solución actual (La "Justicia de Parejas")

Hasta ahora, los expertos intentaban arreglar esto con una idea llamada "Justicia Diádica" (o de pares).

• La analogía: Imagina que el urbanista mira solo las puertas que se abren entre dos casas. Si ve que una puerta conecta a dos personas de grupos diferentes, piensa: "¡Genial! Eso es justo". Si ve una puerta entre dos personas del mismo grupo, piensa: "¡Mal! Eso es injusto".
• El fallo: Esta visión es demasiado simple. Imagina que tienes una casa en un barrio muy diverso (con muchos vecinos de diferentes grupos). Si el algoritmo te conecta con otro vecino diverso, está bien. Pero, ¿qué pasa con la persona que vive en una isla aislada, rodeada de un desierto de solo un tipo de gente? Si el algoritmo solo mira las puertas, podría ignorar a esa persona aislada porque "ya hay suficientes puertas diversas en la ciudad". La justicia de pares no ve la posición de la casa en el mapa, solo el color de la puerta.

La nueva idea: "Justicia de k-hops" (La Justicia de los Vecinos)

Los autores proponen una nueva forma de ver la ciudad: la Justicia de k-hops.

• ¿Qué es un "hop" (salto)?

  • 1-hop: Tus vecinos directos (los que viven justo al lado).
  • 2-hops: Los vecinos de tus vecinos (lo que puedes ver caminando dos calles).
  • 3-hops: Lo que puedes ver caminando tres calles, y así sucesivamente.

• La analogía creativa:
  Imagina que eres un árbol en un bosque.

  • La justicia antigua solo miraba si el árbol tenía ramas que tocaban otros tipos de árboles.
  • La nueva justicia (k-hops) pregunta: "¿Qué hay en el radio de visión de este árbol?".
    • Si miras a 1 metro de distancia (1-hop), ¿ves solo árboles del mismo tipo?
    • Si miras a 3 metros de distancia (3-hops), ¿ves un bosque diverso?

El paper descubre que los algoritmos actuales suelen ser justos a corta distancia (1-hop) pero muy injustos a larga distancia (3 o 4 hops). Pueden conectar a dos personas diferentes, pero si esas personas viven en "burbujas" separadas por varios saltos, la desigualdad estructural sigue ahí.

¿Cómo lo arreglan? (Las herramientas)

Los autores proponen dos formas de reorganizar la ciudad para que sea más justa en todos los niveles de distancia:

1. Antes de construir (Pre-procesamiento):

   • Imagina que, antes de que el algoritmo empiece a recomendar amigos, tú mismo dibujas nuevos caminos en el mapa.
   • Conectas deliberadamente la "isla aislada" con el "barrio diverso" añadiendo puentes (caminos) que no existían antes. Esto cambia la estructura de la ciudad para que, al mirar a 3 o 4 calles de distancia, todos vean diversidad.

2. Después de construir (Post-procesamiento):

   • Imagina que el algoritmo ya ha hecho su lista de recomendaciones de amigos.
   • Tú tomas esa lista y reescribes algunas recomendaciones. Si el algoritmo dijo "Conéctate con tu vecino del mismo grupo", tú dices: "Espera, mira a 3 calles de distancia, hay alguien diferente que te conviene más".
   • Hacen esto sin romper la ciudad, solo ajustando las probabilidades de quién se conecta con quién.

¿Qué descubrieron? (Los resultados)

• El mapa importa: No basta con mirar las conexiones directas. La desigualdad está escondida en las distancias largas (3 o 4 saltos).
• Todo está conectado: Si arreglas la injusticia en un nivel (por ejemplo, a 2 saltos), a veces esto cambia lo que pasa a otros niveles (a 3 saltos). Es como mover una pieza en un tablero de ajedrez; afecta a todo el juego.
• Su método funciona: Su técnica de "reescribir" las recomendaciones (post-procesamiento) logra que las personas tengan acceso a grupos diversos a diferentes distancias, sin perder la calidad de las recomendaciones (siguen siendo buenos amigos o contactos laborales).

En resumen

Este paper nos dice: "No basta con mezclar un poco de sal en la sopa (conectar dos grupos diferentes). Hay que asegurarse de que, si miras desde cualquier punto de la ciudad hacia cualquier distancia, veas un paisaje diverso y justo."

Es como pasar de un urbanista que solo mira las puertas de las casas, a uno que diseña la ciudad entera para que nadie quede atrapado en una burbuja, sin importar cuán lejos mire.

Resumen técnico

Resumen Técnico: Equidad k-hop en la Predicción de Enlaces en Grafos

1. El Problema: Limitaciones de la Equidad Diádica

La predicción de enlaces (Link Prediction - LP) es fundamental en aplicaciones como la recomendación social. Sin embargo, los grafos del mundo real a menudo reflejan sesgos estructurales, siendo el más notable la homofilia (la tendencia de nodos con atributos similares a conectarse).

• Enfoque actual (Equidad Diádica): La mayoría de los métodos existentes de LP justa se basan en el paradigma de "equidad diádica". Este enfoque trata la equidad como un balance entre enlaces intragrupales (dentro del mismo grupo sensible, ej. mismo género) e intergrupales (entre grupos diferentes). Su objetivo es promover conexiones entre grupos para mitigar la segregación.
• La limitación crítica: El artículo argumenta que la equidad diádica es insuficiente porque:
  1. Ignora la estructura subyacente: Trata todos los enlaces intergrupales como equivalentes, sin considerar la posición topológica de los nodos.
  2. Oscurece la segregación interna: Al forzar enlaces intergrupales en las áreas más conectadas y diversas del grafo, se pueden reforzar las disparidades dentro de los grupos sensibles, dejando a los nodos aislados o segregados sin acceso a información diversa.
  3. Falta de granularidad: Las métricas actuales agregan sesgos de todas las distancias en un solo valor, impidiendo identificar en qué "saltos" (hops) del grafo ocurren las desigualdades.

2. Metodología Propuesta: Equidad k-hop

Los autores proponen un nuevo marco conceptual y algorítmico llamado Equidad k-hop, que evalúa las disparidades condicionadas a la distancia entre nodos en el grafo.

A. Definiciones Fundamentales:

• Exposición de Atributo k-hop ($f^{(k)}_s(v)$): Mide la probabilidad de que un nodo $v$ forme conexiones con nodos de un grupo sensible $s$ que se encuentran exactamente a $k$ saltos de distancia.
• Exposición Grupal k-hop ($\phi^{(k)}_{s \to s'}$): Promedia la exposición local de todos los nodos de un grupo $s$ hacia un grupo $s'$ a distancia $k$.
• Brecha de Equidad k-hop ($NF^{(k)}$): Define la equidad en un salto $k$ fijo como la diferencia máxima en la exposición de un grupo fuente hacia diferentes grupos objetivo. Un valor bajo indica un acceso equilibrado.
• Sesgo Estructural k-hop ($NB^{(k)}$): Una métrica puramente estructural que mide la diversidad de atributos sensibles en los vecindarios reales de $k$ saltos del grafo original (sin predicción).

B. Estrategias de Mitigación:
El paper propone métodos agnósticos al modelo para reducir estos sesgos:

1. Pre-procesamiento (Modificación del Grafo): Se optimiza la matriz de adyacencia del grafo para minimizar el sesgo estructural $NB^{(k)}$ mediante la adición o reasignación de bordes, equilibrando la fidelidad al grafo original mediante un término de regularización.
2. Post-procesamiento (Ajuste de Predicciones): Se ajusta la matriz de probabilidades de enlaces predichos ($P$) restringiendo las modificaciones solo a pares de nodos que están exactamente a $k$ saltos de distancia. Se minimiza una función de pérdida que combina la brecha de equidad $NF^{(k)}$ y la magnitud del cambio aplicado.

C. Complejidad Computacional:

• El cálculo de las métricas $NB^{(k)}$ y $NF^{(k)}$ tiene una complejidad de $O(n^2)$ bajo suposiciones de grafos dispersos, utilizando búsquedas en anchura (BFS) o potencias de matrices de adyacencia.
• El post-procesamiento es eficiente porque la estructura del grafo subyacente (la matriz de indicadores $k$-hop) permanece fija durante la optimización.

3. Contribuciones Clave

1. Nueva Definición de Equidad: Introducen la "Equidad k-hop", que permite evaluar y mitigar disparidades a distancias específicas en el grafo, superando la visión binaria de la equidad diádica.
2. Análisis de Interdependencia: Demuestran que los sesgos estructurales en diferentes saltos ($k$) no son independientes; mitigar el sesgo en un salto específico puede afectar (positiva o negativamente) a otros saltos.
3. Métodos de Mitigación Agnósticos: Proponen estrategias de pre- y post-procesamiento que pueden aplicarse a cualquier modelo de predicción de enlaces (como GCN, Node2Vec, GraphSAGE) sin necesidad de reentrenar desde cero.
4. Validación Empírica: Proporcionan una evaluación exhaustiva en múltiples grafos reales y sintéticos, mostrando que los métodos actuales no abordan los sesgos k-hop.

4. Resultados Experimentales

Los experimentos se realizaron en conjuntos de datos reales (Polblogs, Facebook, Pokec, Citeseer) y sintéticos, utilizando modelos base (GCN, SAGE, Node2Vec) y baselines justas existentes (FairWalk, CrossWalk, etc.).

• RQ1: Relación entre Sesgo Estructural y Equidad: Se encontró una fuerte correlación entre el sesgo estructural $NB^{(k)}$ y la falta de equidad $NF^{(k)}$ en los modelos. Los saltos con mayor sesgo estructural son donde los modelos predicen con mayor injusticia. Además, el sesgo no se limita al vecindario inmediato (1-hop); existen sesgos significativos en saltos mayores (ej. 4-hop en Polblogs).
• RQ2: Dependencia entre Saltos: Al intentar mitigar el sesgo en un salto específico mediante la adición de bordes (pre-procesamiento), se observó una fuerte interdependencia. Reducir el sesgo en $k=2$ puede aumentar el sesgo en $k=3$, lo que indica que las estrategias de mitigación deben ser específicas para cada caso y no universales.
• RQ3: Efectividad del Post-procesamiento:
  • El método de post-procesamiento propuesto logra reducir significativamente la métrica $NF^{(k)}$ en los saltos objetivo.
  • Compensación (Trade-off) AUC-Equidad:
    • En $k=1$, la mejora en equidad no sacrifica el rendimiento (AUC), ya que las modificaciones afectan principalmente a los bordes de entrenamiento.
    • En $k=2$, hay una caída notable en el AUC porque los pares a 2 saltos suelen superponerse con los bordes de prueba (debido al alto agrupamiento local).
    • En $k > 2$, la degradación del rendimiento es mínima o nula, y en algunos casos el AUC mejora ligeramente al eliminar ruido sesgado.
  • A diferencia de los métodos de pre-procesamiento, el post-procesamiento garantiza que la optimización en un salto $k$ no empeore la equidad en otros saltos $k'$.

5. Significado e Impacto

Este trabajo representa un avance significativo en la investigación de equidad en grafos al:

• Desafiar el paradigma dominante: Muestra que la equidad diádica puede ser engañosa y que es necesario considerar la topología del grafo y la distancia entre nodos.
• Ofrecer una herramienta de diagnóstico: Proporciona métricas para identificar dónde (en qué distancia) ocurren las desigualdades, permitiendo intervenciones más precisas.
• Aplicabilidad Industrial: El enfoque es relevante para plataformas como LinkedIn, donde las recomendaciones de conexiones se categorizan explícitamente por proximidad (ej. "amigos de amigos" o 2-hop), y donde la equidad debe asegurarse en cada nivel de proximidad, no solo globalmente.

En conclusión, el paper establece que la equidad en la predicción de enlaces debe ser estructural y específica de la distancia, y ofrece un marco robusto para lograrlo sin sacrificar drásticamente la utilidad del modelo.