Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Problematica
La parità nella predizione dei collegamenti mira a ridurre le disparità nelle probabilità di collegamento predette tra i gruppi. Nelle raccomandazioni di reti sociali, i predittori di collegamenti determinano la visibilità e la connettività, potendo indurre cicli di feedback che rinforzano le connessioni intra-gruppo e svantaggiano i gruppi minoritari. Un problema critico sorge quando questi modelli vengono addestrati su dati storici di grafi, che possono ereditare e amplificare i pregiudizi strutturali esistenti.

Mentre la parità demografica ($\Delta$DP) è una metrica di equità comune nella predizione dei collegamenti classificati (ranked), essa aggrega i collegamenti in categorie grossolane (stesso gruppo vs. gruppo differente). Mattos et al. (2025) sostengono che questa visione diadica non riesce a rilevare il bias di esposizione perché ignora la posizione specifica dei collegamenti all'interno della classifica. Di conseguenza, la parità aggregata può essere rispettata anche quando i collegamenti di specifici sottogruppi (ad esempio, collegamenti femmina-femmina) sono sistematicamente posizionati più in basso rispetto ad altri, oscurando le disparità intra-gruppo.

Metodologia
Questo studio è una riproduzione ed estensione di Mattos et al. (2025). Gli autori formalizzano la predizione dei collegamenti come un problema di classificazione (ranking) in cui gli attributi sensibili definiscono i tipi di coppie di sottogruppi (ad esempio, $E_{0-0}, E_{1-1}, E_{0-1}$).

1. Metriche:

   • Parità Demografica ($\Delta$DP): Misura la differenza nei punteggi medi previsti tra i collegamenti intra-gruppo ($E_{intra}$) e inter-gruppo ($E_{inter}$). È invariante rispetto alla permutazione dell'ordine di classificazione.
   • Divergenza KL Normalizzata Discata (NDKL): Una metrica consapevole del rango (rank-aware) e non diadica che tratta distintamente tutti i tipi di coppie di sottogruppi. Accumula la divergenza di Kullback-Leibler tra la distribuzione di esposizione prevista e una distribuzione target attraverso i prefissi della classifica, pesata da un fattore di decadimento logaritmico per penalizzare maggiormente le deviazioni ai ranghi più alti.
   • Utilità: Misurata tramite Precision@1000 e NDCG@1000.

2. MORAL (Multi-Output Ranking Aggregation for Link Fairness):
   Un algoritmo di post-processing che riclassifica gli output di predittori di collegamenti disaccoppiati (un modello addestrato per ogni tipo di coppia di sottogruppi). MORAL impiega una strategia di aggregazione greedy guidata dalla KL: ad ogni posizione di rango, seleziona il miglior elemento rimanente da ciascun pool di coppie di sottogruppi che minimizza la divergenza KL tra la distribuzione di esposizione aggiornata e una distribuzione target $\pi$ (derivata dal grafo originale).

3. Configurazione Sperimentale:

   • Dataset: Sei dataset di reti sociali (Credit, Facebook, German, NBA, Pokec-n, Pokec-z) e due dataset aggiuntivi (Global Airport Routes Network, Chameleon) per la verifica della topologia.
   • Riproduzione: Gli autori hanno riprodotto l'impostazione principale utilizzando encoder GCN e decoder dot-product, correggendo le incongruenze trovate nel codice originale riguardanti il calcolo della distribuzione target e l'aggregazione KL.
   • Estensioni:
     • Stress-Test di Omofilia Asimmetrica: Grafi sintetici generati tramite il modello Directed Preferential Attachment with Homophily (DPAH) per testare le prestazioni sotto diversi gradi di connettività intra-gruppo.
     • Robustezza della Metrica: Valutazione tramite Attention-Weighted Rank Fairness (AWRF) e NDCG per garantire che i risultati non siano specifici del meccanismo di aggregazione NDKL.
     • Attributi Categorici: Estensione del framework a attributi sensibili con cardinalità $m > 2$.

Contributi Chiave

