How Predicted Links Influence Network Evolution: Disentangling Choice and Algorithmic Feedback in Dynamic Graphs

Deze studie introduceert een tijdsgebonden raamwerk op basis van multivariate Hawkes-processen om het onderscheid te maken tussen intrinsieke interactietendensen en algorithmische feedback in dynamische netwerken, en biedt een nieuwe maatstaf voor directe versterkingseffecten die betrouwbaarder is dan cumulatieve metrics.

De kern

Titel: Waarom de "Vriendenlijst" van je algoritme je wereld kleiner maakt (en hoe we dat kunnen oplossen)

Stel je voor dat je in een enorme, levende stad woont. In deze stad zijn er twee grote groepen mensen: de Roodshoedjes en de Blauwhoedjes. Normaal gesproken praten mensen het liefst met anderen die op hen lijken (Rood met Rood, Blauw met Blauw). Dit noemen we keuze-homofofie: mensen kiezen gewoon hun eigen soort.

Maar nu komt er een nieuwe, slimme stadswachter (het algoritme) die je helpt nieuwe vrienden te vinden. Deze wachter kijkt naar wie je al kent en zegt: "Hey, jij bent Rood, dus ik raad je aan om met die andere Roodshoedjes te praten, want dat lijkt me leuk!"

Dit klinkt onschuldig, maar het heeft een groot probleem. De stadswachter maakt de bestaande voorkeur niet alleen zichtbaar, hij versterkt hem. Hierdoor praten de Roodshoedjes steeds minder met de Blauwhoedjes, en scheiden de groepen zich steeds meer af. Dit noemen we geïnduceerde homofofie: de scheiding wordt veroorzaakt door de machine, niet alleen door de mensen zelf.

Het probleem met de oude meetlat

Tot nu toe keken onderzoekers naar deze stad alsof het een foto was. Ze namen een momentopname: "Kijk, er zijn veel Rood-Rood vriendschappen."
Het probleem? Een foto vertelt je niet waarom dat zo is.

• Is het omdat Roodshoedjes elkaar echt leuker vinden? (De keuze)
• Of is het omdat de stadswachter ze constant naar elkaar heeft verwezen? (Het algoritme)

Als je alleen naar de foto kijkt, kun je die twee oorzaken niet uit elkaar halen. En als je denkt dat het alleen aan de mensen ligt, probeer je het probleem niet op te lossen.

De nieuwe oplossing: Een live-video in plaats van een foto

De auteurs van dit paper (Mathilde, Raphaël, Jefrey en Charlotte) zeggen: "We moeten stoppen met kijken naar foto's en beginnen met kijken naar een live-video."

Ze gebruiken een slim wiskundig model (een Hawkes-proces) dat werkt als een geluidsdetectie-app.

• De Basis (Keuze): Dit is het geluid dat mensen van nature maken als ze praten.
• De Echo (Algoritme): Dit is het geluid dat terugkaatst en steeds luider wordt. Als iemand iets zegt, en de echo is luid, dan gaan mensen dat nog vaker zeggen.

Met hun nieuwe model kunnen ze precies zien: "Ah, dit gesprek is 20% omdat ze elkaar leuk vinden, en 80% omdat de stadswachter (het algoritme) ze er constant aan herinnert."

De nieuwe meetlat: De "Huidige Sfeer"

Ze hebben ook een nieuwe manier bedacht om de sfeer in de stad te meten.

• De oude meetlat (Cumulatief): Telt alle gesprekken die er ooit zijn geweest. Dit is traag. Als de stadswachter morgen stopt met scheiden, duurt het jaren voordat de oude telling daalt. Het is alsof je de temperatuur meet met een ijsklontje dat smelt: het duurt lang voordat je merkt dat het warm is.
• De nieuwe meetlat (Instantane): Meet de huidige drukte op het moment zelf. Het is alsof je een thermometer hebt die direct reageert. Zodra de stadswachter stopt met scheiden, zie je de temperatuur (de scheiding) direct zakken. Dit laat zien wat er nu gebeurt, niet wat er in het verleden is gebeurd.

Wat hebben ze ontdekt?

Ze hebben dit getest in een digitale stad (een simulatie) en op echte data van Twitter (over de Duitse verkiezingen).

