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

Questo lavoro propone la "k-hop fairness", un nuovo concetto di equità strutturale per la previsione dei link che supera i limiti delle approcci basati sulla sola equità diadica valutando e mitigando le disparità tra gruppi sensibili a diverse distanze di vicinato nel grafo.

L'essenziale

🌐 Il Problema: La "Bolla" dei Consigli Amichevoli

Immagina che i social network siano come una gigantesca città fatta di persone (i nodi) e amicizie (i collegamenti). Gli algoritmi di Link Prediction sono come dei "matchmaker" o dei "consulenti di amicizia" molto intelligenti. Il loro lavoro è guardare la città e dirti: "Ehi, tu e Mario potreste andare d'accordo, vi consiglio di diventare amici!".

Il problema è che questi consulenti sono spesso troppo bravi a vedere ciò che è già lì. Se nella città le persone tendono ad amare solo chi è uguale a loro (un fenomeno chiamato omofilia, come se tutti i "gialli" si mettessero insieme e tutti i "rossi" facessero lo stesso), il consulente continuerà a suggerire amicizie tra "gialli" e "gialli".

Finora, gli esperti hanno cercato di risolvere il problema con una regola semplice: "Fai amicizia anche con chi è diverso da te". Questo è il concetto di Fairness Dyadica (giustizia a due). Se un "giallo" deve avere un amico "rosso", il consulente lo forza.

Ma c'è un trucco: Questa regola guarda solo la singola coppia. Immagina un quartiere ricco e isolato dove tutti i "gialli" sono già amici tra loro e hanno già molti amici "rossi". Il consulente, seguendo la vecchia regola, continuerà a farli amicizzare tra loro perché è facile. Nel frattempo, ignora completamente un altro quartiere povero e isolato dove i "gialli" non hanno nessuno amico "rosso" e sono completamente tagliati fuori. La vecchia regola dice: "Bene, il gruppo giallo ha amici rossi, siamo equi!", ma in realtà ha creato una nuova ingiustizia: ha favorito chi era già ben collegato e ha lasciato indietro chi era isolato.

💡 La Soluzione: La "Giustizia a Passi" (k-hop)

Gli autori di questo paper dicono: "Basta guardare solo il vicinato immediato! Dobbiamo guardare quanto è lontano qualcuno".

Hanno introdotto il concetto di k-hop Fairness.
Immagina di lanciare un sasso in uno stagno. Le onde si espandono a cerchi concentrici:

• 1-hop (1 cerchio): I tuoi amici diretti.
• 2-hop (2 cerchi): Gli amici dei tuoi amici.
• 3-hop (3 cerchi): Gli amici degli amici dei tuoi amici.

La loro idea è: La giustizia deve essere misurata a ogni cerchio di distanza.
Non basta che tu abbia un amico diverso (1-hop). È ingiusto se, per arrivare a un amico diverso a 3 passi di distanza, devi fare un giro lunghissimo mentre a qualcun altro basta un passo.

L'obiettivo è assicurarsi che, a qualsiasi distanza (k), le persone di un gruppo abbiano accesso alle stesse opportunità di connessione con altri gruppi, indipendentemente da quanto sono isolate nel loro quartiere.

🛠️ Come lo fanno? (I Due Strumenti)

Gli autori hanno creato due modi per sistemare la città:

1. Ristrutturare la Città (Pre-processing):
   Prima ancora che il consulente inizi a lavorare, prendiamo la mappa della città e aggiungiamo o spostiamo dei ponti (collegamenti) per rendere il quartiere isolato più accessibile.

   • Metafora: È come costruire un nuovo ponte tra il quartiere isolato e il centro città prima che le persone decidano dove andare.

2. Correggere i Consigli (Post-processing):
   Lasciamo che il consulente faccia il suo lavoro, ma poi controlliamo i suoi suggerimenti. Se il consulente dice "Fai amicizia con Mario" (che è vicino), ma ignora "Luigi" (che è lontano ma ha bisogno di un ponte), noi interveniamo.

   • Metafora: È come un supervisore che prende la lista di consigli del matchmaker e dice: "Ok, questo consiglio va bene, ma quel consiglio lì lo cambiamo per aiutare Luigi, anche se è più lontano".

📊 Cosa hanno scoperto? (I Risultati)

Hanno fatto degli esperimenti su città reali (come Facebook, blog politici, ecc.) e hanno scoperto tre cose importanti:

