Revealing graph bandits for maximizing local influence
Abstract Overview
This paper studies a graph bandit problem where the learner aims to identify the most influential node in a graph with no prior knowledge of the graph structure. At each round, the learner selects a node and observes the stochastic set of nodes it currently influences, under a local influence model where influence is limited to immediate neighbors. The authors propose BARE (Bandit Revelator), a two-phase strategy that first uses uniform random exploration to identify promising nodes and then runs a bandit algorithm (GraphMOSS) on the reduced candidate set. The analysis introduces the detectable dimension, a problem-dependent quantity that can be much smaller than the total number of nodes and governs the regret in favorable graph structures.
Novelty
The distinctive contribution is a graph bandit formulation where the graph is initially unknown and is only revealed progressively through the learner's actions, unlike prior work that assumes partial or full graph knowledge (e.g., at least second-neighborhood information). The paper introduces the detectable dimension and uses it to derive regret guarantees for BARE, showing how structural information can be exploited without first scanning the full graph.
Results
The main theoretical result shows that BARE achieves expected regret bounded by C·min(r⋆n, D⋆r⋆ + √(r⋆nD⋆) + nε⋆), where D⋆ is the detectable dimension and ε⋆ is the influential-influenced gap; for undirected graphs (ε⋆=0), this matches the minimax-optimal rate with D⋆ replacing d. A matching lower bound (up to constants) is also provided. Experiments on Barabási-Albert (d=1000), Facebook (d=4039), Enron (d=36692), and Gnutella (d=10879) graphs show that BARE identifies promising nodes earlier than GraphMOSS, with larger gains on more centralized networks and when the influence probability is higher.
Key Points
- The setting assumes no prior graph knowledge: after choosing a node, the learner only observes the stochastic set of nodes currently influenced by that node (its revealed neighbors), not the whole network structure.
- BARE combines a uniform random exploration phase with a bandit phase on a reduced candidate set, and its regret depends on the detectable dimension D⋆ (which can be much smaller than d) rather than directly on the total number of nodes.
- Empirical results show that BARE's advantage over the graph-agnostic GraphMOSS baseline is substantial on centralized networks (Facebook, Enron), smaller on the more decentralized Gnutella network, and increases when the probability of revealing influenced neighbors is higher.