This paper, recently published by researchers from Ruhr-University Bochum and the University of Tübingen, tackles a realistic and messy problem in social network analysis: how do you maximize your influence when some people in the network are actively working against you?
TL;DR
The authors introduce CW-IMLinUCB, a novel bandit algorithm designed for Online Influence Maximization (OIM) that remains robust even when a portion of the network nodes are "corrupted" (acting adversarially). By integrating weighted ridge regression into a linear bandit framework, the algorithm effectively filters out malicious feedback, achieving superior regret performance compared to existing state-of-the-art methods.
What Problem Does This Paper Address?
Influence Maximization (IM) is the classic problem of picking a small set of "seed" nodes in a social network to trigger the largest possible cascade of information (like a viral marketing campaign). In the Online version (OIM), we don't know the "activation probabilities" (how likely one person is to influence another) beforehand. We have to learn them by trial and error—a classic "exploration vs. exploitation" bandit problem.
The "gap" identified here is that almost all previous OIM research assumes every node is a "good actor" following a predictable stochastic model. In reality, social networks are rife with corrupted nodes: bots, trolls, or influencers who might provide counterproductive reviews or adopt "disputed behaviors" to trick the system. Standard algorithms try to learn from this corrupted data, leading them to make poor seeding choices. This paper asks: can we still find the best influencers if some nodes are trying to mislead us?
Methods
The authors model the network using the Independent Cascade (IC) model and treat the learning process as a Linear Contextual Bandit problem. Their proposed algorithm, CW-IMLinUCB (Confidence Weighted Influence Maximization Linear Upper Confidence Bound), introduces a few key innovations:
- Weighted Ridge Regression: Instead of treating every observed interaction equally, the algorithm assigns a weight ($\omega$) to each observation. If an edge's features suggest it might be highly uncertain or potentially corrupted (based on a "confidence radius"), the algorithm down-weights that observation.
- Robust UCB: It calculates an Upper Confidence Bound for activation probabilities that includes an extra term to account for the "corruption budget." This ensures the algorithm remains optimistic enough to explore but cautious enough not to be derailed by adversarial outliers.
- Semi-Bandit Feedback: The learner observes "edge-level" feedback—meaning they see exactly who influenced whom along the path of the cascade, which provides more granular data than just seeing the total number of influenced people.
Datasets
The researchers evaluated their algorithm using:
- Synthetic Datasets: Erdős-Rényi graphs of varying sizes ($n=10$ and $n=50$). These allowed for controlled experiments where the researchers could precisely place corrupted nodes and define their adversarial behavior (e.g., a "flip-$\theta$ attack" where the node acts the opposite of how it's expected to).
- Real-World Dataset: A subgraph of the Facebook network dataset (300 nodes, 2,046 edges). This tested the algorithm's performance on actual social topologies.
Key Insights and Ideas
- Location is Everything: One of the most important "aha" moments is that the number of corrupted nodes matters much less than their position. A single corrupted node in a high-centrality, pivotal position can do more damage to an influence campaign than dozens of corrupted nodes on the periphery.
- The Cost of Robustness: The authors found that if there is no corruption, their robust algorithm actually performs slightly worse than standard ones. This is because the "robustness" terms in the math force the algorithm to perform extra, unnecessary exploration. However, as soon as even a small amount of corruption is introduced, standard algorithms' performance collapses, while CW-IMLinUCB remains stable.
- Topology-Dependent Regret: The theoretical analysis shows that the "regret" (the gap between the algorithm's performance and the theoretical ideal) depends on specific graph properties ($E^*$ and $E^c$), essentially quantifying how "vulnerable" a specific network structure is to corruption.
Key Results
- Superior Robustness: In experiments on the Facebook dataset with 20 corrupted users, CW-IMLinUCB maintained a significantly lower cumulative regret than state-of-the-art algorithms like IMLinUCB and DILinUCB.
- Theoretical Guarantees: The authors proved a regret bound of $O(dBE^* \sqrt{T} \log(nT) + BE^* E^c C d \log(nT))$. Crucially, the second term is linear in the corruption budget ($C$), which is a strong theoretical guarantee for adversarial settings.
- Adaptability: The algorithm showed "inflection points" in its regret plots, demonstrating that it successfully learns to "weight down" and ignore corrupted nodes over time.
Limitations and Future Work
- Worst-Case Assumptions: The current regret bound assumes a "worst-case" scenario where corrupted users can easily spread their influence. The authors suggest that future bounds could be tightened by considering more specific corruption models.
- Detection vs. Mitigation: CW-IMLinUCB mitigates the effect of corruption but doesn't explicitly detect and "ban" the corrupted nodes. Integrating a dedicated corrupted-user detection mechanism is a suggested next step.
- Dynamic Attackers: The paper assumes a fixed corruption budget. A more complex future direction would involve "adversarial" attackers who also learn and change their strategy in response to the seeding algorithm.
Summary updated