AdHeat: an influence-based diffusion model for propagating hints to match ads

Hongji Bao, Edward Y. ChangWWW 2010 · DOI

TL;DR

This paper introduces AdHeat, a novel social ad model that leverages user influence to improve ad matching beyond traditional relevance-based methods. By propagating "hint words" from influential users, AdHeat effectively addresses data sparsity issues and significantly boosts click-through rates (CTR) on online social platforms.

What Problem Does This Paper Address?

Online advertising, particularly on social networks, faces a significant challenge: data sparsity. Traditional ad placement models rely on either content relevance (matching ads to webpage content) or user relevance (matching ads to user profiles and interests). However, these methods struggle when user profiles are incomplete or when users don't generate much content. Furthermore, influential users on social networks often don't click on ads highly relevant to their expertise, suggesting that simple relevance isn't enough. The paper aims to bridge this gap by incorporating user influence into the ad matching process, recognizing that influential users' opinions and activities can guide ad relevance for others.

Methods

AdHeat employs a three-step approach:

  1. Hint Word Generation: This step uses Latent Dirichlet Allocation (LDA), specifically a parallel implementation (PLDA), to represent users by a set of "hint words" derived from their activities (e.g., posts, answers). To account for the recency of information, only recent user activities are considered.
  2. Influential User Ranking: The paper utilizes the HITS (Hypertext Induced Topic Selection) algorithm to rank users by their influence. Crucially, AdHeat constructs a social graph where edge weights are not just based on simple friendships but are quantified by the frequency and quality of user interactions, considering factors like timeliness, relevance, and originality of contributions.
  3. Influence Propagation: This is the core innovation. AdHeat models hint word propagation as a "heat diffusion" process on the social graph. Influential users act as heat sources, and their hint words spread through the network like heat. This diffusion process enriches the hint word lists of less influential users, effectively combating data sparsity and making ad matching more robust. The heat diffusion is modeled using a discrete approximation of the heat equation.

Datasets

The experiments were conducted on Google Confucius, a large online Q&A community available in multiple countries. The study involved analyzing the social graph of half a million registered users to compute influence scores and propagate hints. For the actual ad placement experiments, a subset of 5,000 active users was selected. The ad set was sourced from Google AdSense.

Key Insights and Ideas

  • Influence Matters More Than Relevance for Experts: Influential users, despite their expertise, are less likely to click on highly relevant ads. This suggests that for experts, familiarity can diminish curiosity, and a different approach is needed.
  • Hint Word Propagation Solves Sparsity: For less influential users, data sparsity is a major hurdle for effective ad targeting. AdHeat's influence propagation mechanism effectively remedies this by transferring valuable hint words from influential users.
  • Heat Diffusion as a Metaphor for Influence: The paper elegantly uses heat diffusion as a model for how influence and information spread through social networks, providing a principled way to aggregate hints.
  • Quality of Interaction is Key for Influence: Simply counting friendships isn't enough. The paper emphasizes that the quality of interactions (timeliness, relevance, originality) is crucial for accurately identifying influential users.

Key Results

  • Significant CTR Improvement: AdHeat consistently outperformed traditional content-based ad models and its own influence model without propagation.
  • The influence-based model without propagation showed a 66.9% average CTR improvement over the content-based model over 18 days.
  • The influence model with propagation achieved an impressive 102% peak CTR improvement over the influence model without propagation on day three, with an average improvement of 66.4% over 18 days.
  • Influential Users vs. Performance: While influential users contribute more content, they exhibit lower CTRs. This reinforces the idea that relevance alone isn't sufficient for them, and the propagation mechanism is vital for broader user groups.

Limitations and Future Work

  • Timeliness of Hint Words: The paper notes that the decrease in CTR improvement over time is likely due to the static nature of hint words. Future work should involve periodically recomputing hint words to keep pace with evolving user interests.
  • Feedback for Re-weighting: The paper suggests that using CTR as feedback to dynamically re-weight propagated hint words would be an optimal approach, but this was not implemented in the current study due to the need for real-time feedback.
  • Generalizability: While tested on a Q&A community, the model's effectiveness on other types of social networks (e.g., forums, microblogging) could be explored further.
  • User Boredom: The study acknowledges that users might click on ads less over time due to repeated exposure, and while they tried to mitigate this, it remains a factor in long-term ad effectiveness.

Summary updated

BibTeX
@inproceedings{bao2010adheat,
  author = {Hongji Bao and Edward Y. Chang},
  title = {{AdHeat: an influence-based diffusion model for propagating hints to match ads}},
  booktitle = {The Web Conference},
  year = {2010},
  doi = {10.1145/1772690.1772699},
}
Figure