Socialized Language Model Smoothing via Bi-directional Influence Propagation on Social Networks

Rui Yan, Cheng-Te Li, Hsun-Ping Hsieh, Po Hu, Xiaohua Hu, Tingting HeWWW 2016 · DOI

TL;DR

This paper tackles the "Achilles' Heel" of social media text: extreme sparsity. They propose a novel "Bi-directional Socialized Language Model Smoothing" (BSLMS) method that leverages both textual content and the nuanced, directional influence between users on social networks to improve language model estimation. This approach significantly outperforms existing methods by capturing the asymmetric nature of social interactions.

What Problem Does This Paper Address?

Online social networks are awash with user-generated content, but individual posts (like tweets or microblogs) are often very short. This brevity leads to a "data sparsity" problem: many words appear infrequently, making it difficult for traditional language models to accurately estimate their probabilities. This is particularly problematic for tasks like information retrieval or content analysis, where a poor language model can lead to inaccurate results. Existing language model smoothing techniques often struggle with this extreme sparsity, especially in the context of social networks where user interactions and relationships are crucial. While some methods incorporate social information, they often treat influence as a one-way street, failing to capture the fact that a user's influence on another might be different from the reverse.

Methods

The core of this paper is the Bi-directional Socialized Language Model Smoothing (BSLMS) approach, built upon a socialized factor graph model. Here's a breakdown:

  • Factor Graph Model: This is a probabilistic graphical model that represents dependencies between variables. In this case, it models relationships between documents and users.
  • Bi-directional Influence: This is the key innovation. Instead of assuming influence flows equally between two users (or documents), BSLMS explicitly models influence in both directions (e.g., user A influencing user B, and user B influencing user A). This is crucial because social interactions are rarely symmetrical.
  • Attribute Factors: These capture inherent features of documents and users, such as text similarity, text quality (measured by Out-Of-Vocabulary ratio), posting popularity, social status, user similarity (based on common followers/followees), interaction strength, repost behavior, and user impacts (like PageRank scores).
  • Dependency Factors: These model the relationships between hidden variables (representing influence) within the factor graph, particularly focusing on documents authored by the same user. This helps propagate influence across related content.
  • Learning Algorithm: The model is trained using a factor graph inference algorithm (a directional sum-product algorithm) to estimate the bi-directional influence weights.
  • Language Model Smoothing: Once influence is estimated, term counts are propagated from other documents to the target document, discounted by the estimated influence. This effectively "smooths" the language model by borrowing information from influential sources, thereby mitigating the sparsity problem.

Datasets

The authors evaluated their approach on two large-scale social network datasets:

  • Twitter: English language microblogs, monitored from March 25, 2011, to May 30, 2011.
  • Weibo: Chinese language microblogs, monitored from September 29, 2012, to November 30, 2012.

They used roughly one month of data for training and the subsequent month for testing. No new benchmarks were introduced; they used existing datasets to compare against established methods.

Key Insights and Ideas

  • Direction Matters: The most significant insight is that social influence is inherently directional. Ignoring this asymmetry leads to suboptimal language model smoothing. Capturing this bi-directional influence allows for a more accurate estimation of how information propagates.
  • Text + Social = Better: Combining textual features with social network information provides a richer context for smoothing than relying on text alone. The social graph acts as a powerful prior for understanding content relevance.
  • Nuanced Influence: Different factors contribute to influence in varying degrees. Text similarity is a strong predictor, but social factors like interaction strength and repost behavior are also critical, especially in capturing the nuances of social propagation.
  • Factor Graph Power: The factor graph framework is well-suited for integrating diverse sources of information (textual, social, user attributes) and modeling complex dependencies, making it a flexible tool for this problem.

Key Results

The BSLMS method demonstrated significant improvements across both intrinsic and extrinsic evaluations:

  • Intrinsic Evaluation (Perplexity): BSLMS achieved lower perplexity scores across various hashtag clusters on both Twitter and Weibo datasets, indicating more accurate language model estimation. The paper highlights that BSLMS significantly outperformed the best rival baseline by Wilcoxon test at a significance level of 0.01.
  • Extrinsic Evaluation (Retrieval): In microblog search tasks, BSLMS achieved higher nDCG@k and MAP scores compared to all baselines. For instance, BSLMS achieved a nDCG@50 score of 0.509⋆, outperforming the next best baseline (SLMS) at 0.503⋆. The results indicate that the improved language models lead to better retrieval performance.
  • Factor Contributions: Experiments showed that all individual factors contributed positively, with text similarity and social interaction being particularly influential. The combination of all factors yielded the best results, underscoring the effectiveness of the integrated approach.

Limitations and Future Work

  • Parameter Tuning: The paper mentions that the parameter $\lambda$ (balancing original and smoothed language models) was set to 0.3 based on average performance across datasets, suggesting that dataset-specific tuning might yield further improvements.
  • Factor Contributions: While all factors showed positive contributions, the "dependency factor" was noted as the least powerful predictor, suggesting potential avenues for refinement.
  • Future Work: The authors suggest including more flexible social factors and adapting the model to a wider range of online social network structures. They also plan to investigate more detailed analysis of parameter settings and factor contributions.

Summary updated

BibTeX
@inproceedings{yan2016socialized,
  author = {Rui Yan and Cheng-Te Li and Hsun-Ping Hsieh and Po Hu and Xiaohua Hu and Tingting He},
  title = {{Socialized Language Model Smoothing via Bi-directional Influence Propagation on Social Networks}},
  booktitle = {The Web Conference},
  year = {2016},
  doi = {10.1145/2872427.2874811},
}
Figure