Revealing graph bandits for maximizing local influence

1. Définition du problème

L'article aborde un problème de prise de décision séquentielle connu sous le nom de Bandits de graphes, spécifiquement adapté pour maximiser l'influence locale dans un scénario où la structure du graphe est initialement inconnue.

• Cadre : L'apprenant opère sur un graphe $G$ comportant $d$ nœuds. À chaque tour $t$, l'apprenant sélectionne un nœud $k_t$.
• Retour d'information : Après sélection, l'apprenant observe un ensemble stochastique $S_{k_t, t}$ de nœuds influencés par $k_t$. Cela inclut $k_t$ lui-même et ses voisins immédiats. L'influence est probabiliste : le nœud $i$ influence le nœud $j$ avec une probabilité inconnue $p_{i,j}$.
• Objectif : Le but est d'identifier et de sélectionner à plusieurs reprises le nœud $k^*$ ayant la plus grande influence attendue (la somme des probabilités d'influencer tous les autres nœuds, $r_k = \sum_j p_{k,j}$) dans le cadre d'un budget de $n$ tours.
• Régret : La performance est mesurée par le regret, défini comme la différence entre l'influence totale de la stratégie optimale (connaissant le graphe) et celle de la stratégie de l'apprenant.
• Contrainte clé : Contrairement aux travaux précédents qui supposent une connaissance partielle ou complète du graphe (par exemple, connaître le deuxième voisinage ou la matrice d'adjacence complète), ce cadre suppose aucune connaissance a priori. Le graphe est révélé séquentiellement et activement uniquement par le biais des voisins immédiats des nœuds choisis.

2. Méthodologie : L'algorithme BARE

Les auteurs proposent BARE (Bandit Revelator), un algorithme conçu pour apprendre la structure du graphe et le nœud optimal simultanément sans parcourir l'intégralité du graphe. BARE fonctionne en deux phases distinctes :

Phase 1 : Exploration globale

• Objectif : Estimer la « double influence » (la mesure dans laquelle un nœud est influencé par les autres, $r^\circ_k = \sum_j p_{j,k}$) et identifier un petit sous-ensemble de nœuds prometteurs.
• Mécanisme : L'algorithme sélectionne des nœuds uniformément au hasard.
• Estimation : Il estime la double influence $\hat{r}^\circ_k$ pour chaque nœud en fonction de la fréquence à laquelle il apparaît dans les ensembles d'influence d'autres nœuds choisis au hasard.
• Critère d'arrêt : La phase se poursuit jusqu'à ce qu'une condition spécifique soit remplie, définie par l'Horizon détectable ($T^*$). Cet horizon est le plus petit temps $t$ tel que l'information accumulée soit suffisante pour distinguer les nœuds les plus influents du reste.
• Sélection du sous-ensemble : Sur la base des estimations, BARE filtre les nœuds, ne conservant que ceux qui sont « les plus influencés » (c'est-à-dire ayant une forte double influence). Cela crée un ensemble de candidats réduit de taille $\hat{D}^*$.

Phase 2 : Phase de bandit

• Objectif : Trouver le nœud ayant l'influence sortante maximale ($r_k$) au sein de l'ensemble de candidats réduit.
• Mécanisme : L'algorithme exécute un algorithme de bandit minimax-optimal (spécifiquement une variante de GraphMOSS, adaptée d'Audibert & Bubeck) exclusivement sur le sous-ensemble de nœuds identifié lors de la Phase 1.
• Raison d'être : En réduisant l'espace de recherche de $d$ nœuds à $\hat{D}^*$ nœuds, l'algorithme évite le regret linéaire associé à l'exploration d'un grand graphe lorsque $n \ll d$.

3. Contributions théoriques clés

A. La dimension détectable ($D^*$)

L'article introduit une nouvelle quantité dépendante du problème appelée Dimension détectable ($D^*$).

• Définition : $D^*$ représente le nombre de nœuds qui sont « détectablement » distincts en termes de leurs propriétés d'influence par rapport au budget $n$. Elle est dérivée de la fonction $D(\Delta)$, qui compte les nœuds ayant un écart de dualité (sous-optimalité en termes d'être influencés) inférieur à $\Delta$.
• Signification : Dans de nombreux réseaux réels (par exemple, les réseaux sans échelle), $D^*$ est significativement plus petit que le nombre total de nœuds $d$. Cela permet à la performance de l'algorithme de s'adapter à $D^*$ plutôt qu'à $d$.

