Relational learning via latent social dimensions

Lei Tang, Huan LiuKDD 2009 · DOI

TL;DR

Social media networks are complex and multi-faceted, with connections between users arising from various relationships. This paper proposes a novel approach to relational learning that extracts "latent social dimensions" from these networks, representing underlying affiliations. These dimensions are then used as features for discriminative learning, outperforming existing methods, especially when labeled data is scarce.

What Problem Does This Paper Address?

Traditional machine learning often assumes data points are independent and identically distributed (IID). However, social media platforms like Facebook, blogs, and photo-sharing sites generate data in the form of networks where users are interconnected. These connections are not monolithic; a user might be connected to another due to being colleagues, classmates, friends, or sharing similar interests. Existing relational learning methods, particularly those using collective inference, often treat these connections homogeneously, potentially blurring the true relationships and class memberships. This can lead to suboptimal performance in tasks like user profiling, recommendation, and advertising, especially when only a small amount of labeled data is available. The paper aims to address this by explicitly modeling the multi-dimensional nature of social connections.

Methods

The core of the proposed method, termed "Latent Social Dimensions Approach" (SocDim), involves two main steps:

  1. Extracting Latent Social Dimensions: Instead of directly using the raw network connections, SocDim first extracts latent social dimensions. These dimensions are intended to capture underlying affiliations or "communities" within the network. The authors leverage modularity maximization, a technique commonly used in community detection, to achieve this. Specifically, they compute the top eigenvectors of the modularity matrix. This approach allows for "soft clustering," meaning a user can belong to multiple dimensions to varying degrees, reflecting the multi-faceted nature of social interactions. The extracted dimensions are then available for all nodes, both labeled and unlabeled.
  2. Constructing a Discriminative Classifier: Once the latent social dimensions are extracted, they are treated as features. A standard discriminative classifier, such as a linear Support Vector Machine (SVM), is then trained using these features and the available labeled data. The SVM automatically learns which of these latent dimensions are most relevant for predicting the class labels. A key advantage highlighted is that this approach eliminates the need for collective inference during prediction. The latent dimensions themselves are designed to encapsulate the relevant network information, making direct prediction possible and more efficient. The authors also note that other features, like user profiles or content, can be easily incorporated into this framework.

Datasets

The authors evaluated their approach on two real-world social media datasets:

  • BlogCatalog: This dataset consists of blogs organized into categories. Each blog is associated with user-defined tags and snippets from recent posts. The network is formed by users connecting to other bloggers.
  • Flickr: This dataset is from a popular photo-sharing platform. Users can tag photos and add contacts. The network is constructed based on user connections, and labels are derived from user subscriptions to various interest groups.

Both datasets exhibit characteristics typical of social networks, such as sparsity and scale-free degree distributions.

Key Insights and Ideas

  • Social connections are multi-dimensional: The paper strongly emphasizes that user connections in social media are not uniform but arise from diverse underlying reasons (e.g., professional, social, interest-based).
  • Latent dimensions capture affiliations: By extracting latent social dimensions, the method effectively models these diverse affiliations, providing a richer representation of user relationships than simple network connectivity.
  • Eliminating collective inference: A significant insight is that by properly extracting informative latent dimensions, the need for computationally expensive collective inference during prediction can be bypassed, leading to a more efficient and potentially more robust model.
  • Robustness with limited labels: The proposed method demonstrates superior performance, particularly in scenarios with scarce labeled data, suggesting its effectiveness in semi-supervised learning settings common in social media analysis.

Key Results

  • Superior Performance: SocDim consistently outperformed baseline relational learning methods (wvRN, LBC, LGC, MAJORITY, RANDOM) on both BlogCatalog and Flickr datasets across various labeling ratios.
  • Effectiveness with Few Labels: The performance advantage of SocDim was most pronounced when the proportion of labeled data was low. For instance, on BlogCatalog with 10% labeled data, SocDim achieved a Micro-F1 score of 27.35%, significantly higher than the next best method (wvRN at 19.51%).
  • No Benefit from Collective Inference: Combining SocDim with collective inference did not improve performance and, in some cases, even degraded it, supporting the claim that latent dimensions already capture necessary relational information.
  • Sensitivity to Dimensionality: The performance was found to be sensitive to the number of latent dimensions, with an optimal range suggested (around 400-500 dimensions) for the tested datasets.

Limitations and Future Work

  • Orthogonality of Dimensions: The current method extracts orthogonal latent dimensions. The authors suggest exploring fast sparse approximations to avoid large-scale eigenvalue problems and investigate if orthogonality is strictly necessary.
  • Dynamic Networks: Social networks are constantly evolving. The paper acknowledges the challenge of efficiently updating the relational model in large-scale, dynamic networks.
  • Group-Level Information: The authors plan to explore how to incorporate group-level information (e.g., group size, connection density) with social dimensions.
  • Multi-Entity Networks: Extending the approach to handle networks with multiple types of entities is also a future direction.

Summary updated

BibTeX
@inproceedings{tang2009relational,
  author = {Lei Tang and Huan Liu},
  title = {{Relational learning via latent social dimensions}},
  booktitle = {ACM SIGKDD Conference on Knowledge Discovery and Data Mining},
  year = {2009},
  doi = {10.1145/1557019.1557109},
}
Figure