Revealing graph bandits for maximizing local influence

1. Problem Definition

The paper addresses a sequential decision-making problem known as Graph Bandits, specifically tailored for maximizing local influence in a scenario where the graph structure is initially unknown.

• Setting: The learner operates on a graph $G$ with $d$ nodes. At each round $t$, the learner selects a node $k_t$.
• Feedback: Upon selection, the learner observes a stochastic set $S_{k_t, t}$ of nodes influenced by $k_t$. This includes $k_t$ itself and its immediate neighbors. The influence is probabilistic: node $i$ influences node $j$ with an unknown probability $p_{i,j}$.
• Objective: The goal is to identify and repeatedly select the node $k^*$ with the highest expected influence (the sum of probabilities of influencing all other nodes, $r_k = \sum_j p_{k,j}$) within a budget of $n$ rounds.
• Regret: The performance is measured by regret, defined as the difference between the total influence of the optimal strategy (knowing the graph) and the learner's strategy.
• Key Constraint: Unlike previous works that assume partial or full knowledge of the graph (e.g., knowing the second neighborhood or the full adjacency matrix), this setting assumes zero prior knowledge. The graph is revealed sequentially and actively only through the immediate neighbors of the chosen nodes.

2. Methodology: The BARE Algorithm

The authors propose BARE (Bandit Revelator), an algorithm designed to learn the graph structure and the optimal node simultaneously without scanning the entire graph. BARE operates in two distinct phases:

Phase 1: Global Exploration

• Goal: To estimate the "dual influence" (how much a node is influenced by others, $r^\circ_k = \sum_j p_{j,k}$) and identify a small subset of promising nodes.
• Mechanism: The algorithm selects nodes uniformly at random.
• Estimation: It estimates the dual influence $\hat{r}^\circ_k$ for each node based on how often it appears in the influence sets of other randomly chosen nodes.
• Stopping Criterion: The phase continues until a specific condition is met, defined by the Detectable Horizon ($T^*$). This horizon is the smallest time $t$ such that the accumulated information is sufficient to distinguish the most influential nodes from the rest.
• Subset Selection: Based on the estimates, BARE filters the nodes, retaining only those that are "most influenced" (i.e., have high dual influence). This creates a reduced candidate set of size $\hat{D}^*$.

Phase 2: Bandit Phase

• Goal: To find the node with the maximum outgoing influence ($r_k$) within the reduced candidate set.
• Mechanism: The algorithm runs a minimax-optimal bandit algorithm (specifically a variant of GraphMOSS, adapted from Audibert & Bubeck) exclusively on the subset of nodes identified in Phase 1.
• Rationale: By reducing the search space from $d$ nodes to $\hat{D}^*$ nodes, the algorithm avoids the linear regret associated with exploring a large graph when $n \ll d$.

3. Key Theoretical Contributions

A. The Detectable Dimension ($D^*$)

The paper introduces a new problem-dependent quantity called the Detectable Dimension ($D^*$).

• Definition: $D^*$ represents the number of nodes that are "detectably" distinct in terms of their influence properties relative to the budget $n$. It is derived from the function $D(\Delta)$, which counts nodes with a dual gap (suboptimality in being influenced) less than $\Delta$.
• Significance: In many real-world networks (e.g., scale-free networks), $D^*$ is significantly smaller than the total number of nodes $d$. This allows the algorithm's performance to scale with $D^*$ rather than $d$.

B. Regret Bounds

The authors prove that the expected regret of BARE is bounded by:
$$E[R_n] \leq C \min \left( r^* n, \quad D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^* \right)$$
Where:

• $r^*$ is the influence of the optimal node.
• $D^*$ is the detectable dimension.
• $\varepsilon^*$ is the "influential-influenced gap" (the difference between the most influential node and the most influential node among the most influenced nodes).
• Optimality: For undirected graphs (where influence is mutual, so $\varepsilon^* = 0$), the bound simplifies to $O(D^* r^* + \sqrt{r^* n D^*})$. This matches the minimax optimal rate for a bandit problem with only $D^*$ arms, proving that BARE effectively reduces the dimensionality of the problem.

C. Lower Bounds

The paper establishes a lower bound showing that no algorithm can achieve a regret better than $\Omega(D^* r^* + \sqrt{r^* n D^*} + n \varepsilon^*)$ in the worst case, confirming that BARE is minimax-optimal for this setting.

4. Experimental Results

The authors evaluated BARE on synthetic and real-world datasets:

• Datasets: Barabási-Albert (scale-free), Facebook, Enron email network, and Gnutella P2P network.
• Baselines: Compared against GraphMOSS (a standard graph bandit algorithm that ignores the "revealing" aspect and treats nodes as independent arms until the graph is fully known) and a baseline that only observes the count of influenced nodes (no identity).
• Findings:
  • Performance: BARE significantly outperforms GraphMOSS, especially when the time horizon $n$ is smaller than the number of nodes $d$ ($n \leq d$).
  • Structure Dependence: The gain is most pronounced in networks with a clear hierarchy of influence (e.g., Facebook, Enron) where $D^*$ is small. In highly decentralized networks (like Gnutella), the gain is smaller, consistent with the theory that $D^*$ approaches $d$.
  • Revelation Probability: As the probability of observing the influence set increases, BARE's advantage grows, as it can more accurately estimate the dual influence to filter the candidate set.

5. Significance and Impact

• Practical Applicability: The work solves a critical limitation in marketing and social network analysis. In real scenarios, advertisers cannot access the full social graph (privacy constraints) but can observe the immediate results of their campaigns (who bought the product). BARE provides a strategy to find "influencers" under these strict information constraints.
• Theoretical Advancement: It moves beyond the assumption that graph structure must be known or partially known to be useful. It demonstrates that active revelation of the graph structure can be leveraged to achieve learning rates that depend on the intrinsic complexity ($D^*$) of the problem rather than the raw size of the graph ($d$).
• Dimensionality Reduction: The concept of "Detectable Dimension" offers a new lens for analyzing bandit problems on large, unknown graphs, suggesting that efficient learning is possible even without full graph exploration.

In summary, the paper presents BARE, a novel algorithm that efficiently identifies the most influential node in an unknown graph by actively revealing local neighborhoods, achieving regret bounds that scale with the detectable dimension rather than the total number of nodes.