Opinion-aware Influence Maximization in Online Social Networks

Ying Wang, Yanhao Wang

TL;DR

Traditional influence maximization (IM) aims to spread information to as many people as possible, but it ignores a critical reality: not everyone will like what you’re selling. This paper introduces Opinion-aware Influence Maximization (OIM), a framework that uses historical data and Graph Neural Networks to identify seeds that maximize positive word-of-mouth while actively minimizing the spread of negative opinions.

What Problem Does This Paper Address?

In the classic Influence Maximization problem, the goal is to find a small set of "seed" users in a social network to trigger the largest possible cascade of information. The underlying assumption is that all exposure is good. However, in the real world, a product launch can backfire if influential users who dislike the product start spreading negative reviews.

The authors identify two major gaps in existing research:

  1. Item-Unawareness: Most models assume opinions are formed randomly or solely by neighbors, ignoring the fact that users have pre-existing preferences based on the specific item being promoted.
  2. Algorithmic Complexity: When you try to maximize the difference between positive and negative influence, the mathematical objective function loses a property called submodularity. In plain English, this means the standard "greedy" algorithms used for decades no longer provide any theoretical guarantees that the solution is even close to optimal.

Methods

The authors propose a three-stage pipeline to solve OIM:

  1. Opinion Estimation (The GNN Layer): They use a Graph Neural Network (GNN) to learn latent representations (embeddings) of both users and items. By training on historical rating data and the social graph, the model predicts whether a user's opinion toward a specific target item will be positive, neutral, or negative.
  2. Opinion-aware Independent Cascade (OIC): They extend the standard Independent Cascade diffusion model. In this version, when a user is "activated," they spread the specific opinion (positive, neutral, or negative) predicted in step one.
  3. The Sandwich Greedy Algorithm: Since the objective function (Positive Spread minus Negative Spread) is non-submodular, the authors employ a "sandwich" strategy. They derive two submodular functions—one that acts as an upper bound and one as a lower bound. By running a greedy selection on these bounds and the original function, they can find a seed set with a data-dependent approximation guarantee.

Datasets

The researchers evaluated their algorithm on three real-world datasets:

  • Ciao & Epinions: Consumer electronics/product review sites where both social "trust" links and item ratings are available.
  • MovieLens: A classic movie recommendation dataset. Since it lacks a social graph, the authors constructed one by linking users with high Jaccard similarity in their rating histories.

Key Insights and Ideas

  • The "Hater" Effect: Traditional IM algorithms (like IMM) often perform poorly in OIM because they are "opinion-blind." On datasets like MovieLens, where opinions are polarized, traditional methods might accidentally pick seeds that trigger massive negative cascades, resulting in a net-negative impact on reputation.
  • DS Decomposition: The paper treats the objective function as a "Difference of Submodular" (DS) functions. This allows them to leverage optimization techniques usually reserved for much simpler problems.
  • Item-Specific Seeding: The "best" influencers are not universal. A user who is highly influential for action movies might be a "negative seed" for a documentary. The GNN ensures the seed selection is tailored to the specific product's appeal.

Key Results

  • Superior Net Influence: Across all datasets, the OIM algorithm consistently achieved a higher "total opinion" (Positive Spread - Negative Spread) than baselines like random selection, degree-based heuristics, or standard IM algorithms.
  • Robustness to Noise: By varying an error parameter ($\epsilon$), the authors showed that their algorithm can strike a balance between computational speed and the stability of the influence estimation.
  • Efficiency: Despite the added complexity of GNNs and sandwich bounds, the running time of OIM remains comparable to state-of-the-art traditional IM methods (like IMM), making it viable for large-scale networks.

Limitations and Future Work

  • Static Opinions: The model assumes a user’s opinion is fixed once they are activated. In reality, opinions can shift during a conversation or over time.
  • Pre-defined Diffusion: The model relies on the Independent Cascade (IC) assumption. The authors suggest that future work should explore "model-independent" OIM, where the diffusion process itself is learned directly from observations rather than assumed.
  • Data Requirements: The method requires historical rating data to train the GNN. It may not perform as well for "cold-start" items where no prior user feedback exists.

Summary updated

Abstract

Influence maximization (IM) is essential for viral marketing in online social networks (OSNs). Given an OSN represented as a graph, IM finds a set of nodes (users) as “seeds” to initiate a promotion campaign so that the spread of information through word-of-mouth propagation among users is maximized. Previous IM approaches mainly focus on maximizing the total influence spread across the OSN. They assume that all users are potential customers and more exposure can lead to higher profits. However, in real-world scenarios, users who dislike an item may express and spread negative opinions about it, thus lowering the benefits of promotion. In this paper, we study an opinion-aware influence maximization (OIM) problem that selects a set of k seed users to maximize the positive opinions about a target item and minimize the negative opinions about it in an OSN. Given that the sets of users with positive, neutral, and negative opinions about the target item are obtained from historical data, we design a novel algorithm for OIM that consists of an opinion-aware influence estimation scheme based on reverse reachable sets and a seed set selection method based on sandwich approximation. Theoretically, although OIM is NP-hard and non-submodular, our algorithm still has a data-dependent approximation factor. Empirically, by performing extensive experiments on several real-world datasets, we show that our algorithm boosts the spread of positive opinions while limiting the spread of negative opinions compared to existing IM algorithms.
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},
}

Loading related content...

Figure