TL;DR
Most online influence maximization algorithms treat every connection in a social network as an independent mystery, leading to slow learning and poor performance. This paper introduces IMFB, a factorization-based bandit approach that breaks down influence into two latent traits: how much a person influences others and how susceptible a person is to being influenced. By learning these node-level traits, the algorithm can predict influence across unobserved connections, significantly reducing "regret" and finding top influencers faster.
What Problem Does This Paper Address?
Influence Maximization (IM) is the art of picking a small set of "seed" users in a social network to trigger the largest possible cascade of information (like a viral marketing campaign).
The "Online" version of this problem (OIM) is much harder: we don't know the actual probability that one person will influence another. We have to learn these probabilities by trial and error—picking seeds, watching who gets activated, and updating our model.
The authors identify a major gap in current OIM solutions: they treat every edge (connection) independently. In a network with millions of edges, learning each one from scratch is computationally impossible and ignores network assortativity—the biological and social reality that influential people and susceptible people tend to cluster in specific ways. If we know User A is highly influential, we shouldn't have to start from zero to guess their influence on User C just because we've only seen them interact with User B.
Methods
The authors propose IMFB (Influence Maximization with Factorization-Bandits). The core innovation is a low-rank factorization of the activation probabilities.
- Latent Factorization: Instead of learning a single probability $p$ for an edge, they model it as the inner product of two $d$-dimensional vectors: $p_{u,v} = \theta_u^T \beta_v$.
- $\theta_u$ represents the influence factor of the sender.
- $\beta_v$ represents the susceptibility factor of the receiver.
- Upper Confidence Bound (UCB): To balance "exploration" (trying new nodes to learn) and "exploitation" (using known influencers), the algorithm calculates an optimistic estimate of influence using a confidence bound.
- Online Update: As the algorithm observes cascades, it uses a coordinate descent approach to update the latent vectors for all involved nodes.
- Observation Propagation: This is the key differentiator. Because the model is node-based, an observation on one edge provides information about all other edges connected to those same nodes, even if those edges have never been "pulled."
Datasets
The researchers evaluated IMFB on two real-world datasets:
- NetHEPT: A citation network from "High Energy Physics - Theory" with ~27k nodes and ~352k edges.
- Flickr: A social network of image sharing with ~12k nodes and ~138k edges.
- Controlled Flickr: A modified version of the Flickr dataset designed to be "tricky," where nodes with high degrees (many connections) were intentionally given low actual influence to see if the algorithm could look past surface-level popularity.
Key Insights and Ideas
- Complexity Win: Traditional models have a complexity tied to the number of edges $O(|E|)$. IMFB’s complexity is tied to the number of nodes and the latent dimension $O(d|V|)$. In dense networks where $|E| \approx |V|^2$, this is a massive efficiency gain.
- Separating Influence from Susceptibility: The paper highlights that being influential doesn't make you susceptible. By modeling these as distinct vectors, the algorithm captures the "assortative mixing" of social networks more accurately than linear models.
- Learning from the Unseen: Because the model learns node traits, it can estimate the activation probability of an edge it has never seen before. This "observation propagation" allows the algorithm to converge on the best influencers much faster than independent-edge models.
Key Results
- Regret Reduction: IMFB achieved significantly lower cumulative regret (a measure of how much influence was "lost" during the learning phase) compared to state-of-the-art baselines like CUCB and IMLinUCB.
- Massive Gains in Tricky Scenarios: On the "controlled" Flickr dataset, IMFB showed a 230% improvement over standard bandit algorithms. It successfully realized that high-degree nodes were "duds" and pivoted to the true influencers much faster.
- Robustness: The model remained effective even when the researchers intentionally chose the wrong "dimension" ($d$) for the latent factors, suggesting the structural assumption of factorization is more important than perfectly tuning the parameters.
Limitations and Future Work
- Diffusion Model Dependency: The current analysis focuses on the Independent Cascade (IC) model. While common, it doesn't cover all types of social contagion (like the Linear Threshold model).
- Oracle Reliance: Like most IM research, this algorithm relies on an "oracle" (an external sub-algorithm) to solve the NP-hard part of picking the best seeds once probabilities are estimated.
- Node-Level Feedback: The authors assume we can see who activated whom (edge-level feedback). They note that in the real world, we often only see that someone was activated (node-level feedback). Future work involves adapting the factorization model to work with this more limited, "noisy" data.
Summary updated