Beyond Static Influence: Querying and Learning Influence Graphs for Viral Marketing

TL;DR

Viral marketing aims to trigger "word-of-mouth" cascades by targeting a handful of influential users. However, identifying these users is difficult because influence is often hidden and multidimensional. This paper proposes a system that first extracts influence patterns using Regular Path Queries (RPQs) on a graph database and then uses Combinatorial Multi-Armed Bandits (CMAB) to "learn" who is actually influential through an exploration-exploitation mechanism, rather than assuming fixed probabilities.

The Problem: The Blind Spot in Traditional IM

Standard Influence Maximization (IM) is often treated as a pure optimization problem: given a graph and edge weights (probabilities), find $k$ nodes to maximize the spread.

The reality is messier:

1. Unknown Probabilities: We rarely know the exact probability that User A will influence User B just by looking at the graph.
2. Relational Complexity: Influence isn't just about "friendship." It's about shared experiences—like two users reviewing the same business within the same timeframe with the same mood.

Methodology: From Graph Queries to Bandit Learning

The authors propose a two-stage approach to bridge the gap between raw data and actionable marketing insights.

1. Extracting the Influence Graph via RPQs

By modeling OSNs like Yelp as edge-labeled graphs, the researchers use Regular Path Queries to identify "Social Paths." For example, a query can find users who have reviewed the same business ($u_i\stackrel{review}{\to }b\stackrel{review}{\leftarrow }{u}_j$). By applying filters (same mood, close timestamps), they distill a complex multi-relational network into a homogeneous Influence Graph.

Figure 1: The multilayer system architecture integrating Spark, Neo4j, and the CMAB IM module.

2. Learning through CMAB

To solve the IM problem without pre-set weights, the authors frame it as a Combinatorial Multi-Armed Bandit (CMAB) problem:

• Arms: Each edge in the influence graph is an "arm."
• Super-arm: A set of seed nodes $S$ that triggers a cascade.
• Regret Minimization: At each round, the system chooses between Exploring (picking random seeds to gain knowledge) and Exploiting (picking current "winners" to maximize spread).

The formula for Regret ($\rho$) captures the cost of learning: $\rho =n\cdot \sigma (S^{\ast })-{\sum }_{i=1}^n\bar{\sigma }(S^i)$ The goal is to minimize this gap as the system observes which "recommendations" actually result in activations.

Experiments: Real-world Validation on Yelp

The researchers tested their framework on the Yelp Dataset Challenge, involving 1.1 million users. They used the Independent Cascade (IC) model as the underlying diffusion physics.

Figure 2: Spread achieved using the Weighted Cascade Model (WCM) as a benchmark.

Crucially, the study showed that by using a greedy strategy as an approximation oracle within the CMAB loop, the system could converge toward the optimal influence spread even when starting with zero knowledge of individual user influence levels.

Critical Analysis & Conclusion

Takeaway

The synergy between Graph Databases (logic/querying) and Online Learning (stochastic optimization) is the highlight of this work. It moves Viral Marketing from a "static snapshot" analysis to a dynamic, iterative process of discovery.

Limitations

• Computational Overhead: CMAB requires multiple "rounds" or iterations to converge. In a real-world marketing campaign, these "rounds" correspond to actual expensive promotions.
• Sentiment Complexity: While the system uses Sentiment Analysis (GATE libraries), the nuances of sarcasm or industry-specific jargon might still skew the influence graphs.

Future Outlook

The next step for this research is scaling to Graph Streams, where the network topology itself changes every second. Integrating this with state-of-the-art Big Data stacks (like Apache Spark) will be crucial for real-time viral marketing in the age of TikTok and instant trends.