🤖 machine learning

Learning Peer Influence Probabilities with Linear Contextual Bandits

Cet article aborde le défi de l'apprentissage des probabilités d'influence hétérogène entre pairs dans des environnements en réseau en introduisant un cadre de bandit linéaire contextuel qui caractérise le compromis fondamental entre la minimisation du regret et l'erreur d'estimation, proposant un algorithme guidé par l'incertitude pour atteindre une performance optimale à travers ce spectre.

Auteurs originaux : Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

Publié 2026-06-29

📖 5 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Ahmed Sayeed Faruk, Mohammad Shahverdikondori, Elena Zheleva

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous soyez le gestionnaire d'un immense club social où les membres partagent constamment des nouvelles, des produits ou des idées avec leurs amis. Votre objectif est de comprendre qui influence qui. Est-ce que la recommandation d'Alice pousse Bob à acheter un nouveau téléphone ? Est-ce que le post de Charlie pousse Dave à aller à un concert ?

Le problème est que l'influence est complexe. Parfois, les gens partagent des choses parce qu'ils sont similaires (homophilie), et non parce que l'un a réellement convaincu l'autre. Et si vous vous contentez d'observer ce qui se passe naturellement, vous ne pouvez pas faire la différence entre « Alice a convaincu Bob » et « Alice et Bob aiment simplement les mêmes choses ».

Pour résoudre ce problème, les auteurs de cet article proposent une nouvelle façon d'apprendre ces probabilités d'influence en les testant activement, comme un scientifique menant des expériences, plutôt qu'en se contentant d'observer.

Voici l'idée centrale, décomposée en concepts simples :

1. Les deux objectifs conflictuels (Le « tir à la corde »)

Les chercheurs ont découvert que l'on ne peut pas avoir le beurre et l'argent du beurre. Vous êtes coincé dans un tir à la corde entre deux objectifs :

Objectif A : Être un bon vendeur (Minimiser le regret). Vous voulez présenter des recommandations aux personnes les plus susceptibles de dire « Oui » en ce moment. Cela maximise le succès immédiat.
Objectif B : Être un bon détective (Minimiser l'erreur d'estimation). Vous voulez apprendre les véritables probabilités d'influence pour tout le monde, même pour les personnes qui disent rarement « Oui ». Pour ce faire, vous devez tester des personnes dont vous n'êtes pas certain, ce qui signifie que vous pourriez manquer des ventes immédiates.

L'analogie : Imaginez que vous êtes un enseignant essayant de déterminer quels élèves réussiront un examen.

Si vous ne donnez des examens blancs qu'aux étudiants qui sont déjà performants (Objectif A), vous obtenez de bons scores immédiatement, mais vous n'apprendrez jamais si les élèves en difficulté comprennent réellement la matière ou s'ils ont simplement besoin de plus d'aide.
Si vous forcez chaque élève à passer un examen blanc, y compris ceux qui échouent habituellement (Objectif B), vous obtenez une carte parfaite de qui sait quoi, mais la moyenne de votre classe (votre « regret ») chute car vous avez passé du temps à tester des personnes qui n'en avaient pas besoin.

L'article prouve mathématiquement qu'aucune stratégie unique ne peut être parfaite pour les deux objectifs en même temps. Vous devez choisir un équilibre.

2. La solution : L'« Influence Contextual Bandit » (InfluenceCB)

Les auteurs ont construit un système intelligent appelé InfluenceCB qui agit comme un interrupteur flexible. Il vous permet de tourner un cadran pour décider à quel point vous voulez être un « Vendeur » ou un « Détective ».

Le Cadran (Paramètre $\beta$ ) :
- Si vous tournez le cadran vers le Regret, le système agit comme un vendeur prudent. Il présente principalement des recommandations aux personnes qu'il pense diront oui, pour maintenir un taux de succès immédiat élevé.
- Si vous tournez le cadran vers l'RMSE (Erreur), le système agit comme un détective curieux. Il présente délibérément des recommandations à des personnes incertaines ou peu performantes pour recueillir plus de données et apprendre la vérité, même si cela signifie moins de réponses « Oui » immédiates.
Le Compteur d'Incertitude : Le système vérifie constamment : « À quel point suis-je incertain concernant cette amitié spécifique ? » Si l'incertitude est trop élevée, il force une expérimentation (exploration). Si le système est confiant, il suit simplement le mouvement (exploitation).

3. Comment ils l'ont testé

Ils ne se sont pas contentés de deviner ; ils ont réalisé des simulations sur des données de réseaux sociaux réels (comme des blogs, des sites de partage de photos et des réseaux Twitter). Ils ont créé un monde fictif où ils connaissaient les « vraies » probabilités d'influence, puis ont laissé leur algorithme tenter de les apprendre.

Les Résultats :

