🤖 machine learning

Learning Peer Influence Probabilities with Linear Contextual Bandits

Diese Arbeit adressiert die Herausforderung des Lernens heterogener Peer-Einflusswahrscheinlichkeiten in vernetzten Umgebungen durch die Einführung eines kontextuellen Linear-Bandit-Frameworks, das den grundlegenden Kompromiss zwischen Regret-Minimierung und Schätzfehler charakterisiert, und schlägt einen Unsicherheits-gesteuerten Algorithmus vor, um eine optimale Leistung über dieses Spektrum hinweg zu erzielen.

Ursprüngliche Autoren: Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

Veröffentlicht 2026-06-29

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Stellen Sie sich vor, Sie sind der Manager eines riesigen Social Clubs, in dem Mitglieder ständig Neuigkeiten, Produkte oder Ideen mit ihren Freunden teilen. Ihr Ziel ist es herauszufinden, wer wen beeinflusst. Führt Alices Empfehlung dazu, dass Bob ein neues Handy kauft? Veranlasst Charlies Post Dave dazu, zu einem Konzert zu gehen?

Das Problem ist, dass Einfluss schwierig zu greifen ist. Manchmal teilen Menschen Dinge, weil sie sich ähnlich sind (Homophilie), und nicht, weil einer den anderen tatsächlich überzeugt hat. Und wenn man einfach nur beobachtet, was passiert, kann man nicht zwischen „Alice hat Bob überzeugt“ und „Alice und Bob mögen einfach die gleichen Dinge“ unterscheiden.

Um dieses Problem zu lösen, schlagen die Autoren dieser Arbeit einen neuen Weg vor, diese Einflusswahrscheinlichkeiten zu erlernen, indem sie diese aktiv testen – wie ein Wissenschaftler, der Experimente durchführt, anstatt nur zuzusehen.

Hier ist die Kernidee, unterteilt in einfache Konzepte:

1. Die zwei gegensätzlichen Ziele (Das „Tauziehen“)

Die Forscher haben entdeckt, dass man nicht auf zwei Hochzeiten gleichzeitig tanzen kann. Man steckt in einem Tauziehen zwischen zwei Zielen fest:

Ziel A: Ein guter Verkäufer sein (Regret minimieren). Man möchte Empfehlungen an die Menschen geben, die im Moment am wahrscheinlichsten mit „Ja“ antworten werden. Dies maximiert den unmittelbaren Erfolg.
Ziel B: Ein guter Detektiv sein (Schätzfehler minimieren). Man möchte die wahren Einflusswahrscheinlichkeiten für alle lernen, selbst für die Menschen, die selten „Ja“ sagen. Um dies zu tun, muss man Menschen testen, bei denen man sich unsicher ist, was bedeutet, dass man vielleicht einige unmittelbare Verkäufe verpasst.

Die Analogie: Stellen Sie sich einen Lehrer vor, der herausfinden will, welche Schüler eine Prüfung bestehen werden.

Wenn er nur Übungstests an die Schüler gibt, die bereits Spitzenreiter sind (Ziel A), erzielt er sofort gute Ergebnisse, lernt aber nie, ob die schwächeren Schüler das Material tatsächlich verstehen oder einfach nur mehr Hilfe benötigen.
Wenn er jeden Schüler einen Übungstest machen lässt, einschließlich derer, die normalerweise durchfallen würden (Ziel B), erhält er eine perfekte Karte darüber, wer was weiß, aber sein Klassendurchschnitt (sein „Regret“) sinkt, weil er Zeit damit verschwendet hat, Menschen zu testen, die es nicht nötig hatten.

Das Papier beweist mathematisch, dass keine einzelne Strategie gleichzeitig perfekt bei beiden Zielen sein kann. Man muss eine Balance wählen.

2. Die Lösung: Der „Influence Contextual Bandit“ (InfluenceCB)

Die Autoren haben ein intelligentes System namens InfluenceCB entwickelt, das wie ein flexibler Schalter funktioniert. Es ermöglicht Ihnen, an einem Regler zu drehen, um zu entscheiden, wie viel Sie ein „Verkäufer“ versus ein „Detektiv“ sein wollen.

