Online Influence Maximization with Semi-Bandit Feedback under Corruptions

Xiaotong Cheng, Behzad Nourani-Koliji, Setareh Maghsudi

Abstract

In this work, we investigate the online influence maximization in social networks. Most prior research studies on online influence maximization assume that the nodes are fully cooperative and act according to their stochastically generated influence probabilities on others. In contrast, we study the online influence maximization problem in the presence of some corrupted nodes whose damaging effects diffuse throughout the network. We propose a novel bandit algorithm, CW-IMLinUCB, which robustly learns and finds the optimal seed set in the presence of corrupted users. Theoretical analyses establish that the regret performance of our proposed algorithm is better than the state-of-the-art online influence maximization algorithms. Extensive empirical evaluations on synthetic and real-world datasets also show the superior performance of our proposed algorithm.

Introduction

Influence Maximization (IM) is a fundamental problem in social network analysis, aiming to identify a small set of "seed" nodes that trigger the largest possible cascade of information. In the online setting (OIM), the activation probabilities between nodes are initially unknown and must be learned through iterative interactions, typically modeled as a multi-armed bandit problem.

A significant limitation of existing OIM research is the assumption of cooperative node behavior. In real-world social networks, adversarial entities such as bots, trolls, or malicious influencers can provide corrupted feedback or exhibit "disputed behaviors" to mislead seeding strategies. This paper introduces a robust framework to address OIM in the presence of such corrupted nodes, whose adversarial effects can propagate through the network.

Methodology: The CW-IMLinUCB Algorithm

The researchers model the network using the Independent Cascade (IC) model and treat the learning process as a Linear Contextual Bandit problem. To mitigate the impact of adversarial actors, they propose CW-IMLinUCB (Confidence Weighted Influence Maximization Linear Upper Confidence Bound).

Illustration of influence diffusion under normal and corrupted conditions.

The algorithm incorporates three primary innovations:

  1. Weighted Ridge Regression: Observations are assigned weights ($\omega$) based on their estimated reliability. Interactions that appear highly uncertain or potentially corrupted are down-weighted to prevent them from biasing the learning process.
  2. Robust Upper Confidence Bound (UCB): The activation probability estimates include an additional term accounting for the "corruption budget." This allows the algorithm to remain optimistic for exploration while being cautious of adversarial outliers.
  3. Semi-Bandit Feedback: The model utilizes edge-level feedback, observing specific influence paths rather than just aggregate counts, which provides the granular data necessary for robust estimation.

Experimental Evaluation

The performance of CW-IMLinUCB was evaluated against several state-of-the-art algorithms, including IMLinUCB, DILinUCB, and CUCB. Experiments were conducted on:

  • Synthetic Datasets: Erdős-Rényi graphs ($n=10, 50$) with controlled adversarial behaviors, such as "flip-$\theta$ attacks."
  • Real-World Dataset: A subgraph of the Facebook network (300 nodes, 2,046 edges) to test performance on realistic social topologies.

Key Results and Discussion

Empirical results demonstrate that CW-IMLinUCB maintains significantly lower cumulative regret in corrupted environments compared to standard methods.

Average cumulative regret vs. corruption parameters.

Key insights from the study include:

  • Positional Impact: The position of corrupted nodes is often more critical than their quantity. A single corrupted node in a high-centrality position can disrupt the network more effectively than many peripheral nodes.
  • Robustness Trade-offs: In environments with zero corruption, CW-IMLinUCB performs slightly worse than standard algorithms due to the overhead of its robustness terms. However, as corruption is introduced, standard algorithms' performance degrades rapidly, while CW-IMLinUCB remains stable.
  • Theoretical Guarantees: The authors prove a regret bound that is linear in the corruption budget ($C$), providing strong theoretical support for the algorithm's adversarial resilience.

Conclusion

CW-IMLinUCB offers a robust solution for online influence maximization in adversarial settings. By integrating weighted regression and corruption-aware confidence bounds, it effectively filters malicious feedback. Future work may involve developing explicit detection mechanisms for corrupted nodes and addressing dynamic attackers who adapt their strategies over time.

Summary updated

Abstract

In this work, we investigate the online influence maximization in social networks. Most prior research studies on online influence maximization assume that the nodes are fully cooperative and act according to their stochastically generated influence probabilities on others. In contrast, we study the online influence maximization problem in the presence of some corrupted nodes whose damaging effects diffuse throughout the network. We propose a novel bandit algorithm, CW-IMLinUCB, which robustly learns and finds the optimal seed set in the presence of corrupted users. Theoretical analyses establish that the regret performance of our proposed algorithm is better than the state-of-the-art online influence maximization algorithms. Extensive empirical evaluations on synthetic and real-world datasets also show the superior performance of our proposed algorithm.
BibTeX
@article{cheng2025online,
  author = {Xiaotong Cheng and Behzad Nourani-Koliji and Setareh Maghsudi},
  title = {{Online Influence Maximization with Semi-Bandit Feedback under Corruptions}},
  journal = {IEEE Trans. Network Science \& Engineering},
  year = {2025},
  url = {https://openreview.net/forum?id=RCH1hBnZoh},
}
Figure