🤖 machine learning

Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study

Deze reproduceerbaarheidsstudie toont aan dat de voorgestelde rangbewuste NDKL-metriek en de MORAL post-processing methode effectief blootleggen en mitigeren van exposure biases in linkvoorspelling die door traditionele demografische pariteit worden over het hoofd gezien, terwijl ze concurrerende bruikbaarheid behouden in diverse settings.

Oorspronkelijke auteurs: Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

Gepubliceerd 2026-08-11

📖 7 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Valentijn Oldenburg, Floris de Kam, Stef de Wildt, Jarno Nilson Balk

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je de kapitein bent van een enorm digitaal schip, die een vloot aan aanbevelingen stuurt door de uitgestrekte oceaan van het internet. Elke keer dat je een nieuwe vriend, een kandidaat voor een baan of een dienst suggereert, plaats je in feite een link tussen twee mensen. In de wereld van machine learning wordt dit link prediction genoemd. Maar hier komt de crux: alleen omdat je een link kunt voorspellen, betekent niet dat je iedereen gelijk moet behandelen. Als het kompas van je schip een klein beetje afwijkt, blijf je misschien steeds dezelfde groepen mensen naar elkaar toe sturen, terwijl anderen in het donker achtergelaten worden. Dit is het probleem van fairness (rechtvaardigheid).

Lange tijd gebruikten wetenschappers een eenvoudige regel genaamd Demographic Parity om te controleren of je schip eerlijk was. Denk aan het tellen hoeveel passagiers uit Groep A en Groep B op het dek staan. Als de aantallen ongeveer gelijk zijn, neemt de kapitein aan dat iedereen eerlijk wordt behandeld. Maar dit artikel betoogt dat deze regel is alsof je de passagiers telt zonder te kijken naar waar ze zitten. Als Groep A zich allemaal in de VIP-lounge aan de voorkant van het schip bevindt (en alle aandacht krijgt) en Groep B in het laadruim aan de achterkant is gepropt (en wordt genegeerd), dan kan de totale telling er nog steeds gebalanceerd uitzien, maar de ervaring is volkomen onrechtvaardig. Dit is het verschil tussen "er wel zijn" en het krijgen van exposure (blootstelling)—de kans om gezien en gekozen te worden.

De onderzoekers in deze studie, een team studenten van de Universiteit van Amsterdam, besloten een nieuwe theorie over deze "exposure bias" te testen. Ze wilden zien of de oude regel (Demographic Parity) de echte problemen verborg en of een nieuwe, gevoeliger liniaal dit kon oplossen. Ze namen het oorspronkelijke idee niet zomaar voor waar aan; ze herbouwden het experiment vanaf de grond af, repareerden enkele defecte instrumenten die ze onderweg vonden, en creëerden zelfs hun eigen stormachtige zeeën om te zien of het nieuwe kompas stand zou houden. Wat ze vonden, suggereert dat we om echt eerlijk te zijn niet alleen moeten kijken naar wie een link krijgt, maar ook naar waar die link verschijnt in de lijst met suggesties.

Het Verhaal van het Papier

Het artikel, getiteld "Fairness in Link Prediction Beyond Demographic Parity: A Reproducibility Study," is in essentie een detectivespel over rechtvaardigheid in computeralgoritmen. De auteurs, Valentijn Oldenburg, Floris de Kam, Stef de Wildt en Jarno Balk, gingen op pad om een bewering te verifiëren van een ander team onderzoekers (Mattos et al., 2025). Het oorspronkelijke team argumenteerde dat de standaardmanier om rechtvaardigheid te meten gebrekkig was omdat de rangschikking van links werd genegeerd.

Om het probleem te begrijpen, stel je een muziekafspeellijst voor. Als een afspeellijst eerlijk zou moeten zijn, zou deze niet alleen een gelijk aantal nummers van Artiest A en Artiest B moeten afspelen. Het doet er toe wanneer ze worden gespeeld. Als de nummers van Artiest A altijd bovenaan staan (waar mensen echt luisteren), en de nummers van Artiest B onderaan zijn begraven (waar niemand scrolt), dan is de afspeellijst bevooroordeeld, zelfs als het totaal aantal nummers hetzelfde is. In de wereld van link prediction is deze "bovenaan de lijst" waar de exposure plaatsvindt. De oude regel, Demographic Parity, was als het tellen van de totale nummers en zeggen: "Hé, we hebben 50 van A en 50 van B, dus we zijn eerlijk!" De nieuwe regel, genaamd NDKL, kijkt naar de volgorde van de afspeellijst en vraagt: "Wacht, waarom staan al die nummers van A in de eerste tien tracks?"