1. Riproduzione e Correzione: Lo studio riproduce con successo le affermazioni principali di Mattos et al. (2025) rilasciando al contempo un'implementazione corretta e riproducibile. Identifica e corregge le incongruenze nel codice originale riguardanti il calcolo della distribuzione target e la normalizzazione della divergenza KL.
2. Validazione delle Affermazioni:
   • C1: Conferma che $\Delta$DP può indicare una parità aggregata anche quando esistono significative disparità di esposizione all'interno di specifiche coppie di sottogruppi (ad esempio, all'interno di $E_{intra}$).
   • C2: Dimostra che NDKL rileva efficacemente queste disparità nascoste grazie alla sua natura rank-aware e non diadica.
   • C3: Mostra che MORAL mitiga costantemente i bias di esposizione (basso NDKL) mantenendo al contempo un'utilità competitiva (Precision/NDCG) attraverso diversi dataset.
3. Analisi di Robustezza:
   • Lo studio estende il lavoro originale testando l'omofilia asimmetrica, mostrando che MORAL opera in modo robusto, sebbene le disparità di esposizione siano più pronunciate a livelli intermedi di omofilia assoluta.
   • Valida la generalizzabilità del framework ad attributi sensibili categorici (fino a $m=10$) e diverse topologie di grafi (Core-periphery, Heterophilic).
   • Conferma che i miglioramenti di equità non sono semplici artefatti dell'ottimizzazione di NDKL, poiché tendenze simili sono osservate con AWRF.

Risultati

• Equità vs. Utilità: MORAL raggiunge una NDKL prossima allo zero in tutti i dataset, superando significativamente i baseline (FairAdj, FairWalk, DetConstSort). Questa riduzione del bias di esposizione avviene con una perdita di utilità minima; MORAL mantiene un'alta Precision@1000, spesso eguagliando o superando i baseline.
• Sensibilità della Metrica: $\Delta$DP rimane ampiamente invariante rispetto ai cambiamenti nell'allocazione dell'esposizione all'interno dei gruppi, mentre NDKL e AWRF sono altamente sensibili a tali cambiamenti.
• Omofilia: Nei contesti sintetici, le metriche basate sull'esposizione raggiungono il picco a un'omofilia assoluta intermedia ($\approx 0.6$), dove i collegamenti intra-gruppo sono frequenti ma i ranghi rimangono diversificati. Ad alta omofilia, l'utilità scende leggermente poiché i predittori disaccoppiati ricevono segnali di addestramento più deboli.
• Attributi Categorici: All'aumentare del numero di tipi di coppie di sottogruppi ($T$), NDKL e AWRF degradano monotonicamente, indicando che l'allineamento dell'esposizione con la distribuzione target diventa progressivamente più difficile. Tuttavia, l'utilità rimane elevata, suggerendo che i collegamenti ai ranghi superiori rimangono accurati anche quando i rangi inferiori diventano meno stabili.
• Ablazione: Un confronto tra i punteggi pre-rerank e post-rerank mostra che il passaggio di aggregazione greedy KL è responsabile di una sostanziale riduzione del bias di esposizione (riduzione del 66.9% in NDKL, 92.6% in AWRF).

Significatività e Affermazioni
Il paper conclude che la parità demografica diadica è insufficiente per la predizione dei collegamenti classificati perché può oscurare le disparità di esposizione tra le coppie di sottogruppi. Gli autori sostengono che quando gli output della predizione dei collegamenti vengono consumati come classifiche, l'esposizione deve essere la valuta rilevante dell'equità.

Lo studio supporta l'uso di metriche basate sull'esposizione e consapevoli del rango (come NDKL e AWRF) e del metodo di post-processing MORAL come strumenti efficaci per debiasare le predizioni dei collegamenti classificati. Evidenzia un compromesso pratico: sebbene MORAL sia scalabile a setting con alta cardinalità, il costo computazionale e la difficoltà di allineamento dell'esposizione aumentano con il numero di tipi di coppie di sottogruppi. Gli autori sottolineano che preservare la distribuzione del grafo originale ($\pi$) è una scelta di design per prevenire l'amplificazione algorica del bias, piuttosto che una rivendicazione che la distribuzione originale sia intrinsecamente "equa".