Abstract
We study a graph bandit setting where the objective of the learner is to detect the most influential node of a graph by requesting as little information from the graph as possible. One of the relevant applications for this setting is marketing in social networks, where the marketer aims at finding and taking advantage of the most influential customers. The existing approaches for bandit problems on graphs require either partial or complete knowledge of the graph. In this paper, we do not assume any knowledge of the graph, but we consider a setting where it can be gradually discovered in a sequential and active way. At each round, the learner chooses a node of the graph and the only information it receives is a stochastic set of the nodes that the chosen node is currently influencing. To address this setting, we propose BARE, a bandit strategy for which we prove a regret guarantee that scales with the detectable dimension, a problem dependent quantity that is often much smaller than the number of nodes.
Introduction
In digital marketing, "influence maximization" is the task of identifying users who can most effectively propagate information or products through their social contacts. Traditionally, this is modeled as a multi-armed bandit problem on graphs, where each node represents an arm and the reward is the number of neighbors influenced. However, a significant limitation of existing graph-based bandit algorithms is the requirement for prior knowledge of the network structure. In real-world scenarios, social network platforms rarely share proprietary graph data with advertisers. Instead, advertisers must infer influence through trial and error.
This paper introduces BARE (Bandit Revelator), an algorithm designed to find the most influential nodes in a "zero-knowledge" environment. BARE actively discovers the graph structure on the fly, learning the network's shape while simultaneously maximizing cumulative influence.
Methodology: The BARE Algorithm
BARE addresses the challenge of unknown graph structures by leveraging a "dual influence" property: if a node is frequently influenced by others, it is likely to be part of a highly connected region. The algorithm operates in two distinct phases:
- Global Exploration Phase: The algorithm samples nodes uniformly at random. Rather than just measuring their direct influence, BARE tracks "incoming" influence links to build a structural sketch of the graph's most connected hubs.
- Bandit Phase: After narrowing the search space to a subset of promising candidates, BARE switches to a minimax-optimal bandit strategy—a modified version of MOSS called GraphMOSS—to identify the single most influential node.
Central to this approach is the detectable dimension ($D_\star$). This problem-dependent metric measures the number of nodes "close" to the top influencers. BARE proves that in structured graphs (e.g., those with clear hubs), regret scales with $D_\star$ rather than the total number of nodes $d$, effectively breaking the curse of dimensionality in large networks.
Experimental Evaluation
The researchers evaluated BARE against the GraphMOSS baseline using synthetic Barabási-Albert models and several real-world datasets, including Facebook, the Enron Mail Graph, and the Gnutella Network.
In experiments on the Enron and Facebook datasets, BARE significantly outperformed the baseline. While GraphMOSS often suffered from "linear regret" (equivalent to random guessing) for a long duration, BARE's initial exploration phase allowed it to identify and exploit high-influence nodes much earlier in the process.
Key Insights and Results
- Theoretical Guarantees: The authors prove a regret bound scaling with $\sqrt{r_\star n D_\star}$, where $r_\star$ is the maximum influence. This confirms that performance depends on the complexity of the "detectable" part of the graph.
- Efficiency in Small-Budget Regimes: BARE is particularly effective when the number of rounds $n$ is smaller than the number of nodes $d$. In such cases, traditional algorithms fail to sample every node, whereas BARE's hub-detection logic finds influential users quickly.
- Graph Sensitivity: The performance gains are most pronounced in centralized networks like Enron. In decentralized networks like Gnutella, where influence is more uniform, the detectable dimension is larger, leading to a smaller (though still present) advantage.
Limitations and Future Work
Currently, BARE focuses on "local influence," where a node only affects its immediate neighbors. Future research could extend this logic to multi-hop propagation models, such as the Independent Cascade model. Additionally, while BARE assumes a degree of symmetry between influencing and being influenced, future iterations could adapt to directed "follower" networks where such correlations may be weaker.
Summary updated