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

Este artigo propõe o conceito de "justiça k-hop" para link prediction em grafos, introduzindo métricas e estratégias de mitigação que abordam disparidades estruturais além das vizinhanças de primeira ordem, superando as limitações da justiça diádica tradicional e demonstrando, através de experimentos, um melhor equilíbrio entre desempenho e equidade.

O essencial

🌐 O Problema: A "Bolha" dos Amigos

Imagine que você está em uma grande festa (o Grafo). O objetivo de um sistema de recomendação de links é sugerir novas amizades para você.

O problema é que, na vida real, tendemos a nos conectar com pessoas parecidas conosco (mesma origem, mesmo gosto musical, mesma cor de pele). Isso se chama Homofilia. Se o computador apenas olha para quem você já conhece e sugere "mais do mesmo", ele cria uma bolha. Você fica preso no seu grupo, e pessoas de outros grupos nunca se conhecem.

Para tentar corrigir isso, os cientistas criaram regras de "Justiça" (Fairness). A regra atual diz: "Sugira mais amigos de grupos diferentes!". Isso é chamado de Justiça Diádica (focada apenas no par de pessoas).

⚠️ O Pulo do Gato: Por que a regra atual falha?

O artigo diz que essa regra atual tem um defeito grave. Ela é como um professor que só olha para a média da turma e ignora quem está sofrendo.

A Analogia da Festa:
Imagine que na festa há dois grupos:

1. Grupo Azul: Fica no centro da sala, rodeado de gente de todos os tipos. Eles já têm muitos amigos de fora.
2. Grupo Vermelho: Fica num canto isolado, numa sala separada. Ninguém de fora entra lá.

A regra antiga diz: "Faça amizade com alguém de outro grupo!".
O computador, sendo "preguiçoso" (e buscando eficiência), vai sugerir que o Grupo Azul faça amizade com o Grupo Vermelho que está mais perto (no centro da sala).

• Resultado: O Grupo Azul fica ainda mais popular e conectado. O Grupo Vermelho do centro ganha um amigo.
• O Problema: O Grupo Vermelho do canto isolado continua isolado! A regra antiga ignorou que eles estão "longe" de qualquer diversidade. Ela tratou todos os "amigos de fora" como iguais, sem perceber que para alguns, a diversidade está a 1 passo de distância, e para outros, está a 10 passos.

💡 A Solução: A "Justiça k-hop" (Justiça por Distância)

Os autores propõem uma nova regra chamada Justiça k-hop. Em vez de olhar apenas para o "amigo imediato", eles perguntam: "Qual é a diversidade de amigos que você tem a 1 passo de distância? E a 2 passos? E a 3 passos?"

• k-hop significa "passos".
  • 1-hop: Seus amigos diretos.
  • 2-hop: Os amigos dos seus amigos.
  • 3-hop: Os amigos dos amigos dos seus amigos.

A ideia é garantir que, não importa onde você esteja na festa (no centro ou no canto isolado), você tenha acesso a pessoas diferentes em cada "camada" de distância. Se você está isolado, o sistema deve garantir que, a 3 ou 4 passos de distância, você consiga "enxergar" e conectar com a diversidade, não apenas com pessoas do seu próprio grupo.

🛠️ Como eles consertam isso? (As Ferramentas)

O artigo apresenta duas formas de consertar o sistema:

1. O "Reformador de Festas" (Pré-processamento):
   Antes de começar a festa, eles mudam a estrutura da sala. Eles adicionam "pontes" ou corredores entre o canto isolado e o centro. Isso muda o mapa da festa para que, naturalmente, as pessoas consigam se encontrar mais facilmente, sem precisar forçar nada depois.

2. O "DJ Inteligente" (Pós-processamento):
   A festa já começou e o DJ (o algoritmo) já está sugerindo músicas (amizades). O "DJ Inteligente" olha para as sugestões e diz: "Ei, você sugeriu que o João (isolado) conheça a Maria (do mesmo grupo). Vamos mudar isso e sugerir a Ana (de outro grupo) que está a 3 passos de distância". Eles ajustam as recomendações finais para garantir que a diversidade chegue até quem está mais longe, sem estragar a qualidade da festa (a precisão das sugestões).

📊 O que eles descobriram? (Os Resultados)

Eles testaram isso em redes sociais reais (como blogs políticos e redes de amigos) e descobriram três coisas importantes:

1. O Vício da Estrutura: Os computadores tendem a repetir os preconceitos da estrutura da rede em todas as distâncias. Se a rede é segregada perto, ela tende a ser segregada longe também.
2. O Efeito Dominó: Se você conserta a injustiça em uma distância (ex: 1 passo), isso pode mudar a justiça em outras distâncias (ex: 3 passos). Às vezes melhora, às vezes piora. É preciso cuidado.
3. O Método Funciona: O método de "DJ Inteligente" (pós-processamento) conseguiu fazer as sugestões serem mais justas para todos os grupos, especialmente para os que estavam mais isolados, sem deixar de ser um bom sistema de recomendação.

🏁 Conclusão

Em resumo, este artigo diz: "Justiça não é apenas sobre quem você conhece agora, mas sobre quem você pode alcançar a longo prazo."

Para que uma rede social seja verdadeiramente justa, não basta misturar as pessoas que estão perto. É preciso garantir que as pessoas que estão "isoladas" no mapa também tenham acesso à diversidade, não importa quantos "passos" (k-hop) sejam necessários para chegar até elas. É como garantir que todos na festa, mesmo os que estão no canto mais escuro, consigam ouvir a música e dançar com todos os outros.

Resumo técnico

Título: k-hop Fairness: Abordando Disparidades em Previsão de Links em Grafos Além das Vizinhanças de Primeira Ordem

1. Problema e Motivação

A Previsão de Links (Link Prediction - LP) é fundamental em aplicações baseadas em grafos, como redes sociais e sistemas de recomendação. No entanto, grafos do mundo real frequentemente refletem vieses estruturais, sendo o homofilia (a tendência de nós com atributos semelhantes se conectarem) o mais notável.

• Limitação da Abordagem Atual: A maioria dos métodos de LP justa foca no paradigma de justiça diádica (dyadic fairness). Este paradigma busca equilibrar a probabilidade de conexões intra-grupo (mesmo atributo sensível) e inter-grupo (diferentes atributos sensíveis, como gênero ou raça).
• O Gap Identificado: A justiça diádica ignora a estrutura topológica subjacente. Ela trata todas as arestas inter-grupo como equivalentes, sem considerar a posição do nó no grafo. Isso pode levar a:
  1. Ocultação de Segregação: O modelo pode promover conexões inter-grupo apenas em áreas já bem conectadas e diversas, deixando partes segregadas do grafo ainda mais isoladas.
  2. Desigualdade Intra-grupo: Nós dentro do mesmo grupo sensível podem ocupar posições estruturais muito diferentes (ex: um nó central vs. um nó periférico isolado). A justiça diádica não distingue entre adicionar uma aresta para um nó já bem conectado versus um nó isolado.

O artigo propõe que a justiça deve ser avaliada com base na diversidade das previsões dentro das vizinhanças de k-hops dos nós, e não apenas no tipo de aresta.

2. Metodologia e Definições

Os autores introduzem o conceito de Justiça k-hop, que avalia disparidades condicionadas à distância entre os nós no grafo.

2.1 Definições Fundamentais

