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

Cet article propose une nouvelle notion de « k-hop fairness » pour la prédiction de liens, qui évalue et atténue les disparités structurelles au-delà des voisinages immédiats en dépassant les limites de l'équité dyadique grâce à des stratégies de mitigation pré- et post-traitement.

L'essentiel

🌍 Le Problème : La "Bulle" des Amis

Imaginez que vous êtes sur un réseau social géant, comme Facebook ou LinkedIn. Vous cherchez à faire de nouvelles connaissances. L'algorithme qui vous suggère des amis fonctionne un peu comme un météorologue : il regarde votre historique et vous dit : "Tu as 90 % de chances d'aimer cette personne".

Le problème, c'est que dans la vraie vie, nous avons tendance à nous lier d'amitié avec des gens qui nous ressemblent (même origine, même genre, mêmes opinions). C'est ce qu'on appelle l'homophilie.

Si l'algorithme se contente de suivre cette tendance, il crée une bulle de filtre. Il vous propose uniquement des gens qui vous ressemblent déjà. Résultat ? Les groupes différents ne se rencontrent jamais, et les inégalités sociales se renforcent. C'est comme si un restaurant ne servait que des plats que vous avez déjà mangés, vous empêchant de découvrir de nouvelles saveurs.

🛑 La Solution Actuelle (et ses limites)

Jusqu'à présent, les chercheurs ont essayé de corriger cela avec une règle simple appelée "Équité Dyadique".

• L'idée : "Pour chaque personne du groupe A, on doit lui proposer autant d'amis du groupe B que de personnes du groupe A."
• La métaphore : C'est comme un serveur qui s'assure que chaque table reçoit le même nombre de plats.

Mais il y a un gros défaut : Cette règle ne regarde que qui est assis à la table, pas où se trouve la table dans le restaurant.
Imaginez un restaurant où certaines tables sont au centre, très proches du chef et des autres tables, tandis que d'autres sont cachées dans un coin sombre, loin de tout le monde.
Si le serveur donne un plat à tout le monde de manière égale, il ignore le fait que les gens du coin sombre n'ont toujours pas accès à l'information ou aux opportunités. L'algorithme actuel traite tout le monde de la même façon, même si leur position dans le réseau est très différente.

💡 La Nouvelle Idée : La "Justice à k-sauts" (k-hop Fairness)

Les auteurs de ce papier proposent une nouvelle façon de voir les choses : la "Justice à k-sauts".

Imaginez que le réseau social est une ville.

• 1 saut (k=1) : Ce sont vos voisins immédiats (vos amis directs).
• 2 sauts (k=2) : Ce sont les amis de vos amis.
• 3 sauts (k=3) : Ce sont les amis des amis de vos amis.

La nouvelle méthode dit : "Ce n'est pas juste de donner des amis à tout le monde. Il faut s'assurer que chaque personne, où qu'elle soit dans la ville, ait accès à des gens différents, que ce soit à 1 saut, à 2 sauts ou à 3 sauts."

C'est comme vérifier que non seulement votre rue est diverse, mais aussi que les rues voisines, et celles d'après, le sont aussi. Cela permet de détecter des inégalités cachées que l'ancienne méthode ne voyait pas. Par exemple, un groupe de personnes peut être bien connecté à 1 saut, mais totalement isolé à 3 sauts. La nouvelle méthode repère ce problème.

🛠️ Comment ils réparent le système ?

Les chercheurs ont créé deux outils pour corriger ces injustices, un peu comme des architectes qui réaménagent la ville :

1. Avant la construction (Pré-traitement) : Ils modifient la carte de la ville (le graphe) en ajoutant des ponts ou des routes entre des quartiers qui ne se parlaient pas, pour équilibrer la structure même du réseau.
2. Après la construction (Post-traitement) : C'est leur méthode préférée. L'algorithme fait ses prédictions comme d'habitude, puis un "régleur" intervient. Il regarde les suggestions faites à distance (par exemple, à 2 ou 3 sauts) et ajuste légèrement les recommandations pour s'assurer que les groupes isolés reçoivent enfin des suggestions de personnes différentes, sans trop gâcher la qualité des prédictions.

📊 Ce qu'ils ont découvert (Les Résultats)