De auteurs van dit papier deden drie hoofdzaken:

Ze Herbouwden het Experiment: Ze namen de code en methoden van de oorspronkelijke studie uit 2025 en probeerden de resultaten te reproduceren. Ze ontdekten dat de oorspronkelijke code enkele bugs en inconsistenties bevatte. Na het repareren van deze fouten bevestigden ze de belangrijkste bevindingen van het oorspronkelijke team: de oude regel (Demographic Parity) verbergt inderdaad onrechtvaardigheid, en de nieuwe regel (NDKL) vangt het wel op.
Ze Testten de "Fix": De oorspronkelijke studie stelde een methode voor genaamd MORAL om het probleem op te lossen. MORAL is als een slimme DJ die de afspeellijst opnieuw rangschikt nadat de nummers zijn gekozen. Het neemt de initiële suggesties en husselt ze zodat verschillende groepen een eerlijke kans krijgen op de bovenste plekken, zonder de kwaliteit van de muziek te ruïneren. De auteurs ontdekten dat MORAL erin slaagde de oneerlijke exposure bias te verminderen terwijl de aanbevelingen nuttig bleven.
Ze Testten het Systeem tot het Breekpunt: Om er zeker van te zijn dat dit geen toevalstreffer was, creëerden ze hun eigen "stress-tests". Ze bouwden nep sociale netwerken met verschillende niveaus van homofilie (de neiging voor mensen om contact te maken met anderen die op hen lijken). Ze ontdekten dat zelfs wanneer de netwerken lastig waren of de groepen klein waren, MORAL er nog steeds in slaagde om de zaken eerlijk te houden. Ze testten ook wat er gebeurt als er meer dan alleen twee groepen zijn (zoals het toevoegen van een derde of vierde categorie), en het systeem hield goed stand, hoewel het iets moeilijker werd om de balans te bewaren naarmate de groepen kleiner werden.

Wat Ze Vonden

De studie bevestigt dat Demographic Parity een slechte graadmeter is voor rechtvaardigheid wanneer het gaat om gerangschikte lijsten. Het suggereert dat vertrouwen op deze regel is als het beoordelen van een race op basis van hoeveel mensen de finish hebben gehaald, waarbij wordt genegeerd wie de gouden medaille heeft gewonnen. De nieuwe metriek, NDKL, is veel beter in het opsporen van situaties waarin één groep systematisch naar de onderkant van de lijst wordt gedrukt.

De MORAL-methode, die fungeert als een post-processing "re-ranker", bleek zeer effectief. In hun experimenten over zes verschillende real-world datasets (inclusclusief sociale netwerken en kredietgegevens), verminderde MORAL consequent de exposure bias. Zo bracht de nieuwe methode op de "Facebook"-dataset de fairness score bijvoorbeeld terug naar bijna nul (wat betekent dat er zeer weinig bias is), terwijl de nauwkeurigheid van de voorspellingen hoog bleef.

De auteurs ontdekten ook dat het systeem robuust is. Zelfs toen ze netwerken simuleerden waarin één groep erg klein was of waar mensen alleen de neiging hadden om met hun eigen soort te verbinden (hoge homofilie), slaagde MORAL er nog steeds in om exposure eerlijk te verdelen. Ze merkten echter een trade-off op: naarmate het aantal verschillende groepen toenam, werd het iets moeilijker om iedereen perfect in balans te houden, en het systeem had meer rekenkracht nodig. Maar zelfs dan bleven de top-aanbevelingen accuraat.

De Kern van het Verhaal

Dit artikel beweert niet dat het elk probleem in AI-fairness heeft opgelost, maar suggere bent sterk dat we de manier waarop we het meten moeten veranderen. Als we geven om wie gezien wordt en wie wordt genegeerd, kunnen we niet alleen hoofden tellen; we moeten naar de plattegrond van de zitplaatsen kijken. De studie laat zien dat door een metriek te gebruiken die de volgorde van de lijst respecteert (zoals NDKL) en een methode die de lijst actief herrangschikt om eerlijk te zijn (zoals MORAL), we systemen kunnen bouwen die niet alleen accuraat zijn, maar ook werkelijk rechtvaardig voor alle groepen, ongeacht hoe klein of verborgen ze ook zijn. De auteurs hebben zelfs hun gecorrigeerde code vrijgegeven zodat anderen hun werk kunnen controleren en erop voort te bouwen, om er zeker van te zijn dat het pad naar eerlijke AI openstaat voor iedereen.