Der Regler (Parameter $\beta$ ):
- Wenn Sie den Regler in Richtung Regret drehen, agiert das System wie ein vorsichtiger Verkäufer. Es zeigt Empfehlungen hauptsächlich den Menschen, von denen es glaubt, dass sie „Ja“ sagen werden, um die unmittelbare Erfolgsquote hoch zu halten.
- Wenn Sie den Regler in Richtung RMSE (Fehler) drehen, agiert das System wie ein neugieriger Detektiv. Es zeigt absichtlich Empfehlungen an unsichere oder leistungsschwächere Menschen, um mehr Daten zu sammeln und die Wahrheit zu lernen, auch wenn dies bedeutet, weniger unmittelbare „Ja“-Antworten zu erhalten.
Die Unsicherheitsanzeige: Das System prüft ständig: „Wie unsicher bin ich mir über diese spezifische Freundschaft?“ Wenn die Unsicherheit zu hoch ist, erzwingt es ein Experiment (Exploration). Wenn es sich sicher ist, folgt es einfach dem Fluss (Exploitation).

3. Wie sie es getestet haben

Sie haben nicht nur geraten; sie haben Simulationen mit realen Social-Network-Daten (wie Blogs, Foto-Sharing-Seiten und Twitter-Netzwerke) durchgeführt. Sie haben eine fiktive Welt erschaffen, in der sie die „wahren“ Einflusswahrscheinlichkeiten kannten, und dann ihren Algorithmus versuchen lassen, diese zu lernen.

Die Ergebnisse:

Alte Methoden (Statisch): Diese waren wie der Blick auf ein Foto der Vergangenheit. Sie waren zwar gut im Schätzen, konnten aber nichts Neues lernen.
Standard Bandits: Diese waren wie Verkäufer, die nur mit den beliebtesten Menschen sprechen. Sie erzielten gute unmittelbare Ergebnisse, hatten aber ein sehr verschwommenes Bild des gesamten Netzwerks.
Ihre Methode (InfluenceCB): Dies war der Gewinner. Indem sie ihren Regler anpassten, konnten sie eine perfekte Kurve (die sogenannte Pareto-Frontier) zeichnen.
- Wenn der Kunde die besten unmittelbaren Ergebnisse wollte, lieferte InfluenceCB die bestmöglichen Ergebnisse, während es gleichzeitig lernte.
- Wenn der Kunde die genaueste Karte des Einflusses wollte, lieferte InfluenceCB die genaueste Karte, während es gleichzeitig ordentliche Ergebnisse erzielte.

4. Die wichtigste Erkenntnis

Der Hauptbeitrag des Papers ist der Beweis dafür, dass das Lernen von Einfluss ein Balanceakt ist. Man kann nicht einfach den unmittelbaren Profit optimieren und gleichzeitig erwarten, die Wahrheit zu lernen, und man kann nicht versuchen, alles zu lernen, ohne seine Leistung zu beeinträchtigen.

Ihr neues Werkzeug, InfluenceCB, gibt Ihnen das Lenkrad in die Hand. Es lässt Sie genau entscheiden, wie viel Sie in jedem Moment explorieren (lernen) oder exploitieren (verdienen) wollen, um sicherzustellen, dass Sie das bestmögliche Ergebnis für Ihre spezifischen Bedürfnisse erzielen – sei es beim Betrieb einer viralen Marketingkampagne oder einfach beim Verständnis, wie Informationen durch eine Gemeinschaft fließen.

Kurz gesagt: Sie haben einen intelligenten Algorithmus entwickelt, der weiß, dass er nicht in allem perfekt sein kann, und der es Ihnen ermöglicht, genau zu wählen, in welchem Bereich er unvollkommen sein soll, um im anderen Bereich perfekt zu sein.

Technisches Resümee: Lernen von Peer-Einflussprobabilitäten mit Linearen Kontextuellen Banditen

1. Problemformulierung

Die Arbeit befasst sich mit der Herausforderung, heterogene Peer-Einflussprobabilitäten in vernetzten Umgebungen zu erlernen. In sozialen Netzwerken variiert die Wahrscheinlichkeit, dass ein Nutzer (Empfänger) eine Aktion nach Erhalt einer Empfehlung von einem anderen Nutzer (Sender) annimmt, signifikant basierend auf Knotenattributen, Kantencharakteristika und der Netzwerkstruktur.

Die Autoren formulieren dies als ein bi-objektives kontextuelles Multi-Armed-Bandit-Problem (CMAB). Das Setting beinhaltet einen Agenten, der über $T$ Runden mit einem gerichteten, attributierten Netzwerk $G=(V, E)$ interagiert. In jeder Runde:

Beobachtet der Agent einen Pool von Kandidatenkanten (Interaktionen).
Wählt der Agent eine Teilmenge von $k$ Kanten für eine Intervention aus (z. B. das Anzeigen eines Beitrags für eine bestimmte Menge von Empfängern).
Beobachtet der Agent binäre Belohnungen (Aktivierung: 1, wenn der Empfänger handelt, 0 andernfalls).

Die zentrale Schwierigkeit liegt in der Abwägung zweier gegensätzlicher Ziele:

Minimierung des kumulativen Regrets ( $Regret_T$ ): Maximierung unmittelbarer Belohnungen durch Auswahl von Kanten mit den höchsten geschätzten Einflusswahrscheinlichkeiten (Exploitation).
Minimierung des Schätzfehlers ( $RMSE_T$ ): Genaue Schätzung der wahren Einflusswahrscheinlichkeiten für alle Kanten im Netzwerk, einschließlich jener mit geringer oder unsicherer Wahrscheinlichkeit (Exploration).

Die Arbeit argumenttiert, dass Standardmethoden des Online-Learnings entweder Ressourcen durch zufällige Exploration verschwenden (geringe Regret-Garantien) oder ausschließlich auf Belohnungen optimieren, was zu hohen Schätzfehlern für Kanten mit geringer Wahrscheinlichkeit führt. Im Gegensatz dazu scheitern statische Methoden daran, den wahren Einfluss von Störfaktoren wie Homophilie zu entkoppeln.

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

Die Autoren schlagen $InfluenceCB$ vor, ein Framework, das darauf ausgelegt ist, den Kompromiss zwischen Regret und Schätzfehler zu navigieren. Die Methode operiert unter einem linearen Belohnungsmodell, bei dem die erwartete Belohnung für eine Kante mit Kontextvektor $X$ gleich $E[r] = X^\top \theta^*$ ist, wobei $\theta^*$ ein unbekannter Parametervektor ist.

Kernkomponenten:

Unsicherheit gesteuerte Exploration:
- Der Algorithmus berechnet die Schätzunsicherheit für Kandidatenkanten unter Verwendung der Standardmetrik für lineare Banditen: $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$ , wobei $V_{t-1}$ die regularisierte Kovarianzmatrix der beobachteten Merkmale ist.
- Wenn die maximale Unsicherheit im aktuellen Pool einen dynamischen Schwellenwert ( $C_t / t^\beta$ ) überschreitet, tritt der Algorithmus in eine Explorationsphase ein und wählt die Top- $k$ Kanten mit den höchsten Unsicherheitsscores aus. Dies stellt sicher, dass Kanten mit geringer Wahrscheinlichkeit oder hoher Unsicherheit beprobt werden, um die globale Schätzung zu verbessern.
Belohnung gesteuerte Exploitation:
- Wenn die Unsicherheit unter den Schwellenwert fällt, tritt der Algorithmus in eine Exploitationsphase ein.
- Er verwendet eine Standard-lineare CMAB-Subroutine (z. B. CombLinUCB), um Kanten auszuwählen, die die erwarteten unmittelbaren Belohnungen maximieren, wodurch der Regret minimiert wird.
Trade-off-Steuerung:
- Parameter $\beta$ : Steuert die asymptotische Rate des Trade-offs. Ein niedrigeres $\beta$ (z. B. 0,25) priorisiert die Regret-Minimierung, während ein höheres $\beta$ (z. B. 0,5) die Schätzgenauigkeit (RMSE) priorisiert.
- Parameter $C_t$ : Ein adaptiver Schwellenwert, der über die Zeit basierend auf Aktivierungsraten oder Unsicherheitsstatistiken gelernt wird, was es dem System ermöglicht, das Gleichgewicht zwischen Exploration und Exploitation dynamisch anzupassen.

3. Theoretische Beiträge

Die Arbeit liefert eine rigorose theoretische Analyse, welche die fundamentalen Grenzen dieses Problems etabliert:

Existenz eines Trade-offs: Die Autoren beweisen, dass kein einzelner Algorithmus gleichzeitig die optimalen Raten für sowohl kumulativen Regret als auch globalen Schätzfehler erreichen kann.
Erreichbare Ratenpaare: Sie charakterisieren die Pareto-Front der erreichbaren Raten. Speziell gilt: Für jede Policy $\pi$ $π$ , wenn der Regret als $O(T^{2\beta})$ $O (T^{2 β})$ skaliert, muss der RMSE als $\Omega(T^{-\beta})$ $Ω (T^{- β})$ skalieren, wobei $\beta \in [1/4, 1/2]$ $β \in [1/4, 1/2]$ .
- Optimaler Regret ( $\beta=1/4$ ) impliziert suboptimalen RMSE ( $\Omega(T^{-1/4})$ ).
- Optimaler RMSE ( $\beta=1/2$ ) impliziert linearen Regret.
Erreichbarkeit: Theorem 5.1 zeigt, dass $InfluenceCB$ durch Einstellen des Parameters $\beta$ jeden Punkt auf dieser Pareto-Front erreichen kann, indem die Bindungen erfüllt werden:
$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$