• Exposição de Atributo k-hop ($f^{(k)}_s(v)$): Mede a probabilidade de um nó $v$ se conectar a nós do grupo sensível $s$ que estão exatamente a $k$ hops de distância.
• Exposição de Grupo k-hop ($\phi^{(k)}_{s \to s'}$): Agregação da exposição local para todos os nós de um grupo $s$, representando como o grupo $s$ acessa o grupo $s'$ na distância $k$.
• Gap de Justiça k-hop ($NF^{(k)}$): Define-se como a diferença máxima na exposição de um grupo de origem para diferentes grupos de destino na distância $k$. Um valor baixo indica acesso equilibrado.
• Viés Estrutural k-hop ($NB^{(k)}$): Mede a diversidade nos vizinhos reais de $k$-hops do grafo original (substituindo o preditor pela estrutura do grafo).

2.2 Decomposição da Justiça Diádica

O artigo demonstra matematicamente que a métrica padrão de justiça diádica ($\Delta DP$) é uma agregação ponderada de todas as distâncias $k$. Isso mascara quais distâncias específicas estão causando o viés, dificultando a mitigação direcionada.

2.3 Estratégias de Mitigação

Os autores propõem métodos de pré-processamento e pós-processamento que são agnósticos ao modelo:

1. Pós-processamento (Ajuste de Previsões):

   • Modifica as probabilidades de arestas previstas pelo modelo original, restringindo as alterações apenas a pares de nós que estão exatamente a $k$ hops de distância no grafo de treinamento.
   • Otimiza uma função de perda que minimiza o $NF^{(k)}$ enquanto penaliza grandes desvios das previsões originais (fidelidade), controlada por um parâmetro $\alpha$.
   • Vantagem: Garante independência entre as justícias em diferentes hops ($k$); otimizar para $k=2$ não degrada a justiça em $k=3$.

2. Pré-processamento (Reconfiguração do Grafo):

   • Adiciona ou remove arestas no grafo original para reduzir o viés estrutural $NB^{(k)}$.
   • Utiliza uma função de perda que equilibra a redução do viés estrutural com a fidelidade à estrutura original do grafo.
   • Desafio: A reconfiguração altera a estrutura de hops, exigindo métodos diferenciáveis (como potências da matriz de adjacência) para calcular os vizinhos durante a otimização.

3. Contribuições Principais

1. Novo Paradigma de Justiça: Introdução da Justiça k-hop, que permite uma avaliação mais granular e estrutural das disparidades, superando as limitações da justiça diádica ao focar na diversidade dentro das vizinhanças de distância fixa.
2. Métricas e Algoritmos: Definição formal de métricas de viés estrutural ($NB^{(k)}$) e justiça preditiva ($NF^{(k)}$), juntamente com algoritmos eficientes para seu cálculo e mitigação (pré e pós-processamento).
3. Análise de Interdependência: Demonstração experimental de que os vieses estruturais em diferentes hops são interdependentes. Mitigar o viés em um hop específico pode afetar (positiva ou negativamente) os vieses em outros hops.
4. Validação Empírica: Extensa avaliação em múltiplos grafos reais e sintéticos, mostrando que o método de pós-processamento proposto alcança melhores compromissos entre desempenho (AUC) e justiça k-hop comparado a baselines de estado da arte.

4. Resultados Experimentais

Os experimentos foram realizados em conjuntos de dados como Polblogs, Facebook, Pokec, Citeseer e um grafo sintético, utilizando modelos como Node2Vec, GCN e GraphSAGE.

• RQ1 (Relação entre Viés e Justiça): Os modelos padrão tendem a reproduzir os vieses estruturais do grafo em diferentes hops. Frequentemente, os hops com maior viés estrutural ($NB^{(k)}$) correspondem aos hops com menor justiça preditiva ($NF^{(k)}$). A justiça diádica falha em capturar essas nuances específicas por hop.
• RQ2 (Interdependência): A mitigação de viés em um hop específico através de adição de arestas (pré-processamento) tem efeitos complexos e interdependentes em outros hops. Por exemplo, reduzir o viés em $k=2$ pode aumentar o viés em $k=3$, indicando que estratégias de mitigação devem ser específicas para cada hop e dataset.
• RQ3 (Eficácia do Pós-processamento):
  • O método proposto reduz consistentemente o $NF^{(k)}$ nos hops alvo.
  • Compromisso Desempenho-Justiça:
    • Em $k=1$, a mitigação não prejudica o AUC (desempenho), pois as arestas de treinamento são modificadas, mas não afetam as arestas de teste (que geralmente são de maior distância ou não observadas).
    • Em $k$ intermediários (ex: $k=2$), há uma degradação maior no AUC devido à alta sobreposição entre pares de nós de treinamento e teste (agrupamento local).
    • Em $k$ maiores, a degradação é mínima ou inexistente, pois as arestas de teste raramente estão envolvidas na otimização de hops distantes.
  • O método supera as baselines de justiça (como FairWalk, CrossWalk, DeBayes) em termos de justiça específica por hop, mantendo um desempenho competitivo.

5. Significado e Conclusão

Este trabalho representa um avanço significativo na área de IA Justa em Grafos. Ao deslocar o foco da justiça baseada apenas em atributos de arestas (diádica) para a justiça baseada na estrutura de vizinhança (k-hop), os autores oferecem uma ferramenta mais precisa para diagnosticar e corrigir desigualdades algorítmicas.

• Impacto Prático: A abordagem permite que sistemas de recomendação (como LinkedIn ou Facebook) garantam que usuários de grupos minoritários ou segregados tenham acesso a informações e conexões em diferentes níveis de proximidade, e não apenas em conexões imediatas ou em áreas já privilegiadas.
• Limitações: O método depende do cálculo de distâncias exatas (caminhos mais curtos), o que pode ser custoso em grafos massivos, embora o uso de representações esparsas mitigue isso. Além disso, o foco é puramente estrutural, não considerando características (features) dos nós, o que sugere uma direção futura para pesquisas híbridas.

Em resumo, o artigo estabelece que a justiça em grafos não pode ser tratada como um problema monolítico, mas deve ser analisada e mitigada em múltiplas escalas de distância topológica para evitar a perpetuação de desigualdades estruturais.