Contextual Bandits for Maximizing Stimulated Word-of-Mouth Rewards

Technische Zusammenfassung: Kontextuelle Banditen zur Maximierung von stimuliertem Word-of-Mouth-Ertrag

Problemdefinition
Die vorliegende Arbeit befasst sich mit der Herausforderung, den stimulierten Word-of-Mouth (WOM) in sozialen Netzwerken zu optimieren. Im Gegensatz zu organischem WOM basiert stimulierter WOM auf Anreizen (z. B. Belohnungen, Rabatten), um Nutzer dazu zu bewegen, Informationen zu teilen. Das Kernproblem liegt in der Heterogenität des Netzwerk-Spillovers: Die Wahrscheinlichkeit, dass eine Empfehlung eines durch das System aktivierten Nutzers $v_i$ einen Nachbarn $v_j$ zur Übernahme des Produkts beeinflusst, variiert signifikant über verschiedene Nutzerpaare und Netzwerkpositionen hinweg.

In der bestehenden Literatur wird oft davon ausgegangen, dass Spillover-Wahrscheinlichkeiten bekannt sind, oder es liegt der Fokus auf allgemeiner Einflussmaximierung ohne das Lernen individueller Kantenwahrscheinlichkeiten. Diese Arbeit identifiziert eine Lücke, in der aktuelle Strategien für stimulierten WOM diese variierenden Spillover-Effekte vernachlässigen, was zu suboptimalem Targeting führt. Das spezifisch formulierte Problem ist die Vorhersage der Spillover-Wahrscheinlichkeit für die Top-$k$-Nachbar-Empfehlung: Gegeben ein attribuierter Graph $G=(V, E)$, muss das System über $T$ Runden hinweg die Spillover-Wahrscheinlichkeit $e_{ij}.p$ für Kanten lernen, um die Top-$k$-Nachbarn zu empfehlen, die am wahrscheinlichsten aktiviert werden, um den kumulativen Ertrag zu maximieren.

Methodik: SpillCB-Framework
Die Autoren schlagen SpillCB vor, ein neuartiges Kontextuelles Multi-Armed-Bandit (CMAB)-Framework, das darauf ausgelegt ist, individuelle Spillover-Wahrscheinlichkeiten in einem Online-Szenario zu lernen.

• Datenmodell: Das Netzwerk wird als bidirektionaler attribuierter Graph dargestellt, wobei die Knoten Attributvektoren ($v.X$) besitzen. Der Kontext für eine Kante $e_{ij}$ ist definiert als die Konkatenation der Attribute des Quellknotens $v_i$, des Zielnachbarn $v_j$ und relevanter Produktattribute.
• Bandit-Formulierung: Das Problem wird als stochastischer 2-Arm-Bandit für jede Kante modelliert:
  • Arm $a_0$: Keinen Nachbarn empfehlen.
  • Arm $a_1$: Den Nachbarn $v_j$ dem systemaktivierten Knoten $v_i$ empfehlen.
  • Belohnung (Reward): Eine binäre Belohnung (1 oder 0) wird generiert, falls der empfohlene Nachbar $v_j$ aufgrund des Spillovers aktiviert wird. Die Belohnung ist eine Funktion des Kontextvektors und der Aktion, zuzüglich Rauschen.
• Lernstrategie: Das Framework operiert über zwei Phasen über $T$ Runden:
  1. Exploration: Für einen anfänglichen Bruchteil ($z\%$) der Runden werden $k$ Nachbarn zufällig ausgewählt, um die Auswahl der Kanten zu diversifizieren und Daten zu sammeln.
  2. Exploitation: In den darauffolgenden Runden wählt der Algorithmus die Top-$k$-Nachbarn basierend auf den geschätzten erwarteten Belohnungen von Arm $a_1$, die durch den zugrunde liegenden CMAB-Algorithmus vorhergesagt werden.
