Technische Samenvatting: Het leren van de waarschijnlijkheden van peer-invloed met lineaire contextuele bandits

1. Probleemformulering

Het artikel behandelt de uitdaging van het leren van heterogene waarschijnlijkheden van peer-invloed in netwerkomgevingen. In sociale netwerken varieert de waarschijnlijkheid dat een gebruiker (ontvanger) een actie aanneemt na een aanbeveling van een andere gebruiker (afzender) aanzienlijk op basis van knoopattributen, randkenmerken en de netwerkstructuur.

De auteurs formuleren dit als een bi-objectief contextueel multi-armed bandit (CMAB) probleem. De setting betreft een agent die interacteert met een gerichte attribuut-netwerk $G=(V, E)$ over $T$ rondes. In elke ronde:

1. Observeert de agent een pool van kandidaat-randen (interacties).
2. Selecteert de agent een subset van $k$ randen voor interventie (bijv. het tonen van een bericht aan een specifieke set ontvangers).
3. Observeert de agent binaire beloningen (activatie: 1 als de ontvanger handelt, 0 anders).

De kern van de moeilijkheid ligt in het balanceren van twee conflicterende doelstellingen:

• Minimaliseren van Cumulatieve Regret ($Regret_T$): Het maximaliseren van directe beloningen door randen te selecteren met de hoogst geschatte invloeds-waarschijnlijkheden (exploitatie).
• Minimaliseren van Schattingsfout ($RMSE_T$): Het nauwkeurig schatten van de ware invloeds-waarschijnlijkheden voor alle randen in het netwerk, inclus\n bij lage of onzekere invloed (exploratie).

De auteurs stellen dat standaard online leermethoden ofwel middelen verspillen via willekeurige exploratie (lage regret-garanties), ofwel uitsluitend optimaliseren voor beloningen, wat leidt tot hoge schattingsfouten voor randen met een lage waarschijnlijkheid. Daartegenover staan statische methoden die niet in staat zijn om ware invloed te onderscheiden van verstorende factoren zoals homofilie.

2. Methodologie: Influence Contextual Bandit ($InfluenceCB$)

De auteurs stellen $InfluenceCB$ voor, een framework ontworpen om de afweging tussen regret en schattingsfout te navigeren. De methode werkt onder een lineair beloningsmodel waarbij de verwachte beloning voor een rand met contextvector $X$ gelijk is aan $E[r] = X^\top \theta^*$, waarbij $\theta^*$ een onbekende parametervector is.

Kerncomponenten:

1. Onzekerheidsgestuurde Exploratie:

   • De algoritme berekent de schattingsonzekerheid voor kandidaat-randen met behulp van de standaard lineaire bandit onzekerheidsmetriek: $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$, waarbij $V_{t-1}$ de geregulariseerde covariantie-matrix van geobserveerde kenmerken is.
   • Als de maximale onzekerheid in de huidige pool de dynamische drempelwaarde ($C_t / t^\beta$) overschrijdt, gaat het algoritme over naar een exploratiefase, waarbij de top-$k$ randen met de hoogste onzekerheidsscores worden geselecteerd. Dit zorgt ervoor dat randen met een lage waarschijnlijkheid of onzekerheid worden gesampled om de globale schatting te verbeteren.

2. Beloningsgestuurde Exploitatie:

   • Als de onzekerheid onder de drempelwaarde valt, gaat het algoritme over naar een exploitatiefase.
   • Het gebruikt een standaard lineaire CMAB-subroutine (bijv. CombLinUCB) om randen te selecteren die de verwachte directe beloningen maximaliseren, waardoor de regret wordt geminimaliseerd.

3. Afwegingscontrole:

   • Parameter $\beta$: Controleert de asymptotische snelheid van de afweging. Een lagere $\beta$ (bijv. 0,25) geeft prioriteit aan regret-minimalisatie, terwijl een hogere $\beta$ (bijv. 0,5) prioriteit geeft aan de nauwkeurigheid van de schatting (RMSE).
   • Parameter $C_t$: Een adaptieve drempelwaarde die in de loop van de tijd wordt geleerd op basis van activatiesnelheden of onzekerheidsstatistieken, waardoor het systeem de balans tussen exploratie en exploitatie dynamisch kan aanpassen.

3. Theoretische Bijdragen

Het artikel biedt een rigoureuze theoretische analyse die de fundamentele limieten van dit probleem vaststelt:

• Bestaan van een Afweging: De auteurs bewijzen dat geen enkel algoritme tegelijkertijd de optimale snelheden voor zowel cumulatieve regret als de globale schattingsfout kan bereiken.
• Bereikbare Rate-paren: Ze karakteriseren de Pareto-front van bereikbare snelheden. Specifiek, voor elk beleid $\pi$, als de regret schaalt als $O(T^{2\beta})$, dan moet de RMSE schalen als $\Omega(T^{-\beta})$, waarbij $\beta \in [1/4, 1/2]$.
  • Optimale regret ($\beta=1/4$) impliceert een suboptimale RMSE ($\Omega(T^{-1/4})$).
  • Optimale RMSE ($\beta=1/2$) impliceert lineaire regret.
• Bereikbaarheid: Theorem 5.1 demonstreert dat $InfluenceCB$ elk punt op deze Pareto-front kan bereiken door de parameter $\beta$ af te stemmen, waarbij de volgende grenzen worden voldaan:
  $$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$$

4. Experimentele Resultaten

De auteurs evalueerden $InfluenceCB$ op drie semi-synthetische datasets afgeleid van echte netwerken: BlogCatalog, Flickr en Hateful (Twitter). De grondwaarheid van de invloeds-waarschijnlijkheden werd synthetisch gegenereerd op basis van lineaire combinaties van knoop- en randkenmerken.

Baselines:

• Statische Modellen: Random, Similarity, Link Prediction (Ridge, GraphSAGE, NCNC), en een SOTA Recommender (ContextGNN).
• Online Learning: SGD-gebaseerde exploitatie- en exploratievarianten.
• Contextuele Bandits: LinUCB, EENet, Graph Neural Bandits (GNB), en Takemura et al. (combinatorial semi-bandit).

Belangrijkste Bevindingen:

• Expansie van de Pareto-front: $InfluenceCB$ breidt de Pareto-front uit voorbij alle baselines. Terwijl standaard bandits (zoals LinUCB) optimaliseren voor regret, vertonen zij hogere schattingsfouten. Statische modellen presteren slecht op beide metrieken.
• Afstembare Afwegingen: Door $\beta$ aan te passen, kan $InfluenceCB$ de RMSE aanzienlijk verminderen (tot ~60% op Flickr) ten koste van verhoogde regret, of de regret minimaliseren (waardoor het LinUCB met ~5-10% overtreft) met een lichte toename in RMSE.
• Parametergevoeligheid: De parameter $C$ (drempelwaarde) heeft een aanzienlijke impact op de afweging. Het adaptieve leren van $C$ stelt het algoritme in staat om een balans te vinden zonder handmatige afstemming voor specifieke toepassingsbehoeften.
• Robuustheid: De methode behoudt een concurrerende prestatie in ranking-metrieken (NDCG@k) en kalibratiefout (ECE) over verschillende netwerkinstellingen (netwerk-gebaseerde versus buur-gebaseerde randselectie).

5. Betekenis en Claims

Het artikel claimt de eerste te zijn die het leren van de waarschijnlijkheden van peer-invloed expliciet formuleert als een onafhankelijk bi-objectief probleem, verschillend van invloedmaximalisatie of aanbevelingstaken waarbij waarschijnlijkheden als bekend of secundair worden beschouwd.

• Theoretisch Inzicht: Het stelt vast dat het minimaliseren van regret en het minimaliseren van de globale schattingsfout fundamenteel conflicterende doelstellingen zijn in netwerk-gebaseerde bandit-settings, een afweging die voorheen niet gekarakteriseerd was in deze specifieke context.
• Praktisch Nut: Het framework stelt beoefenaars in staat om expliciet een beleid te kiezen dat is afgestemd op hun prioriteiten. Zo kan een virale marketingcampagne prioriteit geven aan regret (directe verkopen), terwijl een beleidsaudit of diffusie-simulatie prioriteit kan geven aan RMSE (nauwkeurige globale invloeds-kaarten).
• Beperkingen en Toekomstig Werk: De auteurs merken op dat hun huidige analyse uitgaat van onafhankelijke Bernoulli-activaties en geen complexe interferentie-effecten modelleert (bijv. cumulatieve blootstelling aan meerdere buren). Toekomstig werk wordt gesuggereerd om het framework uit te breiden naar niet-lineaire settings en dynamische of gedeeltelijk geobserveerde netwerken.

Samenvattend biedt $InfluenceCB$ een geprincipeerd mechanisme om de spanning te navigeren tussen het leren van nauwkeurige invloeds-modellen en het maximaliseren van directe netwerkinterventies, wat een flexibele tool biedt voor besluitvorming in netwerken.