Stochastic Relational Models for Large-scale Dyadic Data using MCMC

Shenghuo Zhu, Kai Yu, Yihong GongNeurIPS 2008 · OpenReview

TL;DR

This paper introduces a scalable, fully Bayesian approach to Stochastic Relational Models (SRMs) for predicting relationships in massive datasets, such as user-item ratings. By leveraging a clever mathematical "dual representation" trick, the authors reduce the computational complexity of inference from cubic in the number of entities to cubic in the number of latent dimensions. This breakthrough allows SRMs to scale to datasets 1,000 times larger than previously possible.

What Problem Does This Paper Address?

The authors tackle the challenge of learning from dyadic data—observations that involve pairs of entities from two different sets (e.g., a user rating a movie). While matrix factorization is a common tool for this, Stochastic Relational Models (SRMs) offer a more powerful generalization. SRMs treat the problem as a supervised learning task that can incorporate entity attributes (like user demographics or movie genres) within a hierarchical Bayesian framework, effectively acting like a Gaussian Process for relations.

Standard Stochastic Relational Model

However, SRMs historically faced a "cubic wall." Previous inference methods based on Variational Bayes had a computational complexity of $O(m^3 + n^3)$, where $m$ and $n$ are the number of users and items. When you have tens of thousands of users, this becomes computationally impossible. The goal of this paper is to break through this bottleneck, making SRMs practical for real-world, large-scale collaborative filtering.

Methods

The core contribution is a shift from Variational Bayes to a fully Bayesian Markov chain Monte Carlo (MCMC) approach, specifically using Gibbs sampling.

The "Aha!" moment comes from a mathematical proof establishing a dual representation for the model's covariance matrices. Instead of sampling massive $m \times m$ and $n \times n$ covariance matrices (representing similarities between all users and all items), the authors show you can sample much smaller $d \times d$ matrices, where $d$ is the number of latent dimensions.

Dual Representation of the SRM

Since $d$ is typically much smaller than the number of users or items ($d \ll m, n$), this flips the complexity bottleneck entirely. Key technical highlights include:

  • Inverted Wishart Process: Used as a prior to generalize the finite-dimensional inverse-Wishart distribution to infinite-dimensional kernel functions.
  • Informative Priors: The model can incorporate side information (features) by structuring the prior covariance matrices.
  • Unblocking Gibbs Sampling: To further speed up the implementation, the authors introduce a conditional sampling version that allows for parallelization across entities.

Datasets

The authors evaluated their approach on three primary datasets:

  1. Synthetic Data: A $30 \times 20$ random matrix with added Gaussian noise to verify the model's ability to reconstruct underlying structures.
  2. EachMovie: A dataset containing ~2.8 million ratings from 74,424 users on 1,648 movies.
  3. Netflix Prize Dataset: A massive dataset consisting of over 100 million ratings from 480,189 users on 17,770 movies.

Key Insights and Ideas

  • The Latent Dimension Advantage: The realization that we don't need to model the full entity-to-entity relationship matrix directly. By focusing on the latent feature space, we can achieve the exact same mathematical results with a fraction of the computation.
  • Fully Bayesian > Variational: The MCMC approach provides a "fully Bayesian" treatment. Unlike Variational Bayes, which often provides a simplified approximation of the posterior, MCMC can more accurately capture the uncertainty and complexity of the model, leading to better predictive accuracy.
  • Feature Integration: The model elegantly bridges the gap between pure collaborative filtering (latent factors) and content-based filtering (using entity attributes) by encoding features into the prior covariance.

Key Results

  • Scalability: The proposed BSRM (Bayesian SRM) successfully handled the Netflix dataset, which was roughly 1,000 times larger than the datasets used in previous SRM research.
  • Accuracy: On the EachMovie dataset, BSRM outperformed standard Variational Bayes and other competitive baselines like fast max-margin matrix factorization (fMMMF).
  • Netflix Performance: On the Netflix validation set, the BSRM with features (BSRM/F) achieved an RMSE of 0.8874, outperforming the then-state-of-the-art Bayesian Probabilistic Matrix Factorization (BPMF) which scored 0.8920.
  • Efficiency: Using the "unblocked" sampling method, the algorithm achieved high accuracy significantly faster than the standard Gibbs approach.

Limitations and Future Work

While the paper successfully moves the bottleneck from the number of entities to the number of latent dimensions, the complexity is still $O(d^3)$. As researchers push for models with thousands of latent dimensions, even this might become a constraint.

The authors suggest that the techniques used here—specifically the efficient handling of inverse-Wishart distributions—could be applied to other large-scale Bayesian inference problems. Future work might also explore non-parametric extensions where the number of latent dimensions $d$ is not fixed but learned directly from the data.

Summary updated

Abstract

Stochastic relational models provide a rich family of choices for learning and predicting dyadic data between two sets of entities. It generalizes matrix factorization to a supervised learning problem that utilizes attributes of objects in a hierarchical Bayesian framework. Previously empirical Bayesian inference was applied, which is however not scalable when the size of either object sets becomes tens of thousands. In this paper, we introduce a Markov chain Monte Carlo (MCMC) algorithm to scale the model to very large-scale dyadic data. Both superior scalability and predictive accuracy are demonstrated on a collaborative filtering problem, which involves tens of thousands users and a half million items.
BibTeX
@inproceedings{zhu2008stochastic,
  author = {Shenghuo Zhu and Kai Yu and Yihong Gong},
  title = {{Stochastic Relational Models for Large-scale Dyadic Data using MCMC}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2008},
  url = {https://openreview.net/forum?id=HyZDGY-uWH},
}
Figure