En testant leur méthode sur de vrais réseaux (blogs politiques, Facebook, réseaux d'auteurs), ils ont vu trois choses importantes :

1. Les biais sont partout : Les modèles actuels reproduisent les inégalités non seulement entre amis directs, mais aussi à plusieurs "sauts" de distance.
2. Tout est lié : Si vous essayez de réparer le réseau à 1 saut, cela change souvent la situation à 2 ou 3 sauts. C'est comme tirer une ficelle : tout le tissu bouge. Il faut donc être très précis.
3. Leur méthode fonctionne : Leur outil de "réglage après coup" réussit à rendre le réseau plus juste (plus de diversité dans les suggestions) sans trop sacrifier la qualité des prédictions. C'est un bon compromis.

🎯 En résumé

Ce papier nous dit que pour être vraiment juste, il ne suffit pas de mélanger les gens de manière globale. Il faut regarder la distance entre eux.

C'est comme organiser une grande fête : ce n'est pas juste de mettre tout le monde dans la même pièce. Il faut s'assurer que les gens qui sont dans le coin le plus reculé de la salle ont aussi la possibilité de discuter avec les gens du groupe principal, et ce, à différentes distances. C'est une façon plus fine et plus humaine de concevoir l'intelligence artificielle.

Résumé technique

1. Problématique et Contexte

La prédiction de liens (Link Prediction - LP) est fondamentale dans les applications basées sur les graphes, notamment pour les recommandations sociales. Cependant, les graphes réels reflètent souvent des biais structurels, principalement l'homophilie (la tendance des nœuds similaires à se connecter). Bien que cette propriété puisse améliorer la performance prédictive, elle risque d'exacerber les disparités sociales existantes (ex: bulles de filtres, plafond de verre).

Les méthodes actuelles de "LP équitable" (Fair LP) se concentrent principalement sur la équité dyadique (dyadic fairness). Ce paradigme vise à équilibrer les prédictions entre les liens intra-groupe et inter-groupe en se basant sur les attributs sensibles des nœuds connectés (ex: genre, race).

Limites de l'approche dyadique :

• Elle ignore la structure sous-jacente du graphe au-delà de la connexion directe.
• Elle traite tous les liens inter-groupes comme équivalents, sans distinguer si les nœuds concernés sont déjà bien connectés à des groupes diversifiés ou s'ils sont isolés.
• Elle peut masquer des phénomènes de ségrégation à des distances plus grandes (k-hops) et renforcer les disparités au sein même des groupes sensibles en favorisant les nœuds déjà centraux.

2. Contribution Principale : L'Équité k-hop

Les auteurs proposent une nouvelle notion structurelle d'équité : l'équité k-hop. Au lieu de se limiter aux voisins directs (1-hop), cette approche évalue les disparités conditionnées à la distance topologique $k$ entre les nœuds.

Définitions Clés

• Exposition k-hop ($f^{(k)}_s(v)$) : Probabilité qu'un nœud $v$ soit connecté à un nœud du groupe sensible $s$ à exactement $k$ sauts de distance.
• Exposition de groupe ($\phi^{(k)}_{s \to s'}$) : Moyenne de l'exposition locale pour tous les nœuds d'un groupe $s$ vers un groupe $s'$ à distance $k$.
• Écart d'équité k-hop ($NF^{(k)}$) : Mesure le déséquilibre maximal d'exposition entre différents groupes cibles pour un groupe source donné à une distance $k$.
• Biais structurel k-hop ($NB^{(k)}$) : Mesure le biais inhérent à la structure du graphe original (sans prédiction) à distance $k$.

Cette approche permet de détecter des biais qui sont invisibles pour les métriques dyadiques classiques (comme la Parité Démographique $\Delta DP$), car elle ne moyenne pas les effets sur toutes les distances, mais les analyse spécifiquement pour chaque $k$.

3. Méthodologie

L'article propose des stratégies de pré- et post-traitement pour quantifier et atténuer ces biais.

A. Mesure des Biais

• Calcul de $NB^{(k)}$ et $NF^{(k)}$ : Les auteurs utilisent des matrices indicatrices de distance $k$ ($\tilde{A}^{(k)}$) pour isoler les paires de nœuds exactement à $k$ sauts.
• Complexité : Le calcul est effectué en $O(n^2)$ pour les graphes clairsemés, rendant la méthode scalable. Une approche par BFS (Breadth-First Search) ou par puissances de matrices est utilisée selon le besoin de différentiabilité.

B. Stratégies d'Atténuation

1. Pré-traitement (Re-wiring du graphe) :

   • Modification de la matrice d'adjacence $A$ pour réduire le biais structurel $NB^{(k)}$.
   • Minimisation d'une fonction de perte combinant le biais structurel et une fidélité au graphe original ($\ell^{(k)}_{pre} = NB^{(k)}(A') + \alpha \|A' - A\|_F$).
   • Résultat clé : La réduction du biais à un hop spécifique $k$ a des effets interdépendants sur les autres hops (certains biais diminuent, d'autres augmentent), nécessitant des stratégies spécifiques aux données.

2. Post-traitement (Ajustement des prédictions) :

   • Ajustement direct des probabilités de prédiction $P$ pour les paires de nœuds exactement à distance $k$.
   • Minimisation d'une perte $\ell^{(k)}_{post} = NF^{(k)}(P') + \alpha \|U \odot \tilde{A}^{(k)}\|_F$, où $U$ est la matrice de modification.
   • Avantage majeur : Contrairement au pré-traitement, le post-traitement garantit l'indépendance entre les biais à différents hops. Optimiser l'équité à $k=2$ ne dégrade pas nécessairement l'équité à $k=3$.

4. Résultats Expérimentaux

Les expériences ont été menées sur plusieurs jeux de données réels (Polblogs, Facebook, Pokec, Citeseer) et synthétiques, utilisant des modèles standards (Node2Vec, GCN, GraphSAGE) et des baselines équitables existantes.

RQ1 : Relation entre biais structurel et équité prédictive

• Il existe une forte corrélation : les hops où le biais structurel $NB^{(k)}$ est élevé sont ceux où l'équité prédictive $NF^{(k)}$ est la plus faible.
• Les modèles standards reproduisent les biais structurels à différents niveaux de $k$, pas seulement au 1-hop.
• Les métriques dyadiques échouent à capturer ces disparités spécifiques à chaque distance.

RQ2 : Interdépendance des hops (Pré-traitement)

• La réduction du biais à un hop donné (via l'ajout d'arêtes) se propage aux autres hops de manière complexe (renforcement ou compensation).
• Exemple : Sur Polblogs, réduire le biais à 2-hops diminue le biais à 1-hop mais l'augmente à 3-hops. Cela montre la nécessité d'une approche ciblée.

RQ3 : Efficacité du Post-traitement

• La méthode de post-traitement proposée atteint des compromis performance-équité (AUC vs NF) supérieurs aux baselines existantes.
• Cas $k=1$ : Réduction significative du biais sans perte de performance (AUC), car les modifications ne touchent pas les arêtes de test.
• Cas $k > 1$ : La réduction du biais entraîne parfois une baisse de performance, mais la méthode reste supérieure aux approches dyadiques.
• Indépendance : Le post-traitement permet d'optimiser l'équité sur un hop spécifique sans détériorer l'équité sur les autres hops, offrant un contrôle modulaire.

5. Signification et Conclusion

Signification :
Ce travail remet en cause le paradigme dominant de l'équité dyadique dans les graphes. Il démontre que l'équité ne peut pas être évaluée uniquement par la nature des liens (intra/inter-groupe), mais doit intégrer la topologie locale et globale (la distance $k$). En se concentrant sur la diversité des prédictions au sein des voisinages k-hop, l'approche proposée offre une vision plus nuancée et complète des inégalités structurelles.

Limites et Perspectives :

• Scalabilité : Le calcul exact des distances $k$ peut être coûteux sur de très grands graphes (bien que des estimateurs approximatifs puissent être utilisés).
• Approche purement structurelle : L'article ne prend pas en compte les attributs des nœuds (features) pour l'équité, se concentrant uniquement sur la topologie. Une combinaison avec des approches basées sur les features serait une direction naturelle.

Conclusion :
L'article introduit un cadre rigoureux pour l'équité k-hop, fournissant à la fois des métriques de diagnostic et des algorithmes d'atténuation (pré/post-traitement). Les résultats expérimentaux valident que cette approche permet de mieux comprendre et corriger les biais structurels profonds que les méthodes traditionnelles ignorent, tout en maintenant une performance prédictive compétitive.