Probleemstelling
Rechtvaardigheid in linkvoorspelling streeft naar het verminderen van verschillen in voorspelde link-waarschijnlijkheden tussen groepen. In aanbevelingen voor sociale netwerken bepalen linkvoorspellers de zichtbaarheid en connectiviteit, wat potentieel feedbackloops kan induceren die binnengroep-verbindingen versterken en minderheidsgroepen benadelen. Een kritisch probleem ontstaat wanneer deze modellen worden getraind op historische graafgegevens, die bestaande structurele vooroordelen kunnen overnemen en versterken.

Terwijl demografische pariteit ( $\Delta$ DP) een veelgebruikte rechtvaardigheidsmetriek is in gerangschikte linkvoorspelling, aggregeert het links in grove categorieën (dezelfde groep versus verschillende groepen). Mattos et al. (2025) betogen dat dit dyadische perspectief falen in het detecteren van exposure-bias (blootstellingsvooroordeel), omdat het de specifieke positie van links binnen de rangschikking negeert. Bijgevolg kan geaggregeerde pariteit standhouden, zelfs wanneer specifieke subgroup-pair links (bijv. vrouw-vrouw links) systematisch lager worden gerangschikt dan andere, waardoor binnengroep-verschillen worden verborgen.

Methodologie
Deze studie is een reproductie en uitbreiding van Mattos et al. (2025). De auteurs formaliseren linkvoorspelling als een rangschikkingsprobleem waarbij gevoelige attributen subgroup-pair typen definiëren (bijv. $E_{0-0}, E_{1-1}, E_{0-1}$ ).

Metrieken:
- Demografische Pariteit ( $\Delta$ DP): Meet het verschil in gemiddelde voorspelde scores tussen intra-groep ( $E_{intra}$ ) en inter-groep ( $E_{inter}$ ) links. Het is permutatie-invariant met betrekking tot de rangorde.
- Genormaliseerde Gedisconteerde KL-divergentie (NDKL): Een rang-bewuste, niet-dyadische metriek die alle subgroup-pair typen afzonderlijk behandelt. Het cumuleert de Kullback-Leibler-divergentie tussen de voorspelde exposure-distributie en een doelverdeling over rangschikkingsprefixes, gewogen door een logaritmische vervalfactor om afwijkingen bij hogere rangen zwaarder te bestraffen.
- Utiliteit: Gemeten via Precision@1000 en NDCG@1000.
MORAL (Multi-Output Ranking Aggregation for Link Fairness):
Een post-processing algoritme dat de outputs van ontkoppelde linkvoorspellers (één model getraind per subgroup-pair type) opnieuw rangschikt. MORAL gebruikt een guldtige (greedy) KL-gestuurde aggregatiestrategie: op elke rangpositie selecteert het de beste resterende edge uit elke subgroup-pair pool die de KL-divergentie tussen de bijgewerkte exposure-distributie en een doelverdeling $\pi$ (afgeleid van de oorspronkelijke graaf) minimaliseert.
Experimentele Opzet:
- Datasets: Zes sociale netwerkdatasets (Credit, Facebook, German, NBA, Pokec-n, Pokec-z) en twee aanvullende datasets (Global Airport Routes Network, Chameleon) voor topologieverificatie.
- Reproductie: De auteurs reproduceerden de kernopstelling met behulp van GCN-encoders en dot-product decoders, waarbij inconsistenties in de oorspronkelijke codebase met betrekking tot de berekening van de doelverdeling en KL-aggregatie werden gecorrigeerd.
- Uitbreidingen:
  - Asymmetrische Homofilie Stress-test: Synthetische grafen gegenereerd via het Directed Preferential Attachment with Homophily (DPAH) model om prestaties te testen onder variërende graden van binnengroep-connectiviteit.
  - Metriek Robuustheid: Evaluatie met behulp van Attention-Weighted Rank Fairness (AWRF) en NDCG om te waarborgen dat resultaten niet specifiek zijn voor de NDKL-aggregatiemechanisme.
  - Categorische Attributen: Uitbreiding van het framework naar gevoelige attributen met cardinaliteit $m > 2$ .

Belangrijkste Bijdragen

