Cognitive Analysis in Social Networks: Winning Viral Marketing via CMAB and Graph DBs

TL;DR

Modern viral marketing is often hamstrung by a lack of data on how much one user actually influences another. This paper addresses this by treating the social network as a heterogeneous graph database and solving the Influence Maximization (IM) problem using Combinatorial Multi-Armed Bandits (CMAB). Instead of guessing influence probabilities, the system learns them on the fly.

The "Probability" Bottleneck in Viral Marketing

Influence Maximization (IM) is the task of finding a small set of "seed" users who can trigger the largest "word-of-mouth" cascade. Historically, researchers assumed we knew the probability of User A influencing User B. In reality, we don’t. Most state-of-the-art (SOTA) algorithms like TIM+ or IMM perform excellently if the probabilities are known, but fail or rely on poor heuristics when they are not.

The authors' insight is twofold:

1. Heterogeneity matters: Influence isn't just about "friendship." It's about shared experiences (e.g., two people reviewing the same restaurant with the same sentiment).
2. Learning while doing: If we don't know the probabilities, we should use Online Learning to estimate them while simulating or running the campaign.

Methodology: From Heterogeneous Graphs to Influential Paths

The framework operates in three distinct phases:

1. The OSN Graph Database

Unlike a simple adjacency matrix, the authors model the network (using Neo4j) as a feature-rich graph.

• Nodes: Users and Business Objects (e.g., Yelp restaurants).
• Edges: Friendships and Reviews.
• Attributes: Timestamps and Sentiment scores (extracted via NLP tagging).

2. Extracting Influential Paths with RPQs

The authors use Regular Path Queries (RPQ) to find specific behavioral patterns. For example, a "Social Path" might be:

User A reviews Business X $\to$ User B (who is a friend of A) reviews Business X with the same mood within 50 days.

Figure: Abstracting a complex heterogeneous network into a simplified influence graph using path queries.

3. The CMAB Strategy

To solve the IM problem without initial probabilities, the authors map IM to the Combinatorial Multi-Armed Bandit problem:

• Arms: Edges in the influence graph.
• Superarm: A set of outgoing edges from the chosen seed nodes.
• Reward: The total "spread" (number of newly activated users).

By using an $ϵ$-greedy strategy, the algorithm balances Exploration (trying new nodes to see if they are influential) and Exploitation (using nodes known to have high influence).

Figure: Step-by-step activation of the graph using the CMAB superarm mechanism.

Experimental Battleground: The Yelp Dataset

The authors tested their prototype on the massive Yelp Challenge dataset. They compared three CMAB variants (Pure Exploration, Pure Exploitation, and $ϵ$-greedy) against the SOTA TIM+ algorithm.

Key Findings:

• Near-Optimal Spread: After roughly 300 iterations, the CMAB approach achieved a spread nearly identical to TIM+, which had the "unfair" advantage of knowing the true probabilities.
• Efficiency: The CMAB approach showed superior scalability. For extremely large graphs, its execution time remained linear and lower than many greedy SOTA heuristics.

Table: Mapping of CMAB terminology to Influence Maximization concepts.

Critical Insight & Future Outlook

The brilliance of this work lies in its agnosticism. It doesn't care how you define influence; as long as you can write an RPQ to find the path, the CMAB engine will handle the math of finding the best seeds.

Limitations: The 50-day window for the Yelp study was chosen for computational feasibility; however, real-world influence might be much faster or much slower depending on the industry.

The Takeaway for Tech Leaders: Don't wait for perfect data to start a viral campaign. By implementing a bandit-based reinforcement learning layer on your graph data, your marketing engine can "learn" your most influential customers through trial and error, often outperforming static models that rely on shaky assumptions.