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

Deze paper introduceert $k$-hop eerlijkheid als een nieuwe structuur voor linkpredictie in grafen die bestaande methoden voor dyadische eerlijkheid overstijgt door dispariteiten op verschillende afstanden te analyseren en te mitigeren, waardoor een betere afweging tussen prestaties en eerlijkheid wordt bereikt.

De kern

Stel je voor dat je een grote, levende stad bent, waar elke persoon een huisje heeft en de wegen ertussen vrienden, collega's of kennissen voorstellen. In deze stad proberen slimme computers (link prediction) nieuwe wegen aan te leggen: "Hé, jij en die persoon daar, jullie zouden misschien vrienden kunnen worden!"

Het probleem is dat deze stad niet helemaal eerlijk is. Mensen hebben de neiging om alleen vrienden te maken met anderen die op hen lijken (dezelfde kleur, dezelfde hobby's, dezelfde achtergrond). Dit noemen we homofilie. De computer ziet dit patroon en zegt: "Oké, ik ga ook alleen maar mensen met dezelfde achtergrond aan elkaar koppelen."

Dit klinkt misschien logisch, maar het creëert een filterbel. Mensen komen nooit in contact met nieuwe ideeën of andere groepen. Bestaande ongelijkheid wordt versterkt.

Het oude idee: "Twee mensen, één regel"

Tot nu toe keken onderzoekers alleen naar de directe verbinding tussen twee mensen. Ze dachten: "Als ik ervoor zorg dat er evenveel verbindingen zijn tussen Groep A en Groep B als tussen Groep A en Groep A, dan is het eerlijk."

Maar de auteurs van dit paper zeggen: "Wacht even, dat is te simpel."

Stel je voor dat er in de stad een heel rijke wijk is (Groep A) en een arme wijk (Groep B).

• De computer maakt nu veel nieuwe wegen aan tussen de rijke wijk en de arme wijk.
• Maar... die nieuwe wegen lopen allemaal naar de rijkste mensen in de arme wijk. De armste mensen in die wijk krijgen nog steeds geen enkele nieuwe weg.
• Het oude systeem zegt: "Kijk, we hebben veel wegen tussen A en B gemaakt, dat is eerlijk!"
• Maar in werkelijkheid zijn de armste mensen nog steeds geïsoleerd.

Het nieuwe idee: K-hop eerlijkheid (De "Blik op afstand")

De auteurs introduceren een nieuw concept: K-hop eerlijkheid.

In plaats van alleen te kijken naar de directe buur (1 hop), kijken ze naar hoe ver je moet reizen om iemand te bereiken.

• 1-hop: Je directe buren.
• 2-hop: De vrienden van je vrienden.
• 3-hop: De vrienden van de vrienden van je vrienden.

De kernboodschap is: Eerlijkheid moet worden gekeken op elke afstand.

Stel je voor dat je in een dorp woont waar de "blauwe" mensen en de "rode" mensen gescheiden wonen.

• Als je kijkt naar 1-hop (directe buren), zie je misschien dat er al wat wegen zijn.
• Maar als je kijkt naar 3-hop, zie je dat de "blauwe" mensen aan de rand van het dorp nooit een weg hebben naar de "rode" mensen in het centrum, zelfs niet via tussenpersonen. Ze zitten vast in een hoekje.

De oude methoden zien dit niet omdat ze alleen naar de directe lijnen kijken. De nieuwe methode zegt: "We moeten zorgen dat mensen op elke afstand (1, 2, 3 stappen weg) evenveel kans hebben om contact te maken met iedereen, ongeacht hun kleur."

Hoe lossen ze dit op? (De "Verkeersregelaar")

De auteurs hebben twee manieren bedacht om dit op te lossen:

1. De "Stadsplanner" (Pre-processing): Voordat de computer überhaupt begint met het maken van vrienden, kijken ze naar de wegen in de stad. Als ze zien dat bepaalde groepen te ver van elkaar af zitten, bouwen ze nu al nieuwe bruggen aan om de stad eerlijker te maken.
2. De "Post-Processor" (Post-processing): De computer maakt eerst zijn lijstje met vriendsuggesties. Daarna nemen de auteurs die lijst en zeggen: "Wacht, deze suggestie is niet eerlijk voor de mensen die ver weg wonen. Laten we die suggesties iets aanpassen." Ze schuiven de suggesties een beetje op zodat ook de mensen die verder weg wonen, een kans krijgen.

Waarom is dit belangrijk?

In het echte leven (zoals op LinkedIn of Facebook) betekent dit dat je niet alleen vrienden krijgt die je al kent of die op je lijken. Het zorgt ervoor dat je ook verbindingen krijgt met mensen die verder weg in je netwerk zitten.

• Voor jou: Je ziet meer diversiteit, nieuwe kansen en ideeën.
• Voor de maatschappij: Het breekt de "glazen plafonds" en "filterbellen" die bepaalde groepen uitsluiten.

Kortom:
Deze paper zegt: "Eerlijkheid is niet alleen wie je direct naast je hebt, maar ook wie je kunt bereiken als je een paar stappen verder kijkt. We moeten zorgen dat niemand, waar hij ook in de stad woont, de kans krijgt om de wereld te ontdekken."

Technische samenvatting

Probleemstelling

Link prediction (LP) is een kerncomponent in grafgebaseerde toepassingen, zoals sociale aanbevelingen. Echter, real-world grafen vertonen vaak structurele bias, met name homofiele (de neiging van knopen met vergelijkbare attributen om met elkaar te verbinden). Hoewel dit de voorspellende prestaties kan verbeteren, versterkt het bestaande sociale ongelijkheden.

Bestaande methoden voor eerlijke link prediction (Fair LP) richten zich voornamelijk op dyadische eerlijkheid (dyadic fairness). Dit paradigma probeert de verhouding tussen intra-groeps- en inter-groepsverbindingen te balanceren door de sensitive attributen van knopen (bijv. geslacht, ras) te projecteren op de randen.
De auteurs identificeren twee fundamentele tekortkomingen in deze aanpak:

1. Verwaarlozing van de grafstructuur: Dyadische eerlijkheid behandelt alle inter-groepsranden als gelijkwaardig, ongeacht hun positie in de graf. Dit kan leiden tot het versterken van bestaande, goed verbonden diverse clusters, terwijl geïsoleerde of gesegregeerde delen van de graf (bijv. een geïsoleerde groep binnen een cluster) worden genegeerd.
2. Interne dispariteiten: Het paradigma kijkt niet naar de diversiteit binnen de lokale omgeving van een knoop. Het kan dus gebeuren dat knopen die al toegang hebben tot diverse informatie nog meer voordeel krijgen, terwijl geïsoleerde knopen achterblijven, wat interne ongelijkheid binnen een groep verergert.

Methodologie: k-hop Eerlijkheid

Om deze beperkingen te overwinnen, stellen de auteurs k-hop eerlijkheid voor. Dit is een structurele notie van eerlijkheid die dispariteiten evalueert op basis van de afstand (in hops) tussen knopen in de graf.

1. Definities en Metrieken:

• k-hop knoop-attribuut blootstelling: In plaats van alleen naar randen te kijken, wordt gekeken hoe waarschijnlijk het is dat een knoop $v$ verbindingen aangaat met knopen van een specifieke gevoelige groep $s$ op een exacte afstand $k$.
• k-hop groepsblootstelling ($\phi^{(k)}$): Een aggregatie van de lokale blootstelling over alle knopen binnen een gevoelige groep. Dit geeft een maatstaf voor hoe goed een groep toegang heeft tot andere groepen op afstand $k$.
• k-hop buurt-eerlijkheid ($NF^{(k)}$): De ongelijkheid in blootstelling tussen verschillende doelgroepen voor een bron-groep op afstand $k$. Een lage $NF^{(k)}$ betekent dat knopen binnen een groep gelijkwaardige toegang hebben tot verschillende andere groepen op die specifieke afstand.
• k-hop structurele bias ($NB^{(k)}$): Een maatstaf voor de bestaande bias in de graf zelf (zonder voorspellingen), gebaseerd op de verdeling van gevoelige attributen in de werkelijke $k$-hop-buurt van knopen.

2. Mitigatiestrategieën:
De auteurs stellen zowel pre-processing als post-processing methoden voor om deze bias te verminderen:

• Pre-processing (Graf Rewiring): De grafstructuur (adjacentiematrix) wordt aangepast om de $k$-hop structurele bias ($NB^{(k)}$) te minimaliseren. Dit gebeurt via optimalisatie waarbij een verliesfunctie wordt geminimaliseerd die de bias afweegt tegen de fideliteit aan de oorspronkelijke graf.
• Post-processing (Voorspelling Aanpassing): De voorspellingen van een reeds getrainde link prediction model (de kansmatrix $P$) worden aangepast. De methode beperkt modificaties uitsluitend tot knoopparen die precies $k$ hops uit elkaar liggen. Een verliesfunctie minimaliseert de $k$-hop eerlijkheidsgap ($NF^{(k)}$) terwijl de wijzigingen in de voorspellingen worden geregulariseerd om de algehele prestatie (AUC) te behouden.

Belangrijkste Bijdragen

1. Conceptuele Innovatie: Introductie van k-hop eerlijkheid, een kader dat dispariteiten evalueert binnen de $k$-hop-buurt van knopen. Dit vult het bestaande dyadische paradigma aan en is van toepassing op grafen met multi-waardige gevoelige attributen, evenals gewogen en gerichte netwerken.
2. Algoritmische Methodes: Ontwikkeling van model-onafhankelijke methoden om $k$-hop ongelijkheid te kwantificeren en te mitigeren via pre- en post-processing.
3. Empirische Validatie: Uitgebreide experimenten op diverse real-world datasets (Polblogs, Facebook, Pokec, Citeseer) en synthetische grafen.

Resultaten

De experimenten leveren drie cruciale inzichten op:

1. Structuur van Bias: Modellen hebben de neiging om structurele bias op verschillende $k$-hops te reproduceren. De bias is niet uniform; soms is de bias op afstand 1 hoog, maar op afstand 4 juist significant (afhankelijk van de dataset). Dit bevestigt dat het aggregeren van bias over alle hops (zoals in eerdere werken) niet ideaal is.
2. Interdependentie: Er is een sterke onderlinge afhankelijkheid tussen structurele bias op verschillende hops. Het minimaliseren van bias op één hop (via pre-processing) kan onbedoeld de bias op andere hops verhogen of verlagen, afhankelijk van de specifieke grafstructuur.
3. Prestatie vs. Eerlijkheid: De post-processing methode slaagt erin om de doelgerichte $k$-hop eerlijkheid ($NF^{(k)}$) aanzienlijk te verbeteren.
   • Bij k=1 (directe buren) kan eerlijkheid worden verbeterd zonder verlies aan voorspellende prestatie (AUC), omdat training-edges worden aangepast die niet direct de testset beïnvloeden.
   • Bij intermediaire hops (bijv. k=2) is er een grotere trade-off, omdat deze hops vaak overlappen met de testranden in real-world grafen (hoge clustering).
   • Bij grotere hops is de impact op de AUC vaak minimaal of zelfs positief, omdat het verwijderen van bias soms nuttige voorspellende signalen vrijmaakt.
   • Cruciaal: In tegenstelling tot pre-processing, garandeert post-processing dat het optimaliseren van eerlijkheid op hop $k$ de bias op andere hops $k'$ niet verslechtert.

Betekenis en Conclusie

Dit artikel verschuift het perspectief van link prediction eerlijkheid van een puur "edge-based" (dyadisch) benadering naar een node-centric en structureel perspectief. Het toont aan dat het simpelweg het bevorderen van inter-groepsverbindingen onvoldoende is om echte sociale gelijkheid te bereiken, omdat dit de bestaande topologische ongelijkheden kan maskeren.

Door eerlijkheid te conditioneren op de afstand in de graf, biedt de k-hop benadering een fijnmaziger en nauwkeuriger diagnose van ongelijkheid. De voorgestelde post-processing methode biedt een praktische, model-onafhankelijke oplossing om specifieke vormen van ongelijkheid aan te pakken zonder de algehele prestaties van het systeem drastisch te verstoren. Dit is van groot belang voor industriële toepassingen (zoals LinkedIn-suggesties), waar aanbevelingen vaak worden gecategoriseerd op basis van nabijheid (bijv. "2e graad" of "3e graad" connecties).