4. Experimentelle Ergebnisse

Die Autoren evaluierten $InfluenceCB$ auf drei semi-synthetischen Datensätzen, die aus realen Netzwerken abgeleitet wurden: BlogCatalog, Flickr und Hateful (Twitter). Die Grundwahrheits-Einflussprobabilitäten wurden synthetisch basierend auf linearen Kombinationen von Knoten- und Kantenmerkmalen generiert.

Baselines:

Statische Modelle: Random, Similarity, Link Prediction (Ridge, GraphSAGE, NCNC) und ein SOTA-Recommender (ContextGNN).
Online Learning: SGD-basierte Exploitation- und Exploration-Varianten.
Kontextuelle Banditen: LinUCB, EENet, Graph Neural Bandits (GNB) und Takemura et al. (combinatorial semi-bandit).

Kernergebnisse:

Expansion der Pareto-Front: $InfluenceCB$ erweitert die Pareto-Front über alle Baselines hinaus. Während Standard-Banditen (wie LinUCB) auf Regret optimieren, weisen sie höhere Schätzfehler auf. Statische Modelle schneiden in beiden Metriken schlecht ab.
Abstimmbare Trade-offs: Durch Anpassung von $\beta$ kann $InfluenceCB$ den RMSE signifikant reduzieren (um ca. 60 % auf Flickr) auf Kosten des Regrets, oder den Regret minimieren (den LinUCB um ca. 5–10 % übertreffen) bei einem leichten Anstieg des RMSE.
Parametersensitivität: Der Parameter $C$ (Schwellenwert) beeinflusst den Trade-off erheblich. Das adaptive Lernen von $C$ ermöglicht es dem Algorithmus, ein Gleichgewicht zu finden, ohne manuelles Tuning für spezifische Anwendungsbedarfe zu erfordern.
Robustheit: Die Methode behält eine kompetitive Performance in Ranking-Metriken (NDCG@k) und dem Kalibrierungsfehler (ECE) über verschiedene Netzwerksettings hinweg bei (netzwerkbasierte vs. nachbarsbasierte Kantenwahl).

5. Bedeutung und Ansprüche

Die Arbeit beansprucht für sich, die erste zu sein, die das Lernen von Peer-Einflussprobabilitäten explizit als ein eigenständiges bi-objektives Problem formuliert, das sich von Influence-Maximization- oder Recommendation-Aufgaben unterscheidet, bei denen Wahrscheinlichkeiten als bekannt oder sekundär vorausgesetzt werden.

Theoretische Erkenntnis: Sie stellt fest, dass die Minimierung von Regret und die Minimierung des globalen Schätzfehlers in vernetzten Bandit-Settings fundamental gegensätzliche Ziele sind – ein Trade-off, der in diesem spezifischen Kontext zuvor nicht charakterisiert wurde.
Praktischer Nutzen: Das Framework erlaubt es Praktikern, explizit eine Policy zu wählen, die mit den Prioritäten ihrer Anwendung übereinstimmt. Beispielsweise könnte eine Viral-Marketing-Kampagne den Regret priorisieren (unmittelbare Verkäufe), während eine Policy-Audit oder eine Diffusionssimulation eher den RMSE priorisieren sollte (genaue globale Einfluss-Maps).
Limitierungen und zukünftige Arbeit: Die Autoren merken an, dass ihre aktuelle Analyse von unabhängigen Bernoulli-Aktivierungen ausgeht und keine komplexen Interferenzeffekte (z. B. kumulative Exposition durch mehrere Nachbarn) modelliert. Zukünftige Arbeiten werden vorgeschlagen, um das Framework auf nicht-lineare Settings und dynamische oder teilweise beobachtete Netzwerke zu erweitieren.

Zusammenfassend bietet $InfluenceCB$ einen fundierten Mechanismus, um die Spannung zwischen dem Erlernen genauer Einflussmodelle und der Maximierung unmittelbarer Netzwerk-Interventionen zu navigieren, und stellt somit ein flexibles Werkzeug für die Entscheidungsfindung in Netzwerken bereit.