1. Algoritmes versterken de scheiding: Zelfs als je een eerlijk algoritme probeert te maken, kan het door de feedbacklus (het "echo-effect") toch leiden tot meer scheiding op de lange termijn.
2. Hertraining is een tweesnijdend zwaard: Als je het algoritme vaak opnieuw traint (leren van de nieuwe vriendschappen), kan het de scheiding juist verergeren, omdat het steeds meer leert van de gescheiden wereld die het zelf heeft gecreëerd.
3. De nieuwe meetlat werkt: Hun nieuwe manier van meten (de "huidige sfeer") laat veel sneller zien of een algoritme eerlijk is of niet, dan de oude methoden.

De les voor ons allemaal

Dit paper vertelt ons dat we niet alleen moeten kijken naar het resultaat (de foto), maar naar het proces (de video). Als we algoritmes gebruiken om ons te helpen kiezen, moeten we beseffen dat deze keuzes de wereld om ons heen veranderen.

Het is alsof je een spiegel hebt die niet alleen je gezicht laat zien, maar ook je houding beïnvloedt. Als je in de spiegel ziet dat je boos bent, en de spiegel maakt je bozer, dan moet je de spiegel niet alleen "boos" noemen, maar de spiegel zelf aanpassen.

Kortom: Om eerlijke netwerken te bouwen, moeten we begrijpen dat algoritmes niet alleen kijken naar wat er gebeurt, maar ook maken wat er gebeurt. En we hebben een nieuwe, snellere meetlat nodig om te zien of die algoritmes ons dichter bij elkaar brengen, of juist verder uit elkaar.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "How Predicted Links Influence Network Evolution: Disentangling Choice and Algorithmic Feedback in Dynamic Graphs" in het Nederlands.

1. Probleemstelling

Link-predictiemodellen worden steeds vaker gebruikt om interacties in evoluerende netwerken (zoals sociale media) aan te bevelen. Een groot probleem is dat de impact van deze algoritmen op de netwerkstructuur vaak wordt geëvalueerd aan de hand van statische momentopnamen. Dit leidt tot een verward beeld van homofilie (de neiging van vergelijkbare individuen om verbindingen aan te gaan).

De auteurs identificeren twee bronnen van homofilie die in bestaande studies vaak worden verward:

• Keuze-homofilie (Choice Homophily): De intrinsieke neiging van individuen om verbindingen aan te gaan op basis van hun eigen kenmerken (demografie, interesses), onafhankelijk van het netwerk.
• Geïnduceerde homofilie (Induced Homophily): Homofilie die wordt veroorzaakt of versterkt door de systeemstructuur, tijdsdynamiek en vooral door algoritmische feedback (bijv. aanbevelingen die zichtbaarheid creëren).

Bestaande methoden kunnen niet onderscheiden of een toename in homofilie komt door de oorspronkelijke voorkeuren van gebruikers of door een "feedback-lus" waarbij het algoritme bestaande patronen versterkt. Dit maakt het moeilijk om eerlijkheid (fairness) in graf-gebaseerd leren correct te evalueren en te verbeteren.

2. Methodologie

De auteurs stellen een temporeel raamwerk voor dat gebaseerd is op multivariate Hawkes-processen. Dit is een klasse van zelfopwekkende tijdstochastische processen waarbij eerdere gebeurtenissen de kans op toekomstige gebeurtenissen vergroten.

Kerncomponenten van het model:

• Groep-gestructureerde Hawkes-processen: Het netwerk wordt gemodelleerd als een reeks activeringsgebeurtenissen van randen. De intensiteit van interacties tussen groepen $i$ en $j$ wordt bepaald door:
  1. Een baseline intensiteit ($\mu_{ij}$): Dit vertegenwoordigt de intrinsieke (keuze) homofilie.
  2. Een excitatiekern ($\phi$): Dit modelleert hoe eerdere interacties (en aanbevelingen) de toekomstige intensiteit beïnvloeden. De excitatiesterkte ($\alpha$) kan worden gekoppeld aan de scores van een link-predictiemodel.
• Instantane Bias-maatstaf ($B_{inst}$): In plaats van cumulatieve tellingen van randen (empirische bias), introduceren de auteurs een maatstaf gebaseerd op de huidige intensiteit van interacties:
  $$B_{inst}(t) = \frac{\lambda_w(t)}{\lambda_w(t) + \lambda_c(t)}$$
  Waar $\lambda_w$ en $\lambda_c$ respectievelijk de geaggregeerde intensiteiten voor binnen-groep en tussen-groep interacties zijn.
  • Voordeel: Deze maatstaf reageert direct op veranderingen in het systeem (zoals een update van het algoritme) en isoleert de geïnduceerde dynamiek van de historische cumulatieve data.

