🤖 machine learning

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Cette étude de reproductibilité démontre que la métrique NDKL sensible au rang proposée et la méthode de post-traitement MORAL révèlent et atténuent efficacement les biais d'exposition dans la prédiction de liens qui sont négligés par la parité démographique traditionnelle, tout en maintenant une utilité compétitive à travers divers contextes.

Auteurs originaux : Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

Publié 2026-08-11

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous êtes le capitaine d'un immense navire numérique, dirigeant une flotte de recommandations à travers l'océan vaste de l'internet. Chaque fois que vous suggérez un nouvel ami, un candidat à un emploi ou un service, vous établissez essentiellement un lien entre deux personnes. Dans le monde de l'apprentissage automatique, cela s'appelle la prédiction de liens. Mais voici le piège : ce n'est pas parce que vous pouvez prédire un lien que vous devez traiter tout le monde de la même manière. Si la boussole de votre navire est légèrement déréglée, vous pourriez continuer à diriger les mêmes groupes de personnes les uns vers les autres, tout en laissant les autres laissés à l'abandon dans l'obscurité. C'est le problème de l'équité.

Pendant longtemps, les scientifiques ont utilisé une règle simple appelée Parité Démographique pour vérifier si leur navire était équitable. Cela revient à compter combien de passagers du Groupe A et du Groupe B se trouvent sur le pont. Si les chiffres sont à peu près égaux, le capitaine suppose que tout le monde est traité équitablement. Mais cet article soutient que cette règle revient à compter les passagers sans regarder où ils sont assis. Si le Groupe A est tout entier dans le salon VIP à l'avant du navire (recevant toute l'attention) et que le Groupe B est entassé dans la cale à l'arrière (étant ignoré), le décompte total peut sembler équilibré, mais l'expérience est profondément injuste. C'est la différence entre simplement "être là" et obtenir de l'exposition — la chance d'être vu et choisi.

Les chercheurs de cette étude, une équipe d'étudiants de l'Université d'Amsterdam, ont décidé de tester une nouvelle théorie sur ce "biais d'exposition". Ils voulaient voir si l'ancienne règle (la Parité Démographique) cachait le véritable problème et si une règle plus sensible pouvait le corriger. Ils n'ont pas simplement pris l'idée originale pour acquise ; ils ont reconstruit l'expérience de fond en comble, réparé certains outils défectueux qu'ils ont trouvés en chemin, et ont même créé leurs propres mers agitées pour voir si la nouvelle boussole tenait le coup. Ce qu'ils ont découvert suggère que pour être véritablement équitable, nous ne devons pas seulement regarder qui reçoit un lien, mais où ce lien apparaît dans la liste des suggestions.

L'histoire de l'article

L'article, intitulé « Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study », est essentiellement une histoire de détective sur l'équité des algorithmes informatiques. Les auteurs, Valentijn Oldenburg, Floris de Kam, Stef de Wildt et Jarno Balk, se sont donné pour mission de vérifier une affirmation faite par une autre équipe de chercheurs (Mattos et al., 2025). L'équipe originale affirmait que la manière standard de mesurer l'équité était défaillante car elle ignorait le classement des liens.

Pour comprendre le problème, imaginez une playlist musicale. Si une playlist est censée être équitable, elle ne doit pas seulement jouer un nombre égal de chansons de l'Artiste A et de l'Artiste B. Il importe de savoir quand elles sont jouées. Si les chansons de l'Artiste A sont toujours en haut (là où les gens écoutent réellement), et que les chansons de l'Artiste B sont enfouies en bas (là où personne ne fait défiler), la playlist est biaisée, même si le nombre total de chansons est le même. Dans le monde de la prédiction de liens, ce "haut de la liste" est l'endroit où l'exposition se produit. L'ancienne règle, la Parité Démographique, revenait à compter le nombre total de chansons et à dire : « Hé, nous avons 50 chansons de A et 50 de B, donc nous sommes équitables ! » La nouvelle règle, appelée NDKL, examine l'ordre de la playlist et demande : « Attendez, pourquoi toutes les chansons de A sont-elles dans les dix premiers titres ? »