Anciennes méthodes (Statiques) : Elles étaient comme regarder une photo du passé. Elles étaient correctes pour deviner, mais ne pouvaient pas apprendre de nouvelles choses.
Bandits standards : Ils étaient comme des vendeurs qui ne parlent qu'aux personnes populaires. Ils obtenaient de bons résultats immédiats, mais avaient une image très floue de l'ensemble du réseau.
Leur méthode (InfluenceCB) : C'était le vainqueur. En ajustant leur cadran, ils pouvaient dessiner une courbe parfaite (appelée frontière de Pareto).
- Si le client voulait les meilleurs résultats immédiats, InfluenceCB donnait les meilleurs résultats possibles tout en apprenant.
- Si le client voulait la carte d'influence la plus précise, InfluenceCB donnait la carte la plus précise tout en obtenant des résultats corrects.

4. La conclusion principale

La principale contribution de cet article est de prouver que l'apprentissage de l'influence est un exercice d'équilibre. Vous ne pouvez pas simplement optimiser le profit immédiat et espérer apprendre la vérité, et vous ne pouvez pas simplement essayer de tout apprendre sans nuire à votre performance.

Leur nouvel outil, InfluenceCB, vous donne le volant. Il vous permet de décider exactement à quel point vous voulez explorer (apprendre) ou exploiter (gagner) à n'importe quel moment, garantissant ainsi le meilleur résultat possible pour vos besoins spécifiques, qu'il s'agisse de mener une campagne de marketing viral ou simplement de comprendre comment l'information se diffuse au sein d'une communauté.

En bref : Ils ont construit un algorithme intelligent qui sait qu'il ne peut pas être parfait en tout, alors il vous laisse choisir exactement à quel point il doit être imparfait dans un domaine pour être parfait dans l'autre.

Résumé technique : Apprentissage des probabilités d'influence par les pairs avec des bandits contextuels linéaires

1. Formulation du problème

L'article traite du défi de l'apprentissage de probabilités d'influence par les pairs hétérogènes dans des environnements en réseau. Dans les réseaux sociaux, la probabilité qu'un utilisateur (récipiendaire) adopte une action après avoir reçu une recommandation d'un autre utilisateur (émetteur) varie considérablement en fonction des attributs des nœuds, des caractéristiques des liens et de la structure du réseau.

Les auteurs formulent cela comme un problème de bandit contextuel à deux objectifs (bi-objectif). Le cadre implique un agent interagissant avec un réseau dirigé et attribué $G=(V, E)$ sur $T$ tours. À chaque tour :

L'agent observe un ensemble de liens candidats (interactions).
L'agent sélectionne un sous-ensemble de $k$ liens pour une intervention (par exemple, montrer une publication à un ensemble spécifique de récipiendaires).
L'agent observe des récompenses binaires (activation : 1 si le récipiendaire agit, 0 sinon).

La difficulté centrale réside dans l'équilibre entre deux objectifs conflictuels :

Minimiser le regret cumulé ( $Regret_T$ ) : Maximiser les récompenses immédiates en sélectionnant les liens ayant les probabilités d'influence estimées les plus élevées (exploitation).
Minimiser l'erreur d'estimation ( $RMSE_T$ ) : Estimer avec précision les véritables probabilités d'influence pour tous les liens du réseau, y compris ceux ayant une influence faible ou incertaine (exploration).

L'article soutient que les méthodes d'apprentissage en ligne standard soit gaspillent des ressources via une exploration aléatoire (faibles garanties de regret), soit optimisent uniquement les récompenses, conduisant à des erreurs d'estimation élevées pour les liens à faible probabilité. Inversement, les méthodes statiques ne parviennent pas à distinguer l'influence réelle des facteurs de confusion comme l'homophilie.

2. Méthodologie : Bandit contextuel d'influence ($InfluenceCB$)

Les auteurs proposent $InfluenceCB$, un cadre conçu pour naviguer dans le compromis entre regret et erreur d'estimation. La méthode opère sous un modèle de récompense linéaire où l'espérance de la récompense pour un lien avec un vecteur de contexte $X$ est $E[r] = X^\top \theta^*$ , où $\theta^*$ est un vecteur de paramètres inconnus.

Composants clés :

Exploration guidée par l'incertitude :
- L'algorithme calcule l'incertitude d'estimation pour les liens candidats en utilisant la métrique d'incertitude standard des bandits linéaires : $U_t(X) = \sqrt{X^\top V_{t-1}^{-1} X}$ , où $V_{t-1}$ est la matrice de covariance régularisée des caractéristiques observées.
- Si l'incertitude maximale dans le pool actuel dépasse un seuil dynamique ( $C_t / t^\beta$ ), l'algorithme entre dans une phase d'exploration, sélectionnant les $k$ meilleurs liens ayant les scores d'incertitude les plus élevés. Cela garantit que les liens à faible probabilité ou incertains sont échantillonnés pour améliorer l'estimation globale.
Exploitation guidée par la récompense :
- Si l'incertitude tombe sous le seuis, l'algorithme entre dans une phase d'exploitation.
- Il emploie une sous-routine de CMAB linéaire standard (par exemple, CombLinUCB) pour sélectionner les liens qui maximisent les récompenses immédiates attendues, minimisant ainsi le regret.
Contrôle du compromis :
- Paramètre $\beta$ : Contrôle le taux asymptotique du compromis. Un $\beta$ plus faible (par exemple, 0,25) privilégie la minimisation du regret, tandis qu'un $\beta$ plus élevé (par exemple, 0,5) privilégie la précision de l'estimation (RMSE).
- Paramètre $C_t$ : Un seuil adaptatif appris au fil du temps basé sur les taux d'activation ou les statistiques d'incertitude, permettant au système d'ajuster dynamiquement l'équilibre entre exploration et exploitation.

