Opinion-aware Influence Maximization in Online Social Networks

Ying Wang, Yanhao Wang

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:

  1. Item-Unawareness: It assumes opinions are formed solely by social influence, ignoring pre-existing user preferences for specific items.
  2. 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.

Overview of the OIM framework pipeline, from historical data to seed selection.

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.

Performance comparison of OIM against baselines (Rand, DegDis, IMM) across three datasets.
  • 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

Abstract

Influence maximization (IM) aims to find seed users on an online social network to maximize the spread of information about a target product through word-of-mouth propagation among all users. Prior IM methods mostly focus on maximizing the overall influence spread, which assumes that all users are potential customers of the product and that more exposure leads to higher benefits. However, in real-world scenarios, some users who dislike the product may express and spread negative opinions, damaging the product's reputation and lowering its profit. This paper investigates the opinion-aware influence maximization (OIM) problem, which finds a set of seed users to maximize the positive opinions toward the product while minimizing the negative opinions. We propose a novel algorithm for the OIM problem. Specifically, after obtaining the users with positive and negative opinions towards the product from historical data, we design a reverse reachable set-based method for opinion-aware influence estimation and a sandwich approximation algorithm for seed set selection. Despite the NP-hardness and non-submodularity of OIM, our algorithm achieves a data-dependent approximation factor for OIM. Experimental results on three real-world datasets demonstrate that our algorithm improves the spread of positive opinions while reducing the spread of negative opinions compared to existing methods.
BibTeX
@inproceedings{wang2023opinion,
  author = {Ying Wang and Yanhao Wang},
  title = {{Opinion-aware Influence Maximization in Online Social Networks}},
  booktitle = {DSIT},
  year = {2023},
  url = {https://openreview.net/forum?id=Qrih9OGlle},
}
Figure