Les auteurs de cet article ont fait trois choses principales :

Ils ont reconstruit l'expérience : Ils ont repris le code et les méthodes de l'étude originale de 2025 et ont tenté de reproduire les résultats. Ils ont constaté que le code original contenait des bugs et des incohérences. Après avoir corrigé ces problèmes, ils ont confirmé les principales conclusions de l'équipe originale : l'ancienne règle (la Parité Démographique) cache effectivement l'injustice, et la nouvelle règle (NDKL) la détecte bien.
Ils ont testé la « correction » : L'étude originale proposait une méthode appelée MORAL pour résoudre le problème. MORAL est comme un DJ intelligent qui réorganise la playlist après que les chansons ont été choisies. Il prend les suggestions initiales et les mélange afin que différents groupes aient une chance équitable d'occuper les premières places, sans pour autant gâcher la qualité de la musique. Les auteurs ont constaté que MORAL réduisait avec succès le biais d'exposition injuste tout en maintenant l'utilité des recommandations.
Ils ont mis le système à l'épreuve : Pour s'assurer qu'il ne s'agissait pas d'un simple coup de chance, ils ont créé leurs propres « tests de résistance ». Ils ont construit de faux réseaux sociaux avec différents niveaux d'homophilie (la tendance des individus à se connecter avec des personnes qui leur ressemblent). Ils ont découvert que même lorsque les réseaux étaient complexes ou que les groupes étaient de petite taille, MORAL réussissait toujours à maintenir l'équité. Ils ont également testé ce qui se passe lorsqu'il y a plus de deux groupes (comme en ajoutant une troisième ou quatrième catégorie) : le système a bien résisté, bien qu'il soit devenu un peu plus difficile de trouver l'équilibre lorsque les groupes devenaient plus petits.

Ce qu'ils ont trouvé

L'étude confirme que la Parité Démographique est un mauvais indicateur de l'équité lorsqu'il s'agit de listes classées. Elle suggère que s'appuyer sur elle revient à juger une course en regardant combien de personnes ont franchi la ligne d'arrivée, en ignorant qui a réellement remporté la médaille d'or. Le nouveau métrique, NDKL, est bien plus efficace pour repérer lorsqu'un groupe est systématiquement poussé au bas de la liste.

La méthode MORAL, qui agit comme un « re-classeur » (re-ranker) post-traitement, s'est révélée très efficace. Dans leurs expériences sur six ensembles de données du monde réel (incluant des réseaux sociaux et des données de crédit), MORAL a systématiquement réduit le biais d'exposition. Par exemple, sur l'ensemble de données « Facebook », la nouvelle méthode a ramené le score d'équité proche de zéro (ce qui signifie très peu de biais), tout en maintenant une grande précision des prédictions.

Les auteurs ont également découvert que le système est robuste. Même lorsqu'ils ont simulé des réseaux où un groupe était très restreint ou où les gens préféraient ne se connecter qu'avec leurs semblables (homophilie élevée), MORAL a réussi à distribuer l'exposition de manière équitable. Cependant, ils ont noté un compromis : à mesure que le nombre de groupes différents augmentait, il devenait légèrement plus difficile de tout équilibrer parfaitement, et le système nécessitait plus de puissance de calcul. Mais même dans ce cas, les recommandations de tête restaient précises.

L'essentiel

Cet article ne prétend pas avoir résolu tous les problèmes d'équité de l'IA, mais il suggère fortement que nous devons changer notre façon de la mesurer. Si nous nous soucions de savoir qui est vu et qui est ignoré, nous ne pouvons pas nous contenter de compter les têtes ; nous devons regarder le plan de table. L'étude démontre qu'en utilisant une métrique qui respecte l'ordre de la liste (comme NDKL) et une méthode qui réorganise activement la liste pour être équitable (comme MORAL), nous pouvons construire des systèmes qui sont non seulement précis, mais aussi véritablement justes pour tous les groupes, aussi petits ou cachés soient-ils. Les auteurs ont même publié leur code corrigé afin que d'autres puissent vérifier leur travail et s'en inspirer, garantissant ainsi que le chemin vers une IA équitable soit ouvert à tous.