• Algorithmen: Das Framework ist agnostisch gegenüber dem spezifischen CMAB-Solver, wird jedoch unter Verwendung von LinUCB und EENet evaluiert. Das Ziel ist die Minimierung des kumulativen Regrets, definiert als die Differenz zwischen den Belohnungen der optimalen Top-$k$-Menge und der ausgewählten Menge.

Experimentelles Setup und Ergebnisse
Die Autoren evaluierten SpillCB auf zwei realen attribuerten Netzwerk-Datensätzen: Flickr und Facebook. Die Spillover-Wahrscheinlichkeiten wurden synthetisch generiert, basierend auf einer gewichteten Funktion der Kosinus-Ähnlichkeit, Level-Ähnlichkeit, topologischen Überlappung, Diffusions-Wichtigkeit und dem Gradprodukt.

• Baselines: Die vorgeschlagene Methode wurde mit folgenden Verfahren verglichen:
  • Random: Zufällige Auswahl von $k$ Nachbarn.
  • Similarity-based: Auswahl basierend auf der euklidischen Distanz der Attributvektoren.
  • Ridge Regression: Vorhersage von Kantengewichten mittels Ridge-Regression auf gelabelten Kanten.
  • GraphSage: Vorhersage von Kantengewichten mittels Knoteneinbettungen und einer neuronalen Netzwerk-Scoring-Funktion.
• Metriken: Die Leistung wurde mittels Recall@k (Fähigkeit, die wahren Top-$k$-Nachbarn zu identifizieren) und dem Root Mean Squared Error (RMSE) der gelernten Spillover-Wahrscheinlichkeiten gemessen.
• Kernergebnisse:
  • SpillCB-Varianten (SpillCBLinUCB und SpillCBEENet) übertrafen alle Baseline-Methoden konsistent im Recall@k über variierende Werte von $k$ (5 bis 25) auf beiden Datensätzen.
  • Ein steigendes $k$ reduzierte im Allgemeinen den RMSE, da es die Exploration von mehr Kanten ermöglichte und somit den Lernprozess beschleunigte.
  • Es wurde ein Trade-off zwischen der Explorationsrate ($z$) und der Performance beobachtet: Eine Erhöhung der Exploration von 0 % auf 20 % reduzierte den RMSE (verbesserte die Genauigkeit der Wahrscheinlichkeitsschätzung), verringerte jedoch leicht den Recall@10 in der finalen Runde.
  • Mit zunehmender Anzahl der Runden ($T$) verbesserte sich der Recall@10 und der RMSE sank, was die Effektivität des Online-Lernansatzes demonstriert.

Bedeutung und Ansprüche
Die Autoren behaupten, eine vorläufige Arbeit zu präsentieren, die kontextuelle Multi-Armed-Banditen nutzt, um heterogene Spillover-Effekte zu schätzen – ein Faktor, der in der Optimierung von stimuliertem WOM oft übersehen wird. Der primäre Beitrag ist ein Framework, das individuelle Spillover-Wahrscheinlichkeiten lernt, anstatt davon auszugehen, dass diese bekannt sind.

Die Autoren führen an, dass die Berücksichtigung der Spillover-Heterogenität die Zielgenauigkeit der Top-$k$-vernetzten Nutzer erhöht, die Belohnungen steigert und Methoden übertrifft, die keine individuellen Spillover-Effekte lernen. Die Arbeit zielt darauf ab, die Effektivität von Empfehlungssystemen zu verbessern, indem sie personalisiertere Nutzererlebnisse bietet und die WOM-Belohnungen maximiert. Die Autoren bleiben hinsichtlich ihrer Ansprüche bescheiden und merken an, dass die Ergebnisse vorläufig sind und zukünftige Arbeiten darauf abzielen werden, den Ansatz auf mehr Datensätze und Baselines zu testen, um die Stärken und Grenzen des Ansatzes weiter zu verstehen.