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:
- 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.
- 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:
- 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.
- 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.
- 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