Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback

Zheng Wen, Branislav Kveton, Michal Valko, Sharan VaswaniNeurIPS 2017 · OpenReview

In the world of viral marketing, the goal is simple: pick a small set of "influencers" to give free samples to, and hope they trigger a massive chain reaction of adoption across a social network. But there’s a catch—in the real world, we don't actually know the "activation probabilities" (the likelihood that one person influences another). We have to learn them on the fly.

This paper introduces IMLinUCB, an algorithm designed to solve the Online Influence Maximization (IM) problem efficiently, even when the network has millions of users.

TL;DR

The authors present IMLinUCB, the first algorithm for online influence maximization that uses linear generalization to scale to large networks. By assuming activation probabilities can be modeled as linear functions of edge features, they achieve "near-optimal" regret bounds that depend on the network's topology rather than just its size.

What Problem Does This Paper Address?

Influence Maximization is a classic problem: given a graph, pick $K$ seed nodes to maximize the expected number of influenced nodes under a diffusion model like the Independent Cascade (IC) model.

The "Online" version adds two massive hurdles:

  1. Unknown Dynamics: We don't know how likely an edge is to "fire." We only learn by trying different seed sets and observing who gets influenced (edge semi-bandit feedback).
  2. The Combinatorial Explosion: The number of ways to pick $K$ influencers grows exponentially with $K$. Furthermore, social networks are huge, making it impossible to learn every edge's probability independently.

Previous solutions often had "regret" (the difference between our performance and the optimal strategy) that scaled poorly, sometimes depending on the reciprocal of the smallest probability in the network—which can be infinitesimally small.

Methods

The authors propose IMLinUCB (Influence Maximization Linear Upper Confidence Bound). Here’s the breakdown of the approach:

  • Linear Generalization: Instead of learning a probability for every single edge, they assume each edge $e$ has a feature vector $x_e$. The probability of activation is $w(e) \approx x_e^T \theta^*$. This allows the algorithm to share knowledge across similar edges.
  • The UCB Strategy: In each round, the algorithm calculates an Upper Confidence Bound (UCB) for every edge. It essentially asks: "What is the highest plausible probability for this edge given what I've seen?"
  • The Oracle: Since finding the optimal seed set is NP-hard even with known probabilities, the algorithm uses an offline approximation oracle. It feeds its UCB estimates into this oracle to pick the best $K$ seeds for the current round.
  • Semi-Bandit Feedback: After picking seeds, the algorithm observes which edges were actually traversed during the influence spread and uses that data to update its estimate of $ heta^*$.

Datasets

The paper evaluates the algorithm using two types of data:

  1. Synthetic Topologies: They tested on Bar, Star, Ray, and Grid graphs to verify how the algorithm's regret scales with different network structures.
Synthetic graph topologies used for evaluation: (a) Bar, (b) Star, (c) Ray, (d) Grid.
  1. Real-World Social Network: A subgraph of Facebook (from the SNAP dataset) containing 327 nodes and 5,038 directed edges. They used node2vec to generate the edge features required for the linear model.

Key Insights and Ideas

  • The $C_*$ Complexity Metric: The authors introduce "maximum observed relevance" ($C_*$). This is a new way to measure how hard a network is to learn. Unlike previous metrics that look at the worst-case (where every edge has a probability of 1), $C_*$ accounts for the fact that real-world activation probabilities are usually low, meaning the algorithm actually has to learn much less than a worst-case analysis would suggest.
  • Breaking the $1/p^*$ Barrier: Previous work had regret bounds that blew up if any edge had a very low probability ($p^*$). This paper’s bounds are polynomial in all quantities, making them much more robust for real-world graphs.
  • Generalization is Mandatory: The experiments show that "tabular" algorithms (which try to learn every edge independently) fail to scale. By using linear features, IMLinUCB can predict the behavior of edges it has never even seen "fire" yet.

Key Results

  • Theoretical Tightness: The regret bounds are $O(\sqrt{n})$, which is near-optimal for time dependence in bandit problems.
  • Topology Matters: The paper proves that regret scales differently based on graph shape. For example, a "star" graph is much easier to learn than a "ray" graph.
Regret scaling comparison between Star and Ray topologies, demonstrating how network shape impacts learning difficulty.
  • Facebook Performance: In the Facebook subgraph experiment, IMLinUCB significantly outperformed CUCB (the tabular version). Because IMLinUCB could generalize across edges using features, its cumulative regret was much lower, proving it can effectively handle the "limited feedback" problem in social networks.

Limitations and Future Work

  • Linearity Assumption: The core of the scaling relies on the assumption that activation probabilities are linear functions of features. If the underlying influence mechanism is highly non-linear, the model might struggle.
  • Oracle Dependency: The algorithm's efficiency is tied to the efficiency of the offline IM oracle. While good approximation oracles exist, they can still be computationally expensive for massive graphs.
  • Feature Engineering: The performance on real-world data depends heavily on the quality of the edge features (e.g., those generated by node2vec). The paper doesn't explore how sensitive the algorithm is to "noisy" or poor features.

Summary updated

Abstract

We study the online influence maximization problem in social networks under the independent cascade model. Specifically, we aim to learn the set of "best influencers" in a social network online while repeatedly interacting with it. We address the challenges of (i) combinatorial action space, since the number of feasible influencer sets grows exponentially with the maximum number of influencers, and (ii) limited feedback, since only the influenced portion of the network is observed. Under a stochastic semi-bandit feedback, we propose and analyze IMLinUCB, a computationally efficient UCB-based algorithm. Our bounds on the cumulative regret are polynomial in all quantities of interest, achieve near-optimal dependence on the number of interactions and reflect the topology of the network and the activation probabilities of its edges, thereby giving insights on the problem complexity. To the best of our knowledge, these are the first such results. Our experiments show that in several representative graph topologies, the regret of IMLinUCB scales as suggested by our upper bounds. IMLinUCB permits linear generalization and thus is both statistically and computationally suitable for large-scale problems. Our experiments also show that IMLinUCB with linear generalization can lead to low regret in real-world online influence maximization.
BibTeX
@inproceedings{wen2017online,
  author = {Zheng Wen and Branislav Kveton and Michal Valko and Sharan Vaswani},
  title = {{Online Influence Maximization under Independent Cascade Model with Semi-Bandit Feedback}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2017},
  url = {https://openreview.net/forum?id=SkWNLdZdZr},
}
Figure