1. Il pregiudizio è ovunque: Gli algoritmi attuali non sono ingiusti solo con gli amici diretti, ma riproducono le disuguaglianze anche a 2, 3 o 4 passi di distanza.
2. Tutto è collegato: Se provi a sistemare la giustizia solo per gli amici diretti (1-hop), potresti peggiorare la situazione per gli amici degli amici (2-hop). È come se spostassi un mobile in una stanza e, per sbaglio, bloccassi la porta della stanza accanto. Bisogna guardare l'intero edificio.
3. Il loro metodo funziona: Il loro sistema di "correzione dei consigli" (post-processing) riesce a rendere le raccomandazioni più eque a tutte le distanze, senza rovinare troppo la qualità dei consigli (non si perde la capacità di prevedere amicizie vere).

🎯 In Sintesi

Pensa a questo paper come a un nuovo modo di guardare la giustizia sociale nelle reti.

• Vecchio modo: "Assicurati che ogni persona abbia almeno un amico diverso." (Ma ignora chi è isolato).
• Nuovo modo (k-hop): "Assicurati che ogni persona, sia che viva al centro o in periferia, abbia la stessa possibilità di raggiungere persone diverse, sia a un passo di distanza che a tre passi."

È un approccio più attento, che non si ferma alla superficie, ma guarda la struttura profonda della città per garantire che nessuno rimanga davvero solo.

Sommario tecnico

1. Il Problema

La previsione dei link (Link Prediction - LP) è fondamentale nelle applicazioni basate su grafi, come i sistemi di raccomandazione sociale. Tuttavia, i grafi reali spesso riflettono bias strutturali, in particolare l'omofilia (la tendenza dei nodi con attributi simili a connettersi). Sebbene l'omofilia possa migliorare le prestazioni predittive, rischia di rafforzare le disparità sociali esistenti (es. "bolle informative" o "soffitto di cristallo").

Le attuali metodologie di LP equo si basano sul paradigma della fairness diadica (dyadic fairness), che mira a bilanciare le connessioni intra-gruppo e inter-gruppo (es. tra uomini e donne). Tuttavia, questo approccio presenta due limiti critici:

1. Ignora la struttura sottostante: Tratta tutte le connessioni inter-gruppo come equivalenti, senza considerare la posizione del nodo nel grafo.
2. Nasconde le disparità interne: Promuovendo ciecamente le connessioni inter-gruppo, si rischia di favorire i nodi già ben connessi all'interno di gruppi diversificati, lasciando indietro i nodi isolati o segregati all'interno dello stesso gruppo sensibile.

Il paper evidenzia che la fairness deve essere valutata considerando la diversità delle previsioni all'interno delle vicinanze k-hop dei nodi, non solo sulla base del tipo di bordo (link).

2. Metodologia e Contributi Chiave

Gli autori propongono un nuovo quadro concettuale e algoritmico per misurare e mitigare le ingiustizie a diverse distanze nel grafo.

A. Definizione di k-hop Fairness

Il lavoro introduce una nozione strutturale di fairness basata sulla distanza $k$ tra i nodi.

