Abstract
Influence maximization (IM) traditionally seeks to find seed users in a social network to maximize information spread. However, conventional methods often assume all exposure is beneficial, ignoring that users with negative opinions can damage a product's reputation. This paper introduces Opinion-aware Influence Maximization (OIM), which aims to select seeds that maximize positive word-of-mouth while minimizing negative spread. We propose a three-stage framework utilizing Graph Neural Networks (GNNs) for opinion estimation and a sandwich approximation algorithm to handle the non-submodular nature of the objective function. Experimental results on real-world datasets show that OIM significantly improves net positive influence compared to opinion-blind methods.
The Problem: Beyond "All Publicity is Good Publicity"
In the classic IM problem, the goal is to trigger the largest possible cascade of information. This approach has two major flaws:
- Item-Unawareness: It assumes opinions are formed solely by social influence, ignoring pre-existing user preferences for specific items.
- Algorithmic Complexity: Maximizing the difference between positive and negative influence makes the objective function non-submodular. This breaks the theoretical guarantees of standard greedy algorithms.
The OIM Framework
The authors propose a pipeline to address these challenges by integrating preference learning with social diffusion.
1. Opinion Estimation via GNNs
Using a GNN, the model learns latent representations of users and items from historical rating data and social graphs. This allows the system to predict whether a specific user's reaction to a target item will be positive, neutral, or negative before the campaign begins.
2. Opinion-aware Independent Cascade (OIC)
The standard Independent Cascade model is extended so that activated users spread their specific predicted opinion. This more accurately reflects real-world word-of-mouth dynamics.
3. The Sandwich Greedy Algorithm
To solve the non-submodular optimization problem, the authors employ a "sandwich" strategy. They derive submodular upper and lower bounds for the objective function. By running greedy selection on these bounds, they achieve a data-dependent approximation guarantee for the final seed set.
Key Results and Insights
The researchers evaluated OIM on three datasets: Ciao, Epinions, and MovieLens.
- The "Hater" Effect: Traditional algorithms like IMM often perform poorly because they are "opinion-blind." On polarized datasets like MovieLens, traditional methods may accidentally pick seeds that trigger massive negative cascades, resulting in a net-negative impact on reputation (as seen in the negative opinion scores for baselines in the MovieLens plot).
- Superior Net Influence: Across all datasets, OIM consistently achieved higher "total opinion" (Positive Spread - Negative Spread) than random, degree-based, or standard IM heuristics.
- Efficiency: Despite the complexity of GNNs and sandwich bounds, OIM's running time remains comparable to state-of-the-art traditional methods, making it viable for large-scale social networks.
Conclusion
OIM represents a shift from quantity-based to quality-based influence. By tailoring seed selection to specific products and accounting for potential negative feedback, the framework provides a more robust tool for viral marketing. Future work may explore dynamic opinions that shift during interaction and model-independent diffusion processes.
Summary updated