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

Diese Arbeit stellt „k-hop Fairness" vor, ein neues strukturelles Fairnesskonzept für die Link-Vorhersage in Graphen, das über die traditionelle dyadische Fairness hinausgeht, um Verzerrungen in verschiedenen Entfernungsebenen zu erfassen und durch vorgeschlagene Minderungsstrategien zu adressieren.

Das Wesentliche

Das Problem: Der "Blasen-Effekt" in Freundschaftsnetzwerken

Stell dir vor, du lebst in einem riesigen Dorf, das durch ein riesiges Netz von Wegen verbunden ist. Jeder Weg ist eine Freundschaft oder eine Verbindung zwischen zwei Menschen. Ein Computerprogramm (ein Algorithmus) versucht nun, dir neue Freunde vorzuschlagen.

Das Problem ist: Menschen neigen dazu, Freunde zu finden, die ihnen ähnlich sind (gleiche Herkunft, gleiche Interessen, gleiches Geschlecht). Das nennt man Homophilie (Liebe zum Gleichen).

Wenn der Computer nur auf die nächsten Nachbarn schaut (die Leute, die direkt neben dir wohnen), sieht er nur diese Ähnlichkeiten. Er schlägt dir also vor: "Hey, du magst Rockmusik und wohnst in Stadtteil A? Hier sind 10 weitere Rockfans aus Stadtteil A!"

Das ist zwar effizient, aber es baut eine Blase. Du hörst nie Jazz, triffst nie jemanden aus Stadtteil B und verpasst Chancen. Das ist unfair, weil bestimmte Gruppen im Dorf isoliert bleiben.

Die alte Lösung: "Mische einfach alles durcheinander"

Bisher haben Forscher versucht, das zu beheben, indem sie dem Computer sagten: "Mache mehr Verbindungen zwischen verschiedenen Gruppen!" (z. B. zwischen Stadtteil A und B).

Das klingt gut, hat aber einen Haken: Der Computer macht das nur dort, wo es am einfachsten ist. Er verbindet die "beliebtesten" Leute aus Stadtteil A mit den "beliebtesten" Leuten aus Stadtteil B.

• Das Ergebnis: Die bereits gut vernetzten Leute werden noch besser vernetzt.
• Das Problem: Die einsamen Leute am Rande des Dorfes, die weit weg von den Hauptwegen wohnen, werden immer noch ignoriert. Die Ungleichheit innerhalb der Gruppen bleibt bestehen.

Die neue Idee: "Schau weiter weg" (k-hop Fairness)

Die Autoren dieses Papers sagen: "Halt! Wir müssen nicht nur auf die direkten Nachbarn schauen, sondern auch auf die Nachbarn unserer Nachbarn, und deren Nachbarn..."

Sie nennen das k-hop Fairness.

• Hop 1: Deine direkten Nachbarn.
• Hop 2: Die Freunde deiner Freunde.
• Hop 3: Die Freunde deiner Freunde' Freunde.

Stell dir vor, du stehst auf einem Hügel.

• Wenn du nur Hop 1 betrachtest, siehst du nur das Haus direkt neben dir.
• Wenn du Hop 3 betrachtest, siehst du, ob es überhaupt einen Weg zu den Leuten im anderen Tal gibt, auch wenn er weit weg ist.

Die Forscher haben herausgefunden, dass die Ungerechtigkeit oft erst sichtbar wird, wenn man weiter weg schaut. Manchmal gibt es eine Gruppe, die zwar viele direkte Freunde hat, aber niemanden in der Ferne, die ihnen helfen könnte. Eine faire Empfehlung muss also auch diese "fernen" Verbindungen berücksichtigen.

Die Lösung: Ein neuer Kompass und ein Nachbesserungs-Tool

Die Autoren haben zwei Werkzeuge entwickelt:

1. Ein neuer Maßstab (Die Diagnose):
   Sie haben eine Formel erfunden, die nicht nur zählt, wie viele Freunde jemand hat, sondern wie vielfältig die Umgebung in verschiedenen Entfernungen ist.

   • Analogie: Statt nur zu zählen, wie viele rote und blaue Kugeln in deiner Hand sind, schauen wir, ob die Kugeln in deinem ganzen Garten (10 Meter entfernt) und im ganzen Park (50 Meter entfernt) gut gemischt sind. Wenn im Park nur rote Kugeln sind, ist das unfair, auch wenn in deiner Hand alles gemischt ist.

2. Zwei Methoden, um es zu beheben:

   • Vor dem Training (Pre-Processing): Man baut im Dorf neue Wege, bevor der Computer lernt. Man fügt absichtlich Pfade hinzu, die isolierte Gruppen verbinden. Das ist wie das Bauen einer neuen Brücke zwischen zwei Inseln, damit der Verkehr fließen kann.
   • Nach dem Training (Post-Processing): Der Computer macht seine Vorhersagen, und dann korrigiert man die Ergebnisse.
     • Analogie: Der Computer schlägt dir 10 Freunde vor. Du schaust dir die Liste an und sagst: "Moment, diese 3 Leute sind alle aus demselben Dorfteil und weit weg von den anderen. Ich streiche sie und nehme stattdessen jemanden aus dem fernen Tal, auch wenn der Computer ihn nicht zuerst genannt hat."

Was haben sie herausgefunden?

• Alte Methoden sind blind: Die bisherigen "fairen" Algorithmen haben oft nur die oberflächliche Ebene (Hop 1) repariert, aber tiefer liegende Ungerechtigkeiten (Hop 3, 4, 5) ignoriert.
• Alles hängt zusammen: Wenn man einen Weg in der Nähe repariert, verändert das oft auch die Situation weiter weg. Man muss vorsichtig sein, wo man eingreift.
• Der Erfolg: Ihr neues "Nachbesserungs-Tool" (Post-Processing) funktioniert sehr gut. Es kann die Ungerechtigkeit in den "fernen" Teilen des Netzes reduzieren, ohne dass die Qualität der Vorhersagen (also ob die vorgeschlagenen Freunde auch wirklich passen) stark leidet.

Fazit

Stell dir vor, du möchtest ein Dorf fair gestalten.

• Die alte Methode sagte: "Verbinde die Leute, die sich gerade gegenüberstehen."
• Diese neue Methode sagt: "Schau dir das ganze Dorf an. Stelle sicher, dass auch die Leute am äußersten Rand des Dorfes einen Weg zu den anderen haben, egal wie weit sie entfernt sind."

Das Ziel ist nicht nur, dass die meisten Verbindungen fair sind, sondern dass jeder im Dorf – egal wo er wohnt – Zugang zu den gleichen Möglichkeiten hat.

Technische Zusammenfassung

1. Problemstellung und Motivation

Hintergrund:
Link Prediction (LP) ist eine zentrale Aufgabe in graphbasierten Anwendungen, insbesondere in sozialen Empfehlungssystemen. Standard-Modelle neigen jedoch dazu, strukturelle Verzerrungen (Bias) in den Daten zu reproduzieren und zu verstärken, insbesondere die Homophilie (die Tendenz ähnlicher Knoten, sich zu verbinden). Dies kann zu „Filterblasen" und der Verstärkung sozialer Ungleichheiten führen.

Limitationen bestehender Ansätze (Dyadic Fairness):
Bisherige faire Link-Prediction-Ansätze basieren meist auf dem Paradigma der dyadischen Fairness. Dieses betrachtet Fairness ausschließlich auf der Ebene von Kanten (Paaren von Knoten) und versucht, Verbindungen zwischen Gruppen mit unterschiedlichen sensiblen Attributen (z. B. Geschlecht, Ethnie) zu fördern, um intra-gruppale Verzerrungen auszugleichen.

Das Kernproblem:
Die Autoren argumentieren, dass dyadische Fairness unzureichend ist, weil sie:

1. Die zugrunde liegende Graphenstruktur ignoriert.
2. Alle inter-gruppalen Kanten als gleichwertig behandelt, unabhängig davon, ob die Knoten bereits gut vernetzt sind oder isoliert liegen.
3. Intra-gruppale Disparitäten übersehen: Nicht alle Knoten innerhalb einer sensiblen Gruppe befinden sich in der gleichen strukturellen Position. Eine reine Fokussierung auf Kanten kann dazu führen, dass bereits gut vernetzte Knoten weiter begünstigt werden, während isolierte Knoten innerhalb derselben Gruppe weiterhin benachteiligt bleiben.

2. Methodik: k-hop Fairness

Die Autoren schlagen ein neues Konzept vor, das Fairness nicht nur auf Kanten, sondern auf der Vielfalt der Vorhersagen innerhalb der k-hop-Nachbarschaften von Knoten definiert.

Definitionen und Metriken:

• k-hop Knoten-Attribut-Exposition ($f^{(k)}_s(v)$): Misst, wie wahrscheinlich es für einen Knoten $v$ ist, Verbindungen zu Knoten mit sensitivem Attribut $s$ in genau $k$ Schritten Entfernung einzugehen.
• k-hop Gruppen-Exposition ($\phi^{(k)}_{s \to s'}$): Aggregiert die lokale Exposition über alle Knoten einer Gruppe $s$, um zu messen, wie gut diese Gruppe Zugang zu Gruppe $s'$ in Entfernung $k$ hat.
• k-hop Nachbarschafts-Fairness Gap ($NF^{(k)}$): Definiert als die maximale Differenz in der Exposition zwischen verschiedenen Zielgruppen für eine Quellgruppe. Ein kleiner Wert bedeutet faire Verteilung der Vorhersagen in der $k$-ten Nachbarschaft.
• k-hop Struktureller Bias ($NB^{(k)}$): Eine rein strukturelle Metrik, die die Ungleichheit in den tatsächlichen $k$-hop-Nachbarschaften des Originalgraphen misst (ohne Vorhersagemodell).

Beziehung zu dyadischer Fairness:
Das Paper zeigt mathematisch, dass die klassische dyadische Metrik ($\Delta DP$) eine gewichtete Summe aller $k$-hop-Expositionen ist. Dies verdeckt jedoch, welche spezifischen Distanzen für den Bias verantwortlich sind, und gewichtet zentralen Knoten übermäßig stark.

Mitigationsstrategien (Bias-Reduktion):
Die Autoren entwickeln Algorithmen zur Minimierung von $NF^{(k)}$ und $NB^{(k)}$:

1. Pre-Processing (Graph-Rewiring): Direkte Modifikation der Adjazenzmatrix $A$. Ein Verlustfunktionsansatz minimiert den strukturellen Bias $NB^{(k)}$ unter Beibehaltung der Fidelity zum Originalgraphen. Dies erfordert differenzierbare Methoden zur Berechnung von $k$-hop-Strukturen (basierend auf Matrixpotenzen).
2. Post-Processing (Vorhersage-Anpassung): Anpassung der Wahrscheinlichkeitsmatrix $P$ des trainierten Modells. Nur Paare mit genau $k$ Schritten Entfernung werden modifiziert, um $NF^{(k)}$ zu minimieren, während die Vorhersagegenauigkeit (Fidelity) durch Regularisierung erhalten bleibt.

Komplexität:
Die Berechnung der Metriken hat eine Komplexität von $O(n^2)$ unter der Annahme sparser Graphen. Die Optimierung für Pre-Processing hat eine Kosten von $O(kn^2)$ pro Iteration.

3. Wichtige Beiträge

1. Einführung von k-hop Fairness: Ein neues, strukturelles Fairness-Paradigma, das Disparitäten in Abhängigkeit von der Entfernung im Graphen bewertet. Es erweitert das dyadische Modell und ist auf gewichtete und gerichtete Graphen sowie multi-valente sensitive Attribute anwendbar.
2. Algorithmische Methoden: Entwicklung von Pre- und Post-Processing-Strategien, die modellunabhängig sind und gezielt Bias in spezifischen Nachbarschaftstiefen ($k$) adressieren können.
3. Empirische Analyse: Umfassende Experimente zeigen, dass strukturelle Verzerrungen auf verschiedenen Hop-Ebenen unterschiedlich stark ausgeprägt sind und dass diese Ebenen voneinander abhängig sind.

4. Ergebnisse

Die Experimente wurden auf realen Datensätzen (Polblogs, Facebook, Pokec, Citeseer) und synthetischen Graphen durchgeführt, verglichen mit Standard-Modellen (Node2Vec, GCN, GraphSAGE) und fairen Baselines (FairWalk, CrossWalk, DeBayes, etc.).

• RQ1: Beziehung zwischen strukturem Bias und Fairness:
  • Es gibt eine starke Korrelation zwischen dem strukturellen Bias ($NB^{(k)}$) und der Vorhersage-Ungerechtigkeit ($NF^{(k)}$).
  • Der Bias ist nicht auf $k=1$ beschränkt; signifikante Verzerrungen treten auch bei höheren Hops (z. B. $k=4$) auf. Eine Aggregation über alle Hops (wie in früheren Arbeiten) ist daher unzureichend.
• RQ2: Abhängigkeiten zwischen Hops:
  • Die Minimierung des Bias bei einem bestimmten $k$ hat komplexe Auswirkungen auf andere Hops. Die Effekte können sich verstärken oder kompensieren. Es gibt keine universelle Lösung; Strategien müssen datenspezifisch sein.
• RQ3: Wirksamkeit der Post-Processing-Methode:
  • Die vorgeschlagene Post-Processing-Methode reduziert den Ziel-Bias ($NF^{(k)}$) signifikant besser als alle existierenden fairen Baselines.
  • Trade-off: Bei $k=1$ (direkte Nachbarn) bleibt die Vorhersagegenauigkeit (AUC) weitgehend erhalten, da Trainingskanten modifiziert werden, die nicht im Test-Set liegen. Bei höheren Hops ($k \ge 2$) kann es zu einem stärkeren Genauigkeitsverlust kommen, da Test-Kanten oft in der Nachbarschaft liegen. Dennoch übertrifft die Methode das Fairness-Performance-Verhältnis bestehender Ansätze.
  • Ein entscheidender Vorteil: Die Post-Processing-Methode garantiert Unabhängigkeit zwischen den Bias-Metriken verschiedener Hops. Die Optimierung für $k$ verschlechtert nicht automatisch die Fairness bei $k' \neq k$.

5. Bedeutung und Fazit

Das Paper leistet einen wesentlichen Beitrag zum Verständnis von Fairness in Graph-Neural-Networks und Link Prediction, indem es den Fokus von der reinen Kanten-Ebene auf die topologische Position der Knoten verlagert.

• Theoretische Bedeutung: Es zeigt auf, dass dyadische Fairness strukturelle Ungleichheiten innerhalb von Gruppen übersehen kann, die für die tatsächliche Chancengleichheit (z. B. Zugang zu Informationen) entscheidend sind.
• Praktische Relevanz: Die vorgestellten Methoden ermöglichen es, gezielt bestimmte Ebenen der Graphenstruktur zu „entzerren", was besonders für Anwendungen wie LinkedIn-Empfehlungen (wo 2- oder 3-hop-Vorschläge üblich sind) relevant ist.
• Limitationen: Der Ansatz basiert auf exakten kürzesten Pfaden, was bei sehr großen Graphen skalierbarkeitskritisch sein kann (Approximationen wären nötig). Zudem ist der Ansatz rein strukturell und berücksichtigt keine Knotenmerkmale (Features), was ein möglicher zukünftiger Forschungsweg ist.

Zusammenfassend etabliert das Paper k-hop Fairness als notwendige Erweiterung des Fairness-Diskurses in Graphen, um tiefgreifendere und strukturierter gerechte Empfehlungssysteme zu entwickeln.