Revealing graph bandits for maximizing local influence

1. Probleemdefinitie

Het artikel behandelt een sequentieel beslissingsprobleem dat bekendstaat als Graph Bandits, specifiek toegespitst op het maximaliseren van lokale invloed in een scenario waarbij de grafstructuur aanvankelijk onbekend is.

• Situatie: De leerder opereert op een graf $G$ met $d$ knopen. In elke ronde $t$ selecteert de leerder een knoop $k_t$.
• Feedback: Bij selectie observeert de leerder een stochastische verzameling $S_{k_t, t}$ van knopen die door $k_t$ beïnvloed zijn. Dit omvat $k_t$ zelf en zijn directe buren. De beïnvloeding is probabilistisch: knoop $i$ beïnvloedt knoop $j$ met een onbekende waarschijnlijkheid $p_{i,j}$.
• Doel: Het doel is om de knoop $k^*$ met de hoogste verwachte invloed (de som van de kansen om alle andere knopen te beïnvloeden, $r_k = \sum_j p_{k,j}$) te identificeren en herhaaldelijk te selecteren binnen een budget van $n$ ronden.
• Regret: De prestatie wordt gemeten aan de hand van regret, gedefinieerd als het verschil tussen de totale invloed van de optimale strategie (met kennis van de graf) en de strategie van de leerder.
• Belangrijke Beperking: In tegenstelling tot eerdere werken die aannemen dat er gedeeltelijke of volledige kennis van de graf is (bijvoorbeeld het kennen van het tweede buurgedeelte of de volledige burenmatrix), gaat deze situatie uit van nul voorafgaande kennis. De graf wordt sequentieel en actief onthuld, uitsluitend via de directe buren van de gekozen knopen.

2. Methodologie: Het BARE-algoritme

De auteurs stellen BARE (Bandit Revelator) voor, een algoritme dat is ontworpen om de grafstructuur en de optimale knoop gelijktijdig te leren zonder de volledige graf te scannen. BARE werkt in twee distincte fasen:

Fase 1: Globale Verkenning

• Doel: Het schatten van de "dual influence" (hoezeer een knoop door anderen wordt beïnvloed, $r^\circ_k = \sum_j p_{j,k}$) en het identificeren van een kleine subset van veelbelovende knopen.
• Mechanisme: Het algoritme selecteert knopen uniform willekeurig.
• Schatten: Het schat de dual influence $\hat{r}^\circ_k$ voor elke knoop op basis van hoe vaak deze voorkomt in de beïnvloedingsverzamelingen van andere willekeurig gekozen knopen.
• Stopcriterium: De fase gaat door totdat een specifieke voorwaarde is vervuld, gedefinieerd door de Detecteerbare Horizon ($T^*$). Deze horizon is de kleinste tijd $t$ zodanig dat de geaccumuleerde informatie toereikend is om de meest invloedrijke knopen te onderscheiden van de rest.
• Selectie van Subset: Op basis van de schattingen filtert BARE de knopen en behoudt alleen diegene die "meest beïnvloedbaar" zijn (d.w.z. een hoge dual influence hebben). Dit creëert een gereduceerde kandidaatset van grootte $\hat{D}^*$.

Fase 2: Bandit-fase

• Doel: Het vinden van de knoop met de maximale uitgaande invloed ($r_k$) binnen de gereduceerde kandidaatset.
• Mechanisme: Het algoritme voert een minimax-optimale bandit-algoritme uit (specifiek een variant van GraphMOSS, aangepast van Audibert & Bubeck) uitsluitend op de subset van knopen die in Fase 1 is geïdentificeerd.
• Redenering: Door de zoekruimte te reduceren van $d$ knopen naar $\hat{D}^*$ knopen, vermijdt het algoritme de lineaire regret die gepaard gaat met het verkennen van een grote graf wanneer $n \ll d$.

3. Belangrijke Theoretische Bijdragen

A. De Detecteerbare Dimensie ($D^*$)

Het artikel introduceert een nieuwe, probleemafhankelijke grootheid genaamd de Detecteerbare Dimensie ($D^*$).

• Definitie: $D^*$ vertegenwoordigt het aantal knopen dat op een "detecteerbare" manier onderscheidend is wat betreft hun invloedeigenschappen ten opzichte van het budget $n$. Het is afgeleid van de functie $D(\Delta)$, die het aantal knopen telt met een dual gap (suboptimaliteit in het beïnvloed worden) kleiner dan $\Delta$.
• Betekenis: In veel real-world netwerken (bijvoorbeeld schaalvrije netwerken) is $D^*$ aanzienlijk kleiner dan het totale aantal knopen $d. Dit stelt de prestaties van het algoritme in staat te schalen met $D^*$ in plaats van met $d$.