• Esposizione al nodo k-hop ($f^{(k)}_s(v)$): Misura quanto è probabile che un nodo $v$ formi connessioni con nodi aventi un attributo sensibile $s$ esattamente a distanza $k$.
• Esposizione di gruppo k-hop ($\phi^{(k)}_{s \to s'}$): Aggrega l'esposizione locale su tutti i nodi di un gruppo sensibile $s$, calcolando la proporzione media di accesso ai nodi del gruppo $s'$ a distanza $k$.
• Gap di Fairness k-hop ($NF^{(k)}$): Definisce la disparità come la differenza massima nell'esposizione tra diversi gruppi sensibili target per uno stesso gruppo sorgente a una distanza $k$ fissa.
• Bias Strutturale k-hop ($NB^{(k)}$): Una metrica puramente strutturale che misura la diversità degli attributi sensibili nelle vicinanze k-hop reali del grafo, senza considerare le previsioni del modello.

B. Strategie di Mitigazione

Il paper propone metodi sia pre-processing che post-processing per ridurre questi bias:

1. Pre-processing (Ri-wiring del grafo): Modifica la struttura del grafo (aggiunta di bordi) per minimizzare il bias strutturale $NB^{(k)}$. Viene definita una funzione di perdita che bilancia la riduzione del bias con la fedeltà alla struttura originale.
2. Post-processing (Regolazione delle previsioni): Agisce direttamente sulla matrice di probabilità delle previsioni $P$. Permette di modificare i punteggi delle previsioni solo per le coppie di nodi che sono esattamente a distanza $k$, minimizzando una funzione di perdita che include il termine di fairness $NF^{(k)}$ e un termine di regolarizzazione per preservare le prestazioni originali.

C. Complessità Computazionale

Gli autori dimostrano che il calcolo delle metriche $NF^{(k)}$ e $NB^{(k)}$ ha una complessità di $O(n^2)$ (sotto l'assunzione di sparsità), rendendo l'approccio scalabile. Per il pre-processing, la complessità per iterazione è $O(kn^2)$.

3. Risultati Sperimentali

Gli esperimenti sono stati condotti su diversi dataset reali (Polblogs, Facebook, Pokec, Citeseer) e su un grafo sintetico, utilizzando modelli standard (Node2Vec, GCN, GraphSAGE) e baselines equi esistenti (FairWalk, CrossWalk, ecc.).

Le domande di ricerca (RQ) e i risultati principali sono:

• RQ1: Relazione tra Bias Strutturale e Fairness:

  • È stata osservata una forte correlazione tra il bias strutturale $NB^{(k)}$ e la fairness predittiva $NF^{(k)}$. I hop con il maggiore bias strutturale corrispondono a quelli con la peggiore fairness.
  • Il bias non è uniforme: spesso è più alto a 1-hop, ma esistono bias significativi anche a hop superiori (es. 4-hop su Polblogs), dimostrando che l'aggregazione globale nasconde problemi specifici.

• RQ2: Interdipendenza tra Hop:

  • La mitigazione del bias a un hop specifico (tramite pre-processing) ha effetti a catena sugli altri hop. Le correlazioni possono essere rinforzanti o compensatorie. Ad esempio, ridurre il bias a 2-hop su Polblogs riduce il bias a 1-hop ma aumenta quello a 3-hop. Questo suggerisce che le strategie di mitigazione devono essere specifiche per il dataset e per l'hop target.

• RQ3: Efficacia del Post-processing:

  • Il metodo di post-processing proposto supera le baselines esistenti nel ridurre il target $NF^{(k)}$ specifico.
  • Trade-off Prestazioni-Fairness:
    • A k=1, la mitigazione non comporta perdita di prestazioni (AUC), poiché le modifiche riguardano solo i bordi di training.
    • A k=2, si osserva un calo delle prestazioni perché le vicinanze a 2-hop si sovrappongono fortemente con i bordi di test (a causa dell'alto clustering dei grafi reali).
    • A k>2, le prestazioni sono generalmente preservate o leggermente migliorate, poiché le modifiche non influenzano direttamente i bordi di test.
  • A differenza del pre-processing, il post-processing garantisce indipendenza tra i bias predittivi a diversi hop: ottimizzare $NF^{(k)}$ non peggiora la fairness a $k' \neq k$.

4. Significato e Implicazioni

Questo lavoro rappresenta un passo avanti significativo nella ricerca sulla fairness nei grafi:

1. Superamento del paradigma diadico: Sposta il focus dalla semplice equità tra coppie di nodi all'equità strutturale delle vicinanze dei nodi, riconoscendo che non tutti i nodi all'interno di un gruppo sensibile hanno la stessa posizione o accesso alle informazioni.
2. Granularità temporale/spaziale: Introduce la possibilità di analizzare e correggere le ingiustizie a diverse distanze topologiche, offrendo un controllo più fine rispetto alle metriche aggregate.
3. Applicabilità Industriale: Il concetto di suggerimenti basati sulla prossimità (es. "persone che potresti conoscere" a 2 o 3 hop su LinkedIn) rende questo approccio direttamente rilevante per le applicazioni reali.
4. Strumenti Pratici: Fornisce metriche computabili e strategie di mitigazione (pre/post-processing) che sono agnostiche rispetto al modello, rendendole facilmente integrabili in pipeline esistenti.

In conclusione, il paper dimostra che per garantire una vera equità nei sistemi di raccomandazione basati su grafi, è necessario considerare la struttura topologica a più livelli (k-hop) e non limitarsi a bilanciare le connessioni dirette.