3. Contributions théoriques

L'article fournit une analyse théorique rigoureuse établissant les limites fondamentales de ce problème :

Existence d'un compromis : Les auteurs prouvent qu'aucun algorithme ne peut simultanément atteindre les taux optimaux pour le regret cumulé et l'erreur d'estimation globale.
Paires de taux réalisables : Ils caractérisent la frontière de Pareto des taux réalisables. Plus précisément, pour toute politique $\pi$ $π$ , si le regret suit une échelle de $O(T^{2\beta})$ $O (T^{2 β})$ , le RMSE doit suivre une échelle de $\Omega(T^{-\beta})$ $Ω (T^{- β})$ , où $\beta \in [1/4, 1/2]$ $β \in [1/4, 1/2]$ .
- Un regret optimal ( $\beta=1/4$ ) implique un RMSE sous-optimal ( $\Omega(T^{-1/4})$ ).
- Un RMSE optimal ( $\beta=1/2$ ) implique un regret linéaire.
Réalisabilité : Le Théorème 5.1 démontre que $InfluenceCB$ peut atteindre n'importe quel point de cette frontière de Pareto en ajustant le paramètre $\beta$ , satisfaisant les bornes :
$Regret_T \in \tilde{O}(T^{2\beta}), \quad RMSE_T \in \tilde{O}(T^{-\beta})$

4. Résultats expérimentaux

Les auteurs ont évalué $InfluenceCB$ sur trois jeux de données semi-synthétiques dérivés de réseaux réels : BlogCatalog, Flickr et Hateful (Twitter). Les probabilités d'influence de vérité terrain ont été générées synthétiquement sur la base de combinaisons linéaires de caractéristiques de nœuds et de liens.

Baselines (Modèles de référence) :

Modèles statiques : Random, Similarity, Link Prediction (Ridge, GraphSAGE, NCNC), et un Recommandeur SOTA (ContextGNN).
Apprentissage en ligne : Variantes d'exploitation et d'exploration basées sur le SGD.
Bandits contextuels : LinUCB, EENet, Graph Neural Bandits (GNB), et Takemura et al. (semi-bandit combinatoire).

Principales conclusions :

Expansion de la frontière de Pareto : $InfluenceCB$ étend la frontière de Pareto au-delà de toutes les baselines. Alors que les bandits standards (comme LinUCB) optimisent pour le regret, ils présentent des erreurs d'estimation plus élevées. Les modèles statiques performent mal sur les deux métriques.
Compromis réglable : En ajustant $\beta$ , $InfluenceCB$ peut réduire considérablement le RMSE (jusqu'à ~60 % sur Flickr) au prix d'un regret accru, ou minimiser le regret (surpassant LinUCB de ~5-10 %) avec une légère augmentation du RMSE.
Sensibilité aux paramètres : Le paramètre $C$ (seuil) impacte significativement le compromis. L'apprentissage adaptatif de $C$ permet à l'algorithme de trouver un équilibre sans réglage manuel pour des besoins d'application spécifiques.
Robustesse : La méthode maintient des performances compétitives dans les métriques de classement (NDCG@k) et l'erreur de calibration (ECE) à travers différents contextes de réseau (sélection de liens basée sur le réseau vs basée sur le voisinage).

5. Signification et revendications

L'article affirme être le premier à formuler explicitement l'apprentissage des probabilités d'influence par les pairs comme un problème bi-objectif indépendant, distinct des tâches de maximisation d'influence ou de recommandation où les probabilités sont supposées connues ou secondaires.

Insight théorique : Il établit que minimiser le regret et minimiser l'erreur d'estimation globale sont des objectifs fondamentalement conflictuels dans les contextes de bandits en réseau, un compromis précédemment non caractérisé dans ce contexte spécifique.
Utilité pratique : Le cadre permet aux praticiens de choisir explicitement une politique alignée sur les priorités de leur application. Par exemple, une campagne de marketing viral pourrait privilégier le regret (ventes immédiates), tandis qu'une politique d'audit ou de simulation de diffusion pourrait privilégier le RMSE (cartes d'influence globale précises).
Limites et travaux futurs : Les auteurs notent que leur analyse actuelle suppose des activations de Bernoulli indépendantes et ne modélise pas les effets d'interférence complexes (par exemple, l'exposition cumulative de plusieurs voisins). Des travaux futurs sont suggérés pour étendre le cadre aux contextes non linéaires et aux réseaux dynamiques ou partiellement observés.

En résumé, $InfluenceCB$ fournit un mécanisme fondé sur des principes pour naviguer dans la tension entre l'apprentissage de modèles d'influence précis et la maximisation des interventions réseau immédiates, offrant un outil flexible pour la prise de décision en réseau.