Énoncé du Problème
La l'équité dans la prédiction de liens vise à réduire les disparités dans les probabilités de liens prédites entre les groupes. Dans les recommandations de réseaux sociaux, les prédicteurs de liens déterminent la visibilité et la connectivité, pouvant induire des boucles de rétroaction qui renforcent les connexions intra-groupe et désavantagent les groupes minoritaires. Un problème critique survient lorsque ces modèles sont entraînés sur des données de graphes historiques, qui peuvent hériter et amplifier les biais structurels existants.

La parité démographique ( $\Delta$ DP) est une métrique d'équité courante dans la prédiction de liens classés, mais elle agrège les liens en catégories grossières (même groupe vs groupe différent). Mattos et al. (2025) soutiennent que cette vision dyadique ne parvient pas à détecter le biais d'exposition car elle ignore la position spécifique des liens au sein du classement. Par conséquent, une parité agrégée peut être respectée même si des liens de sous-groupes spécifiques (par exemple, les liens femme-femme) sont systématiquement classés plus bas que d'autres, occultant ainsi les disparités intra-groupe.

Méthodologie
Cette étude est une reproduction et une extension de Mattos et al. (2025). Les auteurs formalisent la prédiction de liens comme un problème de classement où les attributs sensibles définissent les types de paires de sous-groupes (par exemple, $E_{0-0}, E_{1-1}, E_{0-1}$ ).

Métriques :
- Parité Démographique ( $\Delta$ DP) : Mesure la différence de score moyen entre les liens intra-groupe ( $E_{intra}$ ) et inter-groupe ( $E_{inter}$ ). Elle est invariante par permutation concernant l'ordre du classement.
- Divergence de Kullback-Leibler Normalisée (NDKL) : Une métrique sensible au rang et non dyadique qui traite distinctement tous les types de paires de sous-groupes. Elle accumule la divergence de Kullback-Leibler entre la distribution d'exposition prédite et une distribution cible à travers les préfixes de classement, pondérée par un facteur de décroissance logarithmique pour pénaliser plus lourdement les écarts dans les rangs élevés.
- Utilité : Mesurée via la Précision@1000 et l'NDCG@1000.
MORAL (Multi-Output Ranking Aggregation for Link Fairness) :
Un algorithme de post-traitement qui reclasse les sorties de prédicteurs de liens découplés (un modèle entraîné par type de paire de sous-groupes). MORAL utilise une stratégie d'agrégation gourmande guidée par la KL : à chaque position de rang, il sélectionne l'arête restante la plus haute de chaque pool de paires de sous-groupes qui minimise la divergence KL entre la distribution d'exposition mise à jour et une distribution cible $\pi$ (dérivée du graphe original).
Configuration Expérimentale :
- Jeux de données : Six jeux de données de réseaux sociaux (Credit, Facebook, German, NBA, Pokec-n, Pokec-z) et deux jeux de données supplémentaires (Global Airport Routes Network, Chameleon) pour la vérification de la topologie.
- Reproduction : Les auteurs ont reproduit la configuration centrale en utilisant des encodeurs GCN et des décodeurs de produit scalaire, en corrigeant les incohérences trouvées dans le code original concernant le calcul de la distribution cible et l'agrégation KL.
- Extensions :
  - Stress-test d'homophilie asymétrique : Graphes synthétiques générés via le modèle DPAH (Directed Preferential Attachment with Homophily) pour tester les performances sous différents degrés de connectivité intra-groupe.
  - Robustesse de la métrique : Évaluation utilisant l'AWRF (Attention-Weighted Rank Fairness) et l'NDCG pour s'assurer que les résultats ne sont pas spécifiques au mécanisme d'agrégation NDKL.
  - Attributs catégoriels : Extension du cadre aux attributs sensibles ayant une cardinalité $m > 2$ .

Contributions Clés