B. Regretgrenzen

De auteurs bewijzen dat de verwachte regret van BARE begrensd is door:
$$E[R_n] \leq C \min \left( r^* n, \quad D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^* \right)$$
Waarbij:

• $r^*$ de invloed van de optimale knoop is.
• $D^*$ de detecteerbare dimensie is.
• $\varepsilon^*$ de "invloedrijke-beïnvloedbare gap" is (het verschil tussen de meest invloedrijke knoop en de meest invloedrijke knoop onder de meest beïnvloedbare knopen).
• Optimaliteit: Voor ongerichte grafen (waarbij wederzijdse beïnvloeding geldt, dus $\varepsilon^* = 0$), vereenvoudigt de grens tot $O(D^* r^* + \sqrt{r^* n D^*})$. Dit komt overeen met de minimax optimale snelheid voor een bandit-probleem met slechts $D^*$ armen, wat bewijst dat BARE effectief de dimensionaliteit van het probleem reduceert.

C. Ondergrenzen

Het artikel stelt een ondergrens vast die aantoont dat geen enkel algoritme in het slechtste geval een regret kan bereiken die beter is dan $\Omega(D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^*)$, wat bevestigt dat BARE minimax-optimaal is voor deze situatie.

4. Experimentele Resultaten

De auteurs hebben BARE geëvalueerd op synthetische en real-world datasets:

• Datasets: Barabási-Albert (schaalvrij), Facebook, Enron e-mailnetwerk en Gnutella P2P-netwerk.
• Benchmarks: Vergelijken met GraphMOSS (een standaard graf-bandit-algoritme dat de "onthullende" aspecten negeert en knopen behandelt als onafhankelijke armen totdat de graf volledig bekend is) en een benchmark die alleen het aantal beïnvloede knopen observeert (geen identiteit).
• Vondsten:
  • Prestatie: BARE presteert aanzienlijk beter dan GraphMOSS, vooral wanneer de tijds horizon $n$ kleiner is dan het aantal knopen $d$ ($n \leq d$).
  • Structuurafhankelijkheid: De winst is het meest uitgesproken in netwerken met een duidelijke hiërarchie van invloed (bijvoorbeeld Facebook, Enron) waar $D^*$ klein is. In sterk gedecentraliseerde netwerken (zoals Gnutella) is de winst kleiner, wat overeenkomt met de theorie dat $D^*$ nadert tot $d$.
  • Onthullingswaarschijnlijkheid: Naarmate de waarschijnlijkheid om de beïnvloedingsverzameling waar te nemen toeneemt, groeit het voordeel van BARE, omdat het de dual influence nauwkeuriger kan schatten om de kandidaatset te filteren.

5. Betekenis en Impact

• Praktische Toepasbaarheid: Het werk lost een kritieke beperking op in marketing en sociale-netwerkanalyse. In real-world scenario's kunnen adverteerders niet toegang krijgen tot de volledige sociale graf (privacybeperkingen), maar kunnen ze wel de directe resultaten van hun campagnes observeren (wie het product kocht). BARE biedt een strategie om "influencers" te vinden onder deze strikte informatiebeperkingen.
• Theoretische Vooruitgang: Het gaat voorbij aan de aanname dat de grafstructuur bekend of gedeeltelijk bekend moet zijn om nuttig te zijn. Het demonstreert dat actieve onthulling van de grafstructuur kan worden benut om leersnelheden te bereiken die afhankelijk zijn van de intrinsieke complexiteit ($D^*$) van het probleem in plaats van de ruwe grootte van de graf ($d$).
• Dimensionaliteitsreductie: Het concept van "Detecteerbare Dimensie" biedt een nieuwe lens voor het analyseren van bandit-problemen op grote, onbekende grafen, wat suggereert dat efficiënt leren mogelijk is zelfs zonder volledige grafverkenning.

Kortom, het artikel presenteert BARE, een nieuw algoritme dat efficiënt de meest invloedrijke knoop in een onbekende graf identificeert door lokaal buurgedeelte actief te onthullen, en regretgrenzen bereikt die schalen met de detecteerbare dimensie in plaats van het totale aantal knopen.