Beyond Impressions: Optimizing Social Display Ads via Influence-and-Exploit

TL;DR

Display advertising in social networks often ignores the "social" part. This paper formalizes the Social Display Optimization problem: how to order $B$ impressions to maximize clicks when a user's likelihood to click increases if their friends have already clicked. The authors prove this is computationally "hard" (APX-hard) but show that a Two-stage Heuristic (Influence first, Click-optimization second) can double the performance of conventional greedy methods.

Problem & Motivation: The Social Cue Effect

Most display ads are sold on a CPM (Cost-per-mille) basis, where a publisher promises $B$ impressions. However, social networks like Facebook and LinkedIn have a secret weapon: Social Cues. If you see that "3 friends liked this ad," you are significantly more likely to click.

Current systems often pick users who are most likely to click now (Largest Probability Greedy). The authors argue this is short-sighted. If you show the ad to "Influencer A" first, even if they have a lower initial click probability, their click might "unlock" the interest of 50 other friends. The challenge is that the search space for the "optimal order" of ads is an exponential decision tree, making it theoretically impossible to find a perfect solution in polynomial time.

Methodology: The Two-stage Strategy

The core insight of the paper is moving from a static allocation to an adaptive strategy.

1. The Model

The probability $p_u(S)$ of user $u$ clicking depends on the set $S$ of people who clicked before them. The authors test several functions:

• Linear Influence: $p_u(S)=c_u+\sum w(v,u)$.
• Independent Cascade: $p_u(S)=1-\prod (1-p_{v,u})$.
• Concave Influence: Using $\sqrt{x}$ or $\log (x)$ to model diminishing returns of social cues.

2. The Heuristic: Influence-and-Exploit

Since the problem is $n^{1/8}$ hard to approximate (linked to the Planted Dense Subgraph Conjecture), the authors propose a hybrid approach:

• Stage 1 (Influence): Spend a fraction $\alpha$ of the budget $B$ on the "Most Influential" users. The goal here isn't immediate clicks, but seeding the network.
• Stage 2 (Exploit): Spend the remaining $(1-\alpha )$ budget on users who now have the highest click probability, thanks to the seeds planted in Stage 1.

Figure 1: Conceptual visualization of the social network structure where nodes influence their neighbors' click-through rates.

Experiments & Results

The authors tested their theories on Flixster (movie ratings) and Goodreads (book catalogs) datasets.

Key Findings:

• Huge Gains: The Two-stage heuristic outperformed the "Largest Probability" baseline by 11% to 100% on Goodreads.
• The Alpha ($\alpha$) Trade-off: As the total budget $B$ increases, the optimal $\alpha$ (the time spent in the "Influence" stage) also increases. This suggests that with more resources, you should "explore" (seed) more aggressively.
• Structural Sensitivity: The algorithm performs best when it identifies dense clusters within the social graph where influence can cascade effectively.

Figure 2: Performance comparison on the Flixster dataset showing the Two-stage heuristic (highest line) significantly outperfoming the baseline Most Influential and Largest Probability methods.

Critical Analysis & Conclusion

Takeaway

Social advertising isn't just about who you show the ad to, but when you show it. By treating ad delivery as a sequential process, publishers can create a "virtuous cycle" of clicks.

Limitations

• Privacy: Showing social cues ("Your friend X clicked this") requires user consent, which may limit the reach of the influence function.
• Real-time Latency: Calculating the "Most Influential" user in real-time as clicks happen is computationally expensive for networks with millions of nodes.

Future Outlook

This work paves the way for "Viral Display Ads." Future research could look into Multi-advertiser Social Optimization, where different brands compete to influence the same set of users, or how Generative AI could personalize social cues to further boost the influence function $p_u(S)$.