Reproduction et Correction : L'étude reproduit avec succès les affirmations centrales de Mattos et al. (2025) tout en publiant une implémentation corrigée et reproductible. Elle identifie et corrige les incohérences du code original concernant le calcul de la distribution cible et la normalisation de la divergence KL.
Validation des Affirmations :
- C1 : Confirme que $\Delta$ DP peut indiquer une parité agrégée même lorsque des disparités d'exposition significatives existent au sein de paires de sous-groupes spécifiques (par exemple, au sein de $E_{intra}$ ).
- C2 : Démontre que la NDKL détecte efficacement ces disparités cachées grâce à sa nature sensible au rang et non dyadique.
- C3 : Montre que MORAL atténue systématiquement les biais d'exposition (faible NDKL) tout en maintenant une utilité compétitive (Précision/NDCG) sur divers jeux de données.
Analyse de Robustesse :
- L'étude étend le travail original en testant l'homophilie asymétrique, montrant que MORAL est robuste, bien que les disparités d'exposition soient plus prononcées à des niveaux d'homophilie absolue intermédiaires.
- Elle valide la généralisabilité du cadre aux attributs sensibles catégoriels (jusqu'à $m=10$ ) et à différentes topologies de graphes (Core-periphery, Hétérophile).
- Elle confirme que les améliorations d'équité ne sont pas de simples artefacts de l'optimisation de la NDKL, des tendances similaires étant observées avec l'AWRF.

Résultats

Équité vs Utilité : MORAL atteint une NDKL proche de zéro sur tous les jeux de données, surpassant nettement les bases de référence (FairAdj, FairWalk, DetConstSort). Cette réduction du biais d'exposition s'accompagne d'une perte d'utilité minimale ; MORAL maintient une Précision@1000 élevée, égalant ou dépassant souvent les bases de référence.
Sensibilité de la Métrique : La $\Delta$ DP reste largement invariante aux changements d'allocation d'exposition au sein des groupes, tandis que la NDKL et l'AWRF sont hautement sensibles à ces changements.
Homophilie : Dans les contextes synthétiques, les métriques basées sur l'exposition culminent à une homophilie absolue intermédiaire ( $\approx 0.6$ ), où les arêtes intra-groupe sont fréquentes mais les classements restent diversifiés. À haute homophilie, l'utilité chute légèrement car les prédicteurs découplés reçoivent des signaux d'entraînement plus faibles.
Attributs Catégoriels : À mesure que le nombre de types de paires de sous-groupes ( $T$ ) augmente, la NDKL et l'AWRF se dégradent de manière monotone, indiquant qu'aligner l'exposition avec la distribution cible devient progressivement plus difficile. Cependant, l'utilité reste élevée, suggérant que les arêtes les mieux classées restent précises même si les rangs inférieurs sont moins stables.
Ablation : Une comparaison des scores pré-rerank et post-rerank montre que l'étape d'agrégation gourmande de la KL est responsable d'une réduction substantielle du biais d'exposition (réduction de 66,9 % de la NDKL, 92,6 % de l'AWRF).

Signification et Affirmations
L'article conclut que la parité démographique dyadique est insuffisante pour la prédiction de liens classés car elle peut occulter les disparités d'exposition des sous-groupes. Les auteurs soutiennent que lorsque les sorties de prédiction de liens sont consommées sous forme de classements, l'exposition doit être la monnaie d'échange pertinente de l'équité.

L'étude soutient l'utilisation de métriques sensibles au rang et basées sur l'exposition (comme la NDKL et l'AWRF) ainsi que la méthode de post-traitement MORAL comme outils efficaces pour débiaser les prédictions de liens classés. Elle souligne un compromis pratique : bien que MORAL soit extensible à des contextes de plus haute cardinalité, le coût computationnel et la difficulté de l'alignement de l'exposition augmentent avec le nombre de types de paires de sous-groupes. Les auteurs soulignent que la préservation de la distribution du graphe original ( $\pi$ ) est un choix de conception pour éviter l'amplification algorithmique du biais, plutôt qu'une affirmation que la distribution originale est intrinsèquement « équitable ».

L'histoire de l'article

Ce qu'ils ont trouvé

L'essentiel

Articles similaires