B. Bornes de regret

Les auteurs prouvent que le regret attendu de BARE est borné par :
$$E[R_n] \leq C \min \left( r^* n, \quad D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^* \right)$$
Où :

• $r^*$ est l'influence du nœud optimal.
• $D^*$ est la dimension détectable.
• $\varepsilon^*$ est l'« écart influent-influencé » (la différence entre le nœud le plus influent et le nœud le plus influent parmi les nœuds les plus influencés).
• Optimalité : Pour les graphes non orientés (où l'influence est mutuelle, donc $\varepsilon^* = 0$), la borne se simplifie en $O(D^* r^* + \sqrt{r^* n D^*})$. Cela correspond au taux optimal minimax pour un problème de bandit avec seulement $D^*$ bras, prouvant que BARE réduit efficacement la dimensionalité du problème.

C. Bornes inférieures

L'article établit une borne inférieure montrant qu'aucun algorithme ne peut atteindre un regret meilleur que $\Omega(D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^*)$ dans le pire des cas, confirmant que BARE est optimal minimax pour ce cadre.

4. Résultats expérimentaux

Les auteurs ont évalué BARE sur des ensembles de données synthétiques et réels :

• Ensembles de données : Barabási-Albert (sans échelle), Facebook, réseau de courriels Enron, et réseau P2P Gnutella.
• Lignes de base : Comparaison avec GraphMOSS (un algorithme standard de bandit de graphes qui ignore l'aspect « révélation » et traite les nœuds comme des bras indépendants jusqu'à ce que le graphe soit entièrement connu) et une ligne de base qui n'observe que le nombre de nœuds influencés (sans identité).
• Constats :
  • Performance : BARE surpasse nettement GraphMOSS, en particulier lorsque l'horizon temporel $n$ est inférieur au nombre de nœuds $d$ ($n \leq d$).
  • Dépendance structurelle : Le gain est plus prononcé dans les réseaux présentant une hiérarchie claire d'influence (par exemple, Facebook, Enron) où $D^*$ est faible. Dans les réseaux hautement décentralisés (comme Gnutella), le gain est plus faible, ce qui est cohérent avec la théorie selon laquelle $D^*$ tend vers $d$.
  • Probabilité de révélation : À mesure que la probabilité d'observer l'ensemble d'influence augmente, l'avantage de BARE croît, car il peut estimer plus précisément la double influence pour filtrer l'ensemble des candidats.

5. Signification et impact

• Applicabilité pratique : Ce travail résout une limitation critique dans le marketing et l'analyse des réseaux sociaux. Dans les scénarios réels, les annonceurs ne peuvent pas accéder au graphe social complet (contraintes de confidentialité) mais peuvent observer les résultats immédiats de leurs campagnes (qui a acheté le produit). BARE fournit une stratégie pour trouver des « influenceurs » dans le cadre de ces contraintes d'information strictes.
• Avancement théorique : Il va au-delà de l'hypothèse selon laquelle la structure du graphe doit être connue ou partiellement connue pour être utile. Il démontre que la révélation active de la structure du graphe peut être exploitée pour atteindre des taux d'apprentissage qui dépendent de la complexité intrinsèque ($D^*$) du problème plutôt que de la taille brute du graphe ($d$).
• Réduction de dimensionalité : Le concept de « Dimension détectable » offre une nouvelle perspective pour l'analyse des problèmes de bandit sur de grands graphes inconnus, suggérant qu'un apprentissage efficace est possible même sans exploration complète du graphe.

En résumé, l'article présente BARE, un nouvel algorithme qui identifie efficacement le nœud le plus influent dans un graphe inconnu en révélant activement les voisinages locaux, atteignant des bornes de regret qui s'adaptent à la dimension détectable plutôt qu'au nombre total de nœuds.