Theoretische Analyse:
De auteurs gebruiken een mean-field benadering om de stochastische dynamiek te benaderen door deterministische integralvergelijkingen. Hiermee analyseren ze de stabiliteit en convergentie van het systeem:

• Ze tonen aan dat het systeem convergeert naar een stationaire toestand als de spectrale straal van de excitatiematrix ($\rho(A/\beta)$) kleiner is dan 1.
• Ze bewijzen dat de convergentie exponentieel verloopt, wat impliceert dat fairness-interventies tijd nodig hebben om hun effect te laten zien en dat statische metingen misleidend kunnen zijn tijdens transiënte fasen.

3. Belangrijkste Bijdragen

1. Scheiding van bronnen: Een model dat expliciet onderscheid maakt tussen intrinsieke interactievoorkeuren en versterkingseffecten veroorzaakt door algoritmen.
2. Nieuwe Maatstaf: De introductie van $B_{inst}$, een instantane bias-maatstaf die de huidige structurele neigingen van het systeem weergeeft, in plaats van een verouderde cumulatieve telling.
3. Theoretische Karakterisering: Een analyse van de stabiliteit en convergentiesnelheid van homofilie onder verschillende feedback-regimes, wat inzicht geeft in wanneer fairness-metingen betrouwbaar zijn.
4. Empirische Validatie: Experimenten die aantonen dat verschillende link-predictiestrategieën (zowel eerlijke als niet-eerlijke) leiden tot fundamenteel verschillende langetermijneffecten op de netwerkstructuur.

4. Resultaten

De auteurs voerden experimenten uit op zowel gesimuleerde data als een real-world dataset (Twitter/X tijdens de Duitse verkiezingen van 2021).

• Validatie van $B_{inst}$: In simulaties reageerde $B_{inst}$ onmiddellijk op veranderingen in het systeem (bijv. het starten van een link-predictiemodel), terwijl de traditionele cumulatieve bias ($B_{emp}$) traag was en veranderingen "uitgladde".
• Impact van Fairness-strategieën:
  • Niet-eerlijke modellen (bijv. GCN, Node2Vec): Versterkten binnen-groep interacties sterk, wat leidde tot een hoge $B_{inst}$ en een toename van segregatie.
  • Eerlijke modellen (bijv. FairDrop, DeBayes, CrossWalk): Leidden tot een lagere $B_{inst}$ en meer kruisgroepsinteracties.
  • Retraining: Periodiek hertrainen van modellen (zonder fairness-beperkingen) versterkte de homofilie aanzienlijk, wat aantoont dat dynamische feedback loops bias kunnen opschalen.
• Real-world Toepassing: Op de Twitter-dataset toonde $B_{inst}$ een duidelijke piek in polarisatie voorafgaand aan de verkiezingen, wat overeenkwam met een tijdelijke versterking van binnen-groep zelf-excitatie.

5. Betekenis en Conclusie

Dit onderzoek heeft belangrijke implicaties voor het ontwerpen en evalueren van eerlijke graf-neurale netwerken en aanbevelingssystemen:

• Statische metingen zijn onvoldoende: Het evalueren van eerlijkheid op een statisch moment kan misleidend zijn omdat het de dynamische feedback-lus negeert. Een model dat op het eerste gezicht eerlijk lijkt, kan op de lange termijn bias versterken.
• Tijdsdynamiek is cruciaal: Fairness-interventies hebben vaak vertraagde effecten. De snelheid van convergentie naar een evenwichtstoestand bepaalt hoe snel we het effect van een interventie kunnen meten.
• Design-implicatie: Ontwikkelaars moeten rekening houden met hoe hun voorspellingen de toekomstige netwerkstructuur vormen. Het gebruik van instantane bias-maatstaven zoals $B_{inst}$ biedt een robuustere manier om de langetermijneffecten van algoritmen op sociale segregatie te monitoren.

Kortom, de paper pleit voor een verschuiving van statische naar dynamische evaluaties van eerlijkheid in netwerken, waarbij het onderscheid tussen menselijke keuze en algoritmische versterking centraal staat.