Generate&Extend: Redefining Influence Maximization for the Multi-Relational Era at WeChat
Influence Maximization in Multi-Relational Social Networks
This paper introduces "Generate&Extend," a novel Influence Maximization (IM) framework designed for Multi-Relational Social Networks (MRSNs) like WeChat. It addresses the gap in traditional IM by incorporating 1-to-N group relations alongside 1-to-1 friendships, achieving SOTA performance in both offline simulations and large-scale online deployment (serving 200M+ users).
Executive Summary
TL;DR: Most Influence Maximization (IM) research lives in a world of 1-to-1 "friend" links. This paper, a collaborative effort from Tencent's WeChat team, breaks that mold by introducing Multi-Relational Social Networks (MRSNs). By accounting for the explosive power of 1-to-N group chats, they propose the Generate&Extend framework, which effectively doubles the activation efficiency compared to traditional SOTA methods like OPIM and SSA.
Context: This isn't just a theoretical paper—it's a massive deployment success story, currently powering mini-program promotions for over 200 million WeChat users. It shifts the IM paradigm from simple connectivity to structural identity.
The "Group Chat" Blind Spot: Why Prior IM Fails
Traditional IM algorithms (e.g., DegreeDiscount, TIM, SSA) optimize for social graphs where edges represent individual pairs. However, real-world platforms like WeChat, WhatsApp, or Slack are dominated by Group Relations.
Through data analysis of WeChat's anonymized logs (1.8 billion edges), the authors found two critical insights:
- Reach Power: Users reach significantly more people via groups than via 1-to-1 friendships.
- The "Fake Seed" Problem: A user might be in 100 groups (high degree) but never post (zero influence). Traditional algorithms would wrongly select this user as a prime seed.
Methodology: The Generate&Extend Framework
The framework splits the problem into two distinct phases to balance the trade-off between the high computational cost of 1-to-N relations and the need for high-quality seeds.
1. Truncated Meta-seed Generator
Instead of calculating global influence (NP-hard and slow on billion-scale graphs), the authors use -hop reachable sets to find meta-seeds. This is essentially an optimized version of Reverse Influence Sampling (RIS) that truncates the search space to stay efficient in high-degree environments.
2. Structural Seed Extender
This is the "secret sauce." Since meta-seeds are limited in number, the framework extends them by finding users with similar Structural Identities.
- Relation-aware Distance: It calculates a structural distance that separates 1-to-1 and 1-to-N behaviors.
- Structure-embedded Representation: Using a multi-layer graph, it encodes whether a user behaves like a "hub," a "bridge," or a "silent member" into low-dimensional vectors.
Figure 3: The Generate&Extend Pipeline. (a) Seed generation via truncation; (b) Structural embedding and extension.
Battle-Tested Results
Comparison against SOTA methods (SSA, OPIM) on three massive WeChat datasets (7-day, 15-day, and 31-day windows) revealed:
- Online Activation: Generate&Extend consistently yielded a higher number of activated users across all test days.
- Fake Seed Rate: It achieved a drastically lower fake seed rate compared to DegreeDiscountIC, proving that structural analysis identifies actual influencers, not just high-degree nodes.
- Offline Sharing: The sharing frequency of the selected seeds was nearly 2x higher than the Random and DegreeDiscount baselines.
Figure 4: Online activation across multiple WeChat datasets shows a clear lead for the proposed method.
Critical Insight: Role over Connectivity
The core takeaway is that in the multi-relational era, who you are in the social structure matters more than how many people you are "connected" to. A user who shares effectively in small groups is often a better seed than a user who belongs to many large groups but never engages.
Limitations & Future Work
While highly effective, the framework is currently optimized for static "snapshots" of influence. As social dynamics shift rapidly (e.g., trending topics), integrating Temporal Influence—how timing affects group responsiveness—represents the next frontier for MRSN research.
Conclusion
WeChat’s Generate&Extend framework sets a new standard for industrial-scale Influence Maximization. By treating group relations as first-class citizens and leveraging structural embeddings, it moves IM from a graph-theory exercise to a high-precision marketing tool.