Reproductie en Correctie: De studie reproduceert succesvol de kernclaims van Mattos et al. (2025) terwijl een gecorrigeerde, reproduceerbare implementatie wordt vrijgegeven. Het identificeert en herstelt inconsistenties in de originele code met betrekking tot de berekening van de doelverdeling en KL-divergentie normalisatie.
Validatie van Claims:
- C1: Bevestigt dat $\Delta$ DP geaggregeerde pariteit kan aangeven, zelfs wanneer significante exposure-verschillen bestaan binnen specifieke subgroup pairs (bijv. binnen $E_{intra}$ ).
- C2: Demonstreert dat NDKL deze verborgen verschillen effectief detecteert vanwege de rang-bewuste en niet-dyadische aard.
- C3: Toont aan dat MORAL exposure-biases consistent mitigeert (lage NDKL) terwijl het concurrerende utiliteit (Precision/NDCG) behoudt over diverse datasets.
Robuustheidsanalyse:
- De studie breidt het oorspronkelijke werk uit door asymmetrische homofilie te testen, waarbij wordt aangetoond dat MORAL robuust presteert, hoewel exposure-verschillen het meest uitgesproken zijn bij intermediaire absolute homofilie-niveaus.
- Het valideert de generaliseerbaarheid van het framework naar categorische gevoelige attributen (tot $m=10$ ) en verschillende grafentopologieën (Core-periphery, Heterophilic).
- Het bevestigt dat verbeteringen in rechtvaardigheid geen artefact zijn van het optimaliseren van NDKL, aangezien vergelijkbare trends worden waargenomen met AWRF.

Resultaten

Rechtvaardigheid vs. Utiliteit: MORAL bereikt een bijna nul NDKL over alle datasets, waarmee het baselines (FairAdj, FairWalk, DetConstSort) aanzienlijk overtreft. Deze reductie in exposure-bias gaat gepaard met minimaal utiliteitsverlies; MORAL behoudt een hoge Precision@1000, en evenaart vaak of overtreft zelfs de baselines.
Metriek Sensitiviteit: $\Delta$ DP blijft grotendeels invariant voor verschuivingen in exposure-allocatie binnen groepen, terwijl NDKL en AWRF zeer gevoelig zijn voor deze verschuivingen.
Homofilie: In synthetische settings pieken exposure-gebaseerde metrieken bij intermediaire absolute homofilie ( $\approx 0.6$ ), waar binnengroep-edges frequent zijn maar rangschikkingen divers blijven. Bij hoge homofilie daalt de utiliteit licht omdat ontkoppelde voorspellers zwakkere trainingssignalen ontvangen.
Categorische Attributen: Naarmate het aantal subgroup-pair typen ( $T$ ) toeneemt, nemen NDKL en AWRF monotoon af, wat aangeeft dat het afstemmen van exposure op de doelverdeling progressief moeilijker wordt. De utiliteit blijft echter hoog, wat suggereert dat top-gerangschikte edges accuraat blijven, zelfs als lagere rangen minder stabiel worden.
Ablatie: Een vergelijking tussen pre-rerank en post-rerank scores laat zien dat de guldtige KL-aggregatiestap zelf verantwoordelijk is voor een substantiële reductie in exposure-bias (66,9% reductie in NDKL, 92,6% in AWRF).

Betekenis en Claims
Het artikel concludeert dat dyadische demografische pariteit onvoldoende is voor gerangschikte linkvoorspelling omdat het exposure-verschillen tussen subgroup-pairs kan verbergen. De auteurs betogen dat wanneer linkvoorspellingsoutputs worden geconsumeerd als rangschikkingen, exposure de relevante maatstaf voor rechtvaardigheid moet zijn.

De studie ondersteunt het gebruik van exposure-gebaseerde, rang-bewuste metrieken (zoals NDKL en AWRF) en de MORAL post-processing methode als effectieve instrumenten voor het debiasen van gerangschikte linkvoorspellingen. Het benadrukt een praktische afweging: hoewel MORAL schaalt naar settings met een hogere cardinaliteit, nemen de computationele kosten en de moeilijkheid van exposure-afstemming toe met het aantal subgroup-pair typen. De auteurs benadrukken dat het behouden van de oorspronkelijke graafverdeling ( $\pi$ ) een ontwerpkeuze is om algoritmische versterking van bias te voorkomen, in plaats van een claim dat de oorspronkelijke distributie inherent "rechtvaardig" is.

Het Verhaal van het Papier

Wat Ze Vonden

De Kern van het Verhaal

Meer zoals dit